2014-07-12
ICPC エア国内予選
Other | | 
国内予選当日に、お仕事しつつサブで4問くらい解いてみた。
A
税抜き価格の組を列挙して、税率変更前の価格に合致しているかでフィルタして、税率変更後の価格の最大値を取る。
競プロとしては基本的なことをやるだけなんだけど、プログラミング初心者のゼロ完防止といえるかはちょっとよくわからない。
自然な発想としては、変更前の価格から税抜き価格を生成して、変更後価格を求めたいと思うのだけど、対応する税抜き価格というのは存在性も一意性もないところが落とし穴で、たいがい実装とデバッグが悲惨なことになり、うまく実装するにはそれなりの経験が必要になる。税抜き価格を中心にして発想を逆転させて簡潔にするのが重要になると思われるけれど、それはそんなに自明だろうか？
むむむ。
B
どう転んでも問題文に書いてある通りにやるしかなさそう。
本当にやるだけ。
C
真面目にやるなら座標圧縮で離散的にやるとかしないといけないんだけど、冷静になって制約よく見ると座標は 20 までの整数値しか与えられないので、幅1の長方形に切ってそれぞれについて最大値を求めて最小値を取ればいい。こうすると原点をまたぐやつとか場合分けが減って嬉しい。
見た途端に2分探索という人もいたらしい。
2分探索の基本的な考え方は、特定のパラメータ (ここでは時刻) を固定した状況を考えて更新方向を求めるものである。
状況が複雑なのでこのような考察は重要となる。
なんだけど、よく考えるとこの問題については1次不等式にしかならないので、臨界値を陽に求めることができる上に、ほとんど計算式も同じになる。(そりゃ移項しただけだからな)
自分で実装するなら慣れてるものを使えばいいと思うけど、他の人に書かせるときにそれを勧めるならどうか思わなくもない。
D
ルールをよく見ると1文字につき高々2通りしかできることがないので、制約に注目すると 2^20 で押さえられて普通に1個ずつ作って (順序付き) セットに突っ込んでも良い。
よく見ると最大ケースはサンプルに入っている...。
実際の列挙は、先頭から DFS とかで適当に作れば良い。
ビット列によるエンコーディングでループを回すのはどうなのだろう？ビット列へのエンコーディングは計算量の見積もりができればほぼ自明だけど、デコーディングは局所的にはできなくて、結局 DFS のときと同様に先頭からやれば良いという考えが必要で、探索における分岐だと思ったほうが自然なのでは？と思った。
SRM とかで数え上げ系とか、辞書順最小とか求める問題では、たいてい1個ずつ馬鹿正直作ると計算量で大変なことになるので、その手のコンテストを中心にしていると生理的にちょっと辛かったかもしれない。
まあ、でも C より頭使わなくて良くて簡単では？
感想
- A はちょっとひねりすぎで、初心者には辛かったかもしれない。 (ゼロ完防止なら模擬と同じくらいの難易度にしても...)
- 問題にかかる時間が、実装よりも考察が支配的な傾向が強いせいか、国内予選は時間が短いこともあって、ボラティリティが必要以上に高くなってしまっている気がした。
- ゲームバランス調整むずい。やるの自分じゃないけど
