Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2009-09-22

[]The First KMCMonthly Contest 19:58 はてなブックマーク - The First KMCMonthly Contest - TopCoderの学習のお時間

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

これも難しいデータ構造系だと思ってまともに考えずにいたら、コンテスト後に他の人の解答を見てちょっと気づきさえすればとても簡単だということを知る。

これは解けるべきだった。

 |