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

問題リンク Driving an Icosahedral Rover 概要 20面体を点(0, 0)に、"0"を接地させ"5"が北側になるように置く。1ステップに3方向へ転がすことができる。点(x, y)に数字nが接地するように動かすための最小ステップ数を答えよ。nが接地さえしていれば方向は問…

問題リンク Test Case Tweaking 概要 N個の頂点とM本の有向辺からなるグラフがある。頂点1から頂点Nまでの最短経路のコストがちょうどCになるようにしたい。辺のコストが非負であるという制約のもとで、コストを任意に変えていいとき、コストを変更するべき…

問題リンク Malfatti Circles 概要 三角形の頂点が反時計回りに与えられる。この三角形の中に円を3つ内接させる。その条件は、 円は2本の三角形の辺と接していて且つ他の2つの円と接している である。この条件を満たす3つの円の半径を答えよ。誤差は10^-4よ…

問題リンク Long Distance Taxi 概要 ガソリンが最大capまで積めるタクシーがある。タクシーはガソリン1毎に10km走ることができる。タクシーが町SからTまでガス欠を起こすことなく走るとき、その最短距離を答えよ。辿りつけない場合は-1とせよ。 道路がN本あ…

問題リンク Infected Land 概要 N*Nのグリッドがある。グリッドのマスは '.': 何もない '#': 感染している '@': 車 の3種類からなる。各ステップにつきグリッドの状態は次のように遷移する。 '#'マスは、周囲8マスにある感染マスの個数が2個が3個のとき次の…

問題リンク City Merger 概要 N個の都市の名前が与えられる。全ての都市の名前を部分列に含み、かつ長さが最小となる文字列を答えよ。 N 都市名の長さ 解法 巡回セールスマン問題になります。 dp[S][i]: 訪れた都市の集合S、最後に訪れた都市の番号iのときの…

問題リンク The Sorcerer's Donut 概要 H*Wに文字が並んでいる。ある文字からはじめて、周囲8方向へ向きを決めて読み続けることができる。表の外へはみ出すとき、上辺へはみ出すならば下の辺へ、右辺へはみ出すならば左辺へ、というように読み続ける。 magic…

問題リンク Gift from the Goddess of Programming 概要 ログイン・ログアウトのログ記録がN個ある。ログ記録には「日 時間 IorO ID」が記録されている。Iはログイン、Oはログアウトを表す。神様のIDは"000"である。このとき、神様と一緒にログインしていた…

問題リンク Towns along a Highway 概要 N個の町が直線状に並んでいる。町iと町jの距離の上半分行列に登場する値が降順で与えられる。この行列の値に従って町を配置できるときの隣り合う町の距離を答えよ。配置方法が複数通りある場合、距離の辞書式順序で出…

問題リンク Balloon Collecting 概要 1つの家と1つの車とN個の落ちてくる風船がある。車はX軸上のみを移動する。 風船は場所xに時間tに地面に落ちる。この時間tに車がその場所にいれば風船を取ることができる。しかし、一度に乗せられる風船の数は3つまでで…

問題リンク Membership Management 概要 N個の「グループとそのメンバーリスト」が与えられる。メンバーリストに載っているのは人物の名前だけでなく、別のグループの名前が書かれていることもある。このとき、入力の一番最初のグループに所属している人物は…