問題 縦行、横列のマス目で構成されているマップについて各マスは 平地……平地のマスは自由に通行できる。 木……木のあるマスは通行できない。 強敵のいるマス……凶暴な強敵のいるマスである。後述の条件を満たさなければ通行できない。 プレイヤーの村……プレイ…

問題 行列の長方形状に並べられた机に対して生徒が一人ずつ座っている。行目列目にいる生徒の成績をとしたとき、ならばとなるようにしたい。そのような席替えのうち、生徒の移動距離(マンハッタン距離)が最小になるものについてその最小値を求めよ。 解法 ま…

問題 整数とが与えられるので、総和がとなるような選び方が何通りあるか求めよ。 解法 半分全列挙。個の数字のうち前半について組み合わせを全て列挙してそれぞれの和を配列に確保しソートする。後半についても組み合わせを列挙して和を求め、に足りない分を…

問題 個の箱が順番に並んでおり、左から個目に目的のものが入っている。開けられる箱は一番左のものだけであり、箱の列に対しては次の操作が行える。 以下の素数について、を、をで置き換える。 箱全体を右か左に一つずらす。両端はループしているとする。 …

問題 1の位が4か7である整数を複数使えるとき和がとなるようにできるか判定し、できる場合はその最小の個数を求めよ。 解法 10の位以降の調整は自由にできるので1の位をに揃えるのに必要な最小個数を求め、それでできる数よりが大きければ大丈夫。 反省 もっ…

問題 アイドル人を集めるために種類のガシャを回すことを考える。それぞれのガシャは一回に一人のアイドルを排出する。各ガシャについて確率分布と回すためにかかる金額が与えられるとき、全てのアイドルを入手することについて最適な戦略の下での必要な金額…

問題 いくつかの単位換算表を与えるので最も大きい単位を最も小さい単位で表したときの関係を示せ。 解法 ある単位から見ての他の単位の大きさを深さ優先探索で求めて、一番大きいものと一番小さいものを出力する。 反省 2時間ほどでAC。最初はワーシャルフ…

問題 円筒の左右から赤緑青の3色のいずれかで塗られているボールを入れていく。ボールは同じ色のボールと接触すると消えるという性質を持つ。左右どちらから入れるかは任意であり、ボールを入れる順番だけが与えられるとき、最終的に円筒内に残る最小のボー…

問題 直方体の豆腐が複数用意される。各豆腐の中には1つ以上のハバネロが埋め込まれており、二人のプレイヤーがハバネロを避けながら豆腐をいずれかの面に平行な平面で切断していく。豆腐の個数、サイズ、ハバネロの位置を与えるので、どちらのプレイヤーも…

問題 19×19の碁盤の状態を与えるので五目並べの盤面として正常かどうかを判定せよ。 解法 盤面について先手後手それぞれが勝っているか(五目並んでいるか)を判定する関数を用意する。まず与えられた局面で先手後手それぞれについて勝っているかを判定し、次…

問題 小文字からなる英単語を変換していく遊びを考える。可能な変換は単語内の1文字を別の文字へと変える操作のみであり、最初の単語と最後の単語、そして経由可能な単語のリストを与えるので最小の変換回数での変換とその過程を示せ。 解法 リストの重複を…

問題 色のうちどれか1色で塗られているブロックが個順番に落ちてくる。1個落ちてくるたびにそのブロックを山に積むか捨てるか選ぶことができ、最終的に山に積まれたブロックによって次のように点数を付ける。 色ボーナス:色ごとに決められた点数が個数分与え…

問題 個の街がありそれぞれには人口が定められている。 2つの街を選んで人口の小さい方を大きい方へ統合する 操作を街が1つになるまで繰り返したとき、最終的に残り得る街の数を求めよ。 解法 人口が大きい順にソートして、人口が自分以下の街の人口の和が次…

問題 人のうち人へ手紙を配り間違えたとき、あり得る配り方の組み合わせの数を求めよ。 解法 まず人の中から配り間違えた人を選ぶ方法が。 そして人に対して全て間違った配り方となる組み合わせの数は攪乱順列、あるいはモンモール問題などと言われるもので…

問題 あなたと参加者を足して人の人がおり、あなたは持っている個のたこ焼きを参加者に投げて配る必要がある。参加者もたこ焼きを投げることができ、参加者を経由して他の参加者にたこ焼きを配ることが可能である。各人は2次元座標上に散らばっており、たこ…

