olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

AtCoder

Weird LIS(AtCoder Grand Contest 055)

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); 問題概要 ある $1$ から $N$ までの順列 $P$ があって、$P$ の $i$ 要素目を取り除いたときのLISの長さを $A_i$ とする。$2\l…

Online MST(THIRD プログラミングコンテスト 2021 (AtCoder Heuristic Contest 007))

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); $8$位だったのでやったことを書く。 問題 $N=400$ 頂点 $M=1995$ 辺のグラフがある。辺のコストははじめ不明である。 $ M $ …

第4回アルゴリズム実技検定 感想+解法

序盤の問題の読解や細かい設定がつらい感じで序盤でかなり時間を使ってしまった。反面後半の問題で詰まることはあまりなく、全体としてはスムーズに解けたと思う。(100分41秒) A:vectorにpair持たせてソートした。 B:100倍した。 C:全探索 D:左、右に絶対に…

AGC044-C Strange Dance

ある桁は自分より小さい桁に対して影響を及ぼさないので、操作後の下i桁目について、操作前の下i桁の数によってのみ決まる。 サルサが流れると、すべての桁が変わる。(0のときは変わらないが、変わると考えても困らないので変わると考える。) サルサが2回流…

第二回 アルゴリズム実技検定 解説記事

A 今地上にいるかいないか、目的地が地上にあるかないか4通り場合分けします。 B それぞれの文字が何個あるか見ます。 C 下の行から順に見ていき、Xを見つけたら右上、上、左上のそれぞれについて空白でなければXにします。 D 文字列全部列挙してSのすべての…

全国統一プログラミング王決定戦本戦-F Flights

問題概要 N個の頂点があり、各頂点はx,y座標とコストを持っている。これらをx,y,costで表す。頂点i,jを考えたときに、を満たすときにij間に距離の辺が貼られる。 スタートからゴールまでの距離の最小値を求めたい。距離はで表す。 メモ まずスタートとゴール…

全国統一プログラミング王決定戦本戦-E Erasure

問題概要 N個のブロックが並んでおり、幅K+1以上の全ての区間がある。区間の数をM個とすると区間の選び方は通りある。全てのブロックを選択できる区間の使い方は何通りか。 メモ 素直なDPをする方法と包除原理を用いる方法がある。 素直なDP seicaさんから掲…

AGC008-E Next or Nextnext

問題概要 サイズNの数列Aが与えられる。サイズNの1~Nの順列であるPの中で、 p[i]=a[i],p[p[i]=a[i]の少なくとも一方を満たすPの数を数える。 メモ 途中まではAtCoderの公式解説と同じ考察をする、「ただの閉路」の数え上げがDPで行える理由が分からなかった…

AtCoder Biginner Contest 001 D:感雨時刻の整理

難しいというよりも手間のかかる問題と思う。 開始時刻と終了時刻を5分単位に直し、00:00~23:55からの各5分について雨が降っているか否かをboolで判断する。 その後、bool値と雨が降っているかいないかのbool値から、開始時刻と終了時刻を列挙する。 http:…