この記事はCompetitive Programming Advent Calendar Div2012の第24日目の記事として書かれているものです。自分は競プロでJavaを使っています。環境はWindows版Eclipse Java EE IDE for Web DevelopersのIndigo(3.7)です。 競プロにおいて、無意識に当然の…

コンテストリンク AtCoder早稲田大学の有志主催の第2回WUPCのオンサイトに出場してきました 13:00集合とのことでしたが、私用で遅れて13:45頃に到着。事前に遅れることを伝えていたが申し訳ない... お昼がまだだったので、ツナマヨおにぎりを放り込みながら…

コンテストリンク CodeChef November Challenge 2012 問題 結果 Coin Flip AC Sridhar Likes Travelling AC Delicious Dishes 1RE AC A Wonderful Chocolate 2WA AC Candy Collecting Game AC Lucky Balance AC Jam Board 26RE 9TLE Many Left - Arithmetic …

問題リンク Numbers 解法 「合成数 連続」などで検索すると、次のことが分かります、目からウロコでした。 合成数がN個連続している場所は、 (N+1)!+2, (N+1)!+3, ... , (N+1)!+(N+1) であるというのです。 (N+1)!は2〜N+1のどれでも割りきれます。なので、…

問題リンク War 解法 原点からの距離がkとなるマスは4*k個あります。体力がk以上の兵士は距離kのマスに到達することができ、k以上の体力を持つ兵士が4*k人以上いると、4*k+1番目以降の兵士はどう頑張ってもすでに他の兵士が到達したマスを通らざるを得なくな…

問題リンク Grid 解法 a1, b1, a2, b2の値を使ってO(1)で答え出せるんじゃないかと思い、更にそれにこだわったためにコンテスト中はWA大量生産工場になってました。 座標が1000*1000までなので、2次元配列を作ることができ、ダイクストラすることができます…

問題リンク ID 解法 DPです。 dp[i][j]: インデックスi以降の数字を使って、mod 10の値がjのものがいくつあるか という右からのdpで解けます。 2倍にする数字は、右から数えて偶数番目のやつなので注意です。 ソース

問題リンク Immortal Jewels 解法 答えとなる直線があったとします。この直線を、吸着できる宝石の数を変えないように動かしたとき、それ以上動かせなくなる境界的な置き方が存在します。その直線は、2つの宝石と、磁力の強さだけ半径を増やした2円、これら…

問題リンク Twenty Questions 概要 M個の特徴のみからなる世界がある。ここにN個の物体があり、お互いに全く同じ特徴のものはない。今手元にN個の物体のうちの1つがあり、これが何か特定したい。そのために、人に特徴のうちの1つを聞くことができる。聞いた…

