GCJに参加しました。では結果をば 順位 得点 ペナルティ 631st 35 2:15:55 A-small A-large B-small B-large C-small C-large D-small D-large 53:02 53:45 2:06:14 2WA 2:07:55 未提出 未提出 未提出 未提出 なんと！上位1000人に入ってしまったのでTシャツ…

前置き ゲームの問題(プレイヤーが2人いて、お互いに最適な戦略を取ったとき勝つのはどちらか、みたいな問題）のときにたびたび耳にするGrundy数、これまでさっぱり何のことやら分からなかったのですが、解ける問題のレパートリーを増やすために、少しは理解…

問題リンク Chocolate with Heart Marks 解法 当初、全探索＋枝刈りで頑張っていたのですがどうしてもTLEが解けなくて諦めていました。 何かのきっかけで「最小シュタイナー木」というものの存在を知りました。シュタイナー木とはグラフGと、頂点の部分集合S…

問題リンク Test Case Tweaking 概要 N個の頂点とM本の有向辺からなるグラフがある。頂点1から頂点Nまでの最短経路のコストがちょうどCになるようにしたい。辺のコストが非負であるという制約のもとで、コストを任意に変えていいとき、コストを変更するべき…

5月だというのにやけに冷え込んでいたので暖房つけて参加したTopCoderOpen2012 AlgorithmのRound 2Bの参加記です。 まず結果をば 順位 得点 レーティング 512nd 171.43 1432 → 1497 300 550 900 Challenge 171.43 未提出 未提出 0 という感じです。点が変則…

問題リンク Speed 概要 トランプの「スピード」をプレイするロボットA, Bがいる。このロボットたちの動作をシミュレートしてどちらが勝つかを判定せよ。 「スピード」は手札が4枚、場が2か所、デッキを使い、2人が向かい合って遊ぶ。場に出ている一番上のカ…

問題リンク Finding the Top RPS Player 概要 N人の人を集め、じゃんけんを行う。 N人は最初0勝である。ゲームは1ターンに同時に任意の数だけ試合が行われる。ただし、試合は連勝数の等しい人同士のみ行う事が出来る。k連勝同士の人が試合をすると勝った方が…

他所様のコンテスト参加記を読むのが楽しいので、自分も書いていこうかなと思い立ちました。余力や記憶が残っている時だけ書こうというスタンスです。AOJで解ける問題が少なくなってきたので、こういう形でもブログを頻繁に更新できたらいいな、とも思ってい…

問題リンク Everything Starts With Your Vote 解法 上位K人の中に入れるお気に入りのキャラ数について2分探索して解きます。 キャラは人気度でソートしておきます。 need(X): 上位K人の中にお気に入りのキャラをX人食い込ませるために必要な最低投票数 とい…

問題リンク No Story 解法 分からなかったので解説を見ました(解説の「遅い解法」の方法で攻めていました）。 Lを素因数分解して、 L = p0^e0 * p1^e1 ... とします。すると、a, bはこの指数を決めて得られる整数となります。 また、LCM(a, b)がLとなるには…

問題リンク Gather on the Clock 概要 N個の数字が円形にならんでいる。好きな数字Aを1つ選び、時計回りに1つ回った次の数字Bとの差の絶対値|A-B|が得点に加算される。この後、Bは円から無くなる。この操作を円に残った数字がただ1つになるまで続けたとき、…

問題リンク Merry Christmas 概要 N個の家、M本の双方向の道からなる街がある。 更に、L個のクリスマスプレゼントのリクエストがある。リクエストiは{pi, ti}からなり、時刻tiちょうどに家piにプレゼントを配るという意味である。 プレゼントを運ぶためにサ…

問題リンク Road Construction 概要 N個の街がある。街は1〜Nで番号付けされていて1番の街は首都である。 国王が街同士を結ぶ街道をM本作ろうと計画している。街道は双方向で、街iと街jを結び、その距離はd、建設費用はcである。以下の条件を満たすようにM本…

問題リンク Memory Leak 解法 構文解析+シミュレーションです。 Javaでは型がクラスの変数は全て参照なのでそれを流用することにして解きました。 確保した領域クラスRを作ります。メンバーにはメモリ量を持っています。 大きさ26のRの配列rを作り、変数A〜Z…

問題リンク Chicken or the Egg 解法 まとめると、次のように答えを求められます。 同じ単語が続いてる箇所で切る。 切ってできた文字列の中で一番単語数が多いものを選ぶ。複数ある場合は最初のものを選ぶ。 その文字列の最後の単語が答え。 eggとchickenを…

問題リンク Angel Stairs 解法 逆向きに考えます。 まず、N+1段目に降り立つには、直前にNかN-1段目にいることになります。 N段目にいたとします。このN段目にいるには、Tnを踏んでSmの音を出さないといけないです。そして、TnをSmの音で出すためにどう踏む…

問題リンク Champernowne Constant 概要 Champernowne定数とは、"0."の後ろに正の数を連続で並べたような無理数の事である。 0.1234567891011121314... 2つの正の整数NとKが与えられる。Champernowne定数の小数点以下N位からK文字を求めよ。 1 1 解法 区間分…

問題リンク Reverse a Road 概要 1〜Nまでの番号がついた街と、M本の有向路(番号1〜M)がある。街SからTまでの最短距離を求めよ。 ただし、M本の辺のうち1本だけ向きを逆向きにすることができる。最短距離を得るために変えた辺の番号も答えよ。そのような辺が…