マラソンで奇跡が起きて優勝しちゃった！ Marathon Final 今年から24hになったので大変だった・・・ 問題概要 崩壊する洞窟からコインを回収するゲームのAIを作成せよ 通路は単位時間で1歩移動でき，壁を壊すのにはT時間かかる 通路上にはところどころにコイ…

Subgraph Isomorphismする問題 暫定8位だけど、おそらくシステムテストで順位が超入れ替わると思われるので安心出来ない 通過できてるといいなぁ 戦略上重要なこと スコアが絶対評価なので、点が稼げるところで一気に稼がないといけない 難しいケースは頑張…

TCOのシードを得るために一年ぶりに参戦 結果は11位orz まぁ、久しぶり過ぎた上に時間がなさすぎたのでしょうがない… 方針はまず、何段にするかと、それぞれの段の高さを決めるために、次のように制約をきつくした問題を考え、それを解くことにした。 i段目…

hos先生のセット 250 全通り調べるだけ n=1の場合を忘れて再提出orz しかも、再提出ミスって再々提出orzorz 147.68 550 見た瞬間、二分探索＋2SAT 492.89 1000 現在位置*安全だと分かっている色の集合*危険だと分かっている色で状態数が50^2*2^7*8 これをDP…

またしてもりんごさんのセット… 250 ソートして、Π(a_i-i)計算するだけ すぐに気づけなくて時間かかったorz 239.85 500 よくわかんなかったのでとりあえず小さいの二つ取り出して足すのと掛けるので大きい方にして、一つになるまで繰り返すーをやってみたら…

やっぱりSRMは11:00なんていう早朝にやるもんじゃないねｗ 250 1,"11"で0返してて再提出orz 落とし穴いっぱいで撃墜しまくりだーと思ったら自分のも落ちたorzorz 1,"110"とかどう見ても解あるじゃん… Failed System Test 450 全てのやつを独立に考えて良くて…

300 直径と半径間違えたり、直径と高さ等しいやつ使う意味ないよねーとかやったりしたせいで時間かかったorz 219.33 500 ただのダイクストラだなと思って組んだら、最大ケース入れてみると1.0sくらいかかる… これTLEすんじゃね… よく考えたら点追加せずに移…

帰国してすぐで寝不足がやばかったけど欝なICPCの気晴らしのため参加 250 てきとーに探索した 頭が回らなくて色々バグったorz 218.76 500 DPするだけ 確率計算をミスってなんか足して1にならなかったけど係数考えるのもめんどかったのでてきとーに正規化した…

250 0.5刻みで全部試した 241.08 500 一番下の数字の寄与は二項係数となるので、個数制約なしのナップサックみたいな感じのDPするだけ 430.89 1000 O(NM)くらいで解の存在判定ができる？→わかんね パターン見つけゲー？→わかんね Challenge なにも落とせるの…

250 弾性衝突=すり抜け 242.65 450 まず、コインの金額が決まっていたら貪欲に使うだけなので、a円以上のコインでb円を払おうとすると残りb%a円をそれ未満のコインで払うことになる よって、 dp[i]:=一番小さいコインがi円の時に全部i円未満になるまで貪欲に…

Petr+ACRush部屋にあたっていきなり絶望した 250 めんどくさいので24*60*19通り全部生成して試した 235.46 500 あれーmodとらなかったらオーバーフローするんじゃね… とか思ったら、全然そんなことはなかったｗ どれがmod nで等しくなるかを全パターン試して…

250 2(0,+1)=(+1,+1)+(-1,+1) だから、上に進む回数は一回以下として良くて、(dx+dy)%2で場合分けするだけ 245.12 450 ソートを昇順と勘違い→カットいっぱいした方が得じゃん→ちょうどC回カットでいいね→サンプル通らね→よく読んだら降順じゃん→脳内ちょうど…

300 ドーナッツを探す O(n^4)のDP 手抜きしてO(n^5)でやったけど間に合った 254.56 900 550>900の法則より900からやることに ただのDPかと思って組んだらサンプルが通らない… 問題文読み直したら勘違い発覚orz ルートvの部分木はv以下のノード全部取り出した…

250 やるだけゲー 245.26 500 dp[i][j][k]:=i文字目でj本取り除いてk本使った時の総数 みたいなかんじで漸化式つくってDP 394.62 1000 Σを頑張って計算するだけ 一箇所ミスってサンプル通らずorz Challenge 落とせるのないーorz 合計639.88の20位 2899 → 2917

