134. AtCoder参加記録（AtCoder Regular Contest 147）

37回参加でレート 1369 です。

今回はパフォーマンス 1319 です。

ABを通して、CDEFは未解答です。Aで2ペナ、Bで1ペナ。

各問題の思考過程など。

A

問題

初回提出9分47秒、そこから2回目提出4分20秒、Bから戻ってACまで18分59秒。

1. 操作回数は一定らしいので愚直にシミュレートすればよさそう。
2. 最大値・最小値を取り出しつつリストを更新したいので、MultiSetを使ってみる → 2ケースTLE
3. 計算量的にはたぶん間に合っているので定数倍っぽい。PriorityQueue でも解けるしこっちの方が軽いので、こちらにしてみる → 最終ケースのみTLE（意地悪…）
4. これで間に合わないなら何らかの数学的性質を使う？ユークリッド互除法的な操作だとは思うけど、どうしたらいいのか分からない…Bへ移る。
5. Bから戻ってきて改めて紙上で操作してみると、1回の操作で計算後の値は必ず次の最小値になると気付く。
6. 昇順にリストが並ぶと考えれば先頭・末尾のみ操作する形になるので、Deque が使える。対数時間が定数時間に落ちるので、これで通らないか賭けてみる。普通に通って唖然…。

C++だと 2. の解法で通ったらしい……

ACコード

B

問題

Aを諦めてから初回提出21分21秒、そこからACまで16分27秒。

1. 操作回数には十分余裕がありそうなので、この制約は無いものとして考える
2. 各要素について正しい位置のインデックスと偶奇が一致していない場合は操作Aを行う必要がある。1の場所から順に見て、偶奇が一致していなければ操作Aを1度行ってから、あとは操作Bで正しい場所へ持っていく → 大半WA
3. 少し考えると、 のようなケースでうまくいかないことが分かった。このケースは と について操作Aが必要だが、本来は1度で済むところが 2. のアルゴリズムだと2度以上行ってしまう。これは、偶奇の一致してない要素が隣り合っていないため上手く行ってない。
4. 偶奇が一致してない場所は必ず偶数箇所あるので、一致してない要素を全部先頭側へ（操作Bで）持っていき、操作Aを奇数番目に対して順に行い偶奇を一致させた後、操作Bで正しい場所へ持っていけばよい。

ACコード 

C, D, E

それぞれ10分ほど考えたが、解決の糸口になりそうなものは何も浮かばず。

F

見てないです。

A、なんとなくC++だと通る解法なのでは…と思っていましたが、案の定で…割と萎えました。

最近仕事が忙しくあまり問題を解いていなかったので、レートが下がるのは甘んじて受け入れ、来週また頑張ります。