ICPC Tsukuba 2015 参加記

11/28昼

・チームメイトと秋葉原で合流。
・つくばエクスプレス、椅子が硬いとの噂で、コンクリート並みの硬さをイメージしていたけど、そんなことはなかった。普通の在来線という感じ。
・駅で静岡チームに出会い、着いていく。
・つくばカピオに着く。カピオはラテン語で「財産」
・会場の前でJOIOBの東大３チームがチームメイトを待っていた。
・プラクティス、キーボードの右シフトを押すと「↑」が入力されるバグに悩まされる。多分'_'キーが長すぎるせい。
・Backspaceを押すとEndが入力されるバグもあるらしい。
・という感じで、日本語キーボードの配列がやばかった。（twitterでもめっちゃ見かけた）
・環境はキーボード以外は素晴らしかった。競技者として嬉しい点は、
　・会場が適温
　・チームに与えられるスペースが広い
　・配線等がしっかりしてて、足元に電源スイッチがあってPCが突然落ちるといったことがない
　・windowsじゃなくてlinuxが使える
・JavaChallenge、さすがに２時間かつ提出して無限に待たないとフィードバックが得られないのではなにも作れず。
・紹介文に書いた迷路解いて写真アップしてもらえててうれしい。他にも解いてくれてた人がいてうれしい。

焼肉 pic.twitter.com/iZTOv7PJWo

— 忘れ物に気をつけよう (@hadrori) November 28, 2015

11/28夜

・懇親会、飯がうまい。皆が寿司にかまけてる間に串カツを１通り食べる。
・チームスライドはperyaudoが韓国の空港で作ってくれました。かっこいい。
・宿に向かう。宿の前に焼肉屋があった。
・風呂が混むのは容易に想像がついたので、爆速で風呂に向かう。
・しかし、準急がすでにいてさすがだと思った。
・ロビーとか研修室で雑談をした。
・歯ブラシを忘れたのでコンビニに買いに行く。コンビニ近くてうれしい。
・寝る。

11/28闇

以下闇情報です。反転すると一応読めます。
・全く寝付けず。
・今回に限らず、ICPC前日はいつも寝付きにくいが、今回は特にひどかった。
・事前に「大会どうせ勝てないしどうでもいいどうでもいい、みたいに考えることによって緊張をなくして安眠する」という作戦を考えていたが、見事に失敗した。
・結局３時間くらいしか寝られなかった。一睡もできないのとは大差があるので、まぁ良かった。
・睡眠薬試してみようかなぁ・・・
・もう完全に絶望的な気持ちでツラかった。

11/29朝

・鮭は皮まで食べる人です。（おいしいよ）
・プリンとユンケルを投入する。
・移動してコンテスト
・時間通りに開始されなさそうな気配を感じていたら、時間通りに開始されてびっくりした。

11/29コンテスト

チームメイト

・peryaudo：３年間チームを組んでいる。JOIで知り合ったスーパープログラマ。googleのインターンとか行ってて完全にプロ。きゅうりとは小学生からの付き合いらしく、いじられキャラの素養がある。
・mine：今年からチームを組んだ。高校が同じで、superconでチームを組んだこともある。ごちうさ。

チーム体制

・snuke：メインコーダー。ひたすら解く。
・peryaudo：持ち前の英語力を生かし、主に問題文を読んでもらう。ライブラリを写してもらったり、サンプルを試してもらったりもする。ちょっかいをかけると楽しい反応をしてくれるので、和む。
・mine：精度の高い仕事をしてくれる頼れる仲間。主に環境設定、幾何・グラフ系のサンプルの図示、数式の計算などをしてもらう。複雑な状態を持つDPの問題の遷移の係数を表す14*8くらいの表を埋めてもらったとき、全部合っててびっくりした。
・問題文について：問題文を簡潔に伝えてもらうというのはもちろん重要だけど、制約・入力がdistinctかどうか・問題の細かい設定などを聞いたら答えてもらえるというのも実に助かる。

記録・感想

