こんにちは。ふぁんたです。



2020年8月2日のABC174に参加しました。



どういうふうに考えて、どういった実装をしたのか、

自分の頭の中の整理を兼ねて、書き出してみようと思います。

---

C - Repsept

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

D - Alter Altar

問題概要

RとWからなる文字列があります。





・RをWにする操作

・WをRにする操作

・好きな文字２つを入れ替える操作

ができます。





「Wの右にRがある」という状態を避ける文字列にするために、最低何回の操作が必要ですか？

\\(2 \\leq N \\leq 2 \\times 10^5\\)

考えたこと

1.全部Wにすればいい。



2.全部Rにしてもいい。



…このどちらかで、手数が少ない方では？





→という思いを打ち壊してくれたのが、入力例３です。

8

WRWWRWRR

Wは4つ、Rも4つなのに、出力は3。



「入れ替えを上手いこと使えば、全部いっしょの文字にしなくてもいいよ」

ということを言いたいがための入力例なんだと思います。





そこで、左側にR、右側にWを集めてしまえば、「WR」という文字列はなくなるので、

そうなるようにシミュレートすると、この入力例では３になりました。





なので、



1.右からRを探す。左から探している探索範囲に踏み込むか、探索範囲が文字列を超えたら終了。



2.左からWを探す。右から探している探索範囲に踏み込むか、探索範囲が文字列を超えたら終了。



3.両方見つかったら必要な操作数を1足して、その内側から探索をする(1に戻る)





をすればよいな、とわかりました。









ちなみに、Alter Altarという問題名ですが、



Alter…変える者

Altar…祭壇



という意味です。祭壇に供えられた石の色を変えるからですね。

E - logs

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

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)というのを使えばいいそうです。これは要復習ですね。