問題リンク The Balance of the World 解法 再帰で解きました。 左から文章を見ていって閉じ括弧が見つかればfalseです。 開き括弧ならば、対応する閉じ括弧との間の文章はバランスしているはずなので再帰します。 間の文章がバランスしてなければfalse。間…

問題リンク Chebyshev's Theorem 解法 123456*2の大きさのエラトステネスの篩を作ります。それと累積和の配列を作れば勝ちです。 ソース

問題リンク Gap 概要 Gapというカードゲームをやる。これをクリアするまでにかかる最短の手数を答えよ。 Gapは4*8のボードを使い、1〜4の柄それぞれについて1〜7の数が1枚ずつある。ボードには常に4か所の空欄がある。 1手につき、空欄にカードを移動するこ…

問題リンク Molecular Formula 概要 原子と原子量の表と、化学式が与えられる。与えられた化学式の総原子量を計算せよ。 化学式はBNFに従っている。化学式中に表に登場していない原子が現れたらUNKNOWNと出力すること。 解法 BNFがあるのでこれをもとに構文…

問題リンク Weather Forecast 概要 4*4の大きさの国があり、16個の町がある。そして2*2の大きさの雲がある。雲の下は必ず雨でそれ以外は晴れている。雲は国の国境をまたぐような位置にいることはできない。雲は最初に5,6,10,11の町の上部を覆う位置にいる。 …

問題リンク Lagrange's Four-Square Theorem 概要 ラグランジュの4平方の定理は、全ての自然数は4つの平方数の和で表せるというものである。整数Nが与えられるので、Nを4つの平方数の和による表し方は何通りあるかを答えよ。 N 解法 4重for文+枝刈りで何とか…

問題リンク Unreliable Message 概要 王様と、6人の家臣J, C, E, A, P, Mがいる。 王様に対するメッセージSが6人の家臣を伝って王様に届くが、彼らは受け取ったメッセージを少し変えてしまい、王様は変わってしまったメッセージTを受け取る。 王様は元のメッ…

問題リンク 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辺の比が、与えられた三角形のそれと誤差…

問題リンク Shredding Company 概要 ターゲットとなる整数tと印字された整数numが与えられる。numを任意の場所でカットし、できた断片に書かれている数字の総和を考えたとき、tを超えずに最大となるものを求め、更にそれを実現するカットを答えよ。 どのよう…

問題リンク Map of Ninja House 概要 忍者屋敷を探検した結果が与えられる。忍者屋敷の構造を答えよ。 忍者屋敷は部屋と、部屋を結ぶドアからなる。 最初どこかの部屋にいる。その部屋のまだ開けていないドアを1つ開け、その先が未訪問の部屋ならば入室する…

問題リンク Life Line 概要 石とりゲームをする。プレイヤーの番号をCとする。ほかのプレイヤーの番号はC以外の1〜9の数字である。 大きさNの正三角形上の空マスに自分の石を置いたとき、得られる得点の最大値を求めよ。 得点とは（自分の番号以外の取り除い…

問題リンク GIGA Universe Cup 概要 4つのチームによるサッカーの総当たり戦の試合結果表から、あるチームがグループ通過する確率を求めよ。 グループ通過とは1位もしくは2位になることである。 以下の用語を定義する。 勝ち点： チームが試合に勝ったら3点…

問題リンク Equals are Equals 概要 多項式Pが与えられる。更に多項式のリストLが与えられるので、これらがPと同値かを判定せよ。 多項式の変数には'a'-'z'が使われる。そのほかは'0'-'9', '(',')', '^', ' ', '+', '-' の文字のみが登場する。 '+', '-'は2…

問題リンク Calling Extraterrestrial Intelligence Again 概要 m, a, bの3つの値が与えられる。 2つの素数の組p, qを p*q a/b を満たすものとするとき、p*qを最大にするようなp, qを答えよ 4 1 解法 エラトステネスの篩で10^5までの素数を求めておきます。 …

問題リンク Nim 概要 Nimというゲームをやる。石の山から石を1〜4個交代でとっていき、最後の1個を取った人が負けである。 ただ、今回のNimは少しルールが違う。 まず、チームでプレイする。1チームはN人であり、全部で2N人でプレイする。石を取る順番は味方…

問題リンク Young, Poor and Busy 概要 KenとKeikoはそれぞれHakodateとTokyoにいる。2人はどこの都市でもいい(Hakodate,Tokyoでもよい)ので合流し、30分以上一緒にいた後、それぞれの都市に帰りたい。2人はAM08:00以降に出発でき、PM18:00までには帰らなけ…

問題リンク 77377 概要 携帯電話の文字入力を効率的にしたい。"press"という文字列を出したいとき「77377」と打つだけで済むようにする。 キー入力のシーケンスが与えられたとき、作ることができる文章を全て出力せよ。出力する順番は任意でよい。 ただし、…

問題リンク Fishnet 概要 1辺が1の正方形の各辺にN個の釘を打ち、水平方向と鉛直方向に糸を張る。 糸を張るときは必ず(a1, b1),(a2, b2)...(an, bn), (c1, d1),...,(cn, dn)の組の釘に対して張る。 水平方向に張った糸同士、鉛直方向に張った糸同士は交差し…