・開始後はとても穏やかな気持ちだった。
・ユンケルのおかげか、結構眠さとかはなかった気がする。
・いつもは慌てて問題を解いてハマって余計に時間がかかるというパターンが多かったので、今回は冷静にゆったりと問題を解くことにしていた。
・mineに設定をしてもらってる間にAを読む
・これsubsequenceじゃなくない？と思いつつやるだけなのでやる。
・サンプルをダウンロードできるページ情報を得るためにclarを投げる。
・Bから悩ましい問題だなぁと少し驚きつつも、他のチームもどうせ驚いてるだろうと思いつつ解く。なぜかDAGの最長経路問題に落として解いた。
・Cで今回のセットは前半の重さが増していると確信しつつ、冷静にやる。
・D、時間がかかりそうなので飛ばすべきかと思いつつもABCの次にD以外をやっているチームがなかったのでやる。
・E、桁DPを考えるがprod無理じゃね？となるが、2,3,5,7で何回割れるかを状態として持てば良さそうとなり実装する。添え字がやたら多くて笑いながらコーディングする。
・DPテーブルを再利用してもメモリが足りなかった。
・prodをmapで持った方が状態数減るしなんとかなるやろと思いmapに切り替える。
・TLが1秒なのに実行してみると2秒近くかかってあーと思うが、O2をつけたらなんとか1秒に納まりそうだったので投げたら通った。
・あらかじめ積を列挙しといて状態をlower_boundとかでintに変換すれば高速化できそう。
・ここまでずっと５〜９位くらいだったのでこの調子で行けば良さそうと思う。
・会津が強くてびびる
・他のマークしてたチーム（台湾勢、阪大、FCCPC、筑波、九大、京大...etc）に勝っていたのでほっとする。
・Fを聞くが、複雑で少し時間がかかるが理解する。
・少し余裕がありそうだし、少し疲れたのでリフレッシュ目的でトイレに行く。
・トイレ待ち行列に行ったらいつの間にかperyaudoがいて話しかけたら係りの人に怒られた。チームメイトだけどダメか。
・小走りで席に戻ってたら「don't run」と怒られる
・「トイレに行くだけで２回怒られる男」とperyaudoに煽られ続ける
・F、問題さえ読めばC~Eより簡単。
・問題文に乗ってないサンプルのデータが合って、それだけ答えが違った。
・デバッグしてAC
・G、むずそうなのにA~Fを埋めるより先に解いてるチームがいくつかあってビビる。
・H~Kを聞いてみて、Gをやることを決める。
・結構悩んだ末AC。よくできた問題だった。
・「長さがhogeの回文」ではなく「長さが最短な回文」であることが重要であることに気づくのに時間がかかった。
・解かなければならない問題は全部解き切ったので少し休憩をしつつI,Jあたりを考える。
・残り45分くらい、そろそろどれに取り組むかを決める必要があった。
・H、Jは時間的に無理そう。
・Iでなんらかの嘘解法を生やして枝狩りとかを入れつつ提出しまくるというのも魅力的な選択肢。
・Kは簡単な場合はCFで最近見たなぁと思った。
・残り時間的にはIかKだと思ったけど、台湾がKを解いていたのを見てKにする。
・嘘解法を生やすも、撃沈。
・終了...しなかったので暇を持て余す。
・周りを見渡して凍結後に増えた８完がいないことを確認する。
・阪大チームが延長戦でAC出してたのが楽しそうだった。

コンテストまとめ

・過去の参加経験を生かして「冷静」を実践できたのはよかった。
・持てる力の80%は出し尽くせた（bestを尽くせなかったという意味ではない）かなと思う。これ以上出そうとするとハマる確率が上がって安定しないので後がない状況では最善の戦略だったと思う。
・結果は8位、大学別6位でした。
・メダル枠と別地区を除くと、NTU→Aizu→Keioなので、WFの希望は残っているのではないかなぁと思う。Aizuのシンガポールでのご活躍とCJ先生に祈るしかない。
・＋１完がなかなか難しいんだよなー。今回は残り時間が少なかったから仕方ない気はするけど。
・まぁそれでも嘘を並べれば想定解でなくてもうっかり通ってしまう可能性があるかもしれないタイプのI問題を選択した方が期待値は高かったかなという反省は少しある。
・今年は結果を出したかったので、それなりの結果を出せて良かったです。
・ペナルティ0なの、すっごくないですか？

11/29昼

