問題 n個の部屋があり、部屋と部屋を結ぶ通路はn-1本存在している。 通路はどちらの方向へも進むことができ、距離が設定されている。 ある部屋からすべての部屋へ行くことが可能である。危険度とは、ある部屋から別の部屋へ移動するとき、最短で移動するパス…

問題 nが与えられるので、n個の連続した正の整数を求める。 ただし、その正の整数すべてについて、合成数でなければならない。1 考え方 nが大きい。 合成数の連続というのは、2つの連続する素数の差(prime gaps)が1500以上になるところが答えになる。 調べて…

問題 ある無限に広い2次元グリッドの、あるマスにいる。兵士をn人つれており、各兵士の体力が与えられる。 各兵士は上下左右の隣接マスに移動できるが体力が1減る。 通ったマスを占領できるとき、最大でいくつのマスを占領できるか。 考え方 最初に降順にソ…

問題 r*cの2次元グリッド上の2点間マンハッタン距離で最小となる経路の数を返す。 ただし、グリッドは上下、左右がつながっており、右端は左端に移動、などができる。(トーラス) 考え方 2つの座標a,bについて、aを固定して考える。 bについて、グリッドの周…

問題 n桁のIDのチェックを行う。チェックは各桁について、右端を1桁目として、偶数桁の数字を2倍してすべての桁を足したものが10で割り切れるかどうかで確認する。2倍して2桁になった場合はそれらをさらに分割し、それを足したものを用いる。 IDには*が含ま…

問題 N個の1列に並んだセルからなる真っ白なボードがあり、これに色をつけたい。各セルの色は赤、青、緑の3色。 各セルの塗りたい色desiredColorが与えられ、R,G,Bならばその対応した色、*ならばどれでもよい、を表す。 色をつけるときはL個分の隣接セルをま…

問題 あなたはQBで、普通の少女を魔法少女にできる。 n人の普通の少女と、少女iが少女jを好き(非対称)、というリストが与えられる。 ある普通の少女iが魔法少女になったとき、その少女が好きな女性をプロテクト状態にでき、プロテクトされた少女の好きな少女…

問題 ある村にN個の家がある。これらの家は以下の条件を満たして存在している。 ある実数Rが存在 2つの家の距離がR以下なら、同じ表札を持つ 2つの家の距離が3R以上なら、違う表札を持つ 任意の2つの家はR以下もしくは3R以上のいずれか この村の表札の種類は…

問題 じゃんけんの手の数がN個ある一般化じゃんけんをする。 各手の勝ち負けあいこのリストが与えられ、勝ちなら3点、あいこなら1点、負けなら0点がもらえる。 1000回AIとじゃんけんをするとき、350点以上獲得せよ。 ただし、AIはあらかじめ手が決まっていて…

問題 N個の部屋が1直線上に並んでおり、外からの侵略者が各部屋を狙っている。 侵略者から部屋を守りたい。 ある人は、ある区間をまとめて守ることができ、人と守れる区間のリストが与えられる。 できるだけ少ない人数で守る時、その人数を答える。 全ての部…

問題 N匹のうさぎちゃんがいる。m個の船に何匹かずつのっている情報が与えられる。 仲の悪いペアのリストが渡されるので、仲が悪いペアが同じ船にいるうさぎちゃんの数を返す。 考え方 各うさぎちゃんについて、仲の悪いうさぎちゃんがのっているかどうか一…

問題 1xmのマスでオセロを行う。「o」と「x」があり、初期状態が与えられる。 「o」から始める場合、どちらが勝つか答えよ。 考え方 両端のコマに注目する。 「o~~~~~o」の場合、最初はパスでxがどちらかに置く。その次に「o」は置かれた「x」の外側に置くこ…

問題 一つの砂時計を連続で使い続け、T-E秒〜T+E秒のどれかを計測したい。 いくつかのTi秒の砂時計が与えられるので、その中から上記が計測できる砂時計を返せ。 考え方 各砂時計についてT-E〜T+E秒すべてについてTiで割り切れるかどうかチェック。

問題 WxHのグリッドが与えられる。 各点について、スタート地点、ゴール地点、移動できる場所、壁の情報が与えられる。 上下左右に移動でき、スタート地点から2回まで隣接する壁を壊して移動できる場合、ゴール地点にたどり着くことができるかどうかを答える…

