見た部分はストレートフォワードなセット。 275 1からNまでの数の(連続である必要はない)部分列について、小さい順に素数かどうかが与えられる。このとき、元の部分列をできる限り復元せよ、という問題。 探索するだけ。部分列のどれかがある値だと仮定する…

仕切り直しでもう一回。SRMとかぶってたので適当にしかやってない。 Wine Tasting 1からNまでのPermutationのうち、i番目の値がiであるものが少なくともK個あるのは何通りか答えよ、という問題。 一致している個数をKからNまで全通り試す。一致している個数…

手も足も出なかった自分がふがいない...。 250 NxMの盤面に、黒いものが置かれている。黒いものがどれもKxKの黒いものの正方形に含まれているような、最大のKを答えよ、という問題。 KxKの正方形の端の点になるとして、最大のKを各点について求める。このと…

たまたま先日のPower Overwhelmingと似たような問題に当たった。こちらはlong溢れしない良い問題。 250 N人の人が1列に並んでおり、自分より背の高い人が左側に何人いたかを背の低い人から順に答えたリストが与えられる。どのような順番に並んでいた答えよ、…

NHCタグがここまでふさわしいのは久し振り。そしてIEに感謝したのも久し振り。 After the Dance Battle 二次元グリッド上を上下左右に移動して目的地に移動する。ただし、同じ色の床は移動と同じコストでワープできる。最短移動回数を答えよ、という問題。 B…

450の割には意外と通っていないみたい？ 300 N個のものの中に一つだけ白いものがM番目に入っている。白いものを含む連続するK個を選択して、逆順に並び替える、という操作を行って、L番目に移動させるという行動を交互に行う。目的を達成した方が勝利とする…

7章 最短パス グラフに負の重みのコストの辺がなければ、移動すればするほどコストがかかるので、比較的貪欲なアプローチで二点間の最短パスが求められる、というのがダイクストラ。ある点集合のコストがそれより改善されないことが分かっているなら、それら…

確率とか期待値とかは式を立てて愚直に計算(場合によっては行列乗算)するだけなんだけど、式を冷静に立てられる気が余りしない...。 250 文字列の集合が与えられるので、ある要素が他の要素の接頭辞にならないような部分集合のうち最大のものの要素数を答え…

3-5章 (読み飛ばし...) 単体法・内点法・楕円体法とかその辺...、と言いつつ、内点法については記載がまったくないような気がする。 制約条件下で特定の値を最大化(あるいは最小化)するとき、制約条件のどれかがギリギリのところになるのを利用して、どの条…