・解説、スケジュールの伝達ミスで巻きでやってしまったっぽくて、かなり雑だった。でもなんとなくどんな感じかは分かった。
・Java Challengeについて（負なので反転）：Java Challenge作られた方、去年４回も問題を使い回していた方なので非常に印象が悪い。今年は使いまわしではなかったので良かった。しかし、ローカルでテストできない上サーバのレスポンスが激遅だった点、IDとかが0-indexedなのに与えられる座標がどうやら1-indexed（問題文に書いてない）だった点は残念だった。
・Java Challengeがグダグダになるのはいつものことだし、それが面白いってところもあるので楽しかった。メインコンテンツでもないしまぁ多少はね。お疲れ様でした。
・謎の空白時間。
・秋葉さんのカメラから逃げる遊びをしていると、よすぽが素材としてのプロ意識を発揮する。
・表彰式。プレゼントの中身が気になる。（クリスマスはちょっと早くない？w）
・Dreadnoughtまじで圧倒的だったなぁ。あと、風船22個を阻止してしっかり9完したIIIlIIIllIIlIlIIllIlIllllllIIIもさすがだった。
・IIIlIIIllIIlIlIIllIlIllllllIIIがJOMANDAしてた。参考：

J O M A N D A pic.twitter.com/lRlBSoRipN

— おめ (@omeometo) November 14, 2015

dic.nicovideo.jp

11/29夜

・閉会パーティー
・皆んな大好きK理事長の乾杯音頭
・料理は今日もわりとうまい。焼きそばが二種類あるのが謎だった。
・googleブースの謎解きがハイクオリティだった。
・ヨーヨー楽しい。
・社会人のいろんな方と話した。
・例の数式の会社の社長さん、SFCの先輩らしい。（ちなみにここでperyaudoがバイトしてたらしい）
・２つくらい企業賞をもらう。やったぜ！！
・yahooからもらったアダプタkit（しかもmac高速充電）が嬉しかった。

・東大勢と一緒のつくばエクスプレスで帰る。

11/29家

・いつのまにかタイムシフトを見はじめていた。
・眠すぎたので最後まで見れなかった。
・tozangezanのためにまとめを作った。www.youtube.com

まとめ

・日本の運営、すごいしっかりしてて最高。
・つくば以外と近いし、それでいて旅をした気分になれるので良い。（会津も好き）
・コンテストはそれなりの結果が出せて良かった。
・運営お疲れさまでした。ありがとうございました！

Sorting game

謎のゲームを作った。
Sorting game
swapしてソートするだけのゲーム。

マージソート風にやるよりもクイックソート風にやった方が強いっぽい。
適当に似た色を選んでいく方法も割と強い。

マージソートのやり方

2個組、4個組、8個組までは気合。
このとき、各組はソート済みにしなくてよくて、大事なのは各組内での順序が一意に定まるようにすること。
マージ操作は色に頼りつつ頭の中で頑張る。
8個組と8個組のマージは頭の中だときつい。
小さいやつから順番に正しい位置に置いていく。
「残りのものから最小の数を見つける」という操作が必要になるが、そのような数の候補は２つしかないので極小のもの２つを見つけて比較すればいい。
操作数はだいたい60くらいかな。

Golden Week Contest 2015 解説

Golden Week Contest 2015 - Golden Week Contest 2015 | AtCoder
というコンテストをAtCoderさんで開かせていただいていました。

まずは、チーム/個人それぞれののtop10から。

チーム

順位	チーム名	点数	問題数	時間	全体順位
1	カラフルジャンボチキン	621	7.5	234:17	3
2	代々木に行くよ（回文）	563	7	221:34	8
3	チーム爽健美茶	563	7	246:07	10
4	†地獄†零春 ‡チーム‡	563	7	246:07	12
5	chikOkU	487	6	274:59	16
6	yosky	435	6	139:42	18
7	camypaper,nuip	435	6	211:44	21
8	お姉ちゃんと猫	435	6	225:42	22
9	btk(チーム（一人))	136	2	92:09	43
10	sonna*baka*na	25	1	126:10	110

個人

※すぬけ さんはりんごさんです。

順位	ユーザ名	点数	問題数	時間	全体順位
1	すぬけ	1000	10	198:16	1
2	semiexp	837	9	201:25	2
3	uwi	621	7.5	266:46	4
4	chokudai@AtCoder社長	621	7.5	273:04	5
5	すぎむ	621	7.5	306:56	6
6	cgy4ever	598	7	312:52	7
7	satos	563	7	230:22	9
8	kmjp	563	7	245:27	11
9	stqn	563	7	272:15	13
10	Lepton_s	563	7	297:44	14

