問題リンク Co-occurrence Search 概要 文字列Sとk個の文字が与えられる。文字列Sの部分文字列の中で、k個の文字が全て現れるものの中で最短の長さとなる区間がいくつあるかを答えよ。そのような区間が1つ以上存在する場合、最も最初に現れた区間を答えよ。 …

問題リンク Walking Ant 概要 大きさH*Wのマップがあり、蟻と蟻の家と食べ物と石がある。蟻は単位時間に上下左右4マスに動くことができる。石のある場所は通れない。蟻が自分の家にたどり着くのにかかる最短時間を答えよ。 蟻はHPを持っており、その初期値と…

問題リンク Heavenly Jewels 概要 大きさ、[0, 10000]*[0, 10000]の島にIC, PC, ACMの3人の男の家がある。島のある座標に天から宝石がおとされ、男たちは同時に同じ速度で宝石に向かって一直線に向かい、最初に宝石にたどり着いたものが宝石を手に入れる。同…

問題リンク Mirror Illusion 概要 1辺が8mの正方形がある。中には幅1mの鏡がN枚あり、水平もしくは鉛直に平行に置かれている。 今、男が正方形内の座標(0.75, 0.25)に居て、(1, 0.5)の座標の方を向いている。このとき、男の目に入る景色は正方形内のどこの座…

問題リンク Trapezoids 概要 台形が'*'で描かれた図が与えられる。描かれている台形の面積とその個数を答えよ。 台形は水平方向の辺は必ず平行で、垂直方向は水平方向の辺に対して斜めに45度か直角である。 ある2つの台形が隣接していることはない。つまり、…

問題リンク Die Game 概要 サイコロをコマンド通りに動かした後、上部に描かれている数字を答えよ。 コマンド数 解法 サイコロを転がすだけです。 ソース

問題リンク Square Coins 概要 1, 4, 9, ..., 289(=17^2) の価値のお金がある。これらの硬貨を使ってN円を払う方法は何通りあるかを答えよ。 N 解法 DPです。 dp[i][j]: i^2までの硬貨を使ってj円を表せる組み合わせ数 の表を作るだけです。 ソース

問題リンク Rational Irrationals 概要 正の整数p, nが与えられる。ここで、Qnをn以下の正の整数を使って表せる有理数の集合とする。Qnに属するものの中で√pより小さくて最大のものu/vと、√pより大きくて最小のものx/yを答えよ。 解法 1/1から始めていき、√p…

問題リンク The Devil of Gravity 概要 エディターを実装し、与えられたコマンドのシミュレート結果を答えよ。 このエディタは下に向かって重力が働いている。ある文字列の全ての範囲においてその下が空いており且つ最下段でなければその文字列は全体が落ち…

問題リンク Pump up Batteries 概要 N人の警備員がいる。彼らはそれぞれPCで仕事をする。しかしバッテリーが貧弱なので充電器で充電する必要があるが、充電器が1つしかない。彼らは、仕事をする時間s、充電する時間tの時間がサイクルになって決まっている。s…

問題リンク Push!! 概要 大きさH*Wのマップ上で1人の男、1つの荷物、1つのゴールがある。 男は上下左右に動くことができる。そのとき、荷物を自分の進む方向と同じ方向へ動かすことができる。引くことなどはできない。 男がゴールに荷物を運ぶのに必要な、荷…

問題リンク Family Tree 概要 ある人物を唯一の根とする家系図が与えられる。 ある2人の人物の間柄の質問が与えられるのでそれの真偽を答えよ。 質問に登場する人物は必ず家系図に登場していることが保証されている。 家系図に登場する人物の数 質問 解法 家…

問題リンク Lost in Space 概要 三角形の辺の長さQR, RP, PQ(cm)と、N個の3次元座標が与えられる。 N個の中の3点を使い、与えられた三角形と相似になる三角形を作る点の番号を答えよ。 相似とは、三角形の中の全ての2辺の比が、与えられた三角形のそれと誤差…