Kyoto University Programming Contest 2017
Updated:
Source codes
Solutions
A - Credits
貪欲法。
B - Camphor Tree
$T$ をシフトして $S$ になるかどうか確かめる。
ポイント
$S$ をシフトしようとして 2WA してしまった。
C - Best Password
基本的には貪欲法で処理できる。ハッシュ値を予め計算できればなんら問題がないが、長さが膨大であるためハッシュ値を持っておけない。そこで元の文字列を読み込みながら、前から決定していく。
算数で言うところの「繰り上がり」の処理がポイントで、最後にはその部分が問題になる。元の文字数より短くなる可能性があり、その処理が難しい。だから最後の 7 文字くらいになったら、今度はハッシュ値を直接計算しておく。こうすればミスなく終わる。
ポイント
これは最初から本解答を書かずに、ハッシュ値を計算するメソッドと、ハッシュ値から貪欲法をするメソッドを最初に書いてテストしていたのがよかった。時間が長いコンテストだから冷静に処理でした。
D - Sanmoku
$N = 1, 2$ は答えが書いてある。 $N \geq 3$ で $2$ 以上の数字が必要なのは自明。 $112211221122 \dots$ を延々と並べたものが条件を充すので、最小値は $2$ である。
そこで問題になるのが場合の数。1100, 0110 を上から並べるギミックが例外的になるが、これができるのは $N \leq 4$ に限る。だから $N \geq 5$ は上にあげたものしかない。 $N = 3, 4$ だけ全探索すればよろしい。 $10^9 + 7$ は見掛け倒し。
ポイント
これが時間内に解けたのは大きかった。 DP でなくて助かった。 頑張ってみるものである。
E - Treasure Hunt
頂点＝宝箱、辺＝鍵として、連結成分を確かめる。連結成分が木であれば、最小の宝箱を諦める。 そうでなけれrば総取りする。
ポイント
即座にグラフを思いつけたのが大きかった。この手の読み替えは意識しているとできる。
F - 575
放棄。正解者 0 人。
G - encode/decode 2017
60 bit を処理する。 bit を直線で表す。 bit が立った部分に枝を刺す。 始点・反転フラグや終点マージンに数 bit を使っても 96 頂点くらいで済む。
実装上の残る問題はそいつをどうやって構成するか。自己辺多重辺が禁止されている。 ボトルネックとなる元の木は、 1 点が過半数の親になっているような木。 この場合、この頂点だけ除外しておけばあとは乱択で事足りる。 残りの頂点の最大次数はせいぜい $50$ なので、運任せで構成してもまず足りる。 私の実行時間は 1ms だった。
ポイント
これも、コーディング終了後に、提出せずに、 冷静にテストプログラムを ruby で書いたのが大きい。 案の定入っていたたくさんのバグを潰した。
H - Make a Potion
これだけはあとでやってみようかなと。最大フローの問題。
ポイント
I - Activate It!!
ポイント
J - Paint Red and Make Graph
ポイント
K - Xor Summation Pattern
ポイント
L - Coin Game 2017
ポイント
Others
私としてはかなり頑張ったよ。普通のコンテストなら ABCE で終わる。 G も解けないし、 D だって時間以内にはとけないところだ。しかし粘って AC できた。
WA を減らしていれば順位が上がったが、些細なことである。 5 時間フルに使って戦った。久しぶりに悔いが残らない結果になった。もちろん実力は磨き続けなければならないが、このコンテストは反省点はもうないです。
ABCE を解いた段階で、順位表を見にいったのが大きい。 G は通している人がいたので、これを見にいった。自分にもできそうなタイプの問題だった。非常に集中してコーディングして 2 時間程度で解けた。 D が 1 時間で解けたのも運がよかった。 DP なら死んでいた。
謝辞
毎年 KUPC は楽しめています。スタッフの皆様のおかげです。ありがとうございました。
会場と懇親会の場を提供してくださった PFN 社様、ありがとうございました。