各問題の解説

A 得点

DPすればいいです。G問題を初期化のときに処理しておくと楽です。

2^9 * 3 個全部を列挙して重複を取り除いても良いです。

B アリ巣

10080ターン目あたりから長さ104の周期に入ります。

ラングトンの蟻です。

ラングトンの蟻はこれで知りました。

C Snukeと対戦！

HとWのどちらかが偶数の時

後手を選択し、相手の手と点対称な位置に相手と反対の色の碁石を置く。

HもWも奇数の時

先手を選択し、真ん中に碁石を置く。

その後は、相手の手と点対称な位置に相手と同じ色の碁石を置く。

D 最短絡問題

dist(1,1,i,j) を質問し、h[i][j] としておく。

dist(si,sj,ti,tj) を質問されたら、ti>siのときは、siとti・sjとtjを交換しておいて、

• si ≦ ti かつ sj ≦ tj のとき：h[ti][tj] - h[si][sj]
• そうでないとき：(h[ti][tj] - h[si][tj]) + (h[si][sj] - h[si][tj])

を答える。

左上（マス(1,1)の方）から右下へ行く経路は（左や上に行かなければ）どんな経路でもコストは同じで、左下から右上へ行く経路は最初に上にずっと行ってそこからずっと右に行くような経路が最短であることが証明できます。

タイトルが少し変なのは、間違い探し的な意味しかないです。（問題自体に短絡要素はあんまりない気がする）

E シフト塗り分け

L = N のとき

蟻本のポリアのところに書いてあります。

L が偶数の時

• 12345 → 41235 → 45123

というようにシフトすると、L+1 のシフトを偶数回繰り返したものが構成できます。L+1 が奇数なので、L+1 のシフトも構成できます。

L のシフトと L+1 のシフトを組み合わせると、

• 12345 → 41235 → 12354
• 12345 → 45123 → 24513 → 13245

のように任意の場所をswapできます。ということは、全ての順列を作ることができます。

この場合は「K個の色からN個の色を重複アリで選ぶ場合の数」になります。

L が奇数の時

• 123456 → 512346 → 561234

というようにシフトすると、L+1 のシフトを偶数回繰り返したものが構成できます。

L のシフトと L+1 の偶数回シフトを組み合わせると、

• 123456 → 451236 → 123645
• 123456 → 145623 → 231456
• 123456 → 561234 → 235614 → 142356

のように任意の場所で 3 のシフトができます。

3 のシフトができると、偶置換が作れます。（前からN-2個を順番に埋めていけばいい）

偶置換を同じとみなす時の塗り分け方は、

• 全部異なる色で塗る場合：各色の選び方について 2 通り
• 同じ色がある場合：各色の選び方について 1 通り

となるので、この場合は「K個の色からN個の色を重複アリで選ぶ場合の数」+「K個の色からN個の色を重複ナシで選ぶ場合の数」が答えになります。

F ピラミッド - 誕生日編

N が奇数の場合

石の総数の偶奇で決まる。

N が偶数の場合

石の個数が最小の山にある石の個数に注目します。これを X とします。

• X = 0 のとき：石の総数の偶奇で決まる。
• X = 1 のとき：その山の石を取る or 全部の山から石を取る のどちらかを行うことで、X = 0 にでき、石の総数の偶奇を自由に選べるので勝ち
• X = 2 のとき：X を 1 にすると負けるので、全部の山から取る操作をすると負ける。つまり、石の総数の偶奇で決まる。
• X = 3 のとき：その山の石を取る or 全部の山から石を取る のどちらかを行うことで、X = 2 にでき、石の総数の偶奇を自由に選べるので勝ち

というふうに、X が奇数のときは先手必勝、X が偶数のときは石の総数の偶奇で勝敗が決まる。

G ピラミッド - 球編

ある穴が壊れた時に石を置けなくなる場所は、直方体状になっています。

部分点は包除原理で計算すれば良いです。

満点は、JOI2011-2012 Day1 Fish 解説

H ピラミッド - デコ編

