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 だったり行列のサイズがまちまちになるんだろう。１文字分の冗長さはどこから生じてて、なんでお構いなしで答えが合うんだろう。参照する必要のない６文字前を使って入出力を無駄に細かく分類してもそれが理由で間違えるわけではない。なんなら７文字前８文字前まで利用してさらに細分化しても手間が増えるだけで答えが違ってくるわけではない。ということ？