問題概要 座標平面の原点から、(x,y)まで、格子点を通り移動する。 1回の移動は座標軸に平行に、ちょうど1の距離だけ動ける。 座標平面上には、m個の泥の点があり、それらの点には移動することができない。 ゴールまで辿り着く最小の移動回数を求めよ。 500≦…

問題概要 幼稚園にはB人の男の子およびG人の女の子がいる。 男の子同士、女の子同士は全てお互いに知り合いである。 また、M組、お互いに知り合いの男女のペアがある。この中から任意二人が知り合いであるようなグループを作るとき、そのようなグループの最…

問題概要 5x5マスの迷路が与えられる。0は可能なマスであり、1は壁である。 上下左右に、壁のないマスに動ける。出発点は左上で、ゴールは右下のマスである。 スタートからゴールへの最短路を出力せよ。 最短路は一意に存在することが保証されている。

問題概要 n次正方行列A,B,Cが与えられる。 A×B=Cが成り立っているかを判定せよ。 n≦500,A,Bの各成分は絶対値100以下、Cの各成分の絶対値は10億以下とする。

問題概要 n個の空港がある。それぞれの空港はフライトによって直接または間接に行き来することができ、なおかつ行き来の仕方は一意に定まる。 二人のテロリストが次のようなゲームをする。 空港kから開始して、便に乗れなくなるまで以下を繰り返す。 今いる…

問題概要 スタートの日付から二人のプレイヤーが交互に日付を動かす。 日付は、カレンダーの次の日または、次の月の同じ日にのみ動かすことができる。 次の月に同じ日がない場合は、そこに動かすことはできない。 2001年11月4日に日付を到着させたほうが勝ち…

問題概要 n枚のカードが一列に並んでいる。 二人のプレイヤーが交互に両端のどちらかのカードを、カードがなくなるまで取っていく。 プレイヤーの得点は、プレイヤーが取ったカードにかかれた数字の和である。先攻のプレイヤーは最適な戦略を、後攻のプレイ…

問題概要 p,q,r,s,tは変数で1(true)または0(false)の値を取る。 K,A,N,C,Eは、それぞれand,or,not,imply,equalを表わす。 与えられた式が変数の値によらずtrueの値を取る時、tautologyを、そうでないときはnotを出力せよ。

問題概要 縦M横Nのグリッドで表わされる迷路がある。 各グリッドにおいて.は何もないマスを表わし、Xは壁を表わし、a〜eは扉A〜Eの鍵をあらわす。 スタートとゴールはそれぞれS,Gの文字であらわされる。 迷路において、扉を開けるためには、対応する小文字の…

問題概要 上側と下側に数字の書かれたドミノがn枚ある。 上側と下側の数字はそれぞれ0以上6以下である。 ドミノの上側の数字全ての和と、下側の数字全ての和の差を、いくつかのドミノをひっくり返してできるだけ小さくしたい。 そのような最小値を与えるとき…

問題概要 円周上に点が順に1,2,3,...,2nと並んでいる。 これらの点を全て、交差しない線分で一対一にペアを作るように結ぶ。 このような結び方は何通りあるか求めよ。 n≦100とする。 解法 1番の点が2i番目に結ばれるとする。 すると、円は2(i-1)個の点の部分…

問題概要 n個の数字の最大公約数を求める。 それが10億より大きくなるならMore than a billionを出力。

問題概要 60文字のG,A,T,Cからなる塩基配列がn個与えられる。 n個全てに共通する連続する塩基配列で、最も長いものを求めよ。 複数ある場合はアルファベット順で最も最初に来るものを求めよ。 n≦10を満たす。

問題概要 5x5のグリッドにH,Jが書かれている。 このグリッドの縦または横に連続した大きさ7の部分で、Jの数がHの数より多いものは何通りあるか。

問題概要 0,1からなる文字列の0を10,1を01に置き換える操作を、 最初に1から始めてn回行う。 操作後の文字列に00の出現する回数を求めよ。 n≦1000とする。 解法 小さい数(n≦10くらい）で試すと、漸化式はa[i]=a[i-1]+(-1)^(i+1)となっていることがわかる。 …

問題概要 H,Wが与えられる。H行W列に並んだアルファベットの渦巻きを出力せよ。 渦巻きは右上から時計回りに内部に進む。

問題概要 ある数nがSmith Numberであるとは、 nの各桁の和と、nの素因数全ての各桁の和が等しいことをいう。 ただし、nが素数であるときはnはSmith Numberではないとする。 ある数nが与えられたとき、nより大きな最小のSmith Numberを求めよ。 nは最大で8桁…

問題概要 K台の搾乳機およびC頭の牛がいる。搾乳機はM頭の牛から乳を搾れる。 各牛と搾乳機の距離が与えられる。各搾乳機にM頭以下の牛が割り当てられた状態になるよう牛が移動するとき、 最も移動距離の長い牛の移動距離の最小値を求めよ。 K≦30,M≦15,C≦300…

問題概要 k日間の株価が与えられる。 i日目におけるn日間の平均をPn(i),i日目におけるm日間の平均をPm(i)とする。 Pn(i)とPm(i)の大小が入れ替わった時点で株を購入することにする。 Pn(i)＞Pm(i)のときは売り注文、そうでないときは買い注文をする。また、n…

問題概要 R行S列の行列が与えられる。 この行列のR1行S1列からR2行S2列までの長方形の部分の成分の和を求めよ。 行列の各成分はintに収まる範囲であり、R,S≦1000を満たす。

問題概要 テキストが入力として与えられる。 テキスト中に含まれる変数=(数字)(接頭辞)(単位）から、 残りの変数を求めよ。変数はP（単位W）,I（単位A）,U（単位V）のいずれか、 接頭辞はm（1/1000）,k（1000）,M(1000000）のいずれかである。 解法 getline…

問題概要 多角形の各辺の中点を順に結んだ多角形が与えられる。 元の多角形を求めよ。

問題概要 木の頂点それぞれに何個かおはじきが置いてある。 一度の操作で、好きなおはじきを一つを、隣り合う頂点のうち好きなものに移動させることができる。全ての頂点に1つずつおはじきが置かれた状態にするために必要な操作の回数の最小値を求めよ。 n≦1…