ある石の色が勝敗に関係するかどうかを計算します。

数式はいろいろありますが、x = B-1, y = A-B, z = L-A とすると

• (x|y|z) == x+y+z なら勝敗に関係する

となります。あとは、勝敗に関係する黒の位置の個数 (mod 2) を求めればいいです。

段数によって結果が反転するので気をつけてください。

I ピラミッド - 立方体編

簡単だったらしい。

DP[i][j] = min(DP[i-1][j]+1, DP[i][j-1]+1, DP[i-1][j-1]+1, H[i][j])

を４方向に計算すればいい。

想定解ではもう少し複雑なDPをしてしまっていました・・・

J ピラミッド - 2D編

ヤング図形 - Wikipedia

これを求めるときの分母を効率的に求めたい。

• f(a, x, y) = a~a+x+y-2がずら〜と並んだx*yの長方形の積

という関数を求められれば良い。

例えば、f(4,4,3) は

4 5 6 7
5 6 7 8
6 7 8 9

の積を求めればよくて、4*5*6*7*5*6*7*8*6*7*8*9 になる。

これを求めるためには、10^6 くらいまでの

• ∏ i^i
• i! （階乗）

の値が前計算してあれば良い。

次に、以下の図のイメージで計算（赤を掛けて青を割る）すれば三角形の部分（∏ (i+a)^i）が求まる。

あとは、以下の図のイメージで計算すれば f も求まる。

sublimeのプラグイン作った

sublimeの競プロプラグインを作りました。github.com

適当にプラグインの作り方をググって、雰囲気を把握して、あとはAPI referenceを眺めながら作ったらできた。どう実装するのかわからないところが出てきたらサンプルをあさるのも吉っぽい。

pythonで書けるのが嬉しい。

作ったやつの機能としては、ライブラリを貼ったり、scanf文とかの省略形を展開したり出来ます。詳細はgithubに置いたreadmeを読んでください。

もともとはシェルスクリプトとかでやってコマンドラインからやってたんですが、エディタのプラグインにしてみたらめっちゃ快適でびっくりした。

ちなみに、「[rand]っていつ使うねん汎用性低すぎへん？」って思うかと思いますが、
これはテストケース作るときの乱数シード書くときに欲しかったから作りました。

追記：github.com

こんなのも作った。使いたいシチュエーションが割とあって、使ってみるとすごい便利だった。

プラグイン作るの手軽すぎて、単純なやつなら探すより作った方が早いっていうのすごく気軽な感じで良い。

sublimeをカスタマイズした

Sublime Textが気に入ってずっと使ってるんですが、今更ながらsublimeのカスタマイズをした。なんかMicrosoftが新しいエディタを出したのに触発されてやった。

とりあえずまず、Sublime Textの気に入ってる点と不満点を挙げます。（今朝の時点での）

気に入ってる点

• シンプル
• 欲しい機能（インデントとか）が大体揃っている
• マルチプラットフォームだし、Windowsを突然渡されてもエディタに困らなさそう
• マルチカーソル、"⌘d"がめちゃ便利
• プラグインが作りやすいらしい
• その他カスタマイズもしやすい

不満点

• C++で「for (i=0;i<N;++i) sum+=i;」みたいに１行でfor文を書くとインデントがバグる
• 保存するとたまに変なダイアログが出てくるバグがある
• tabで補完が出来るんですが、日本語入力で予測変換でtabを使うと補完が発動してバグる
• 検索パネルの閉じ方が分からない

で、不満点のうち３つ目以外を今日解消しました。

インデントのバグ

C++で「for (i=0;i<N;++i) sum+=i;」みたいに１行でfor文を書くとインデントがバグる、という件

メニューから「Preference」→「Sublime Text 2」→「Preferences」→「Browse Packages...」から"Package"フォルダを開いて、"C++"フォルダ内の"Indentation Rules.tmPreferences"ファイルを探して開く。

どうやら27行目が悪さをしてるようなので、コメントアウトしてみた。

//24~28行目
<key>bracketIndentNextLinePattern</key>
<string>(?x)
^ \s* \b(if|while|else)\b [^;]* $
<!--| ^ \s* \b(for)\b .* $-->
</string>

当然ですが、２行に分けてforを書きたいときとかでもインデントされないようになりましたΩ＼ζ°)ﾁｰﾝ

