最終更新: 2024-01-18T16:02+0900
AtCoder の問題ではないが精進。ABCE の４問。
基本的にはカードを順番にスキャンして判断をする。ハッシュ表を使って自分が一番小さいカードである場合、２番目、３番目の場合の３パターンについてカードが３枚揃っているかを確かめる。もしくは、昇順にソートして自分が一番大きいカードであるケースについてカードが揃っているかを確かめる。
N 個の商品がありそれぞれの商品は M 種類の商品カテゴリのどれかに属している。M 日間のセールがあり、セール期間のある一日にはあるひとつのカテゴリの商品が半額になる。Q 人の客がそれぞれある日に訪れ、ある範囲の連続する商品を購入する。さていくら？ Q 個答えよ。
割引がなければ範囲の総和を知るのに累積和を引くだけ。しかしある日にはあるカテゴリの商品が半額になっているので、範囲内にそのカテゴリの商品がいくつあるか知りたい。カテゴリごとに位置を昇順に記録して二分探索をした。
カテゴリごとに累積和を用意しようとすると最悪の場合長さ N の配列が M 個になって、N×M は大きすぎる。更新のあったところだけ記録しようとすると、さっき書いた「カテゴリごとに位置を昇順に記録」する方法になる。
難しいね。いっぱい間違えた。制限時間が１秒とやや厳しめ。
３の倍数の長さ(0,3,6,9,...)の範囲を切り取ってみれば、左端の位置と右端の位置、それと RGBRGB...RGB 文字列との不一致の数からコストがわかる。不一致を単位時間で数えるためには３種類の累積和を用意しておけばいい。すなわち、RGB...RGB..、BRG...BRG..、GBR...GBR.. 文字列と S との不一致を数えた３種類。
ところで、N の上限が 20 万のときに範囲の両端を自由に選ぶと 20 万の２乗(割る２くらい)で間に合いませんね。範囲の左端を総当たりすることにして最善の右端をどうやって決めるかというところで３回 WA を出した。
最初の提出 #48448208 では左端を右に移動するごとに右端を左右に移動させてみる尺取りをした。特定の制約を追加したサブタスクはクリアしたが、N の制約を甘くしただけのサブタスクで一定割合の WA がある。時間は間に合っていて(局地的に)最適な答えを見つけることもできているが、最善の答えをときどき見逃しているということ。
次の提出 #48453131 は不等号にイコールを追加するような微修正で、３割くらい WA の数は減ったけど本質的な誤りは修正されていない。
３番目の提出 #48453143 は３つのサブタスクで２つずつ WA があるという結果で、ほぼ AC と同じ。実はこれまでの２つの提出ではケアしていた、左右どちらかから全ての文字列を削除するケースに対応したコードを削った結果 WA を生んでしまっている。正しい解法を見つけたときにもういらない気がしたんだよなあ。
これが AC。右端を見つけるのにスライド最小値(？)だと思うものを使った。実装はしなかったけど三分探索も検討していた。知っている解法を総当たりして正当性の判断をジャッジに委ねるのはやめようね。
時間に依存したコストをどう扱うか。t=0 となる位置を１から N へのパスの中のどこに置くかでコストが変わる。パスの外に置いても得をしないので考えない。どこに置くのが最善で、どうすれば最善が見つけられるか。
t=0 となる地点をあるパスの中のある辺に置くとする。１がある方のパスに A 個の頂点が、N がある方のパスに B 個の頂点があるとして、A<B なら t=0 の地点を辺上で N の方に近づけるのが良い。A=B なら辺上のどこにあっても同じ。なので、t=0 の地点をどこかの頂点から選んで良い。
t=0 となる頂点を決め打って、１からの最小コストと、N までの最小コストが求まれば良い。１からは順方向に探索し、N からは逆方向に探索すれば、２回の手間で答えが求まる。N 頂点全てを始点にして N 回の探索をすることは時間的に許されない。
提出日の開きを見るとわかるけど、この AC はほぼ一週間がかりだった。
探索は BFS。移動コストが固定値の C と、パスに含まれる頂点数に比例する L×K なので、BFS によって頂点数が単調増加だと想定できると、単純にコストの総和を比較するだけで最短経路が見つけられるし、頂点数に比例したコスト計算もやりやすい。
サンプルの４、５、６あたりの答えがいつまでも合わなくて、ああでもないこうでもないと試行錯誤していた。さっぱり見えていなかったのは AC 提出の 22 行目、頂点 N までのコストを探索する D 関数に与える初期値(DN = D[ヨ[N].group_by{|s,|s}.map{|s,stcs| [s,stcs.map{_3}.min] }.to_h,ヨ])。１からのコストを求める 21 行目(D1 = D[{1=>0},E])と比較すると長さだけ見ても段違いなのがわかる。この違いがさささっと把握できる人はすごすぎると思います。
N から逆向きにコストを計算するのに N の隣接頂点を始点にすればいいとはなかなか……全然わからない。そこにやっと気がついても N とその隣接頂点 V を端点とする辺が複数あるということがまた思い出せない。
たいへんだった。これ予選なんですって。
今３ページくらい E 問題の AC 提出があるんだけど、Ruby の 113 ms が最速だった。おもしろ。ただ、前回の言語アップデートから AtCoder のジャッジは、言語ごとに最初の１ケースだけウォームアップ時間が計測に含まれるみたいな雰囲気があるので(このときの話の関連>20230807)、ワースト１ケースのタイムが特異例である場合の比較に意味はない。
こちらの提出 #48433529 を見ると N×M のループを順方向と逆方向の２回回してるだけに見える。辺を端点ごとにまとめたりもしていない。どういうことなの？ 結局 L[j]*K に (i+1) を掛けるか i を掛けるかというだけの違いだったの？ そうみたい。
頂点数を１減らしてコスト計算する試みはけっこう初期にやっていて、でもたぶん他の部分のバグのせいで答えが合うところまでいかなかった。AC コードがある今同じ方針でやってみるとふつーに、よりシンプルに、答えが出た。なんだよもー。さっき書いた 21、22 行目だけど、こうなった。
D1 = D[1,1,E] DN = D[N,0,ヨ]
そう、これくらい単純に順方向と逆方向の探索ができると思っていたし、実際できるのに、どうして１週間も沼にはまりこむ結果になったのか、謎だ……。
split(/0+/) した結果の 12 文字列について考えた。１の数を c1、２の数を c2 として、[c2,c1-M].max の max を答えにしたら WA だった。たぶん c2+[c1-M,0].max の max を答えにすべきだった。今以て確信はもてない。２パスの別方針の解答をでっちあげたらそちらはミスがなかったらしくそれで AC をとったので。■D 問題「Swapping Puzzle」。制約が５以下とささやかなので階乗の２乗に２乗を掛けても大丈夫。たぶん賢く操作を構成しようとすると、同じ値を持つマスの扱いが問題になりやすいと思う。すべての並べ替えを列挙して盤面が一致しているかを確かめるのが確実。■E 問題「Lucky bag」。解けてないよ。15 15／1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 という入力に対して３秒弱かかるのでは TLE が避けられない。勘違いする人がいるみたいだけど、３秒弱っていうのはコードテストで 2778 ms (＜３秒) かかったって意味だよ。俺は勘違いしてないよ。■F 問題「Random Update Query」。区間適用のセグメント木の香りがします。もっとも、仮にそれが手持ちの道具箱に入っていたとしても関数の合成が書けたわけではない。どこかで読んだけど、Ax+B の A と B を覚えておくだけで合成できたのかな。Array#count■B 問題「Minimize Abs 1」。問題文が難しすぎる。数分かけてじっくり根気よく投げ出しそうになる気持ちを抑えながら理解する必要があった。要するに、ある範囲(L-R)に含まれる整数のうち最も A[i] に近い数を、A[1] から A[N] について答えよ、という問題だった。ループと配列はいらなかった。繰り返しなしでも十分に B 問題だったのに、ループがさらにややこしくしていた。答えの候補は {L,R,A[i]} に限られるんだけど、謎に {L,R,A[i]-1,A[i]+1} を候補にしてペナルティ５分。根気が尽きていた。■C 問題「Minimize Abs 2」。平方数を２つ足してある数 D にどれだけ近づけられますかという問題。図形的な意味があるかは知らない。大きくなりすぎない範囲の平方数を列挙して調べた。■D 問題「Counting Ls」。ちょっと方針に迷った。グリッドをスキャンしながら２種類の累積和を更新しつつ数えていけるかと思ったけど、欲しい数が足りていないことに気がついて頓挫した。正解方針はこう。最初にある行またはある列にある o の数を数えておく。その後もういちどグリッドをスキャンして、ある点が L 字の角にあたる場合の数を数えて足し合わせて答えにする。ところで、@kyopro_friends さんは頓挫せずに解ききってしまったようですよ。「フェネック「アライさんは最初このことに気づかずに、L字を置く向きを4通り試す実装をしてるんだけどねー」 アライグマ「そのことは秘密なのだ！」」■E 問題「Mex and Update」。デバッグ時間が１分14秒足りなかったせいでこれは精進です。こいつ先々週も似たようなこと言ってたな(「なんてことのない F 問題を通すのに２分６秒ぽっち足りなかったのがくやしい」)。セグメント木を使って該当する数のうち最も小さいものを探す。値の上限が 10^9 だということで座圧したのだけど、そのせいでバグらせたケースが 3 1／0 2／1 0 みたいなの。クエリでは数列を書き換えていないので {0,2} の MEX である１が答えなのだけど、座圧しているせいで１番小さい値(0)と２番目に小さい値(2)のあいだに隙間があることに気付けなかった。+1 した値を加えておおよそ２倍の数の数字を扱うことで AC になったのだけど、バグの原因を見つけるのに手間取って時間が過ぎてしまっていた。Ruby での他の提出より倍くらい遅いみたいだから、もう少しスマートな解決法があるかも。■F 問題「Minimize Bounding Square」。終了後に問題を読んで、根を詰めずに休み休み考えてだいたい１時間とちょっとで AC になった。時間内に解けた可能性はゼロなので悔しさはなく解けた喜びだけがある。まず X 座標と Y 座標に問題を分ける。X 座標(Y 座標)の幅をどれだけ狭められるかは左からの累積和と右からの累積和でわかる。Sandwiches (20230902) と同じ要領で、座標の和と個数から操作回数が求まる。ところで、全部でいくつ狭めるかが決まっているときに、右からいくつ狭めるかと左からいくつ狭めるかは貪欲にステップを刻んで決めることができない。１狭めるだけなら左から狭めた方が得なケースでも、３狭めるときにはすべて右から狭めた方が良くなるケースというものが考えられる(※)。N≦20万なので答えを二分探索する中で線形時間のスキャンをしても大丈夫。２秒を 67 ms 超えたけど(#47948117)、制限時間が３秒だったのでセーフ。■Twitter の成れの果ての何かを眺めているとギリギリで E が通っていても緑パフォだったらしいとわかる。じゃあなんにも惜しくねーな。そのラインは伸るか反るかの最前線よりずっと下だ。■F 問題についてすごいツイートを見かけた。「FのC++の最短コードを見てる atcoder.jp/contests/abc33… X/Y座標を長さLの中に包含させる最小の操作回数は外側から順にペアを作ったときに max(ペアの長さ-L,0)の総和になる ってことだと思うけど頭いい」。なんでそれが答えになるのか全然わかんない。■※ 嘘を書いていたっぽい。貪欲に狭めて良い……らしい。「アライグマ「いま左右の端にある点のうち少ない方を全部1個となりに詰めるのが最適なのだ。ということは答えの関数は、こういう感じの折れ線になるのだ。元の2次元の問題なら、x方向とy方向で解いて足せばいいのだ！」」。考慮してその結論が間違ってるなら何を頼りにして答えが導き出せるというのだ。■■■E 問題。座圧したときの値の抜けは落とし穴というよりも答えへのショートカットだ。A 数列に存在せずクエリで設定されることもない値は常に MEX として選ばれる可能性がある。そういう値の最小値が答えの上限になる。問題に対する総合的な理解が足りていないから見落としてバグらせる。提出 #47966425 (AC / 1211 Byte / 642 ms)。BIT で MEX 候補の上限までを座圧なしで管理したら 1973 ms だったのが 642 ms まで早くなった。■F 問題。ゴルファーの理解できない解法はさておき貪欲に四辺を内へ寄せる解法を実装してみた。提出 #47975884 (AC / 976 Byte / 642 ms)。2067 ms だったのが 642 ms まで縮んだ。クラスを使ってコードの重複をできる限り省いたつもりだけど、それでもかなーり面倒くさい実装になっている。/(.)\1*/ みたいな正規表現パターンでうまくできないかとあれこれ考えて、できなかった。同じ文字の繰り返しを意味するパターンって難しくない？ キャプチャを使うとできるけどそうすると String#scan メソッドが役立たずになるので困ってしまった。■D 問題「Election Quick Report」。D 問題で BIT とかプライオリティキューとか使いたくないよね。考えました。最高得票者が入れ替わる瞬間がつかまえられさえすればいいので、誰が最高得票者で得票がいくつかがわかればそれでいい。■E 問題は解けなかったのでひとまずとばして F 問題「Colored Ball」。ただのマージテク。考える時間も書く時間もいらない。E 問題を考えていたせいで F 問題の AC が 30 分近く遅れたのを挽回するためには、最終的に E 問題も通すほかなかったんだけど、結果はあのとおり。残念無念。■■■E 問題「Stamp」。難しかったよね。時間内のこの提出 #47726211 (WA×5) だけど、19 行目が嘘貪欲なのはわかっていて、でも残り数分で新しい方針をでっちあげることもそれを実装することもできない。昨日はもうお手上げだった(あ、この日記は翌日に書いています)。■提出 #47752502 (AC / 515 Byte / 393 ms)。これは翌日の今日なんとなく転がしていたアイディアを実装したもの。貪欲なのは同じ。違うのは起点が複数あること。昨日は左右端を起点にしてスタンプを上から押したり下に差し込んだりする操作を考えていた。今日は T と完全一致するすべての場所を起点にして、そこから(端でなければ)左右にスタンプを繰り返し差し込む操作を考えた。操作の起点を複数考えることでスタンプを上から押す操作を考えなくて済んだのが昨日との違い。複数の可能性を考えなくてよくなり貪欲法がはまるようになった。最終行の判定がやや複雑で条件が３つある。両端の条件に２つで、貪欲法と貪欲法の狭間に残る部分の判定に１つ。■たしかに D 問題とのあいだで配点はひらいているけども、これを E 問題に配置しようって判断が、それもあの F 問題の前に配置しようって判断が謎すぎる。でも考えるのが楽しい問題だった。知識問題というよりのーみそこねこね(コンパイル)な問題だったのでは。