ABC257後記(A~E)
A - A to Z String 2
問題概要
A,B,C...がN個連続されて作られる文字列のM番目を出力してください。
解法
制約がと小さいので作っちゃうのが簡単そう
提出
B - 1D Pawn
問題概要
N個のマスとK個の駒がある。Q回駒に対して、「端か隣に駒がなければ右に動かす」という操作を行ったあとの各駒の場所を出力してください
解法
問題だけをみると、右端かどうかと、隣にコマがあるかどうかでややこしそう(このままやっちゃうのもアリ)。
ただ、マスN+1に駒を置いてしまえば、処理は「隣に駒があるかどうか」で済む。
提出
C - Robot Takahashi
問題概要
体重で大人と子供を判断したい。ボーダーXを適切に決めてXとの上下で判断するとき、最大で何人正しく識別できるか
解法
まず、この問題で与えられる数の順番は変えても問題ないので、体重でソートしてみる。
そうすると、高橋ロボは決めた基準より左側は子供、右側は大人と判断することがわかる(つまり、iとi+1の間をボーダーに決めたとき、[1,i]は子供、[i+1,n]は大人)。あとは、どこをボーダーにするかを全探索して、それぞれについて右側、左側それぞれで正しく判断できている数を数えてあげれば良い。この部分は累積和を使ってあげれば高速に判定できる。
(ソート後の)i番目とi+1番目の体重が同じの場合は、そこはボーダーにできないことに注意
提出
D - Jumping Takahashi 2
問題概要
各ジャンプ台の数値と高橋君のジャンプ力S(=訓練回数)で、マンハッタン距離が
までの場所にジャンプできるジャンプ台がいくつかあるとき、ある1点からどのジャンプ台にも何回かのジャンプで到達可能になるための訓練回数の最小値を出力してください。
解法
まず注目するのは制約でとなっていること。ここから、ジャンプ台の数に依存した解法が良さそうと見当をつけて考察。
そして、求めるものは訓練回数の最小値なので、二分探索ができないか考える。(無理そうならDPを覚悟)
二分探索となると、訓練回数に対して十分に高速な判定方法を考えることになる。ここで、Nが小さいので最初は愚直解を考えてみよう。
問題によると、訓練回数の条件は、「あるジャンプ台を始点として、そこから0個以上のジャンプ台を経由してどのジャンプ台にも到達できる」とのこと。ということは、愚直解は
- 始点は全探索
- 到達可能かはグラフ探索
で、この二つを組み合わせることになる。
ここで計算量を見積もると、始点探索が
、グラフ走査が
(頂点
個、辺が
本)だから、
で、この問題だと十分に高速だとわかるので、これで実装を進める。
二分探索の上限値は要注意(大きいとオーバーフローする)
提出
E - Addition and Multiplication 2
問題概要
1桁の整数iを買うのに円かかるとき、N円以下で作れる最大の数を出力してください。
解法
1. 入力の加工
まずは最終的な数は置いといて、与えられるCを「大きい数ほどコストがかかる」ように最適化したい。見てみると、
i<jかつのとき、整数iは使わない。(iの代わりにjを使った方がいい)
となることがわかる。さらに考察すると、
末項がの最長増加部分列を取り出す
という操作をすればいい。実装的には、「末尾から、『それまでの最小値>現在の値』となった値を取り出す」ことをする。
2. 問題の考察
では本題に入っていこう。制約と入出力例2を見る限り、DPなど値を保持しながらの解法は厳しそう。ここで、整数を買う順番を入れ替えても総出費は変わらないことが自明なので、問題のは無視して良さそう(後で並び替えればいい)。そうなると、答えとして保持するのは「整数iを何個買うか」を保持した配列で十分で、出力するときは配列の各値から大きい順に出力すれば良い。
ここまで、答えをどう生成するかがわかったので、次は「どの数をどれだけ買うか」を考える。
ここで、数字の大小を決定するのは、
- 桁数
- (桁数が同じの場合)桁を上から見た時の各桁の大小
なので、まずはたくさん買うことから始めると良さそう。
(ここからは議論簡略化のため、1.の処理の後1から9全ての整数が使えるとする。)
とはいえ、いくら桁数の多い11111...でも91111...には勝てない。つまり、最初の「桁数が最大のケース」から始めて、最終的には「桁数は変えないままなるべく大きい数を買うケース」に移行させたい。
ここで、91111...が作れる状況で81111...を作ること、一般化すると「ある数Nより大きい数が買える状況でNを買う」という操作は自明に愚行なので、これは貪欲に大きい数から買っていけばいい。
実装は、
- まずは一番小さい(=コストが安い)数aで埋めて桁数を決定
- 処理1で決めた使う数の中で、大きい数から順にaを変えられるだけその数に置き換える
を繰り返していけばいい。
(提出例だと一番最初に「使う数」として整数0コスト0を追加して、実装を楽にしている)
あとは提出で理解してほしい
提出
