hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

動的計画法における空間計算量削減テク

この記事は 「競プロ!!」競技プログラミング Advent Calendar 2017 9 日目の記事として書かれました。

競技プログラミングをそれなりにやってきた方となれば、動的計画法に触れたことも多いでしょう。今回は、その動的計画法における空間計算量削減テクを色々紹介したいと思います。

普通のナップザック問題

題材として、ごく普通のナップザック問題を考えてみましょう。

容量  W のナップザックに、品物をいくつか入れたいと考えています。品物は全部で  N 個あり、 i 番目の品物は価値  v_i 、容量  w_i です。品物の在庫はそれぞれ  1 個ずつなので、同じ商品を複数個入れることはできません。ナップザックの容量を超えることなく商品を入れる時、入れた商品の価値の総和の最大値を求めてください。

制約は

  •  1 \leq N \leq 10^{4}
  •  1 \leq W \leq 10^{4}
  •  1 \leq v_i \leq 10^{4}
  •  1 \leq w_i \leq 10^{4}
  • 時間制限  3 sec
  • メモリ制限  64 MB

とします。せっかく空間計算量削減の話をするんですから、これくらい厳しくしないとですよね!

まずは普通に実装してみます。結論から言うと、このコードは空間計算量  O(NW) で配列とりすぎなので Memory Limit Exceeded になるはずです。

#include <iostream>
#include <algorithm>
using namespace std;
 
int v[10000], w[10000];
int dp[10001][10001];
int main(){
    int N, W, ans = 0; cin >> N >> W;
    for(int i=0; i<N; i++) cin >> v[i] >> w[i];
    for(int i=0; i<N; i++) {
        for(int j=0; j<=W; j++) {
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
            if(j-w[i] >= 0) dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i]);
            ans = max(ans, dp[i+1][j]);
        }
    }
    cout << ans << endl;
    return 0;
}

このメモリ制限に対応するためには、何か工夫が必要です。どうすれば良いでしょうか?

インデックス  \bmod 2 DP

ここで、 DP の遷移に着目します。(該当箇所再掲)

dp[i+1][j] = max(dp[i+1][j], dp[i][j]);
if(j-w[i] >= 0) dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]] + v[i]);

f:id:tsutaj:20171108203105p:plain

 i+1 番目の状態を得るために参照している状態は、 i 番目の状態のみです。もっと言うと、 i-1 番目以前はもう使いません。これは無駄そうです。更新に必要な部分だけを保存していくように変えたいですね。

次の状態を得るには今の状態だけ分かっていればいいのですから、  i のインデックスは  2 つあれば十分です。 i の偶奇を気にすると、次のようにすれば良さそうです。

f:id:tsutaj:20171108203116p:plain

このように、 i の偶奇に応じて参照先を変え、最新  2 つの状態を持っておくことで空間計算量を大幅に削減できます。更新時にどのインデックスを見るかに着目して、必要なものだけ持つ、ということが本質です。この工夫をすることによって、空間計算量は  O(W) になりました。

改善後のコードは以下の通りです。

#include <iostream>
#include <algorithm>
using namespace std;
  
int v[10000], w[10000];
int dp[2][10001];
int main(){
    int N, W, ans = 0; cin >> N >> W;
    for(int i=0; i<N; i++) cin >> v[i] >> w[i];
    for(int i=0; i<N; i++) {
        int mo = i % 2;
        for(int j=0; j<=W; j++) {
            dp[mo^1][j] = max(dp[mo^1][j], dp[mo][j]);
            if(j-w[i] >= 0) dp[mo^1][j] = max(dp[mo^1][j], dp[mo][j-w[i]] + v[i]);
            ans = max(ans, dp[mo^1][j]);
        }
        for(int j=0; j<=W; j++) dp[mo][j] = 0;
    }
    cout << ans << endl;
    return 0;
}

dp 配列の  1 次元目が大幅に減りました。これで、メモリ制限に対応できますね。

この実装で注意すべきは、使い終わったインデックスは初期化する ということです。上の実装でいう for(int j=0; j<=W; j++) dp[mo][j] = 0; の部分にあたります。これをやらないと次の更新をするときに本来いらないはずの値が既に入ってしまっており、不具合が生じるからです。

更新の順番工夫 DP

実はもっと空間計算量を削減できます。今まで  2 次元の DP で解いてきましたが、今から紹介する工夫をすることで  1 次元の DP になります。とはいえ、今の方針を無理やり  1 次元にしてしまうと、既に更新した状態を次の更新時に使ってしまい、二重更新が発生します。どうやったらうまくできるでしょうか?

