ACM-ICPC Japan Domestic Warm Up II
無事終了しました。
多くの皆様の御参加、ありがとうございました。
以下、簡単な解法やどうでもいい話などを。
Problem A: Sleeping Cats
原案・問題文の作成を担当しました。
元々は「メモリのallocとfreeのシミュレーション」という問題設定だったのですが、いざ問題文を書こうとした瞬間、頭の中にねこが現れてにゃーにゃー鳴き始めました。なので、急転直下ねこ問題に変更。
完成した後に、国内模擬予選にこの問題の上位互換(Problem D: 制限されたファイルシステム)が出てきたので焦りました。
解法
Ad-hoc, Simulation.
問題文のとおりに書くだけです。私はSTLのcountやfillなどを使ってみました。
A問題にしては若干面倒くさいです。
Problem B: Monster Factory
問題文の作成を担当しました。原案はnobです。
問題文を書きやすいように細かい条件などを勝手に変更したら、答えが一意に決まらなくなったりして焦りました。大変だった問題の一つです。
ストーリーなども付け加えてみた結果、食わせ物な問題文が出来上がりました。その割にプログラムはかなり簡潔で、国内予選のB問題っぽさが出せたと言えなくもないかもしれません。
解法
Ad-hoc.
push_downとpush_rightのどちらを実行するべきかは、中心にある文字を見ればわかります。
Problem C: Midnight Teatime
原案・問題文の作成を担当しました。
Tree+DPの問題を作ろうとしたら、どこでどう方向性を間違えたのか、結局去年の国内予選のC問題によく似たものが出来上がってしまいました。仕方ないので、問題文で誤魔化そうとがんばりました。
解法
Brute-force / DP.
DPやビット演算を知らなくても頑張れば解けるように、入力サイズは小さめに設定しています。どちらにしろ知ってる人はDPするだろうから構わないよね、と思ってました。実際ほとんどの人がDPしてたようです。
Problem D: Dr. Nakamura's Lab.
ノータッチ。なので、この問題だけコンテスト中に解いてみました。
(コンテナの位置)*(使ったパネル)*(現在地)をキーにしてsetに突っ込みながらDijkstra。
ビット演算と論理演算を間違えてしばらく嵌ってましたが、どうにか解けました。
一回だけ、間違えてチームのアカウントで送ってしまいました。ごめんなさい> yuk, 後輩K
Problem E: Frisbee Dogs
原案・問題文・ジャッジデータのの作成を担当しました。
幾何 + シミュレーション。とはいえ、どちらも比較的易しめです。去年の国内予選のEぐらいの難易度でしょうか。
もう少し難しくしようかとも思ったのですが、Judge's Solutionを抜かりなく作れる自信がなかったのでやめました。
Problem F: Chocolate with Heart Marks
ノータッチ。ですがコンテスト前に解いておきました。
解法
Search / DP.
最小のブロックの枚数で1を繋ぐことが出来ればいいのですが、もちろん全探索は現実的ではありません。
少し考えれば、「全ての1ブロック」「(上または下)にも(右または左)にも1ブロックがあるような全ての0ブロック」を直線で繋いでいったものの中に答えがあることが分かります。MSTに似ていますが、この問題では0ブロックを含む必要はないので、シュタイナー木と呼ばれる問題になります。
この木を探索 + 枝狩りで求めるのが一つ目の想定解法です。
シュタイナー木はDPでも求められます。私はSpaghetti Sourceを参考にしながら、集合の生成をサボった嘘Dreyfus-Wagnerを実装しました。1ブロックの数を n とすると O(4^n * n^4) ぐらいにはなりましたが、n <= 6なので0.1秒以下で終わりました。
勝者
| Rank | ID | Solved | Time |
|---|---|---|---|
| 1 | wata | 6 | 421 |
| 2 | iwiwi | 6 | 523 |
| 3 | lyrically | 6 | 532 |
| 4 | laycurse | 5 | 543 |
| 5 | mirac | 4 | 318 |
おめでとうございます！
