指数時間アルゴリズムというのは，NP困難問題を頑張って指数時間かけて解くアルゴリズムのことで，できるだけ指数の底の小さいアルゴリズムを開発することが目指されています． コンテスト界では部分和問題の半分全列挙による2^(n/2)時間アルゴリズムなどが…
（この記事は Competitive Programming Advent Calendar の 18 日目の記事として書かれました．まだ18日です！セーフ！！！）自分はICPC時代によく嘘解法を駆使して問題を解いていたので（ジャッジの方々ごめんなさい），よく使われる嘘解法テクニックを紹介…
日本開催ということで今年は初めて大規模なチームを組んで本気参加 チーム名は"Unagi: The Gathering"で，チームメンバーは 自分，秋葉，いるーん，いもす，hos先生，tos先生 の競技プログラミングに最適化された６人結果は多分今ひとつな感じぽいけど，問題…
マラソンで奇跡が起きて優勝しちゃった！ Marathon Final 今年から24hになったので大変だった・・・ 問題概要 崩壊する洞窟からコインを回収するゲームのAIを作成せよ 通路は単位時間で1歩移動でき，壁を壊すのにはT時間かかる 通路上にはところどころにコイ…
前回のSRMでLayCurseさんの900の解法を見て思い出したので解説。次のように、二分探索の中で全探索をしているようなプログラムを考える。 int lb = 0, ub = INF; while (ub - lb > 1) { // 二分探索 int mid = (lb + ub) / 2; boolean tmp = false; for (Sta…
id:iwiwiとkita_masaとの３人で、一年ほど前からのんびり書いていた本がついに発売されるらしいです。 http://book.mycom.co.jp/book/978-4-8399-3199-5/978-4-8399-3199-5.shtml ちょい高めですが、自分たちがプログラミングコンテストで得た知識、ノウハウ…
Subgraph Isomorphismする問題 暫定8位だけど、おそらくシステムテストで順位が超入れ替わると思われるので安心出来ない 通過できてるといいなぁ 戦略上重要なこと スコアが絶対評価なので、点が稼げるところで一気に稼がないといけない 難しいケースは頑張…
きたまさが数学界に引きこもってしまったので今年はid:iwiwiと二人で参加。 チーム名はHITOCry 前回は劣化マラソンな感じで初日で飽きてしまったが、今回はなんか面白かったので完走した。 結果は7位だったorz 作業はGmailチャット+DropBoxのファイル共有で…
今年は個人で参加した。 8問半解いて、全体で15位、個人の部では1位だった。 A 数列が与えられるので、ソートされてないように並び替える問題 やるだけ B 平面上に一本直線があり、この直線上と上下左右への移動のみによる二点間の最短距離を求める問題 二点…
TCOのシードを得るために一年ぶりに参戦 結果は11位orz まぁ、久しぶり過ぎた上に時間がなさすぎたのでしょうがない… 方針はまず、何段にするかと、それぞれの段の高さを決めるために、次のように制約をきつくした問題を考え、それを解くことにした。 i段目…
CPU実験が終了しました。 我々の超ksk班はスーパースカラ+動的スケジューリング(OutOfOrder実行)で100MHzというのを作成し、17.3sという記録でした。 なんとか過去の記録は抜けたものの、基板の変更があったので単純には比較出来ない上、実は150MHz(もしくは…
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すんじゃね… よく考えたら点追加せずに移…
うちのチームのライブラリを公開しておきます 半分ネタなので、こんなのいつ使うんだーとかいうやつはバグってるかもしれないですhttp://up.chokudai.net/src/chota1219.pdf.html ぱすわーどはてきと追記: 二円の共通部分面積バグってるので使っちゃダメです…
今回のが２回目の世界大会だったので、もうこれで引退となります 自分は大学に入ってICPCに出会ったのがプログラミングコンテストに参加し始めたきっかけとなったこともあり、数あるコンテストの中でも一番気合を入れていました 今年こそは金メダルを取りた…
帰国してすぐで寝不足がやばかったけど欝なICPCの気晴らしのため参加 250 てきとーに探索した 頭が回らなくて色々バグったorz 218.76 500 DPするだけ 確率計算をミスってなんか足して1にならなかったけど係数考えるのもめんどかったのでてきとーに正規化した…
開始 Aからやろうと思ったらいきなり構文解析だったのでパスして色々読み始める Jが簡単そうだったので、どうせてきとーにやっても間に合うだろと思ってくんだら案外遅かった 座標圧縮するだけのCをきたまさが組み始める Aをまじめに組みなおして提出→AC 1時…
明日から中国のハルビンに行ってきます 本番は日本時間で2月5日の10:30〜くらい なんでも気温が-30℃とからしい！ 寒いの苦手…
以前O(n log n)の空間凸包を組もうとして挫折してずっと放置してたが、こないだの冬コンテストで出たのでそこそこ高速で楽な実装を考えてみた。 とりあえず、４点が同じ平面上に乗ってるのはないとして、 1. 点を徐々に追加していく 2. 凸包の各面が見えるか…
開始 簡単な問題がない！！！ JがただのDPな気がしたので提出したらWAったorz 間違いに気づいて直したら二乗のDPじゃなくて三乗になってしまった…のでパス きたまさがAの最小二乗法やってようやく1AC 1時間経過 Cの漸化式をがんばって立てて2AC目 早くも解け…
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で等しくなるかを全パターン試して…
いろいろ改良したらかなりまともになったのでとりあえず完成六角形の個数を求めるやつだと、 $x1$y1$x2$y2$x3$y3$x4$y4$x5$y5$x6$y6[0x4-y4][x3+y3=x4+y4][x4>x5][y4=y5][y5>y6][x5=x6][x6-y6=1 こんな入力を与えると、 long res = N * (12 + N * (4 + N * (…
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以下のノード全部取り出した…
