AOJ Volume12
問題リンク Sum of Consecutive prime Numbers 概要 整数Nが与えられる。連続する素数の和がNになる組み合わせは何通りあるか答えよ。 2 解法 10000以下の素数の数は1229個しかないので、先頭の素数を1つ決めて、連続和を計算しても余裕で間に合います。 ソ…
問題リンク Dice Puzzle 概要 サイコロを27個使って3*3*3の立方体にする。ただし、サイコロ同士の面が接触しているところはその和が7でなければならず、立方体の上面と正面に現れる数字は、予め決められた数字になっていなければならない。これらの条件を満…
問題リンク Color the Map 概要 国の領域を表す、多角形の座標リストがn個与えられる。領域は1つの国に属する。国は他の国と国境線が0より大きい長さの共通部分を持つ時、隣接していると見なされる。これらの国に色を塗るとき、必要な色の最小数を答えよ。た…
問題リンク Confusing Login Names 概要 N人の名前と整数Dが与えられる。N人の中で混乱する名前の対を全て求めよ。 混乱する名前の対(i, j)とは、 任意の1文字を消す 任意の位置に文字を1字入れる 任意の1文字を別の文字にする 隣接している文字同士を1か所…
問題リンク Pathological Paths 概要 N個のファイルの絶対パスが与えられる。このシステムには、絶対パス中に現れるディレクトリ、フォルダ以外のものは何もない。さらにM個の絶対パスの組が与えられる。この組の指すファイルが同一のものかどうかを判定せよ…
問題リンク Leaky Cryptography 概要 整数N1〜N8とチェックサムN9が16進数表記で与えられる。これらは32ビット整数である。 Σ(Ni xor K) = N9 xor K を満たすような32ビット整数Kを16進数表記で求めよ。 解法 Kを0ビット目から31ビット目まで順番に決めてい…
問題リンク Make a Sequence 概要 N*Nの各マスに棒がささったボードでM目並べゲームをする。Pターンの間の2人のプレイヤーのボールを置いたマスのリストが与えられるのでゲームの結果を答えよ。(i, j)の棒にボールを置くとき、ボールは重力に従った動きをす…
問題リンク The Balance 概要 aグラムとbグラムの錘を使ってdグラムを量りたい。使う錘の個数を最小化せよ。そのような個数の組み合わせが複数ある場合は錘の総重量が最も軽いものを答えよ。a, bの錘を使ってdグラムを量れないということは起こらないことが…
問題リンク Telescope 概要 半径1の円周上の点がN個与えられる。これらの点を使ってM角形を作った時の最大面積を答えよ。 3 解法 いくら考えても分からなかったのでプログラムプロムナードを参考にしました。 メモ化再帰で解きます。 始点sを決めている前提…
問題リンク 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の正三角形上の空マスに自分の石を置いたとき、得られる得点の最大値を求めよ。 得点とは（自分の番号以外の取り除い…