まぁそれでいいやと一瞬思ったけどやっぱり困る気がしたのでちょっと考えた結果こうなった。

<key>bracketIndentNextLinePattern</key>
<string>(?x)
^ \s* \b(if|while|else)\b [^;]* $
| ^ \s* \b(for)\b[^;]*;[^;]*; [^;]* $
</string>

いい感じに動いてくれました。

追記(2015/05/01 02:24)：これでもまだ「for(;;)for(;;)\n」（二重forを一行に書いて次の行に処理を書く）というコーナーケースがありますね。これは諦めてforを２行に分けたりしてください。完璧な正規表現はかなり難しそうです。

追記(2015/05/10 16:09)：range-based forに対応できていなかったので修正しました。

<key>bracketIndentNextLinePattern</key>
<string>(?x)
^ \s* \b(if|while|else)\b [^;]* $
| ^ \s* \b(for)\b([^;]*;[^;]*;|[^:;]*:[^:;]*) [^;]* $
</string>

ちなみにsublimeを再起動しないと更新されません。

Sublime Text 3での解決法は知りません。

変なダイアログ

保存するとたまに変なダイアログが出てくるバグがある、という件

お金で解決しました。70$でした。

補完と予測変換

tabで補完が出来るんですが、日本語入力で予測変換でtabを使うと補完が発動してバグる、という件

これはよくわからなかった。解決できるようにできる条件は多分、

• 補完を別のキーにする
• MacのデフォルトのIMEを使うのをやめる

のいずれかっぽいんですが、どっちも嫌なので諦めました。

検索パネルとかの閉じ方

検索パネルの閉じ方が分からない、という件

Sublime Text 3の検索パネルにはxボタンがあるのに他にはないせいで余計ハマっていましたが、解決法はシンプルでした。

Escキーで閉じれるそうです。

ちょうどK個選ぶ部分和問題

JAG春コンのB問題の解法が面白かったので僕なりにまとめておこうと思います。

この解説を参考にしました。

問題（要点を抜き出したバージョン）

N 個の数が与えられる。その中からちょうど K 個選んで作れる和を列挙せよ。

制約

与えられる N 個の数の和を M とすると、

• K ≦ N ≦ 600
• M ≦ 180000

普通のDPをすると O(NKM) になって TLE です。（bitsetでもなんとか間に合うらしいです）

こんなにシンプルだし、有名問題なのに、なんと O(NM) のDPがあるらしいです。

解法

まず数を K 個と N-K 個に分けます。これをそれぞれ Aグループ、Bグループと呼ぶことにします。

考えうる全ての選び方は、以下のような操作で実現できます。

1. 最初に Aグループを全て選ぶ（K個選択中）
2. 次に、Bグループの数を１つ追加する（K+1個選択中）
3. Aグループから１つ数を取り除き、2.に戻る（K個選択中）

コードにすると、

bool selected[N];
for (i = 0; i < K; i++) selected[i] = true;

for (i = 0, j = K; j < N; j++) {
  if  (j番目の数を選ぶ) {
    selected[j] = true;
    while(true) {
      if (i番目の数を取り除く) {
        selected[i] = false;
        break;
      }
      i++;
    }
  }
}

みたいなイメージ。

こんな方針をDPに落とし込むとこうなります。

• dp0[i][j][s] = Aグループを i 個、Bグループを j 個見終わった時点で数を K 個選んでいて和が s になるように出来るか
• dp1[i][j][s] = Aグループを i 個、Bグループを j 個見終わった時点で数を K+1 個選んでいて和が s になるように出来るか

「上のコードでのi,jの値が i,jとなっているときに選んでいる数の和をsに出来るか」みたいなtrue/falseのDPです。（厳密には少し違って、このDPでは、数を追加したり削除したりしないならいつでも自由にi++かj++をできます）

遷移は、「if (b) a = true」を「update(a,b)」と書くことにして、

• update(dp0[i][j+1][s], dp0[i][j][s])
• update(dp0[i+1][j][s], dp0[i][j][s])
• update(dp1[i][j+1][s+x[j]], dp0[i][j][s])
• update(dp1[i+1][j][s], dp1[i][j][s])
• update(dp1[i][j+1][s], dp1[i][j][s])
• update(dp0[i+1][j][s-x[i]], dp1[i][j][s])

