天下一プログラマーコンテスト 2015 参加記

Klabさん主催の天下一プログラマーコンテストという大会に参加してきました。3位でした。

F問題

A, Bはペナルティが無いらしいし、問題を見る限り高々80点しか差がつかないので放置

とりあえず一番配点の低いFを考える

根へのパスに1を足すこととパスの値を求める事さえできれば二分探索でできるなとなる。

そこから頭のいい解法を考える事すらせずに殴って終わらせてしまった。反省。

E問題

とりあえずブロックを高い順に追加して考えると見通しが良くなりそう

期待値の線形性でガリガリやると、どうやらO(N)時間で解ける事が判明

式を書き写してAC。最近10億7に強くなってきた気がする(といっても天下一に出るような人の平均よりはまだダメだと思う。今回は運が良かった)。

C問題

うわぁなんだこれ

行列と置換が交互に置かれるような形になるので最初行列累乗の線で考えていたが、流石に無理。

どうしようもないので、とりあえず部分点を取ることを考える。

それはダイクストラでホイだった(本当は01-BFSするべきだったが、H=100なのでどうとでもなると思った、実際は危なかった?)

D問題

部分点が60点とは思えないがパッと書いてパッと提出。ジャッジに無限時間かかる。

この後Cを考えるがわからず、どうしようもないのでA,Bに移ることに

B問題

10点は流石に秒殺。 さすがに少しは真面目な戦略を考えたい 次数でsortしてdfsを考える。それなりに良さそうだったので書いて提出

A問題

とりあえずいい感じのグラフを考える。 特に思いつかないので、頂点を50個50個に分けて間にランダムに辺を追加、を繰り返すことを考える。 これは前述のB問題で次数に注目したため、使う頂点と使わない頂点での次数の分布を同じにすることを考えたから。 よく考えたら自明に二部グラフなため、危なかった。(まあこの短時間コンテストで二部グラフの処理の追加までできる人はそうそういないと思うため大丈夫)

多重辺の処理を忘れていてWAを連発する。相当焦る。死ぬほど焦る。

が、ギリギリ気付けて投げることができた。危ない。

さすがにAB合わせてラスト20分は危険すぎた。もう少し早めに片付けておいたほうが良かった。

ブレイクタイム

ABの結果で順位が3位から7位まで変動するため気が気ではない しかもABで特に力を入れたわけではない(つもりだった)ので…

何とは言わないがB問題の結果があれしてかなりあれなことがわかったのでこれはもしかして…?みたいになる

結果発表

BどころかAもかなり上位で、無事3位になることができた。とても嬉しい。 実際20分でこれはかなり勘が冴えていたのではないかと思う。

感想

Klab問題の無慈悲難易度本当勘弁してくり〜

Gを読みもしなかったのは勿体無かったですね(といってもこのタフセットで誰も解いていない問題を読みにいくのは戦略上どう考えてもミスだと思うので、これで正しいとは思う。)

Eはシンプルで面白かった。

Cはなー、さすがに頭がこんがらがって無理。EFの前の元気なうちに取り掛かっていればあるいは…?(これも結果論で、F->E->Cの順で解いたのは正しいから言うだけ無駄。)

問題はG以外(まだ読んでいないので判定できない…ゴメンナサイ?)すべて(A, Bも含めて!)面白かったです。