Blog

この記事はシステス前に書いている．現在 49,247,218,607 点で 71 位．新レートの詳細は不明だが，アルゴ水色程度の判定が欲しいところ．

URL https://community.topcoder.com/stat?c=problem_statement&pm=13846&rd=16548 概略 $R \times C$ のマス全てをちょうど $K$ 回だけ通るような一筆書きの経路は存在するか？ 方針 $K = 1$ で巡回路が作れれば，$K > 1$ についても構築可能です．巡回できないケースは $R$ と $C$ の両方が奇数の場合のみです．これが真に構築不能であることの証明ができなかったので参考リンクを貼っておきます． 巡回路ができないことの証明 yukicoder : No.85 TVザッピング(1) — kmjp’s blog 構築不能であることの証明 TopCoder SRM 668 Div1 Easy PaintTheRoom — kmjp’s blog [展開する] 反省 そこそこ自信はあったが証明はできていないので，本番ですぐに提出できるかは微妙．

URL https://community.topcoder.com/stat?c=problem_statement&pm=13709 概略 グリッドに色を塗る操作を行う．最初は全て白である．1回の操作では，$k \times k$ の正方形を選び，その中を黒または白で塗りつぶす事ができる．この操作を任意回繰り返すとき，与えられる最終的な色の配置が実現できるかどうかを調べる． 方針 最終状態から操作を逆にたどってみることにします．今戻すことができるのは $k \times k$ が全て同じ色で塗られている箇所です．問題は戻したあとの盤面がどうなっているかです．「戻す」操作は，順方向から見れば「塗りつぶす」操作であることに注意します．「塗りつぶす」際に重要なことは，その下の色などどうでも良いということです．つまり「戻す」操作における遷移先は，黒と白のどちらもとることができます．便宜上これを D と置くと，全てのマスをDにできるかという問題に変化し，これはシミュレーションすれば良いです．$n \leq 20$ なので何でもできます．実装は $O(n^6)$ です． [展開する] 反省 DはDottidemoiiのD．

URL https://community.topcoder.com/stat?c=problem_statement&pm=13747&rd=16416 概略 大きさの異なるパンケーキをランダムに積む．自分より小さいパンケーキの上には積むことができず，積めなくなった時点で美味しさの総和が計算される．総和の期待値を求める． 方針 dp[i][j] := 一番上の大きさがiで既にj個積んでいる確率とします．パンケーキは大きい順に見ると遷移が簡単です． 個数が $j$ で一番上が $k$ である山に積む場合を考えます．パンケーキ $i$ を引く確率は $\dfrac{1}{n - j}$ なので，dp[i][j + 1]について，$\sum_{k}^{i - 1}$ dp[k][j] / (n - j)です． また $i$ を積む場合の確率はこれで網羅できていることになるので，その期待値は $\sum_{j}$ dp[i][j] * d[i]です． [展開する] 反省 確率DPは配るDPのほうが良いと思っているのに，なんで貰うDPにしたのか謎．

URL https://community.topcoder.com/stat?c=problem_statement&pm=13694&rd=16318 概略 ?を含む文字列が与えられる．同じ文字種のみを含む連続部分文字列の個数がスコアとなる．?が確率 $P_i$ で変化するとき，スコアの期待値を求める． 方針 文字種cと左端 $L$ を固定します．左端が $L$ である連続部分文字列の個数は $L$ から右に伸ばしていくことで $O(|S|)$ で求まります．期待値の線形性から，途中で?が来る場合には $P_c$ を乗じれば良く，これを全文字種，全左端で行って $O(|P||S|^2)$． [展開する]

