参加記は後日書こうと思っていたのですが、記憶が鮮明なうちにコンテストの反省をしたほうが良いだろうなあと思ったので、コンテスト部分だけ別記事で先に書くことにしました。
※割と真面目に分析したり反省したりしているので、おもしろ要素はありません。ただ、失敗談も有益になるかなと思うのでここに残しておきます。
はじめに
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 を取れば良いことは割とすぐに気づいたが、どうすれば求まるのかがわからない。こういうのは定式化するのが一番だと思うので定式化してみる。
値を求めたい区間 と、 overlap しているかどうかを判断する区間
があるときに、
または
が成り立てば良いことはすぐわかる。この条件を満たすものがいくつあるかは、仮に 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 問題については、定式化するところまではいいものの、それが悪い定式化であることに気づきませんでした。実は上で出てきた式の 否定 を取ると見通しが良くなります。
「 または
」の否定は、「(
または
) かつ (
または
)」 です。ここで、「
が
以下である」とすると、
より
も
より小さいことは簡単に分かり、この条件を満たします。また、 「
が
以上である」とすると、
も
より大きいことは簡単に分かります。さらにこれらは独立であり、どちらの条件も満たすような区間は存在しません。したがって、 overlap とならない 区間は、その終点が
以下であるか、その始点が
以上であるかのいずれかであり、独立なのでこの 2 つを普通に数えれば良くて、区間の数全体から引けば値を出すことができます。
このように、定式化したものをうまく変形して解く力がチーム全体として不足したように思います。
分析
今回のセットは明らかに少なくとも 4 完するべきセットでしたが、それとはかけ離れた結果となりました。結局、チームとしてなにが足りなかったのでしょう？自分なりに分析しました。
ハマった時に抜け出すノウハウを誰も持っていない
とにかくこれに尽きます。リカバリーする能力が全体的に足りていませんでした。ハマった時になにをすればよいかはおそらくパターンがある気がしているので、次回はそのパターンをチームで共有して挑みたいと思っています。
実装方針を見誤った
特に B で顕著に現れました。その問題に合った実装方法を正しく選択する必要があります。
個人的な話をすると、思い返してみれば AOJ-ICPC 埋めをしているとき、バグが全く取れないまま 5 時間が経過した問題があったりしていたので、この力はまだまだ足りていないのかなあと思います。
解けないことを引きずりすぎた
B が全く通らなくて、それで精神的に引きずられた、ということもあると思います。少なくとも自分はそうでした。もっと他の問題に目を向けるべきだったかもしれません。
今後の目標
同じチームであと 2 年出ることができるため、ぜひリベンジをしたいです。
自分は他のサークルとの兼ね合いもあって週 2 の練習会のうち 1 回しか出れていなかったのでチームメイトには本当に申し訳ありませんでしたが、来年は普通にフル参加できるので、全力で頑張りたいです。練習会の感触からして、チームとして ICPC の問題が極端に苦手である気がするので、対策を練っていこうと思います。
来年の目標は・・・、国内予選・アジア地区ともに 20 位以内でしょうか？今回の結果からするとアホみたいに高い目標と思われるかもしれませんが、これから 1 年真面目に取り組めば不可能ではないと思っています。 (これは来年の自分へのプレッシャーです。)
