hogecoder

tsutaj 競技プログラミングの記録

ACM-ICPC 2017 Asia Tsukuba Regional Contest 反省記 (コンテスト部分のみ)

参加記は後日書こうと思っていたのですが、記憶が鮮明なうちにコンテストの反省をしたほうが良いだろうなあと思ったので、コンテスト部分だけ別記事で先に書くことにしました。

※割と真面目に分析したり反省したりしているので、おもしろ要素はありません。ただ、失敗談も有益になるかなと思うのでここに残しておきます。

はじめに

rsk0315, TAB, tsutaj でチーム four-t としてアジアつくば大会に参加しました。結果は A と C の 2 完で、43 位 / 50 チーム でした。

正直 2 完で終わることは全く予想していなかったため、結構ショックです。でも冷静に分析するとなぜこうなったかは割と見えていて、来年以降ここを改善したほうが良いのではないかなあという部分も明確になったので、まあそういう点では良かったのかなあと思っています。

本番の流れ

初めに rsk0315 が A 問題を解く + 環境設定をする ということになっていたため、自分と TAB で封筒を開け rsk0315 に素早くログイン情報と問題文を手渡して、自分は B を考えて、TAB は全体を見渡して解ける問題を探していく、ということをした。

A は combination で考えて 15 分ほどで AC。 B は全探索で間に合うことがわかったためコードを書く。

B を提出すると TLE が返ってくる。重そうな部分を前処理するもまたしても TLE が返ってくる。よく分からないので C の解法が生えた TAB 君と交代。なんか WA がでていてつらそうだったがバグを取って AC。

B のソースコードをよく見ると、次の状態を探す処理に無駄があることを発見 (例えば "0000" という状態から "1111" という状態に移るときに "0000" -> "1010" -> "1111" と "0000" -> "0101" -> "1111" を両方試すのは明らかに無駄で、その時点でビットが立っていないところがひとつ見つかればそれを必ず選び、もう片方を適当に選ぶようにすると無駄が減る) したのでそれを直すも、今度は WA が返ってくる。今直した TLE 対策が間違っているとも思えないし、なにが間違っているのかコードを印刷しながら考える。なかなか見つからないので 3 人がかりでコードを見るがやっぱりわからない。順位表では B は当然のように解かれていたのでかなり焦る。

他の問題を考えるもつらそう、みたいな感じの虚無が 2 時間くらいできる。

順位表で結構多くのチームが解いている I を考察してみる。ある区間についてそれと overlap している区間の数を求めて、それの max を取れば良いことは割とすぐに気づいたが、どうすれば求まるのかがわからない。こういうのは定式化するのが一番だと思うので定式化してみる。

値を求めたい区間  \left[ l, r \right] と、 overlap しているかどうかを判断する区間  \left[ a, b \right] があるときに、 l \leq a \lt r または  l \lt b \leq r が成り立てば良いことはすぐわかる。この条件を満たすものがいくつあるかは、仮に 2 つの条件が独立であるとすれば累積和を求めるだけで解けるが、実際はどちらも満たす区間が存在するので、それをどう省くかが大変だなあという気持ちになっていた。

結局 B の WA の原因も I の解決法もわからないままコンテストが終了した。正直生きた心地がしなかった感が・・・。

本来すべきだった解決法

B と I でハマって終了したわけですが、それはどうすればうまく行ったのか?ということを書きます。

B 問題については、直線を「傾き」の情報で管理していました。すなわち、 dx と dy の値を pair<int, int> の形で持ち、値が同じならば平行、という実装にしていました。

もちろん dx が非負になるように符号を決められたルールで揃えたりだとか、 dx と dy を gcd(dx, dy) の値で割って同じ増分であれば unique になるようにしたりとかはやりました。しかし通りませんでした。なぜでしょう?結論から言うと、dx が 0 のときに dy の符号が異なると、異なる傾きとして扱われていたことが原因でした。 (どちらの場合でも y 軸に平行な直線になるだけなので、同一視されなければならない)

軸に平行なケースがやばそうだなあということはわかっていて、実際手元でもそのようなケースはいくつか試しましたが、dx が 0 のときに dy が正になるものも負になるものもできるようなケースは確かに作っていませんでした。デバッグ能力が低かったというのもありますが、それよりも 実装方針を変えなかった というのが最大の敗因ではないかと思っています。今回の問題は外積を使うべきであって、その実装にたどり着いていない時点でダメでした。

I 問題については、定式化するところまではいいものの、それが悪い定式化であることに気づきませんでした。実は上で出てきた式の 否定 を取ると見通しが良くなります。

 l \leq a \lt r または  l \lt b \leq r」の否定は、「( a \lt l または  r \leq a) かつ ( b \leq l または  r \lt b)」 です。ここで、「 b l 以下である」とすると、 a \lt b より  a l より小さいことは簡単に分かり、この条件を満たします。また、 「 a r 以上である」とすると、 b r より大きいことは簡単に分かります。さらにこれらは独立であり、どちらの条件も満たすような区間は存在しません。したがって、 overlap とならない 区間は、その終点が  l 以下であるか、その始点が  r 以上であるかのいずれかであり、独立なのでこの 2 つを普通に数えれば良くて、区間の数全体から引けば値を出すことができます。

このように、定式化したものをうまく変形して解く力がチーム全体として不足したように思います。

分析

今回のセットは明らかに少なくとも 4 完するべきセットでしたが、それとはかけ離れた結果となりました。結局、チームとしてなにが足りなかったのでしょう?自分なりに分析しました。

ハマった時に抜け出すノウハウを誰も持っていない

とにかくこれに尽きます。リカバリーする能力が全体的に足りていませんでした。ハマった時になにをすればよいかはおそらくパターンがある気がしているので、次回はそのパターンをチームで共有して挑みたいと思っています。

実装方針を見誤った

特に B で顕著に現れました。その問題に合った実装方法を正しく選択する必要があります。

個人的な話をすると、思い返してみれば AOJ-ICPC 埋めをしているとき、バグが全く取れないまま 5 時間が経過した問題があったりしていたので、この力はまだまだ足りていないのかなあと思います。

解けないことを引きずりすぎた

B が全く通らなくて、それで精神的に引きずられた、ということもあると思います。少なくとも自分はそうでした。もっと他の問題に目を向けるべきだったかもしれません。

今後の目標

同じチームであと 2 年出ることができるため、ぜひリベンジをしたいです。

自分は他のサークルとの兼ね合いもあって週 2 の練習会のうち 1 回しか出れていなかったのでチームメイトには本当に申し訳ありませんでしたが、来年は普通にフル参加できるので、全力で頑張りたいです。練習会の感触からして、チームとして ICPC の問題が極端に苦手である気がするので、対策を練っていこうと思います。

来年の目標は・・・、国内予選・アジア地区ともに 20 位以内でしょうか?今回の結果からするとアホみたいに高い目標と思われるかもしれませんが、これから 1 年真面目に取り組めば不可能ではないと思っています。 (これは来年の自分へのプレッシャーです。)

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

この記事は 「競プロ!!」競技プログラミング 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]);

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

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

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

この性質は、容量の大きい状態から順に確定していくことを意味します。これを利用して、容量の大きい順に 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!来年は本選にいきたいなあ・・・!