ABC174に出たので、考えたことを整理してみる。
スポンサードリンク
こんにちは。ふぁんたです。
2020年8月2日のABC174に参加しました。
どういうふうに考えて、どういった実装をしたのか、
自分の頭の中の整理を兼ねて、書き出してみようと思います。
C – Repsept
問題概要
Kが与えられます。
7,77,777,7777,77777 と7が増えていく数列について、Kの倍数が初めて出てくるのはいつですか？
制約として、\(K \leq 2 \times 10^6\)
考えたこと
・愚直にやってしまうと、すぐにオーバーフローしてしまいそう
→999983の入力例があり、7が90万個続く数字は流石によくないので。
・数列の実装方法は、「前のやつに10かけて７足す」をやればできそう。
・ある数字Aに１０かけて７足した数をKで割ったあまりは、
AをKで割ったあまりに１０かけて７足すのと同じ。
→ なら、7を増やす操作をするたびにKで割った余りを取るようにすれば、捜査する数字がKより大きくなることはない
ということに気づけば、実装ができる。
D – Alter Altar
問題概要
RとWからなる文字列があります。
・RをWにする操作
・WをRにする操作
・好きな文字２つを入れ替える操作
ができます。
「Wの右にRがある」という状態を避ける文字列にするために、最低何回の操作が必要ですか？
\(2 \leq N \leq 2 \times 10^5\)
考えたこと
1.全部Wにすればいい。
2.全部Rにしてもいい。
…このどちらかで、手数が少ない方では？
→という思いを打ち壊してくれたのが、入力例３です。
|
1 2 |
8 WRWWRWRR |
Wは4つ、Rも4つなのに、出力は3。
「入れ替えを上手いこと使えば、全部いっしょの文字にしなくてもいいよ」
ということを言いたいがための入力例なんだと思います。
そこで、左側にR、右側にWを集めてしまえば、「WR」という文字列はなくなるので、
そうなるようにシミュレートすると、この入力例では３になりました。
なので、
1.右からRを探す。左から探している探索範囲に踏み込むか、探索範囲が文字列を超えたら終了。
2.左からWを探す。右から探している探索範囲に踏み込むか、探索範囲が文字列を超えたら終了。
3.両方見つかったら必要な操作数を1足して、その内側から探索をする(1に戻る)
をすればよいな、とわかりました。
ちなみに、Alter Altarという問題名ですが、
Alter…変える者
Altar…祭壇
という意味です。祭壇に供えられた石の色を変えるからですね。
E – logs
問題概要
N本の丸太があります。K回まで切ることができ、その丸太たちの中で最も長いやつの長さを最小にしたいです。
最小で長さはいくつになりますか？
\(丸太の本数 \leq 2 \times 10^5\)
\(切れる回数 \leq 10^9\)
\(初期状態の各丸太の長さ \leq 10^9\)
考えたこと
（間違った判断をしました。）
・切るべき丸太は最も長いやつで確定。
・それを半分にするという操作をしていけば、最小の長さは求まる。
・使うべきはPriority Queueで、実際にシミュレートして答えを出せば良い。
→ 切れる回数Kは\(10^9\)まであるので、絶対に間に合わない。
→ また、半分にするのが最適というわけでもない。その反例は入力例１である。
（ここから正しい判断でした）
・「最大」の丸太を「最小」化する問題 なので、二分探索を使うだろう。
→「全ての丸太の長さをX以下にすることは、カットK回以内でできるか？」という関数で二分探索を行えば良い。
・探索範囲が十分小さくなれば探索を打ち切る。
ただし、「4.9999にはできないけど、5.000001にはできるよ！」といったような場合、愚直にCeilingしてしまうと6を出力する。
→これを避けるため、出力予定の値をFloorした値を突っ込んで、達成できるかどうかを見る。
（この時彼は知る由もなかった この実装が大きくバグり散らかすことになろうとは）
注意点が２つ。
・まず、「切る回数を間違えないこと」。
長さ5の木を、長さ5以下にするために必要なカット回数は0です。
余りを計算しておいて、余りが0ならカット回数を1減らす、としましょう。
・次に、「出力予定の値をFloorした値を突っ込んで、達成できるかどうかを見る」などというその場しのぎの実装はしないようにしましょう。
0.5の長さに出来てしまう入力の場合、「丸太の長さを0にしようとして、割り算で無限大を出しWA」になります。
しないようにしようね！（3敗）
F – Range Set Query
問題概要
N個の玉が並んでいて、左からi番目の色はciです。
Q個の範囲について、その中の色の種類数を教えて下さい。
\(N \leq 5 \times 10^5\)
\(ci \leq N \)
考えたこと
（WAどころか提出すらできていないので、迷走をお楽しみください）
・Queryの問題はSegmentation Treeなんですよ（自信満々）
・セグ木は関数をモノイドにしないといけないので、種類個の大きさのboolの配列を用意して、関数を各要素のORにすればいい。
→結果、bool[50万]を描く要素として持つ配列[524288]を宣言し、手元の環境でもMLEしました。
答えを読むと、「フェンウィックツリー」(New word)というのを使えばいいそうです。これは要復習ですね。
スポンサードリンク