問題 w*hのチェスボード上をチェスのナイトが動く。 ナイトツアーとは、任意の場所からスタートし、スタート地点に戻ってくる経路のことを言う。 ここで、同じ場所は何度も通ってよい。 ナイトサーキットのサイズとは、1度でも訪れたチェスのマスのuniq数を…

問題 バラとユリが何本か入った箱が与えられる。箱iについて、バラの本数とユリの本数がわかる。 この箱をいくつか使って、R*Lのグリッドの各グリッドに花を植えるために使う。 ただし、各グリッドについて、隣接する4つのグリッドはそのグリッドに植えた花…

問題 文字列がいくつかと、文字列a,b,cが与えられる。 各文字列が以下の条件を1つ以上満たすとき、悪い文字列であるという。 ・接頭辞が文字列a ・接尾辞が文字列b ・接頭辞と接尾辞以外の部分文字列にcを含む いくつ悪い文字列があるか数える。 考え方 実際…

問題 チェスボードと、複数のナイトかポーンがある。 初期配置と最終配置が与えられる。 1手で1つのコマを1回動かせる。各コマの動きは以下。 ・ナイトは、ボードからはみ出ないように全方向の桂馬飛びで移動できる ・ポーンは、1マス進める。一番端まで移動…

問題 正N角形の各頂点だけが配置されている。 ある頂点リストpoints(M個、N 考え方 bitDP。蟻本の「3-4 動的計画法を極める！」と同じような感じで、dp[辿った頂点集合][今いる頂点]で2重ループで書ける。今の辿った頂点集合stと今いる頂点vについて、まだた…

問題 0を含まない整数AとBがあり、交互に各ターンでそれぞれ以下の2つの操作ができる。 ・いまの数字をreverseする(123->321) ・いまの数字/10する(123->12) 2人でそれぞれの数字を操作していくゲームを考える。 このとき、AがBと同じ数字にすることができた…

ox- 638位で敗退。500もオーバーフローだけで、アルゴリズム的には間違ってなかったのでよしとする。。 (凡ミス再提出はだめだったけど) 今回、500で線形探索してる人結構部屋にいたけど、作っておいたテストケースが貼り付けたとき最後になぞのスペースが入…

問題 プログラミングコンテストをやっている。 部屋がn+1部屋あって、0〜n-1までの番号の部屋にはそれぞれ何人か人がいる。 自分はn番の部屋に1人でいて、ほかの部屋の人数は知ることはできない。 各部屋のスコアの合計点数の配列が与えられる。 今、自分よ…

問題 配列の最初と最後だけがわかっていて、隣接する数字は高々dだけしか違わない。 配列のサイズがnだとわかっているとき、配列の中で最大となる数値を返す。 考え方 配列の最初からどんどん+dずつしていくのが左からの最大値、 配列の最後からどんどん+dず…

問題 ぴったりXの距離だけジャンプできるカエルがいる。 数直線上を原点からスタートして、距離D以上になるまでジャンプを繰り返す。 間に、L[i]からR[i]までの幅の穴がいくつか空いている。(L[i],R[i]の端点は穴に落ちない) 穴に落ちないようにする場合、最…

問題 グリッドのマスに数字が書いてあり、一番小さい数字と一番大きい数字の差が1になるようにしたい。 1回の操作で、どれかのマスの数字に1足すか1減らすことができる。 最低何回の操作で実現できるか？ 考え方 全探索する。ある数値を決め打ちし、 ・それ…

問題 N本のブロックのタワーがあり、0からN-1の番号が振られており、それぞれの高さheightsが与えられる。 このタワーを横一列に並べる。 このとき、あるタワーが倒れても横のタワーが倒れないように、2つのタワー間の距離は、その2つのタワーの高いほうの高…

問題 要素が0または1のH*Wの配列が与えられる。 配列の周りを罫線で囲んだものを考える時、左上の部分から右下の部分まで最短距離で結んだ線を引き、その線の下側になるすべての要素の0と1を反転することができる。このとき、すべての要素を0にするために必…

問題 整数値の配列aが与えられる。 配列x[0..N-1]が 1=2*x[i] を満たす場合、convexである、という。 与えられた配列aに対し、次の操作ができる。 ・iを一つ選び、そのa[i]を1引く 配列がconvexになるまでにかかる最小の操作回数を求める。 考え方 要素が10^…

問題 毎晩、毛の色を変えられるオオカミがいる。 色はN色あって、便宜上0〜N-1の番号で扱う。 colorMapという2次元配列が与えられる。 もし色iから色jに変えることができればY、そうでなければNが書かれている。 色は、変化させられる最小の番号の色に変わる…

問題 1*1*1〜1*1*kのレゴブロックが無数にある。 土台が1*1*wのところに重ねていき、高さをhにしたい(土台は高さに含めない)。 条件として、ブロックを重ねるとき、重ねるブロックからはみ出ないようにする必要がある。 そのような重ね方の組み合わせは全部…

問題 ロボットがあり、「right X」「left X」「forward X」「backward X」の命令がいくつか与えられる。 rightとleftの時はXに角度、forwardとbackwardの時はXに距離が与えられる。backwardは向いている向きに対して(向きを変えずに)反対方向へ移動する。命…

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

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

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

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

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

問題 デカルト座標のxまたはyが整数のところをN匹の蟻が動いている。 各蟻はNWESの方向へ一定速度で動いている。 もし衝突した場合は互いに消滅してしまう。各蟻の初期位置と方向が与えられるとき、最終的に消滅せずに残っている蟻の数を返せ。 考え方 一定…

問題 4つの記号「/」「N(バックスラッシュの代わり)」「|」「-」からなる列が与えられる。 記号に対して、4つの操作R(右に回転)、L(左に回転)、F(フリップ)、S(なにもしない)をするとそれに応じた記号に代わる。 与えられた記号列を生成するような操作列を「…

問題 最小公倍数Gと最大公約数Lが与えられるので、そのようになる2つの整数A,Bのうちでその和が最小になるそのA+Bを返せ。 考え方 L/Gが割り切れないならば、そもそもおかしいので-1。 M=L/G、A'=A/G、B'=B/Gとして、素因数分解したものをA'とB'に割り振れば…

問題 フィボナッチ数列のFiが与えられるので、それに対応するインデックスiを計算して返す。 ただし、Fi=1ならばi=2、Fiに対応するiが存在する場合はそのi、Fiに対応するiが存在しない場合(例えばFi=4)はその前後の存在するFi,F{i+1}の値を線形補間して返す…

問題 3文字の組がいくつか与えられる。各文字は数字か「.」。 この3文字の並びは変えることができないが、組の順番は自由に並べることができる。全部の組を適当に並べたときに、1つ以上連続する数字の和で最大のものを返す。 例えば、「4.5」「5.3」ならば「…

問題 音楽プレイヤーに曲がN曲入っている。 プレイリストを作りたいが、P(>=N)曲で構成したい。 条件として、「全ての曲は必ず1回は流す」「すでに使った曲をもう一度流すためには間に少なくとも別なM曲をはさまなければならない」というルールを付ける。 こ…

問題 N種類の飲料によるカクテルがある。しかし、それぞれの飲料の割合を忘れてしまった。 メモには、N-1個の組み合わせについて、2組の飲料の配合比が書かれている。 メモを頼りに、元のN種類全部の配合比を求める。ただし配合比は最小の比率になる整数値。…

問題 文字がセルに敷き詰められた長方形が与えられる。 それをコピーして右、右下、下にくっつける。(サイズ的には4倍) ここで、この拡張した長方形の中の部分長方形を考える。 各部分長方形をすべて考える時、各セルに書かれた文字は全部で何回出現するか。…