2023年05月14日 (日)[AtCoder] 今日は ARC160。配点 400-500-500-(あとは知らん) はゼロ完あるで。参加賞は茶パフォかな。■A 問題「Reverse and Count」。数列を前から見ていく。その値が a であるとする。a より小さい要素が右側に sub 個あるとして、K<sub であるなら、右側にある小さい方から K 番目の要素と a を範囲とする操作が答え。さもなければ、a を含む a より左側の数列の並びをそのまま温存するような操作がいくつあるかを考える。a の左に l 個、右に r 個の要素があるとすると(l+1+r=N)、evn = l+1+r*(r+1)/2 回の操作が a までの数列を固定する。これが K-sub を超えるなら次の要素に処理をまわす。今は a の位置に a より大きい要素を持ってくる操作を考える。a より右にあって a より大きい要素のうち K-sub-evn 番目の要素と a を範囲とする操作が答え。説明しててもわからん。難しいね。提出 #41421021 (AC)。１時間半ちかくかけて 2WA のち AC。■C 問題「Power Up」。これは精進。最初は素朴に A の要素を小さい方から処理するのだと思った。個数を数えて何回の操作が可能か数える。そして次の要素の個数を操作回数分だけ加算する。それではだめなのだな。たとえば現在の要素が a であるとして、最初 n 個あったとする。最大限の操作を駆使して n+c 個まで増やすことができるとする。n+c 個を操作対象にするとき a 以下の要素から成る集合の多様性が最低になる一方、もともとあった n 個の範囲内で操作をしたりしなかったりする場合は、a 未満の要素を対象にした操作にはなんの制限もかからず集合の多様性が最大になる。というのをどうやって管理して数えるのか。提出 #41424512 (AC)。A 問題の AC から１時間後でコンテスト終了からは 30 分後の AC。かかった時間を考えると A 問題の配点は低かったと思う。■B 問題は苦手な苦手な ABC-D の臭いがしたし、ARC の問題ならさらに難しいに決まってるので一瞥だけして飛ばした。正しい判断だったと思う。■■■@2023-05-17 精進。B 問題「Triple Pair」(ぎりぎり水 diff)。動画を見た後でいまさらだけど、x≦y≦z を仮定して並べ替え(６通り３通り３通り１通り)を考えるところまではすぐに考えた。２数の積が N 以下なんだから入力の平方根の範囲で全探索できることもわかる。でもコンテスト終了後にちょっと考えたときは z に関してループを回していた。それは難しくない？■提出 #41484353 (AC / 180 byte / 350 ms)。動画で見た通りに y についてループを回した。普通に ABC-D だったと思う。ただし苦手な苦手な ABC-D ではある。