最終的に dp[K][N][s] がtrueなら s が作れます。

ただ、このままでは O(N^2 M) なので計算量を落としたいです。

• update(dp0[i][j+1][s], dp0[i][j][s])
• update(dp0[i+1][j][s], dp0[i][j][s])
• update(dp1[i+1][j][s], dp1[i][j][s])
• update(dp1[i][j+1][s], dp1[i][j][s])

という遷移があり、「trueの領域は i,j に対して単調」となっています。例えば、trueの領域は以下の図のような領域になっていたりするでしょう。

そこで、

• dp0[j][s] = さっきのDPテーブルで、dp0[i][j][s]==true となるような最小の i
• dp1[j][s] = さっきのDPテーブルで、dp1[i][j][s]==true となるような最小の i

というDPを考えます。つまり、下図のオレンジの部分を記録するという感じ。

遷移は、「a = min(a,b)」を「update(a,b)」と書くことにして、

• update(dp0[j+1][s], dp0[j][s])
• update(dp1[j+1][s+x[j]], dp0[j][s])
• update(dp1[j+1][s], dp1[j][s])

の３つは分かりやすい（さっきのDPの遷移の1,3,5番目とほぼ同じ）。あとは、

• for (i = dp1[j][s]; i < K; i++) update(dp0[j][s-x[i]], i)

があればよい。しかし、これだとまだO(NKM)なのでもう一工夫したい。

• for (i = dp1[j][s]; i < dp1[j-1][s]; i++) update(dp0[j][s-x[i]], i)

試す i の範囲が [dp1[j][s], K) から [dp1[j][s], dp1[j-1][s]) になりました。こうすると、計算量は O(NM) となります。

なぜ、試す i の範囲をこういう風に狭めても良いのでしょうか？

i が dp1[j-1][s] 以上の場合は、

• dp1[j][s] → dp0[j][s-x[i]]

という遷移をしなくても、

• dp1[j-1][s] → dp0[j-1][s-x[i]] → dp0[j][s-x[i]]

という遷移によって更新できるはずだから、わざわざ dp1[j-1][s] 以上の i について遷移をしなくてもちゃんと更新されてくれるからです。

ちなみに、試す i というのは下の図のオレンジの部分に相当します。

ここを試せば、それより上の部分は試さなくても良いという感じでしょうか。

この図を見れば計算量が O(NM) になるのも納得できるのではないかと思います。試す場所の合計は、各 s に対して高々 K 箇所しかないからです。

実装

元の問題は他の要素があって大変そうだったので、ストレートにDPだけの練習問題をNPCA Judgeに置かせていただきました。（今judge止まってるっぽいのでデータも上げておきます）

僕のコードです。

#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
 
const int MAX_N = 605;
const int MAX_M = 180305;
const int INF = 1000;
 
int X[MAX_N];
int dp0[MAX_N][MAX_M];
int dp1[MAX_N][MAX_M];
inline void update(int& a, int b) { a = min(a,b);}
 
int main(){
  int N, K;
  // input
  cin >> N >> K;
  for (int i = 0; i < N; ++i) cin >> X[i];
  int m = accumulate(X, X+N, 0);
  // initialize
  for (int j = K; j <= N; ++j) for(int s = 0; s <= m; ++s) {
    dp0[j][s] = dp1[j][s] = INF;
  }
  dp0[K][accumulate(X, X+K, 0)] = 0;
  // DP
  for (int j = K; j <= N; ++j) {
    for (int s = 0; s <= m; ++s) {
      if (dp1[j][s] != INF) {
        update(dp1[j+1][s], dp1[j][s]);
        int l = dp1[j][s], r = K;
        if (j > 0) update(r, dp1[j-1][s]);
        for (int i = l; i < r; ++i) {
          update(dp0[j][s-X[i]], i+1);
        }
      }
    }
    for (int s = 0; s <= m; ++s) {
      if (dp0[j][s] != INF) {
        update(dp0[j+1][s], dp0[j][s]);
        update(dp1[j+1][s+X[j]], dp0[j][s]);
      }
    }
  }
  // output
  string ans;
  for (int s = 0; s <= m; ++s) {
    ans += (dp0[N][s] == INF) ? '0' : '1';
  }
  cout << ans << endl;
  return 0;
}

