1月 TopCoderの暗号マラソンにハマった この問題が自分の中で一番のお気に入り 2月 OBOG会の冬合宿でロシア＆中国チームのヤバさに絶望した 3月 TCO＆ICPCChallenge＆引越しで忙しすぎて死んだ 4月 ICPC WF@ストックホルム 全然ダメぽだったorz 5月 多分課題…

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

目的 TopCoderとかでいちいちΣ計算するのがだるかったのでプログラムで自動化を試みた。 ただΣ計算するだけではあまり意味が無いので、条件式を自動で場合分けして計算するものを考えたところ、式は多項式に限定し、条件式は線形不等式と定数を法とする合同…

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さん以外全部落ち…

なんとまぐれで３位を取ってしまった！！！ 開始 なんか点数の割り振りがすごく偏っているが気にせずとりあえずAから読むことに 読んですぐ方針は立ったので組んでみたがなんかバグってサンプルが通らないorz 最近はICPCの影響でバグ取りがめんどくなってき…

優勝した！！！ これで２回目の世界大会がほぼ確定したっぽい ついに後１試合のみとなってしまったわけで、ちょっと真面目に感想を書いてみる チーム戦であるICPCで勝つためには、個人力も重要だとは思うけど、一番重要なのはやっぱりチーム力だと最近は特に…

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

奇跡の大逆転により優勝した！！！ 0:00 Aがただのダイクストラだったので組んだらバグって時間かかったorz きたまさがB意味不とかいうので飛ばしてCをやった TLEしそうだったけど、まぁいけんじゃねと思ったら通った 他の問題聞いてもすぐに解法分からなか…

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

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

なんか運よく通過してしまったｗ 一人旅とかやばい…英語勉強しないと… A 全て連結という条件から状態数がとっても減るのでてきとーに幅優先探索するだけ B smallは全組計算するだけ largeもいっぱい提出があったのでずっと考えてたけど、さっぱり分からなか…

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

A 使えるやつで一番上のから貪欲に使うだけ B 現在位置とその段で掘られている区間を状態としてDPすればいい 現在位置は掘られている区間の左端か右端のどちらかなので状態はO(RC^2) 次の状態は左右に移動して穴に落ちるか、ある区間を掘ってその左端・右端…

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

参加者の皆様お疲れさまでした。 以下てきとーな解説を

KMCoderにて9月22日13:00〜18:00に記念すべき第一回KMCMonthlyContestが開かれます 5時間10問のオリジナル問題セットですICPC夏合宿で出題する問題を流用するだけなので、合宿に参加した人の再参加はご遠慮ください ルールはICPCの採点方式で チーム参加の場…

コンテストの問題をJavaで解くときに、ときどき入出力がボトルネックになってTLEするので、その解決策を色々試してみた 入力 1. Scanner 使いやすいけど、正規表現を用いているためとても遅い 100万個のint値読み込むだけで3.5sくらいかかった 2. Integer.pa…

A どうせそこまで大きくならないだろうと想定して、てきとーにsmallを通した largeは最悪ケース試したら遅すぎたので、最初に全パターン計算させることにした てきとーに最適化したら10秒くらいで全部解けるようになったけど、最悪埋め込めばおk B ただのダ…

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

全9回のコンテスト(うち1回はJAGの過去問のため、自分たちが参加したのは8回)を終えて昨日帰ってきた 合宿の詳しい様子はきっとid:iwiwiが書いてくれると思うのでてきとーにまとめると、 総合成績は33チーム中7位でorz 昨年のWF優勝チームであるSPbIFMOが圧…

明日から9/7までロシアに修行に行ってきます 結局課題が終わらなかったので、向こうでIP確保できないと死ぬorz

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

なんか運良く優勝してしまった 普段出てるコンテストとは違って、探索メインかつ入力一つだけという変わった形式だったけどなかなか楽しめた 一日目の一問目 16クイーンの障害物あり版 とりあえずA*組んだが、全然終わらないorz 時間制限後に探索する方向を…

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

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

国内予選までは問題が簡単なので複数コーダー作戦はあまり必要ない気がするので今回のチーム戦略は、 自分がひたすらコーディング きたまさがひたすら問題文を読み、全問読み終えたらペアプロに入る きたまさがどうせ問題文を読み落とすので、りゃんがもう一…

id:iwiwi ときたまさと HITO(ryというチーム名で初参加した 一日目3:00 寝たはずのきたまさが「べ、べつにICFPのためにおきてたんじゃないんだからねっ」とかいって起きてきて吹いた 眠かったけどとりあえず問題文だけ読んだ ルールによるとトップ１０のは別…

ICFPやってたが、早くも飽きたので参戦 A やるだけ 6/0 B シミュレーションするだけ… だがバグりまくったorz 20/0 C サイズの小ささとか気にせずパースして木作ってDP 36/0 D 移動せずにコンテナを押すっていうパターンを完全に忘れていてWAorz 探索空間が(8…