問題 9x9の数字の書かれた乱数カードが与えられる。 (x,y)からW方向に向かって、4文字を取り出す。 ただし、カードの端にきたら折り返して数字を取り出す。 その4文字を返す。 考え方 現在地点(x,y)とWに応じた変化量(vx,vy)を指定しておき、x += vx, y += v…

問題 N個の単語からなる文章が与えられる。 最後の単語には空白を挟まずに「.」がある。 その中で「TAKAHASHIKUN」「Takahashikun」「takahashikun」と完全に一致する単語がいくつあるか答える。 考え方 1単語ずつ一致するかカウント。 ただし、最後の単語だ…

問題 Xが非負の整数であるとき、以下の性質を持つ無限列をXのKleofas tailという。 数列の最初はX 偶数の数字の次の要素は、その数字の半分にしたもの 奇数の数字の次の要素は、その数字から1引いたもの 例えば、X=60の場合は、60,30,15,14,7,6,...となる。 …

問題 1からNまでの値の平均値を計算する際、ある整数Mだけを足し忘れてしまった。 間違った平均値のみわかっている場合、元のN、Mでありうるものを列挙する。既約分数とは限らない分数「X/Y」が与えられ、それぞれ1 考え方 与えられるX,Yは既約にするため、g…

問題 平面上にN+1個の点があり、i番目とi+1番目の間の距離diがN個与えられる。 1番目とN+1番目の点の距離でとりうる最大値と最小値を返す。 考え方 最大値は、一直線に並べたときが最大なので、距離の総和が答え。 最小値は、自明なものとして、N=1のときはd…

問題 N個の平面上の点が与えられる。 2つの点の距離で最大となるものを返せ。 考え方 異なる2つの点を選んで、距離最大値を保持しながら計算していく。

問題 N人で弱いと思う人に投票しあう。 もし、投票数が一番多い人が1人ならばその人が決定し終了する。 もし、そのような人が複数人いる場合、それらの人だけについて投票しなおす。投票は、あらかじめ投票する人を決めている人が何人かいて、その人たちが先…

問題 数字が書かれたカードが与えられる。 カードのうち1枚を引いて、その数字と、その数字の前後のカードがもしあればそれらを取り除く、 というのを繰り返す。 このとき、より多くのカードを引けるようにした場合、何回引けるか。 考え方 連続している数字…

問題 2次元座標平面上に格子点がN個与えられる。 その中から4点選んで、長方形を作る。ただし、各辺は軸に平行でなければいけない。 このとき、長方形内部に点を含まないような長方形で最大の面積となるものの面積を返す。 考え方 N個の点から2点(x1,y1)と(x…

問題 N個の街をつなぐM個の道の情報が与えれる。道の情報として、移動元の街、移動先の街、かかる時間が与えられる。街番号0から街番号N-1まで最短時間で移動したい。ただし、ゴールするときの時間は4か7で割り切れるようにしたい。 最短の到達時間を返す。 …

問題 7 2 3 1 5 3 のような数字の三角形が与えられる。一番上からスタートし、その地点から真下か右下に移動することができる。 一番下の段まで移動したとき、それまでの経路上の数値の合計値の最大値はいくらか。 考え方 DP。 その地点までの経路の合計値の…

問題 家の見取り図が与えられる。 部屋、壁およびスタート地点、ゴール地点、計算機のおいてある地点の情報が与えられる。 壁へは移動できない。 スタートから計算機の部屋へ寄り、ゴール地点までにかかる単位時間を答える。 部屋間の移動は1単位時間ででき…

問題 文字列がN個与えられる。その中から2つ以上選んで、任意の順番でつなげたものの中で、辞書順最小になるものを答える。 考え方 「2つ以上」となっているが、辞書順最小となるものは常に「2つつなげたもの」になるので、2つ(AとB)選んで、A+BとB+Aを候補…

問題 2012年の日付が2つ与えられる。 日付が何日離れているか答える。 考え方 早いほうの日付から1日ずつ足していって、もう片方の日付になるまでカウントする。

問題 円形テーブルにN人座っている。ただし、隣り合わせたくない2人組というのがM組存在する。 適当に2人を選んで場所を入れ替える動作をK回繰り返したときに、隣り合わせたくない2人組が隣り合っていないような確率を求める。 考え方 シミュレーション。制…

問題 NxMの格子状の区画とスタート地点、ゴール地点、各区画の明るさが与えられる。 各隣り合う区画は1秒で移動できる。 区画の明るさはスタートした時刻からt秒立つと、「元の明るさ*0.99^t」になってしまう。 なるべく、スタートからゴールまでの経路中、…