脳log[20230721]

2023年07月21日 (金) [AtCoder] 精進。東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 299）-G「Minimum Permutation」(黄 diff)。愚直解法が作れたら、あとはセグメント木を知っていますかというだけの問題になる。愚直解法とは。M 個の数について末尾の位置を求め、その最小値(もっとも前の位置)を I とする。I とはどういう数か。A 数列のうち I までの範囲からはどんな要素を選んで先頭に配置しても良い。なんなら I 番目を先頭にしても良い。そうしても１から M までの数が欠けることがないので。もちろん最小の要素を選んでこれを答えの先頭の要素とする。以降は選んだ値を取り除き A 数列の範囲を限定して繰り返し、２番目３番目……M 番目の要素を選んでいく。■提出 #43807822 (AC / 757 Byte / 1384 ms)。実装はごくごく素直で難しくない。Ruby によるすべての提出を見ると、セグメント木とヒープを併用するもの、セグメント木と二分探索を併用していて倍速いもの、Array#tally と while ループでゴルフをしているくっそ速いものなどいろいろ。自分のはセグメント木を２つ使っていて一番遅い部類。１つ使ったら２つ使うのも同じだと思ったけど、定数倍の面で最善の選択ではなかったみたい。セグメント木を使わない解法はさっぱりわかんない。セグメント木を使わないで N^2 にならない理由がわからない。■末尾の位置の最小値は最初にソートしておけば Array#shift で更新していける。で、その最前線に向かって増加列を作る。最前線を更新する。増加列を作る。繰り返し。みたいな？■提出 #43911137 (AC / 277 Byte / 278 ms)。そうみたい。Array#tally と、答えの配列(B)と、答えの配列のどこまでが確定しているか(i)と、値から答えの配列の添字を引く逆引きインデックス(I)を使っている。答えの配列の後半の未確定部分に増加列を記録している。最初は配列を２つ使って答えと増加列を保存していたけど、１つの配列でいいなと。そうすれば値の移し替えがいらないなと。最初は増加列の中にすでに同じ値が含まれているかどうかを調べるのに二分探索を使っていたけど、逆引きインデックスがあれば定数時間だなと。tally の使い道はある値が最後に出現する位置を知るためなので、ゴルフをしているのでなければ Array にくらべてオーバーヘッドの大きい Hash を使うことに合理性はない。すでに 213 ms の提出が存在している。■伝わらないことを承知で書くけども、「N^2 にならない理由がわからない」と書いていたときには、増加列を途中までコミットするという操作が欠けていた。どういうことか。各数字の末尾の位置の最前線に到達したときに、必要に迫られて増加列を答えの数列の一部としてコミットする。そのときにコミットした最後の要素の次の位置からまた増加列の作成を開始するなら、それは手戻りであり線形時間の処理では済まなくなる。増加列の前半だけを答えにコミットして後半を残しておくことで、増加列の作成を現在の位置からそのまま継続することができる。手戻りがない。最初はこの手戻りが解決できなくて解けなかった。次にセグメント木を思い出して解けた。しかし NlogN の時間がかかる。途中までコミットするという操作を発見してとうとう線形時間の処理になった。こういう工夫のしがいのある問題好き。たとえば「Simplified Reversi」(20200920p01.03) とか。