Si と Sj をこの順に連結した文字列が回文となるようなものが存在するか判定してください。」という問題文の「
Si と Sj をこの順に連結」という文面から勝手に i<j であるかのような雰囲気を感じ取って勘違いしたのだろう。提出 #42900133 (AC)■C 問題「Ideal Sheet」。制約は大きくないから愚直に実装するだけ。その実装がたいへんだった。ビット列でやるとちょっとは楽になるんだけど、本当にちょっとだけ。これもペナルティをくらった。最初は動かせる範囲を総当たりする４重ループを書いていたのだけど、たとえばシート A がシート X の１行目をカバーしないとき、シート B は必ずシート X の１行目をカバーしないといけない。ということはカバーする範囲を１ずつ動かす総当たりではなく、シート X の四隅をカバーする総当たりでいいのではないかというケチな考えが忍び込んできた。これの罠はシート A と B の一方がシート X を完全にカバーするときで、そこまで想定していながら問題があると気付かずに提出して WA を出してしまった。原因に心当たりがあったのですぐに修正できたのが救い。AC まで 36 分(+ペナ５分)。■D 問題「Mismatched Parentheses」。対の括弧に囲まれた部分を省いて出力すればいい。括弧の中の文字列をスタックで管理するとして、括弧の外の文字列を特別扱いしなければいけない。同じようにスタックで扱えるかと考えてみたけどどうも良くなさそう。AC まで６分半。■E 問題「Distinct Adjacent」。前回の ABC306-D ほどあからさまではないけどこれも２値を記録する DP。人１が選んだ数字とそれ以外の数字をそれぞれ選ぶ場合の数を記録していく。人 N の時点で人１が選ばなかった数字を選ぶ場合の数が答え。AC まで９分。■ところで、E 問題に関して Ruby で一番最初の提出であり AC であるこちらの提出 #42909715 には(目に見える)ループがない。N が数えられないくらい大きな数だった場合は自分の DP 解ではダメでこちらをまねしなければいけない。よく見ると mod(=998244353) の他に mod-1(=998244352) が計算に使われている。mod-1 乗ならともかく mod-1 の累乗にどんな使い道があるのか自分は知らない。■F 問題「Virus 2」(黄 diff) は時間内に解けなかったので精進。長めの時間制限４秒が不安をあおる。ダイクストラ法で感染者からの距離を管理して新規感染者を見つけていきたい。どんな下手を打つと TLE になるだろうか。新規感染者が発生した部屋は次の日には感染者からの距離が０になるわけで、最短距離の更新が広範囲に何度も起こる場合に TLE になりそう。できるだけキューを膨らませないようにケチりはしたけど特別なことはせずに 2863 ms で AC になった。01BFS のように一日一日ステップを刻みながらダイクストラ法を進めるのが頭の中がこんがらかって難しかった。つまり、ダイクストラ法を基本にしつつ日を刻み、１日を２つのステップに分けるのだけど、各ステップでやるべきことすべきでないことを見極めるのが難しかった。無駄を許すと TLE になりそうだったのもあるし、迂闊なことをすると２つのステップが連携できなくて機能しなくなるので。■■■C 問題。ケチな考えを追い出して多少の無駄があっても見通しがいいことを第一に書き直してみた>提出 #42960011 (AC / 515 Byte / 78 ms)。515 バイトはタイプするのに長すぎるということはないね。■■■E 問題の mod-1 について。「グラフ彩色 (ja.wikipedia.org)」のページに
(M-1)^N+(M-1)(-1)^N という式が書いてある。mod-1 は単にマイナス１のことだった(それはそう)。Bob が…… K を置くと」。でもそれが見えなかったのだし、実装も 13 行目の
k-sk<=v を最初は k-sk==v と間違えていたので何も言えない。難しい問題だった。.zip().filter_map{}.min を .zip(){} での逐次処理に書き換えたらローカルで５秒になったので提出したら AC だった。案外いけるもんだ。A={Ck1,Ck2,…,Ck∣A∣} となるような k1,k2,…,k∣A∣ をとる」ことが曖昧でなくできることから逆説的に重複する要素がないと判断できる？ ……あった！ 「
i1!=i2 または j1!=j2 ならば Ai1,j1!=Ai2,j2」って書いてある！ とことん読み違える問題だったなあ。
1000000000000000000 0 なのかな。64×64 のうちダメ文字列に対応する行と列を省いたとしても M=0 のケースでは良くならない。それよりも行列のサイズを 32×32 に抑える方が良くなるだろう。32×32 で十分みたいなんだけどわかんない>#42246448。■提出 #42262239 (AC / 769 Byte / 257 ms)。32×32 で足りるというのでとりあえず 32×32 を基本にしてみてダメ文字列の行と列を省いたりもしてみたら１桁早くなった。なんで 64×64 だったり 32×32 だったり行列のサイズがまちまちになるんだろう。１文字分の冗長さはどこから生じてて、なんでお構いなしで答えが合うんだろう。参照する必要のない６文字前を使って入出力を無駄に細かく分類してもそれが理由で間違えるわけではない。なんなら７文字前８文字前まで利用してさらに細分化しても手間が増えるだけで答えが違ってくるわけではない。ということ？(N+2)/5*5 一発で二捨三入できた。切り捨て切り上げを定型で覚えているだけで考えることをしないから無駄なことをする。……というのもちょっと違う。(A+B-1)/B と (A-1)/B+1 がどうして切り上げになるのか過去に考えたことがあるから (A+2)/5 もわかる。ボーダーは動かせる。■B 問題「ABCDEFG」。もっともあほな書き方をしても 42 通りなので好きに書く。累積和を用意するときに要素数が少ないからうっかり暗算しそうになったけど、間違えるから機械にやらせた方がいい。■C 問題「Snuke the Cookie Picker」。人間はなんとなく答えが出せるけどコンピュータに出す具体的な指示は案外難しい。すべての行と列で上端下端左端右端を検出して数が多いものを採用する解答を提出してランタイムエラーを出した。最小ケースを作ってみて気が付いたんだけど、１対１で同数になるので答えが出せない。たとえば上端には最小値、下端には最大値を採用するのが正解。■D 問題「Sleep Log」。方法はいくつかあるのかな。睡眠時間の累積和に適切な座標を割り当てて二分探索ができればいいように思った。でも実装方法(座標圧縮？)が見えなかったのでもうひとつの案。累積睡眠時間を数えながら各クエリの入りと出のときに値を記録した。同時に扱う時刻が睡眠時間とクエリを合わせて３つあって、組み合わせて正しい式を得るのが難しかった。クエリの入りと出の２か所に書いて揃って間違えた。それは提出前に修正できたけどデバッグ出力の消し忘れで All WA をくらった。人間は都合良くデバッグ出力を無視してサンプルの答え合わせができるんよね……。■E 問題「Art Gallery on Graph」。これは簡単。BFS で頂点を訪問するだけ。罠があるとすれば、グラフを勝手に木だと仮定してはいけないということと、何も考えずに BFS を繰り返して値の更新が続くと O(KN) で TLE になる可能性があるということ。プライオリティキューで提出して２秒ぎりぎりで AC だったけど、BFS を(１回だけ)やりながら適時キューに警備員が立っている頂点を追加するようにするともっと余裕があった。ここでは出力形式を間違えてまた All WA をくらった。■F 問題「Dungeon Explore」。制約からもこちらに許された操作からもグラフをしらみつぶしに訪問するような探索が書ければいいとわかる。隣の頂点にしか移動できないから探索は BFS ではなく DFS。あとは E 問題と似た文面が見えることからわかるように、勝手にグラフが木だと想定しないようにだけ注意。なんでこういう注意が必要かというと、「木ではない木ではない」と唱えていないと勝手に木を想定したコードを手が書いてしまうからだ。E と F が似たようなグラフの問題でどちらも軽い問題だったから、F 問題を提出した後で F 問題を開いて解こうとして混乱したよね。■最近また落ち目だったからか解けるものを(序盤でそれなりに苦戦しながら)解いただけでレートが上がったのは微妙な気持ち。コンテスト成績証。■■■@2023-06-15 F 問題。自分の提出 #42157034 は 10 行目と 11 行目がやばく見える。10 行目は隣接頂点リスト全体を走査しているし、11 行目は隣接頂点リストがソート済みだということを無視して、頂点 N を目指しているというのに最も小さい頂点番号から順に訪れようとしている。10 行目は「DFSを非再帰に書き換えるとTLEするようになったという心霊現象」について 20221125 に書いたまずい書き換えの例と同種のミスだ。たとえば入力が頂点１を中心とするスターグラフで、頂点 N だけが頂点１から距離２の位置にあるとしよう。長さが N に近い頂点１の隣接頂点リストを N 回近くスキャンするのは O(N^2) でいかにもまずい。だけど実際には問題にならないだろうということも予想できて、当日は解答を作成しながら制約を再確認したりしていた。つまり、提出コードがどういう形で書いてあるにせよ、頂点１の隣接頂点リストを N 回近く標準入力から読み込むことは最悪の場合に避けられないのであり、それでも TLE にならないような制約が書かれていないかを確認していた。なかった。でも実際にはまずい解答でも問題が起こらないような入力だったので AC だった。まずい書き方をしたけど実際にはまずくなかったのだという話。■……でもないのかな？ 日記に「(そんな制約は)なかった」と書くに際してまた問題文を読んだけど、これまで見たことがない「
この問題のジャッジはアダプティブです。つまり、制約および以前の出力に矛盾しない範囲でグラフの形が変わる場合があります。」という注意点に気が付いたよ(今です！)。入力が頂点１を中心とする完全なスターグラフだったときに自分のまずい提出は(アダプティブに)救済されようもなく TLE していただろう(一番最初の入力で頂点 N への辺が示されているから)。あまりにも間抜けすぎるのでそんなうっかり提出を弾くためのケースを用意しようとは考えなかったのかな。あぶなかったね！