DP 配列の更新を (更新に使われる) → (更新に使う) の矢印で考えると、次のように 左から右に 矢印が引かれると思います。これは、値の更新時に今よりも容量が小さい状態を見るからです。

f:id:tsutaj:20171108213140p:plain

この性質は、容量の大きい状態から順に確定していくことを意味します。これを利用して、容量の大きい順に DP 配列を更新していくと、品物のインデックスが不要になり、 1 次元の DP で解くことができます。

#include <iostream>
#include <algorithm>
using namespace std;
 
int v[10000], w[10000];
int dp[10001];
int main(){
    int N, W, ans = 0; cin >> N >> W;
    for(int i=0; i<N; i++) cin >> v[i] >> w[i];
    for(int i=0; i<N; i++) {
        for(int j=W; j>=0; j--) {
            if(j-w[i] >= 0) dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
            ans = max(ans, dp[j]);
        }
    }
    cout << ans << endl;
    return 0;
}

逆順ループによる空間計算量削減テクは DP の更新を矢印でイメージすると、適用できるか否かがわかりやすいです。たとえば、XOR を取る DP などはこのように 1 次元 DP に落としこむことはできません。なぜなら、 XOR を取ることで今の数字から増える場合と減る場合の両方があり、更新の矢印の方向に規則性がなく、一度更新したところを再度見てしまう可能性があるからです。

もしこの方法が苦手であっても、大体の DP は先ほどのインデックス  \bmod 2 DP で対応できますので、そちらをマスターするのでも十分だと思います。

演習

最後に、今回紹介した空間計算量削減テクが (おそらく) 必須な問題を挙げました。どれも少し難しめですが、ぜひやってみてください。慣れないうちは、ナップザックなどの簡単な DP で感覚を身につけるのもオススメです。

最近はメモリ制限  256 MB の問題が多いため、空間計算量を意識する機会はそんなに多くない印象です。ですが、昔の JOI などはメモリ制限  64 MB の問題が割とあり、意識しなくてはいけない場合があります。覚えて損はないので、この記事を読んで使えるようになってくれたらうれしいです。

明日の Advent Calendar は tozangezan さんです!

CODE THANKS FESTIVAL 2017 参加記

CODE THANKS FESTIVAL 2017 に参加しました。今回が初参加です。

予選

予選の順位は

予選 順位
qual A 308th
qual B 454th
qual C 757th

予選 A は C 問題までそこそこ早解きできたけど、予選 B と C は D 問題が解けそうで解けなくて結構下の順位になってしまい悲しいね。

おそらく予選 A で THANKS ボーダーに引っかかって参加権を獲得しました。正直行けると思っていなかったので、参加のご案内メールが来たときはびっくりしました。

大会前日

空港に向かう前に、ちょっとヨドバシへ。ボドゲ会が予定されているのにボドゲをなにも持ってなくてアだったので、調達しに行きました。

東京に到着後、 らてあさん・TIke さん・こうきさん・竹雄さん・フェリンさん とボドゲをやるべく、カラオケ屋へ。

自分が持ってきたゲームと、フェリンさんが持ってきたゲーム (インサイダー・ゲーム) でワイワイやってました。ボドゲは久しぶりにやったけど、思考の読み合いがホントに面白かったな〜

その後ふーらくたるさんとも合流し、ご飯へ。ハンバーグおいしい!

ホテルに戻ってしばらくして、ボドゲ会第二弾!竹雄さん・ Treeone さん・らてあさん・こうきさん・やざてんさん とゲームをしました。やったのはギャンブラー・ギャンブルとクーだったはず。ゲーム中に Treeone さんが通知を破壊したり、らてあさんが雑リプを飛ばしたりしていて実質 TL で面白かったです。

大会当日

コンテスト開始前

竹雄さんと会場に向かう。ゆりかもめが今まで見たことない混み方しててヤバを感じた。混みすぎてて最初に来た電車を見送って、次に来たやつに乗ったりしてました。

そんなこんなで無事会場入り。交通費精算何度も WA してすいませんでした。T シャツをゲットしてテンションがめちゃくちゃ上がりました。

なんか誰もマスコット類出してないなあと思いつつ、せっかく持ってきたので †開封の儀† を行い設置。

このマスコットが本当に目印になったかどうかは、よくわかりません・・・

コンテスト

目標はパーカー獲得!がんばるぞいという気持ち。

最初に見たのは A 問題。FA 取るで!と思って流し読みして書いてコンパイルせず提出。

続いて B 問題へ。頭が死んでいたので解法が分からなかった (は?) とりあえず放置したら解けるようになるだろうと思って C 問題へ。

C の解法はすぐ生えた。その時刻で最も小さいものを取り続ける貪欲をすればよいため、 priority_queue で常勝。無事 AC (09:12)

