C問題 Third Largest Number
渡される数列Aを前（0からNまでのi）から少しずつ読み込む形で降順に並べ替えた時の3番目を出力しろ、という問題。
解説
問題文の通り素朴に並べ替えを行うと計算量がO(n2)となり間に合いません。
そこで先頭の要素3つのみを保持するように配列を用意すれば楽です。
計算量について、並び替えはO(n)、末尾の削除はO(1)。並び替えの計算量は理論上ではO(n)ですが、実装上は要素が3つのみなので実質的に定数になります。残るのは少しずつ読み込む処理だけ、というわけで全体の計算量はO(n)になり、間に合います。
疑似コード（公式解説寄り）
疑似コード（折り畳み）
// 標準入力は省略。
先頭から3番目までの要素を抜き出した変数bを用意する
bを降順で並び替え
bの3番目を出力する
for (iを2から始めてnまで繰り返す)
{
aのi番目をbに追加
bを降順で並び替え
bの末尾を削除
bの3番目を出力する
}
ACコード
こちらはConsole.WriteLine()を書く場所と並び替えをそれぞれ1行にしたいが故にif文で1通りしかない場合分けなどをしていますが、普通に疑似コードそのままの実装が簡潔だと思います。行数的には大差ないです。
D問題 Automat
N個あるデザートの配列AとM個あるドリンクの配列Bがあります。
デザート販売機には1ドル紙幣とKドル紙幣が使えるが、ドリンク販売機にはKドル紙幣しか使えません。お釣りはどちらも1ドル紙幣で返ってきます。1度に複数の商品は買えません。
X枚ある1ドル紙幣とY枚あるKドル紙幣を使ってデザートとドリンクを買う個数を最大化できるか、という問題。
答え自体は最大でもN+Mに収まるためint型でも充分ですが、途中の計算式でint型の最大値を超えるためlong型で計算しないとオーバーフローによりWAになります。long=int+intの計算式にならないように注意。これだとオーバーフローした計算結果がlong型の変数に代入されます。
解説
買う個数を最大化するのであれば価格の小さいものから買っていきたい。ので、AとBは昇順に並んでいた方がよいです。個数を最大化という点が重要で、全体でX+Y*Kの予算内に収める必要があるため、この時点で買える数と買えない数の境界が分かりそうな二分探索が使えそうです。
あとはどちらを優先して買うかを計画したいところ。ドリンクを買う場合にKドル紙幣しか使えないことから、ドリンクをいくつか買ってからデザートを買う方針であれば余すことなく消費できそうです。
ドリンクの購入数が分かれば、残り1ドル紙幣は以下で計算できることも分かります。
// ドリンクの購入数が分かればデザートに使える1ドル紙幣をこのように計算できる。
sx = X + 残ったKドル紙幣Y枚 * K + 消費したKドル紙幣Y枚 - Bの0から購入数iまでの和デザートに使える残りの1ドル紙幣sxが分かれば、Aの累積和に二分探索を使い、返ってきたi1がそのままデザートの購入数になります。
Bの購入数もループの中で処理してもいいですが、Bの累積和も作った方が処理の流れが掴みやすくなります。購入数がAに対するi、Bに対するjになり、全体の購入数つまり答えがi+jと定まるので。ついでに0個買うケースもカバーできます。
これによって解法の流れは「Bを全探索し、Aを二分探索する」になり、その下準備としてAとBの累積和が必要になるのは説明した通りですが、もう一つ準備すると便利な変数があります。
お釣りの計算で、元々Y枚あるKドル紙幣がBの累積和に対して何枚必要になるか、その時点で何枚残るのか。全探索の中で都度処理するのは面倒です。
というわけで、Bの要素それぞれについて必要になるKドル紙幣の枚数BKの累積和を作ります。これで累積和も計3つ作るのでメソッド化してもいいですね。
割り算で切り上げながら変数BKに格納して、それを累積和を作るメソッドに渡すのが良いと思います。BKを作らずにB.Select().ToArray()を累積和を作るメソッドに渡すこともできます。
ここまでの下準備ができれば、あとは探索方針に沿って実装すればいいはずです。必要なものは揃っています。
公式解説の実装例の金額の計算式について
先ほど例に挙げた素朴なお釣りの計算式、合ってはいるのですが、お釣りは1ドル紙幣で返ってくるので全体の予算からすれば減るのは実質的にBの購入に必要な額のみです。
であればBを固定する（＝Bを全探索する）以上はわざわざお釣りの計算をせずとも「Bを何個買うか」でAを買うための予算が計算できます。
公式解説の実装例では、以上のことからj個のBが購入できることを判別するのに、「全体の予算に対するaccB[j]が足りていること＝sxが0以上であること」と「Bの購入に必要なKドル紙幣の枚数が足りていること＝syが0以上であること」が同時に真であればよい、という整理が行われています。
Bを全探索するにあたって、j個のBが買えることが真であるには、全体の予算からBの累積和のj番目を引けば、残りはすべてAを買う予算になります。
これだけではまだ間違っているので、そこから偽となる条件を除外します。Kドル紙幣でしか買えないという整合性を取るべく、Bのjに対しKドル紙幣が何枚必要かの累積和accBKがあれば、Bの購入数jがそのままKドル紙幣が何枚必要かを取得するのに使え、y-accBK[j]で残りのKドル紙幣syが何枚残るかも判別できます。
i個のAを買う予算はsxが0を下回らなければ、Aの購入に回せます2し、syが0を下回らなければj個のBが買えたことを表せます。
疑似コード（素朴なお釣り計算）
疑似コード（折り畳み）
// 標準入力は省略
引数に整数の配列を取り累積和を返すメソッド()
二分探索のメソッドを置く()
Aの累積和accAを作る
Bの累積和accBを作る
Bの要素それぞれについて必要なKドル紙幣の枚数を表す配列BKに変換
BYの累積和accBKを作る
// B.Select(h => h/kの整数切り上げ).ToArray();を累積和を返すメソッドに渡す方法も使える。
変数ansを宣言
for (i = 0; Bの累積和の長さ)
{
残りのKドル紙幣の枚数syを計算
if (syが0未満なら) break;
残りの1ドル紙幣の枚数sxを計算
j = accAをsxで二分探索
ans= ans,i+jのmaxを代入
}
ansを出力疑似コード（公式解説）
疑似コード（折り畳み）
// 標準入力は省略
引数に整数の配列を取り累積和を返すメソッド()
二分探索のメソッド()
Aの累積和accAを作る
Bの累積和accBを作る
Bの要素それぞれについて必要なKドル紙幣の枚数を表す配列BKに変換
BYの累積和accBKを作る
// B.Select(h => h/kの整数切り上げ).ToArray();を累積和を返すメソッドに渡す方法も使える。
変数ansを宣言
for (i = 0; Bの累積和の長さ)
{
全体の予算からaccBK[i]を引いてsxとする
残りのKドル紙幣の枚数syを計算
if (sxが0未満 || syが0未満) break;
j = accAをsxで二分探索
ans = (ans, i+j)の最大を代入
}
ansを出力ACコード
感想
C問題まではスムーズだったが、D問題で1時間悩んでも解法が分からずコンテスト終了。動的計画法？貪欲法？どれも違いそう……とか考えてた。
その後も価格の計算式で色々躓く。Y枚のKドル紙幣が本当に足りているか素朴にループの中で都度計算して処理しようなどと頭の中で考えるのに拘ったせいかほとんど手が動かなかった。Upsolveできないかと思ったぜ。
落ち着いてやれば解けるはずなんだ……頼むよ未来の自分。
コメント