■ [others]The First KMCMonthly Contest
http://kmcoder.ddo.jp:8080/KMCM/contest/contest.html?contestID=23
全部難しかったです。こういうときは、望みのある問題はどれかを選ぶのが重要になってきますね
A.Anime Master
はじっこをまたいでるやつが居なかったらgreedyでいいと思うけど、これだけでこんなに難しくなるんだなー。
B.Cans of Toys
行列掛け算かと思って途中まで書くも間に合わず。行列乗算のコードを書くのは初めてだったり。でもこの方法ではTLEらしい。
C.Containers
比較的簡単そうに見えるも考えていたらよくわからなくなった。
D.Graph Destruction
逆向きにUnionFindしていく。以前作っていたUnionFindライブラリが初めて日の目を見た。
解けたのはこれ1つだけ。
E.Magic Doors
BFSぽいけどいろいろ複雑だったので後回しにしておいた結果まともに考えられなかった。
F.Maximum Segment XOR
データ構造系かなぁ。
G.Moving Points
原点からもっとも遠い点が入れ替わる時刻を全部計算して、任意の時刻で最も原点から離れている点はどれかが特定できるようにしてやった。
しかしTLE。確かに再遠点の入れ替わりは最悪で点の数と同じオーダーの回数起きるので計算量がO(10万^2)になって駄目だ。
まあそんなただの実装ゲーなんて出ないですよね。
H.Shuffling Machine
ループサイズがシャッフルした回数で割り切れるかとかそんな感じじゃないかと思うのだけどそれ以上はさっぱり。
I.Topology
手つかず。
J.Very Intellectual Card Game
これも難しいデータ構造系だと思ってまともに考えずにいたら、コンテスト後に他の人の解答を見てちょっと気づきさえすればとても簡単だということを知る。
これは解けるべきだった。