確率や期待値のDPで式を立てたとき、連立一次方程式 Ax = b を解きたくなることはよくあります。競技プログラミングで使うようなものに限っていくつかメモしておきます。 クラメルの公式 行列式を計算することで厳密解を求めます。nが小さい(2や3)ときに式を…

問題概要 長さBのパスワードがあって、A文字目まで打ち込んでいる。これまでに打った文字が正しいかどうか確率が与えられるので、最適手順をとったときのパスワードが通るまでの手数の期待値の最小値を求める問題。 解法 期待値DP。状態数A、遷移3つなので素…

結果。 2/3完で通過。問題文長くてだるかった。D言語で参加したけど日本人のD使用者が前回より増えていた。

問題概要 兵士がN( 解法 実はこのままではこの問題は解けず、「合流はない」という条件を付け加えなければならない。 最短経路に使われる辺だけを(有向化して)残すと辺の重みが正なのでDAGになる(距離の近い順がそのままトポロジカル順序になっている)。求め…

問題概要 N(≦16)個の箱があり、各箱の中には石が十分たくさん入っている。この箱の中からいくつか選び、lower[i]以上upper[i](1 解法 愚直に塗りつぶしたりsegtree使ったりしても解けるらしいけど、時間空間ともに危険域なので別の方針で頑張る。 部分集合を…

結果。 Div 1 550にミスがあってunratedだった回。unratedなだけで、勝利数とか正解数とかには反映されてるっぽい。 赤10人うちターゲット3人というエグい部屋だった。全体順位63位で部屋内順位10位。2完できたのはよかったけど550はもう少し早く解けてもよ…

やっと念願かなってTopCoder Algorithm部門で赤コーダーになれた。以前にも書いたようにこの部門が花形だという意識が自分の中にあったのでとても嬉しい。僕はICPC組やJOI組と違ってTopCoderから競技プログラミング始めた人間なので、レーティングの変遷を見…

問題概要 f(X)=A+X+B+X+C (各変数は文字列)がある。f^k(X) (k 解法 Xの中にPがk回現れるとすると、f(X)の中でPは2*k+(AとBとCに一部が含まれるようなPの個数)となる。( .. )の部分は文字列のprefixとsuffixを持っておけばよい。毎回prefixとsuffixを計算し直…

問題概要 蟻がN( 解法 すれ違いを避けるため、最初に座標を全部2倍(どうでもいいことだけど、この座標を2倍するテクニックって結構頻出で、自分は勝手に座標拡大といっている)して毎秒1単位の速度で動かしてシミュレーションする。衝突が起こるとき、かなら…

結果。 2完+撃墜200で5位！前回も撃墜で+300とかしていたので運がよい。開始前は全く自信なくて「きっと半日で赤コーダー陥落するんだろうなー、記念赤って感じだよなー」とか思っていたのに、何と次も赤維持できそうなくらいのバッファができた。撃墜とかは…

結果。 1完(90点！)+撃墜300点で念願の赤コーダーに。medium開いてすらいない意識の低さが自分らしい。 最初は二部マッチングで真面目にやるのかなー、とか考えつついやいやTCOとはいえeasyでそれはないと考え直した。最初は最大サイズ-1が答えかと思ってサ…

問題概要 サイズN( 解法 既に得られた結果の内、互いにまったく区別できないような番号をまとめて、その最大サイズのみに応じて答えは決まる。分割してパラレルに処理することができるので最大サイズのlog程度が答えとなる。矛盾のチェックは集合Sとσ(S)のサ…

問題概要 長さN(スワップすることを繰り返してa[i] 解法 まだよく理解していないのだけど、動かすのは片方の列だけだと考えて大丈夫らしい。 それを踏まえると、(前の列の何番目までは対応付けた、既に動かした後列の集合）を状態としてdpで計算できる。

問題概要 仕事がN( 解法 時間のかかるものから処理した方が良いのは明らか。また、処理してから分裂させるより分裂させてから処理した方がよいこともわかる。 なので、時間の大きい順にソートしてから、（いくつまで処理するか、未処理な狐が何匹いるか）を…

問題概要 長さN(k-1になるものをつくるかのいずれかである。kの最大値を求める問題。 解法 答えについて全探索する。こういうのは上手い方法があるのかも知れないけど、間に合うなら愚直にやってよいと思う。もちろん愚直に書くのがバグ生みにくいときの話だ…

問題概要 山がN個あって各山には石がいくつか置かれている。ふたりでゲームを行う。各プレイヤーは山を一つ選び、石を1個以上取り除く。また、その山に残っている任意個の石を他の山に移すことができる。この際移す山の対象はいくつあってもよい。最後の石を…

問題概要 ノード数N( 解法とか コンテスト直後に解説放送を見ていたので打ち切り+FFTで解くことは知っていた。とはいえDPの式立てるのにも大分苦労したけど(高さh以下、というのを状態にするのに中々気づけなかった)。 D言語の標準ライブラリにFFTが入ってい…

問題概要 (sx,0)から(gx,N) (N 解法 愚直に可視グラフ作ってからDPするのはO(N^3)。少し工夫を加えるとO(N^2)まではすぐに落ちる。 想定解っぽいのは適宜メモ化しながら下から順に計算するらしい。 自分は左側と右側の壁で交互に凸包つくって、凸包の頂点は…

問題概要 一部が埋められた8クイーンがあるので残りを埋めて出力する問題。 解法 5!+枝刈りとかでもよいのだけど、以前書いたN-Queenソルバ(全生成)があるのでそれを使って8-Queenの盤面全部出して与えられたのと合致するかだけ調べた。

問題概要 幅優先探索で距離を求める問題。

問題概要 数字の列が与えられるので、出現回数の最大値と最小値を出力する。

問題概要 正整数列Xが与えられる。i番目とi+k+1番目をペアでとることができる。重複してとることはできない。とることのできる最大スコアを求める問題。 解法 MOD k+1で考えてよい。配列をMOD k+1で分類したとき、長さが偶数なら全部とることができて、奇数…

問題概要 片方のサイズ26以下の二部グラフが与えられる。完全マッチングを作るときに一位に定まるものを出力する問題。 解法 全てのペアに対して、一度固定してから残りを使って完全マッチングができるかどうかを判定すればよい。二部マッチングは差分のみ計…

問題概要 RGBの値が、直前の値と離れすぎず近づきすぎずになるようにランダムに塗っていく。最初と最後が整合しない確率を求める問題(適当)。 解法 愚直にやると、状態数が40*50^3で参照先が50^3となりTLEする。累積和を用いてO(1)で参照できるように加速す…

問題概要 ある数列A(|A|=N0でなくてはならない。無数にある場合は指摘せよ。有限である場合、答えはsinged 32bit integerの範囲に収まる。 解法 こういうのは何も考えずに初項を適当に変数で置いてそれ以降を表す。こうすると上限と下限が得られるので範囲を…

結果。 1完だけど皆落ちまくって何とかレートは微増した。550は誤読したけど、十分難しかったのでちゃんと読めていてもダメだったっぽい。250は実にわかりやすい撃墜ポイントがあって、それには気づけたし大量に落ちるとも思っていたけど撃墜ケース作れなく…

問題概要 コインがN( 解法 (何枚目まで見た、いくら)を組にして必要な最小枚数でDP。よくある01ナップザック。

問題概要 白い玉がN個、黒い玉がM個ある。この中からランダムに二つの玉を選んで白く塗る。全ての玉が白になるまでかかるに必要な回数の期待値を求める問題。 解法 よくある一次方程式型のDPを解くだけ。

問題概要 文字列が3行与えられる。各列に含まれる母音の数が5,7,5になっているかどうか判定する問題。

問題概要 3色のビーズを使って数珠が何通り作れるか求める問題。 解法 とりあえず反転を無視して回転対称だけ重複を取り除いた個数をx個とする。これは蟻本で紹介されてる問題そのもの。左右対称な個数をr個とすると、求める個数は(x - r) / 2 + rとなる。左…