ACM-ICPC Japan Domestic Warm Up I - 純粋関数型雑記帳

ICPC参加資格も何もないですけど、
リハビリのために参加しました。
最近老化がひどいので…。

二つの列を一緒に読み込んで、0加えて、ソートして、前からスキャン、
が一番速そうだったので、そう実装。

3次元配列をつくって、適当に塗っていく実装。

シンプルなparser。
10分でかけるparserとかいう記事を公開しながら
20分かかったのは、多分老化のせい。

20個しか科目がないので、2^20とおりビットパターン生成して
条件満たしてるかチェックで書いたのだけど、
1秒の制限時間を5秒ぐらいかかっている。
ちょいちょい変えながら再送するが、
ちっとも速くならない。
TLE厳しすぎる…。
問題チェンジ

Eが図形でFが探索なのを見て、
どっちかというとFかなと思う。

起点からのばして探索する方針で適当に書いて
サブミットしたが、全然間に合わない。
これもTLEを量産した揚句、いったん中断。

Dに戻る。
枝刈りが入らないのがいけないんじゃないかなあ、というので、
DFSで書き直し。
普通にとおる。うーむ…。

こっちも枝刈りを入れることにする。
正のマスについて、
負のマスにつなぐことができないのがあれば、だめ。
負のマスについて、隣接する正のマスの合計が超えてなければだめ。
この二つを入れたら、0.01秒とかで通った。
探索は博打みたいなところがあるなあ…。

のこり25分ぐらいだったけど、一応書いた。
座標と向きをノードとしてダイクストラみたいなので、
一応書き終わってサブミットしたが、
バグバグだった模様。