A 問題が通っているかどうか確認したら WA でビビる。どうやら N 個の問題があるわけではなく、問題数は 8 で固定らしい。ちゃんと問題を見ようね。そんなこんなで AC (10:01)

D 問題でちょっと詰まる。最初変な方針を書いたら WA した。いろいろ紙で実験したら GCD を取れば良さそうなことに気づいたのでそれを書いて AC (47:02)

E 問題と F 問題両方見て、 F の方がすぐ書けそうだったのでとりかかる。和の制約があるため状態数は多くないのかなあと思って自明な bit DP を書いたら TLE、それはそう。

ここでちょっと考える。どうやら、この方法だと 1, 1, 1, ..., 1, 90000 みたいな、 1 がたくさんあって 1 個だけでかい数が出た時に全く節約できないことがわかる。これを節約するにはどうすればよいかを考えた結果、 bit を調べる範囲は 2^(今まで登場した数字の MSB 最大値) までで十分であるため、入力をソートして範囲を絞って bit DP をすれば良いことに気づく。これにはかなり早い段階で気づいていたんだけどなかなか通らない (Submission #1822207、開始 1 時間少しで想定解にはたどり着いているがある部分の実装が不適切であるため TLE)。つらい。つらいので一旦放置。

そういえば B を放置していたことを思い出す。これ書くだけやんけ!回文になる suffix の長さの最大値を全体の長さから引くだけ。 AC (104:49)。 F 問題であれこれやってたのもあって、D 問題の AC から 1 時間近く開いててつらい。

F がまだ通らないので E を考える。本物は奇数で偽物は偶数だから、偶奇でどうにかするのかなあと考えたけど、なかなかうまくいかない。コインが 5 種類しかないから取るコインの枚数を工夫して解くのかなあとも考えたけど (よく考えたらこれが想定解だったのね)、どんなふうに取っていけばいいのかわからなかった。

ついに F の実装のヤバイ点を見つける。 DP で配列を使いまわす時に、その配列を毎回 memset で 0 埋めしていた部分が重かったらしい。なんだそりゃ・・・。結局 vector を resize して swap して・・・みたいな意味不明な実装をして AC (134:28)。今思えば memset ではなく必要な範囲だけ for 文で初期化するとか、 map で DP するとかすればよかったですね。これのせいで 1 時間溶けているので悲しいなあ・・・。

E は頭の悪い自分には無理そうだったので G を書いてみる。自明な全探索を適当に刈る方向性で書いたけど TLE。今思えば辺が少ない時に枝刈りできていないので全然ダメでした。

結果は ABCDF の 5 完 62 位でした。F の実装でハマったのといい、 EGH が解けなかったのといい、完全に実力不足でした。来年はパーカー取れるように頑張ります。

ふーらくたるプロが 5 位になったので前で感想を語っていたのですが、あまりに感動的な内容で頭が真っ白になり、もう内容は覚えていません。

ちょくだいさんが解説をしてくれました。オンサイトコンテストで解説を聞いたのは今回が初めてでした。絶対解き直すぞー・・・

懇親会

CONNECTION HUNT が結構面白かった。いろんな人と話しましたねー。特に、念願の tourist じゃんけんをすることができて胸熱でした。

懇親会のご飯はどれもおいしくてリクルート最高という感じでした。懇親会も実質 TL だったので楽しかったです。

大会後

大会後に、もう少し遊びたい人 (TIke さん・Shinya Kato さん・Noimin さん・minaminao さん・こうきさん・A さん (Twitter やっていないようなので仮名で書かせていただきます)) で集まってボウリングをしに行ったりしてました。その後カラオケの流れもあったけど、こどふぉがあるのでホテルに戻りました。

ホテルで自宅番兵さんとこどふぉオンサイトをやりました! やっぱりコンテスト後にあれこれ議論できるのはいいですね〜。

まとめ

ありがとう THANKS FESTIVAL!来年は本選にいきたいなあ・・・!

DDCC2017 本戦 参加記

DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦 に参加しました。去年の DDCC に引き続き、 2 回目の参加となります。

予選

予選は全完 122 位でした。D 問題が解けたのは嬉しかったのですが、結構条件漏れが多くてサブミットデバッグ気味になってしまい、ペナルティ無しの恩恵を受けまくって本戦進出できた感じですね・・・。

今回は就活枠 (19 卒枠) の対象外ゆえ交通費や宿泊費が自己負担なので正直行くかどうか迷っていたところもありましたが、TL の人々に会いたかったですし、なにより去年のあの雰囲気がとても好きだったのでそれをもう一度味わいたいなあと思い本戦に参加することにしました。

本戦の前

去年の反省を活かして受付 30 分前くらいに会場入り。たぶん一番乗りでした。

ロビーで出会った方々とおしゃべりしつつ、謎パネルを撮りつつ、受付開始を待っていました。

受付後、コンテスト本番が始まるまで時間があったので、なけなしのコミュ力を発揮して人々に会いに行きました。人生で初めてサインを求められてびっくりした (おかゆさん、olphe さんありがとうございました!)

そんなこんなでコンテスト本番の時間が近づく。去年ほどは緊張しなかったとはいえ、やっぱり緊張しますね・・・。

コンテスト本番

本戦は 2 完 77 位でした。去年の本戦は底辺みたいな順位だったので、それに比べたらだいぶ成長しました。が、C 解けなかったのは悔しいですね・・・

A 問題

なんかデジャヴを感じる。去年の自分のソースコード引っ張りだそうかなと思ったけど解読に時間がかかりそうなのでやめた (それはそう)

円の半径を  R とします。各正方形について 4 つの頂点の座標を列挙し、この 4 点すべてについて円の中心との距離が  R 以下なら、その正方形は切り出せます。正直コレだけなんですが、距離を計算するときに x*x + y+y みたいな typo をしたり、配列が作れなかったり (は?) してグダグダでした。大反省ものです。

AC (17:04)

B 問題

正直この問題が最も簡単でした。

自分の解法としてはこんな感じです。早い段階でサンプルから察せたのが良かったのかなと思います。ただ  X を作る際に  gcd の結果を素因数分解する必要があるんじゃないか、みたいに一瞬逸れかけたので危なかったです。反省。

AC (23:47)

C 問題

解けませんでした (悲しいね)。以下嘘考察です。

距離の総和が 0 でないサイクルを列挙して、そのサイクルすべてについて

  • 共通の辺が少なくとも 1 つ存在する (それがないと一部のサイクルについて総和を操作できないので)
  • 各サイクルの距離の総和が同じ (距離を変えられるのは 1 辺だけなので)

が成り立てば嬉しいよなあと思いましたが、そもそもサイクルの列挙があやしいし共通の辺を探すのも難しい。どうすればいいのかなあという感じでした。

上の条件をクリアする策はあまり出てこなくて、なんか 1 辺だけ取り除いた時にトポロジカルソートできたらいいのでは?みたいな謎の考察を苦し紛れに思いついて、他にやることもないのでそれを実装していたのですが、結局嘘だったようです。完全に思いつきだったので仕方ないです。悔しいので解き直します。

D 問題

1100 点問題だしやばみなんだけど一応読みました。でもこれに時間をかけるのは実力的に間違っている気がしたのであまり考察しませんでした。

解説を読んだ感じだと、割と思いつきやすい DP を枝刈りしたみたいな感じだったので意外でした。あとで解いてみようと思います。

DDCC 特別ビュッフェ

えび

結構いろんな人とおしゃべりしました。らてあさんが tourist じゃんけんの人として認識されているのが面白かったです。

特別対談

将棋は全く詳しくないのでどの程度まで話についていけるのかなあと対談前は不安に思っていたのですが、全然そんな心配する必要なかったです。めちゃくちゃ楽しかったです。

コンピューター将棋 vs. 日本将棋界の変遷の概要やプロ棋士の戦術・学習法の変化、さらにはコンピューター将棋の意義まで、興味深い話題がたくさんありました。

これから頑張らなきゃなあと思えた話としては、「競技プログラミング意外の技能も身につけたほうがいいよ」という話。競技プログラミングが狭く深い世界であることは自分も理解していますし、おそらくそういう認識を持っている競プロ er が他にも多くいるような気がします。これから自分がどう成長していけるのか、どのフィールドで輝けるのか、考えていきたいですね。

あとはこんな話題も。

コンピューターの成長は指数的で、人間の予想をはるかに上回るという話。自分は 5 年後くらいにはコンピューターに競プロ負けてるかも。そうなったら悲しいのでがんばります。

社内ツアー

去年に社内ツアーに行ったので、2 回目以降の人向けのツアーに参加しました。

社用車が電気自動車だったり、オフィスの風通しが良かったり、やっぱりすごい会社ですね・・・

毎度おなじみウェーハカットもばっちり見れました。やったね。

懇親会

懇親会もいろんな人と話しました!

RUPC 以来に会った方が結構いました。半年前に比べて強くなった方ばかりなので、自分も成長しないとなあと思います。

ちょくだいさんが最速最強アルゴリズマー養成講座にサインしてくださいました!うれしい!ありがとうございました!!

まとめ

オンサイト最高!!!!!

来月初めの CODE THANKS FESTIVAL でまたお会いしましょう!!!