問題リンク Dial Lock 概要 K桁のダイヤルロックがある。範囲[s, t](0 1 解法 DPの方針で考えていましたが、DFSで解きました。 ダイヤルの左側の数字sから考えていき、S_sとT_sの数字が違えば、数字を合わせるように回します。このとき、回す範囲の右端t (s …

問題リンク Text Justification 概要 N個の単語長と幅Wが指定される。単語は入力の順に並べる。このとき、1行の文字幅がWに近付くように、改行を挿入できる。単語の途中に改行を入れることはできない。以下の方法にのっとって、単語の並べ方のコストを算出す…

問題リンク Beehives 概要 2人の人物がハチの巣の中を調査する。2人はセルを移動した方向を'a'〜'f'で表す。方向'a'〜'f'は反時計回りの順でつけるということは統一されているが、'a'の向きがどこを向いているかは統一されていない。2人の人物が調査した軌跡…

問題リンク Numoeba 概要 ヌメーバと呼ばれる、細胞が木構造の生物がいる。木の根になっている細胞をリーダーと呼ぶ。 木は単位時間毎に構造を変え、リーダーもそれに合わせて変わる。 ヌメーバの各細胞はnumbosomeと呼ばれる奇数の整数値(1〜12345677)を持…

問題リンク Revenge of Champernowne Constant 概要 チャンパーノウン定数とは、"0."に続いて、正の整数を昇順に連続で並べたような無理数である。 "0"-"9"の文字で構成された文字列Sがチャンパーノウン定数の中で最初に出現する位置はどこか答えよ。答えは1…

問題リンク The Two Men of the Japanese Alps 概要 N本の線分で表された山の稜線がある。山の左端と右端にそれぞれ人がいる。彼らは、常にお互いのy座標が等しくなるように線分上を移動する。彼らが出会うために必要な移動距離の最小値を求めよ。 2 0 x_i …

問題リンク Find the Multiples 概要 a_0 〜 a_(n-1)の[0,9]の列と素数Qが与えられる。i a_i a_(i+1) ... a_j を10進数の正の整数とみなす。リーディング0なものは認めない。この正の整数がQの倍数であるような(i, j)の組がいくつあるか答えよ。答えは2^30を…

順位 得点 レーティング 256th 120.36 1594 -> 1631 +37 275 550 1000 Challenge 120.36 Open Unopen +0/-0 Easyしか解けなかったわけですが、周りの人がもりもりEasyを落としたので、350位くらいから250位近くに浮上してきました。不沈艦(?Easy: Stamp 概要…

問題リンク The Tower 解法 シミュレーション問題なので注意深く実装するだけです。が、問題文を読んだだけでは曖昧さが残るところがあるような気がするのでつらっと列挙したいと思います。プレイヤーの動作直後のゲームオーバー判定処理と、プレイヤーの動…

問題リンク ICPC: Intelligent Congruent Partition of Chocolate 解法 チョコレートの総数をNとします。チョコのグループをAとBと呼びます。Aのチョコレートに所属するチョコをN/2個決めたら、AとBのチョコレートがそれぞれ連結しているか調べて解とします…

問題リンク Dr. Podboq or: How We Became Asymmetric 解法 入力文字列を構文解析して木を作ってから、木の根から順番に題意を満たすように子を入れ替えて行きます。 木には次の情報を持たせておきます。 rep: このノードを根とする木の文字列表現 sub: この…

問題リンク School of Killifish 解法 平方分割で解きました。 注目しているバケットの最小値が暫定解を更新しないなら、そのバケットに対する処理をスキップするという枝刈りを入れたらかなり高速になりました。 ソース

問題リンク Beaker 解法 DFS+貪欲で解けました。 一番大きいビーカーの水を小さいビーカーへ振り分けるやり方は非常に多くなるのでたぶん時間が厳しいです。ここで逆転の発想、全てのビーカーに水を注ぐことができた時、最後に水が入っているビーカーはどこ…

問題リンク Jigsaw Puzzle 解法 DFS+枝刈りで解きました。ただ何も工夫をしないと余裕でTLEを貰います。 パズルとピースは全て1行を1つの整数として表すことにします。パズルは穴があいている部分が1、ピースは穴が無い部分が1になるようにします。こうする…

問題リンク School Excursion 解法 最小費用流で解けます。 駅に同時に辿りつかないという制約は次の図のような感じにすれば実現できるかと（コスト/容量） 同じ時刻に到着する電車は同じ頂点に集まるようにして、そこから容量1の辺を伸ばせば、電車が1本し…

問題リンク Mysterious Onslaught 解法 結局、答えを調べたのですが思考の変遷を少し。 状態数は明らかに2^25個なので最初にBFSをかけられなくもないんじゃないかと思い付いたが、TLEが取れそうにない。ですが、最悪の場合でも9ステップしかかからないという…

問題リンク Winter Bells 解法 交差点iの子どもがサンタを見る確率は (iを通る最短経路の数)/(全最短経路の数) となります。 iを通る最短経路の数は (0からiへの最短経路数) * (n-1からiへの最短経路数) となります。 経路の数はDPで求まります。よって、2回…

問題リンク Building Houses 解法 全探索+枝刈りで解きました。 家をどの順番で置いていくかを全通り試します。k番目に置く家は、必ずk-1番目より右に置くようにします。このままだとO(N!)かかるのでTLEします。 枝刈りのヒューリスティックス値に使えそうな…

問題リンク Online Quiz System 概要 オンラインクイズゲームシステムのシミュレートを行い、サーバとクライアント間のデータ通信量を答えよ。 プレイヤー数はM、問題数はNである。 クライアント側のプログラムは全て同じである。 全問題文は事前にダウンロ…

問題リンク Crop Circle 解法 各円それぞれについて、[0, 2π)の範囲のうち、他の円に隠されていない部分はどこかを管理します。隠されていない部分の円周の和が答えとなります。 言うは易し行うは難しでこれが思ったより面倒くさいです。 次の手順を踏みまし…

問題リンク ! 概要 整数NとN進数で表現された文字列Mが与えられる。N進数でM!を計算したとき、末尾に続く0の数を10進数で出力せよ。なお、10を超える整数はA〜Zで表現されるものとする。 8 M 解法 この問題の応用編になります。 まずNを素因数分解し、必要な…