さらに、このコードのようにメモリを再利用をして空間計算量を落とすこともできます。

#include <iostream>
#include <algorithm>
#include <numeric>
using namespace std;
 
const int MAX_N = 605;
const int MAX_M = 180305;
const int INF = 1000;
 
int X[MAX_N];
int dp0[MAX_M];
int dp1[MAX_M];
int dpr[MAX_M];
inline void update(int& a, int b) { a = min(a,b);}
 
int main(){
  int N, K;
  // input
  cin >> N >> K;
  for (int i = 0; i < N; ++i) cin >> X[i];
  int m = accumulate(X, X+N, 0);
  // initialize
  for(int s = 0; s <= m; ++s) dp0[s] = dp1[s] = INF, dpr[s] = K;
  dp0[accumulate(X, X+K, 0)] = 0;
  // DP
  for (int j = K; j < N; ++j) {
    for (int s = 0; s <= m; ++s) update(dpr[s], dp1[s]);
    for (int s = 0; s <= m; ++s) update(dp1[s+X[j]], dp0[s]);
    for (int s = 0; s <= m; ++s) {
      if (dp1[s] != INF) {
        for (int i = dp1[s]; i < dpr[s]; ++i) {
          update(dp0[s-X[i]], i+1);
        }
      }
    }
  }
  // output
  string ans;
  for (int s = 0; s <= m; ++s) {
    ans += (dp0[s] == INF) ? '0' : '1';
  }
  cout << ans << endl;
  return 0;
}

感想

すごい（小並感）

boolのDPはやっぱり効率が悪いんだなぁ、とか思った。

SRM 656

出ました。

250

N個のパンケーキがあり、i番目のパンケーキの幅はi+1で美味しさはd[i]です。以下のような操作をしてタワーを作ります。

• 残っているパンケーキをランダムに１つ選びます。（残っていなければ終了）
• そのパンケーキの幅がタワーの一番上のパンケーキの幅より大きければ終了
• そうでないなら積んで、最初に戻る

タワーに積まれたパンケーキの美味しさの和の期待値を求めよ。

解法

期待値の線形性を使う。

つまり「Σ d[i] * (i番目のパンケーキが使われる確率)」で答えを求める。

dp[i][j] = i個のパンケーキを既に使っていて、一番上のパンケーキの幅がjである確率

というDPをして、答えは「Σ dp[i][j]*d[j]」で求めるといい。

初期化は、番兵をおいて、dp[0][N]とすると楽。

ちなみに遷移は、

if (k < j) dp[i+1][k] += dp[i][j]*(N-i)

みたいな感じ？

500

長さNのパーミュテーションであって、pos[i]の箇所だけp[i]<p[i+1]でそれ以外はp[i]>p[i+1]であるようなものを数え上げよ。
※ len(pos) = Mとします。

• N ≦ 10^6
• M ≦ 2500

解法

包除原理

まず、「posのところの条件を満たす必要がない」という問題を考えます。

単調減少でなければならない区間がM+1個出てきますよね。i個目の区間の長さをa[i]とします。

「posのところの条件を満たす必要がない」という問題の答えは「N!/mul(a[i]!)」です。

では、「posのところの条件を少なくともk個満たさない」という問題を考えます。

これは、

dp[i][j] = i番目の区間までを見て今までで少なくともj個の条件を満たさないものの個数/N!（i=0~M,j=0~M）

みたいなDPを考えるとできます。

「/N!」とかいてありますが、これは計算を簡略化するための工夫で、最後に*N!をするという感じです。

遷移は

dp[i][j] = Σ dp[i-k][j+k]*(Σa[i-k]~a[i])!

みたいな感じです（適当に書いたので細かい±1とかがずれてるかもしれませんが）

で、包除原理を使って答えを求めます。

このままだと３乗ですが、包除原理においては満たす条件の個数はどうでもよくて、その偶奇だけに興味があるので、dp[M][2]のDPにすると２乗になります。

ちなみに、さらにまとめてdp[M]（dp[i][0]-dp[i][1]を記録する）にしても良いです。

雑な解説なので、足りないところがあれば考えてみるか、聞いてください。

（本番では階乗の配列を2505で取ってて落ちました。つらい）