問題 長さの文字列の中から、長さの連続な部分文字列を重複が無いように二つ選んだ時、それらがアナグラムになっているようなものが元の文字列の中に存在するかを判定せよ。 解法 長さの部分文字列が互いにアナグラムになるかどうかは、その中にどの文字が何…

問題 からまでの整数の中で4と7以外の数字を多くとも1つしか使わない数字はいくつあるか求めよ。 解法 桁DPのメモ化が無いようなもの。状態として、 上から何桁目を見ているか 4と7以外の数字が何回出てきたか 今まで見てきた要素でより大きいことが保証され…

問題 整数から数字を1つ以上取り除き残った数字を順番はそのままに右へ詰めてできる整数らの和を9で割った余りを求めよ。 解法 上の桁から順番に9で割った余りがそれぞれ何回出てくるかを記録していく。これをとする()。桁目の数字がだったとき、これを使う…

問題 広義単調増加列のうち一部分が不明となっている列が与えられる。あり得る組み合わせの数を求めよ。 解法 不明な部分が連続している一つの塊に注目する。たとえば定数についてという部分列を考えるとすると、からに至るまでの4回の遷移の総和がとなって…

問題 頂点の木が与えられるので最も距離が長くなるような2つのノードのペアを一つ答えよ。 解法 ある頂点を根として考え、そこから再帰関数を回す。それぞれの関数内では、そのノードから各リーフノードへの距離と、リーフノードの番号を返すようにする。一…

問題 個の建物を回増築することを考える。建物は 最初の価格はである 増築するときには現在の価格に等しい費用がかかる 1回増築すると価格が上昇する 回増築するのに必要な価格の合計値の最小値を求めよ。 解法 解法の流れは、まず最後に増築するときの費用…

問題 ある整数を与えるのでをで割った余りを求めなさい。しかしは非常に大きく、についてが回繰り返されたものを上の桁から順番に並べたものとして表されるものとする。 解法 ダブリング。を回並べてできる整数をとすると、を回並べてできる整数は$$ k \time…

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

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

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

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

問題 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つを制約を満たすように置けるならそのうち一つを出力せよ。 解法 制約を満たすような置き方について全探索をする。各行、列、および右斜め左斜めのラインについてクイーンの…