問題 テレビを点けた瞬間から数えて視聴可能なタイミングを'o'、不可能なタイミングを'x'で表す文字列が与えられる。同じテレビを複数用意し点けるタイミングをずらすことで、最後のテレビを点けて以降はどの瞬間もいずれかのテレビで視聴可能であるようにし…

問題 与えられた整数列の要素を1つ非負の整数へ変化させたとき、要素全ての和と積が一致するかを判定せよ。 解法 要素数が1つの時はどう変えても一致するので2つ以上の場合について考える。 番目の要素をへと変化させることを考える。番目以外の要素の和を、…

問題 の格子状の区画において、各マスは通行可能か不可能かのどちらかとなっている。2回だけ通行不可能なマスを通行できるとき、スタートからゴールまでたどり着けるか判定せよ。 解法 通行可能ならコスト0、不可能ならコスト1として辺を構築してスタート地…

問題 が与えられるのでを満たし$$ \frac{\frac{N (N + 1)}{2} - M}{N} = \frac{X}{Y}$$であるを全て求めて列挙せよ。 解法 式変形をすると$$N = 2\frac{X}{Y} + 2\frac{M}{N} - 1$$でありであるので、としてあり得るのはまたはの2通り。それらについてを計算…

問題 の長方形を本の横棒、本の縦棒を用いて個の長方形に分割する。いくらかの小長方形の面積がわかっているとき、全体の面積を特定するために知る必要がある小長方形の個数を求めよ。 解法 この記事にある通りunion find。 反省 何か共有しているかどうかを…

問題 のマスが与えられ、各マスには障害物か1桁の数字が書き込まれている。各マスのコストはで与えられ、スタートからゴールまでの区間のコストの最小値がその経路のコストとなる。スタートからゴールまでのコストの最大値を求めよ。 解法 2分探索でコストの…

問題 白か黒で塗られているボールが入ったスタックが与えられる。「上からボールを1個を取り出し、黒だったら残りのボールを全て色反転、白だったら残りのボールの順序を反転し、取り出したボールは捨てる」という操作を繰り返したとき、黒いボールを取り出…

問題 8クイーンパズルについて3つクイーンを置いた状況の盤面を与えるので、残り5つを制約を満たすように置けるならそのうち一つを出力せよ。 解法 制約を満たすような置き方について全探索をする。各行、列、および右斜め左斜めのラインについてクイーンの…

問題 を初期値として を引く 以下だったらを足す という操作を繰り返したとき以上で無限ループになるか判定せよ。 解法 1時間考えてもわからなかったので解説PDFを読んだ。以下はそのまま。 まずすぐわかる場合を省きにいく。なら初日で買えないのでfalse。…

問題 最初全て無色である個のブロックを赤緑青の3色で塗り分けることを考える。各ブロックがそれぞれ赤であれば点、緑であれば点、青であれば点、無色のままなら点として、個のブロックの合計得点がになる塗り方は何通りか求めよ。 解法 解説PDFの通り。 緑…

問題 異なる正の整数の集合に対して、どのについてもとのその他の要素の和の最大公約数が1でないとき特別であるということとする。要素数の特別な集合であり、全ての要素の最大公約数が1であり、どの要素も30000以下であるものを求めよ。 解法 1時間半ほど考…

問題 平面上に個の点がある。半径の円内から無作為に1箇所選んだとき、番目の点が一番近くなる確率を求めよ。 解法 が十分大きいので、細かい部分は無視されて点に吸い込まれる角度だけが重要となる。個の点集合に関する凸包を求めて、その頂点となっている…

問題 パンがいくつかの種類に分かれている。ある種類のパンは分でちょうど焼き上がり、それより短い焼き時間だとundertoasted、長い焼き時間だとovertoastedとなる。 いくらかの種類のパンに対してundertoastedとなった焼き時間の列、overtoastedとなった焼…

問題 000000000から999999999までの数字のうち一つが書いてある宝くじを一つ買う。vector<string>が与えられ、その要素のどれか一つでもsuffixになっていれば当選であるとき、当選する確率を求めよ。 解法 同じだったり被ったりする要素を上手く弾くだけ。 vector<string>を</string></string>…

問題 個のスポーツに対して人がそれぞれ1つだけに参加する。番目の人の参加優先順位がで表されるとき、実施するスポーツを適切に選択して最も多くの人が参加するスポーツの参加人数を最小化せよ。 解法 全てのスポーツを実施する状況から考える。このとき選…