250 ただの幅優先探索 236.97 450 ただのナップサック 427.29 1000 ただの包除原理 …なのにびみょーにTLEしてorz ほかので完全に割り切れるのを除外して高速化したら通った Challenge 1000で再帰の終了条件がおかしいのがあったので撃墜 hosさん以外全部落ち…

250 左上から貪欲に置いてくだけ 247.51 500 駄目なパターンは全てのIの間隔が奇数で一定であるときのみ いつの間にかOIが01になったり色々バグって時間かかった上に、なぜかIの間隔のgcdの約数を調べないというあほなことして落ちたorz Failed System Test …

250 11...で割り切れるか調べるだけ 247.78 500 (現在位置,取った数)->最後のk最小化でDPするんだろうけど、最後のkを最小化するところが全くわからん… と思ったら問題文読み違えてたorzorz なぜか脳内ではx増やした次のターンはy増やすことになっていたorz …

250 1の場合は勝敗が入れ替わって、2以上の場合は全部使うか1つ残すかでターンを自由に入れ替えれるので必ず勝てる 248.36 500 ちょいと数式かいて微分したら増資するなら有り金全部使うのがいいということがわかったので、何ターン増資するかでループした …

450 変則セットだったので450からやってみた クラスカル法の各段階において求まるものも、そのサイズにおける最適解なので、各段階ごとに連結成分の数だけ空港を置けばよい そっこーで解けたのに、最後の一回だけ空港0個でいいのをすっかり忘れていて再提出o…

250 候補となる座標はそんなに多くないので全部試すだけ 234.39 950 550>950の法則により950からやった とりあえず漸化式が立ったので小さい場合の値を生成して数列検索に投げたらカタラン数だったｗ 最終的な法は素数だけど、K^nのnに対する法は-1されて合…

前回参加できなかったので１カ月ぶりのSRM 250 ロシアで似たようなのやったなぁと思いながら組んだ 230.22 500 実プロで初めて解いた問題の花札シャッフルなつかしーと思いながら組んだ びみょーにミスってサンプルの最後だけ通らず、なかなかミスに気付けず…

250 さいころ転がすのは、mod3するのといっしょ 244.61 500 1sでiからjに移動する最高スコアをまず計算して、あとは行列n乗ぽい感じでやるだけ 403.11 1000 全然わからなかったorz Challenge 落とせそうなのが何もないorz 合計647.72の5位 3001 → 3054 びみ…

275 最初二分探索かと思ったが、ちょっと考えたら二点の中点以外ないんじゃねと思ってしまったorz 0.5刻みで全部の点を調べればいいだけだったorz Failed System Test 550 一瞬グレイコードだと思ったがよーく見たら違った 何個か手でやってたらパターンが見…

250 三角形の位置*大きさ*判定で50^5くらいだけど全部回るわけじゃないのでまぁ間に合うと信じて実装 添え字間違えたりしてめちゃ時間かかったorz 187.55 500 ただのビットDP またも色々バグって時間かかりすぎorz 376.87 1000 最初桁数が44...の倍数じゃな…

うぉぉぉぉぉぉ ターゲットktkr 300 始点と終点で円の内外が異なれば、その円の境界を必ず１回はまたぐ必要があり、またそのような円の個数回で始点から終点にたどり着けるので、それが最小 296.94 1000 600>1000の法則があるのかは知らないが、1000からやる…

250 やるだけゲー 248.24 950 550>950の法則により先に950からやった 最小カットの典型問題 一瞬で組み終わったのに、入力処理するとこがバグっててびみょーに時間がかかったorz 762.82 550 950が結構早くとき終わったので念のため最大ケース試したりしてか…

250 find the two perfect powers between A and B, inclusive, that are closest to each other をAとBの間にあって、A,Bそれぞれに一番近いのを探すんだと勘違いしたorz しかもオーバーフロー面倒くさいからBigIntegerでいいやーとおもったらTLEしたorzorz…

250 わかんねー でもSummary見るとそっこーで出してる人がいるから簡単に解けるんだろー というわけで勘で置換のループの個数数えてみたらそれっぽかったので提出 218.42 500 てきとーに閉路を壊して繋げてけば連結成分の個数-1回でできるので、連結成分の個…

250 ただの二分探索 奇跡の最高点ゲット 237.38 500 てきとーに回せば収束するに違いない⇒サンプル通った⇒提出 冷静に考えたらそんなすぐに収束するはずないねｗ というわけで考え直し ツリーの葉の方向に進んで戻ってくるのにかかる期待値を順に計算してい…

全然だめぽだったorz システムテスト前の段階で18位なので予選突破は完全に無理orz てかみんな強すぎだー 以下一週間の流れ