URL https://community.topcoder.com/stat?c=problem_statement&pm=14811 概略 有向木の頂点に石を置いていくゲームを行う．葉には無条件で置いてよい．親に置くためには，その直接の子すべてに石が置かれていなければならない．また，任意のタイミングで石を取り除くことができる．根に石を置いた時点でゲームは終了する． 各頂点には重み $w$ が付いている．石が置かれている頂点 $i$ について $W = \sum w_i$ が逐一計算され，ゲームのスコアは $\max W$ である．スコアの最小値を求める． 方針 操作を先読みしたいときにはメモ化再帰が有効です． dp[i] := iに石を置く操作をするときのスコアの最小値とします．頂点iの子がL，Rであるとき，iに石を置く操作には以下の工程が考えられます． Lに石を置く dp[L] Rに石を置く dp[R] Lに石を置く操作を一通り行った後，Rに置く操作を行う．またはその逆．これは小さい方を選択できる． min(w[L] + dp[R], w[R] + dp[L]) LとRの両方に石が置かれていて，iに石を置く w[i] + w[L] + w[R] dp[i]はこのうちの最大値を取ります．子が0, 1つの場合も同様に計算できます． [展開する] 反省 操作順を親と子の重みだけで評価できると思って時間を溶かす．そんなわけない．

URL https://community.topcoder.com/stat?c=problem_statement&pm=13791&rd=16462 概略 果物（リンゴまたはオレンジ）を順に $N$ 個食べる．info[i]番目は必ずリンゴを食べる．直近 $K$ 個の内，リンゴは最大でも $\left\lfloor \dfrac{K}{2} \right\rfloor$ 個までしか食べてはいけないとき，全体で食べるリンゴの最大値を求める． 方針 左から見ていき，リンゴを食べられるならば必ず食べる貪欲をします．$i$ 番目にリンゴを食べるとその影響は $i + K - 1$ 番目まで及ぶため，後回しにして同じ個数を食べられる可能性はあっても，それより多く食べることはできません（？）． あとは $i$ 番目でリンゴが食べられるかを判定できればよく，これは全ての $0 \leq d < K$ について $[i - d, i + (K - d))$ に含まれるリンゴが $\left\lfloor \dfrac{K}{2} \right\rfloor$ 個未満であることが条件です． [展開する] 反省 貪欲の証明があっているのかわからない．脳死でセグ木を貼らない．

URL https://community.topcoder.com/stat?c=problem_statement&pm=14104 概略 宇宙船1隻を作るには，$m$ 種類のパーツが1つずつ必要である．また，店が $n$ 個ある．店 $i$ は種類 $[a_i, b_i]$ のパーツを合計 $k_i$ 個まで売ってくれる． 宇宙船は最大何隻作れるか． 方針 $x$ 隻作れるかを二分探索します．判定にはパーツの種類を時間軸に持った，区間スケジューリング的な考え方を用います．パーツの種類を昇順に見ていき，現時点で購入可能な店について $b_i$（区間の上限）の昇順に合計 $x$ 個購入します．途中で購入可能な店が無くなった場合，失敗です．このような操作は優先度付きキューを2本持つことで簡単に実現できます． パーツの総数は $\sum k \leq nk _ {\max}$ なので操作回数は大体 $m \log \dfrac{n}{m}k _ {\max}$ で，これはおよそ $10^6$ です． [展開する]

URL https://community.topcoder.com/stat?c=problem_statement&pm=14010 概略 泣き顔とは，2つのセミコロンでアンダースコア1つ以上を囲んだもののことを言う．正規表現では;_+;である． 与えられたmessageをいくつかの部分列に分ける分け方のうち，過不足なく泣き顔が作れる分け方は何通りあるか． 方針 dp[i][a][b] := iまで見て使っていない";"がa個，";_+"がb個とします．過不足なく使うことを考えると，解はdp[|message|][0][0]です． kmjpさんのブログの言葉を借りて，;_+;は「閉じている」，;_*は「開いている」と表現すると次のような遷移が考えられます． セミコロンが来たとき 新たに開く dp[i][a][b] += dp[i - 1][a - 1][b] 1つ閉じる dp[i][a][b] += dp[i - 1][a][b + 1] * (b + 1) アンダースコアが来たとき 開いている;のみの状態に追加する dp[i][a][b] += dp[i - 1][a + 1][b - 1] * (a + 1) 開いている;_+の状態に追加する dp[i][a][b] += dp[i - 1][a][b] * b [展開する] 反省 最初，普通に数学をして壊滅した．DP解に目標を絞るも，dp[i][a][b] := iまで見て使っていない';'がa個，'_'がb個からなかなか進まなかった．;，;_のような区別の仕方は典型なので，気づけなかったのは反省． 参考 ABC104D - We Love ABC