/ 最近 .rdf 追記 編集 設定 本棚

脳log[20220815]



2022年08月15日 (月) [AtCoder] 精進。AGC058-A「Make it Zigzag」(緑 diff)。■最初は長さ 2N のソート済み数列を前半後半に分けて交互にファスナー状に配置したらジグザグになるじゃないかと考えた。たとえば N=3 のとき、作る数列を 1,4,2,5,3,6 と決め打つということ。交換回数は転倒数でわかる。提出前に気がついたんだけど、解答に「以下の操作を 0 回以上 N 回以下行うことができます」という制約が付いていた。一応ね、実装前にざっと制約を探しはしていた。でも制約セクションには入力の制約は書いてあっても出力の制約は書かれていなかったのだな。転倒数の総和の最大値はたぶん入力となる数列が逆順にソートされている場合で、0 から 2N-1 の範囲の和(=N(2N-1))になるから、入力次第で操作回数が N を超える。■次に考えたのは、入力の先頭を出力の先頭にとりあえず配置して、次に配置する要素を、出力の末尾との比較によって入力の前の方から貪欲に引っぱってくる方法。考えなければいけないのは、出力の末尾より大きい(小さい)要素が入力の中に残っていないときにどうやってジグザグを維持するか。たとえば出力の末尾2要素が O1,O2 で入力の残りが I1,I2,I3 のときに大小関係が O1<O2<I1<I2<I3 だったら、O2 より小さい要素を入力から選んでジグザグを作ることができない。解決するのは簡単で、入力の先頭を出力の末尾の1つ手前に挿入すればジグザグになる。O1 との大小関係も大丈夫。I1 が O1 より小さいせいでジグザグが壊れるならそもそも苦労していない。この解法のネックも操作回数で、2N の入力のそれぞれに対して 0 回から複数回の操作が必要になる。ランダム入力では N=100000 に対して 180000 回くらいの操作が必要になった。■次に思いついたのは(考えたって書くのやめちゃった)、さっきの解法の例で出した O1,O2,I1,I2,I3 の中で、O2,I1,I2 の大小関係にだけ注目してジグザグが作れるんじゃないかということ。3つの大小関係がどうであれ0回か1回のスワップで山ないしは谷が作れる。(O2 がスワップ対象だけど)スワップによる既成出力への影響はどうか。スワップが必要なのは真ん中の要素が山なら極大値、谷なら極小値になっていなければいけないのにそうではなかったときだから、山を作るためにスワップされたどちらかの端の要素はそれまでより小さくなり、逆に谷を作るためのスワップでは端の要素が大きくなる。山になる要素の隣は谷になるべき要素だから、スワップで小さくなってもジグザグは維持される。谷を作る場合も同じ。■提出 #34071956 (AC / 331 Byte / 212 ms)。N 回のループの各回で1回以下のスワップだから交換回数も大丈夫。精進だからこそトントントンと AC までステップが踏めたんだろうなあ。2番目のトンがなければ AC につながる3歩目のトンはなかったし、次の一歩が出てこないことも2歩目があさっての方向に向いていることもよくあることなので、5割以上の確率で0完になる AGC はリスキーすぎる。緑だったときにレート変動対象から外れて以来不参加だよ。■■■B 問題「Adjacent Chmax」は小さい P から順番に DP かなと思ったけど、何を記録するのかが(実装を始めても)はっきりせず。