問題リンク 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を素因数分解し、必要な…

問題リンク Sheets 解法 a[y][x]: 左下の座標が(x, y)である1*1のマスを覆うシートの数 という表をyについて1行ずつ更新する方法で解くことができました。 シートの枚数が変わるタイミングはシートの上辺と下辺の部分です。 面積はa[y][x]が正になっている部…

問題リンク Make KND So Fat 解法 DPです。 buy[甘味セット][使える金額] -> 体重への影響の最大値 という表を前処理で作ったのち、 dp[何日目][使える金額] -> 体重への影響の最大値 という表を埋めればOKです。 ソース

問題リンク KND is So Sexy 解法 ヘロンの公式を使います。三角形ADCとBECの辺の長さは、計算すると、AD=DC、BE=ECになるような二等辺三角形にすれば面積最大になることが分かります。 ソース

問題リンク Colored Cubes 概要 サイコロがN個あり、各面に色が塗られている。どのサイコロのどの面も任意の色に書きかえることができる。N個のサイコロを全て同じサイコロにするために必要な色の塗り替え回数の最小値を求めよ。 1 解法 全探索です。 サイコ…

問題リンク Manhattan Wiring 概要 H*Wのナンバーリンクのパズルがある。0は空白マス、1は壁、2と3同士が結ぶべきマスである。このパズルを解くために必要な線の長さを最小化せよ。解が無い場合は0とせよ。 1 解法 DFS+枝刈りが方針です。 2を結ぶ線をDFSで…

問題リンク Kuru-Kuru Robot 解法 線分アレンジメントを施したのちダイクストラして解きました。 線分アレンジメントの説明はスパゲッティさんにソースコードと共にあります。ここのソースをおおいに参考にして線分アレンジメントを書きました。オーバーラッ…

問題リンク Ice Maze 解法 色々アプローチを試し、最終的に通ったのは反復深化法でした。 最初に氷をグルーピングしておきます。 ゴールから各マスへの最短距離を調べます。このとき、氷は考慮しません。この距離が、(i, j)からゴールへ辿り着くために必要な…

問題リンク Finding the Largest Carbon Compound Given Its Longest Chain 概要 炭素だけを結合した化合物の構造の中で、最大鎖長がNであるようなもののうち、炭素の数の最大を求めよ 1 解法 Nの偶奇で場合分けすると、炭素の最大数の増え方の規則が見えて…