久しぶりにやったよ。２年ぶりくらいかなー。この間様々なことがあったw
競プロの問題はコンテストやってないときも時々解いてはいたんだけど、 コンテストの日にちに合わせてやろうってなかなかならなかった。 ただ最近は暇もできたのか、気がついたら競プロをはじめていて、コンテストにも参加していた。
今回はABCDEの 5 完でした。 F 問題が強実装で実装しきれなかったんす。方針は合ってたんだけどね。 コンテスト後ACしたよ。 あとめちゃくちゃ疲れたｗこんな疲労感あること毎週やってたのか俺はw
解説とかも見てみたけど、早くやる方法あるのかなこれー。 自分のやり方は、頭文字が全員違うのを使って、配列にレートを対応させる、位のことしか思いつかんかった。
あー、そういや $0$ ってすべての倍数になりうるのか。 言われたとおりに実装をするだけではあるんだけど、ちょっと読み込みづらくて、時間がかかっちゃった。
やり方は、全探索してがっかりしなかったやつを全体から割ればいい。 ただ、なんといっても、実装が面倒くさいｗ 実装例を見てみたけど、実際にシミュレーションするより、順序だけ確かめるという方法もあるみたい。
ウィンドウサイズで二分探索。ただ $W$ の大きさに注意。$2 \times 10^{14}$ くらい必要なのかな？
あとはシミュレーションを頑張る。ちょっと空白の処理が怖い。 ただ、A, B, C と解いてると、素直な問題で嬉しくなる。
$ 1 \leq P_i \leq 8 $ がやはり大事。 時間 $0$ のときはすべてのバス停からバスが出発するわけだけれど、 その $\mathrm{lcm}(1, 2, 3, 4, 5, 6, 7, 8) = 840$ だけ時間がかかったあともまたすべてのバス停からバスが出発する。
ということは、$840$ だけ経つとまた同じバス停の動き方を始めるから、時刻 $q_i$ からのバス停の動きは、 時刻 $q_i \mathrm{mod} 840$ と同じになる。
そうなると、時刻 $0$ から $839$ までの間のシミュレーションだけ予めしておいて、 クエリが来たら $\mathrm{mod} 840$ して計算すればいいので $840 \times N$ くらいの計算量になって、 ぎりぎり間に合う。結構怖い。
この問題は薬の持ち方のbitDPで、$dp_{bit}$ ... 薬を $bit$ とったときにその状態で倒せる敵を倒したときの強さの最大値 というのを持っておけばいい。
DPの強さの値によって遷移自体が変わってくるけど、強ければ強いほど、遷移が単調に有利になるので、 強い値を入れておくことに越したことがないのでDPができる。のだろう。
DPの仕様自体は簡単だけど、じゃあ、ある薬をとったときに、敵を倒して増える強さがどのくらいかとかを うまく調べる必要があって、その実装がかなり辛い。 まず薬を取る前までにどこまで行けるのかをしらべて、そこから薬をとって、実際に強化していくというフェーズ。 まずどこまで行けるのかを幅優先で調べる。条件分岐がかなり嫌だ。 強化していくフェーズでは弱い敵から倒すように、priority_queueで優先させて探索。 重実装を２回も書いてなんとかACした。やだああああ・・・
こんなに重いの!?って思ったことで、自分の解法を疑って、G問題を見始めるという時間があったから、 必死に書いてたらコンテスト内でACしてたかもーなんてちょっと・・・ｗ まあ場数ですな。
G 問題はまだちゃんと見てないし考えてないので解法を見ようとは思わない。あとから解こう。
一応パフォーマンスとかも見てみたけど、2037でレートが上がってた。 あれ、意外だったなと思った。今回は割と死んでたんじゃないかなーとおもってたんだけど。 意外に黄色になるのも早いかもね。まあ色を目的にすると辛くなるので気にしないようにはしようと思ってるけど。
最近はDiff水色あたりの問題を昔解いた問題も合わせて解いてみているんす。 面白いことに問題を何も覚えてないんすねｗうろ覚えもあるけど。 でも結構面白い。程よく難しくて良い。
(2023/09/10 01:39)