1*/2* を拾い出してからスラッシュの位置を探して計算した。なんでか 10 分かかっている。■D 問題 1122 Substring。やることが多いよね。まずペアの列を複数切り出したんだけど、同じ値が３つ以上連続している場合に注意が必要。その部分でペアの列を切って新しい列を始めるのだけど、どちらの列にもペアを登録することになる。たとえば 1 1 2 2 2 3 3 が与えられたとき、得られるペアの列２つは 1 2 と 2 3 になる(同じ数字の繰り返しは省略)。2 と 2 のペアが前後のどちらの列にも属している。その次にペアの列に対して同じ値を含まない最長の範囲を求める。現在の値を右端とするとき左端がどこまで伸ばせるかという DP をした。最初は値ごとに直前の位置を記憶しておくだけでいいかと思ったけど、そうではないのだな。たとえばペアの列が 1 2 3 2 1 だったとき、右側の 1 から左側の 1 の直前までを切り出すと 2 3 2 1 になって違法。直前の位置の最大値を１つ記録しておく必要があった。RE/WA を１回出しつつ 26 分かけた。難しいし妥当だと思う。■E 問題 11/22 Subsequence。25 点だけ配点が上の F 問題に先に取り組んだけど追い返されてきた。スラッシュの位置にそのスラッシュを中心とする 11/22 文字列の長さを記録しておけば、セグメント木の区間クエリで答えが出せると思ってしばらく無駄な時間を費やしていた。何を勘違いしていたか。「(連続とは限らない) 部分列」で 11/22 文字列を構成するということは、スラッシュとスラッシュで 11/22 文字列が区切られるわけではない、ということがわかっていなかった。スラッシュを飛ばしてその向こうまで 1 なり 2 なりの文字を拾い出して構わない。ということを理解すると、スラッシュの位置ごとに左に１がいくつあって、右に２がいくつあるかということだけが重要。クエリで範囲が与えられたとき、どのスラッシュにとっても同じ数だけ１と２の利用が制限される。範囲内のスラッシュに対して二分探索で左右の１と２の均衡点を探る。２つの均衡点(m0, m1)を取り違えるタイポで WA を１回出しつつほぼ１時間かけた。終了５分前に WA が出たときは目の前が真っ暗になる思いがしたけど、上から読み直して運良く見つけられた。F 問題を考えていた時間とセグメント木を使っていた時間が無駄になった。3、40 分で解きたかったね。■F 問題 1122 Subsequence。A の値域が 20 以下という制約からどういう DP がやれるか考えてしまって考えが深まらなかった。D 問題でやった DP と、E 問題で気がついた「都合の悪い要素を飛ばして伸ばせる」という点がヒントになると思うんだけど、未だまとまらず。現在の要素を右端として直前の同値の要素からどれだけ左に伸ばせるかを考えたいんだけど、それをするのに何をキーにして状態を記録するのかが不明。■値が 20 種類しかないということは、最長でも 20 までしか伸ばせないということだ。ということは？ 何ができる？ 長さが問題にならないなら幅が 1<<20 でも問題ないということで、bit DP か？■五線譜ならぬ 20 線譜があって、隣接する同値の２要素を繋いだ区間が線上に乗っていて、20 本の線からオーバーラップのない区間を選んで繋ぐ。同じ線からは１つの区間だけ。N 個のマスすべてに石がちょうど 1 個ずつ入っている」)。石が余る場合に間違えていた。修正に５分。N マスすべてに石が配れるかは確認済みなので、石の総数が N であることをチェックするだけ。ペナルティ込みで 23 分かけた計算。難しいよー。■D 問題「Home Garden」。一転して簡単な問題。配列(生配列とポインタペアで十分)に植えた日を記録していく。収穫は先頭から順番に。４分半。■E 問題「Sum of All Substrings」。かつての ABC-D 緑 diff って感じの問題。まず、余りを取る問題でないことに驚いた。えっ。64 ビットに収まるんですか？ (サンプルを見て)収まらないね。１の位から考える。S の各桁の数字は１の位として何回活用されるか。10 の位、100 の位としては……。繰り上がりも考慮して決めていく。提出までおよそ 30 分。書く量は 252 バイトでもすらすらとは書けない。■F 問題「Buildings 2」。よみがえる ABC372-D「Buildings」の悪夢 (「脳みそがスポンジ化している」「番狂わせの D 問題」「提出するまでほぼ１時間ぐだぐだやっていた」「問題が全然頭に入ってこない」「いったい何を数えるんだよー」「"ビル i とビル j の間にビル j より高いビルが存在しない" という i と j のペアを数えるんだけど、えっとね、i のビルの高さはなんにも関係ないんだよ」「理解したら実装は５分」)。慎重に問題とサンプルを読んで理解に努めた。基本的には自分自身を起点とする増加列を数えておけば良さそう。自分より低いビルも見ることができるんだけど、r より低いビルを l から見ることはできないので、それは数えても意味がない。l と r の高低にかかわらず r から見える r より高いビルの数が答えの候補になる。あと考えることは、l から r が見えない場合。答えはゼロではなく、あいだにある最も高いビルから見えるそれより高いビルの数が答えになる(この条件は r が最も高いビルである場合もカバーするので場合分けが消える)。ランダム入力と愚直解法からこのケースを見つけた。ABC372-D の記憶によって数えるべきものがはっきりわかっていたから、見つけたケースの解釈で迷うことがなかった。あとは増加列を数えるのに LIS をやるポカをした。スタックを１本持って長さを数えるだけでいいのはさっき挙げた Buildings と同じはずなんだけど、なんで同じにできなかったんだろうなあ。最初の提出 #59612302 (WA) を書くのに 20 分かけて、デバッグに 20 分かけた。提出 #59621904 (AC)。■G 問題「Count Grid 3-coloring」。10 分も残っていないので問題を読むだけ。左の数字と上の数字を参照して１,２,３の場合の数を数える DP かなと思ったけど、制約が３乗を許容しているし制限時間も長めの３秒なので、何かが抜けているか全てが間違っているかのどちらか。■コンテスト成績証。青パフォ 1763。■あっ、F 問題の問題名が Buildings 2 だ！ そうか、問題名で自己言及していたのか。■■■C 問題。左にある石の山から処理をしようとするといろいろ保留することになって面倒そうと書いたけど、実際には左からやった方がシンプルになった。提出 #59709275 (左から / 204 Byte)。提出 #59582960 (右から / 280 Byte)。
Ai と等しい要素が i の直前に出現した位置を Bi とする」とあったが、等しい要素を A 数列から探すのか B 数列から探すのかわからなくてフリーズしてしまった。サンプルで理解したけども、読み飛ばして「
より正確には」以下を読むのでも理解できた。だけどそこまでたどりつかずにぐるぐるとスタックしてしまった。わかれば値の範囲を見て Hash でメモ。■D 問題 Count Simple Paths。計算量で難しさを出してくるのが D 問題というイメージなので、愚直 DFS が通るのは甘々です。だけど BFS は書けるけど DFS はなんか苦手という時期が自分にもありました。■E 問題 Mod Sigma Problem。解けてないよ。６問解く実力がなくて F 問題が 25 点だけ上なら F 問題を先に解かない理由がないよ。■F 問題 Add One Edge 2。単純グラフというのは自己辺なし多重辺なし。単純グラフというのは自己辺なし多重辺なし(２回目)。問題文を読んでるときにこの通りに補完しているが、ABC なんだからそこまで書いてもいいと思うんだよね。知らなきゃ解けないという問題は門前払いされたようで面白くないよ。それが概念でなく単なる言い替えレベルの用語がどう定義されているかというだけのことであればなおさらしょうもなくて面白くない。次数２の頂点同士を結んでその LCA までのパスがすべて次数３であるか、LCA が次数２の頂点の一方であるかという場合を数える。とにかく実装が下手だった。WA (隣接している次数２の頂点を結んでしまっていた。それは多重辺)、WA (葉を刈り取る DP をしているのに処理順が LIFO だった。20241019と同じミス。手癖で書いてるんじゃないのよ。pop かな shift かな pop でいいよねと考えた結果なのが救われない)、WAWAWA (葉を刈り取る DP をしているのだから、１を仮の根としたときの親に処理を流すのは間違いなのよね。この場合の根とは最後まで残った１ノードのことなのだから。一番深いところから積み上げる DP なら間違いではなかったし、脳内イメージではそうしていたんだけど、実際にやってることがちぐはぐだった)、AC (再帰関数で再実装したら AC だった。だって何度問題を読み直してももう考えることが残っていなかったので、原因がわからなくても実装が悪いことが明らかだった)。■レートは横ばい。デバッグとペナルティで失った 50 分が痛い。■■■精進。E 問題。累積和とか転倒数とか BIT とかのワードを見かけてもいまいちピンときていなかったが、ある動画でエスアールヒクエスエルが負と聞いてやっとやるべきことがわかった。それを正しくやるのにも散々迷走して凡ミスをして苦しむんだけど。提出 #59430244 (AC)。■■■精進。水 diff ながら抜けていた ABC221-E LEQ。さっきの E 問題を解いたあとだと普通に解ける気がして、普通に解けた。提出 #59440817 (AC)。ABC378-E とは類題ってことでいいのでは？ 自分は感覚とかイメージとかのふわっとしたもので問題を解いているので(○○の△△は二分探索(を疑う)みたいなトリガーを記憶しておくことも適切に引き出すこともできなくて、二分探索の雰囲気がするから二分探索をしている。例「二分探索っぽさがあるよね」)、式を操作したり式を見て糸口を見つけるということが苦手というか、まったくアプローチができていない。そういう苦手を突くという点で類題だと思った。この問題では２の冪乗というものについて、足し合わせてみたり、足し合わせたものをまとめて割ったりするとどうなるかな、何の問題もなく個別に計算したのと同じ結果が手に入るなということを確認するだけで解答が書けた。昨日まではそれができなかった。ある範囲の連続部分列の和が Sr-Sl であると、それが mod を取ったあとだとどうなるか、それをどうするかと考えてみることができなかった。そういうアプローチが存在していなかった。
イギリス人技師のウィリアム・マードックが、自分の小屋で石炭から出るガスによる照明の実験に成功[1][2]。1797年にはイギリスのマンチェスターでガス灯が設置された[2]。」「
初期のガス灯は、直接火口から火を点灯し、炎を直接明かりとして利用するものだった」「
19世紀半ばには一般家庭の室内照明としてもガス灯は普及していたが、当時のガス灯は爆発の危険もあり室内の使用に適したものではなかった[5]。」 19 世紀。イギリス。爆発するっていうのは、口を閉め忘れたり火が消えたりで室内にガスが漏れた結果なのかなと思う。■答え合わせ２。「可燃性ガスが爆発する濃度の基準は？爆発範囲の一覧と安全対策も解説 | 計測・測定器のレンタルならソーキ」から「
可燃性ガスとは、空気中または酸素中で容易に燃焼する気体」「
可燃性ガスと空気の混ざった混合気が着火によって爆発する最低濃度が爆発下限界、最高濃度が爆発上限界です」 空気中または酸素中で。爆発上限界。燃焼ではなく爆発についてだけど、爆発する濃度に上限がある。ガスが濃すぎても爆発しない。■答え合わせ３。「酸素バランス - Wikipedia」から「
酸素バランス（さんそバランス）とは、火薬や爆薬の組成が完全に酸化されるために必要な酸素原子が、火薬の組成中に元々含まれているかどうかを見る指標である。火薬や爆薬の組成中に、火薬を完全に酸化するよりも多い酸素原子が含まれていれば酸素バランスはプラス、少なければ酸素バランスはマイナス、同じであれば酸素バランスはゼロと表現される。」「
火薬学では酸素が余るように配合するように指導している。」 火薬というのがそもそもそういうものだった。そのようにデザインされている。今の今までそれを知らなかったんですよ。ところで火薬学って初めて聞いたんだけど、なにか兵法にも通じる古めかしさとかっこよさを感じる。発破技士というワードも関連に挙がっていた。かっこよすぎ。してみると「はっぱをかける」ってそうとう物騒な物言いだ。尻に火をつけるくらいにとどめておこう。ところで、昔の子供はカエルの尻に詰めた爆竹に火をつけて遊んだと聞きました。なんだじゃあ一緒だな！
D[a][b]==INF だと考えてしまっていた。考えなかったわけではなく、勘違いしていた。無条件に c 書き込んでいいのか一瞬考えて、問題ないと判断していた。■無向グラフにワーシャルフロイド法を使用するとき、ループの回数を半分にすることで TLE の可能性を減らすことができるのは、ABC369-E を通して刻み込んだ学び (20240831)。■C 問題と E 問題についても書きたいけど、まだ解けてないので書けない。■精進２。ARC185-A mod M Game 2 (緑 diff)。すぐにむりむりわからんと投げ出したくなるけど、緑 diff だというのをもう知っているし、テストケースの多さからもシンプルに解けるのがわかる。ちょっとこらえて視覚的に考えてみると (M おきに印が付いた数直線にそって場のカードの和を表す棒グラフが伸びていくイメージ)、そのときどきで出してはいけないカードが高々１枚しかないとわかる。N<M だしね。最後の１枚になるまではどちらも絶対に負けない。2N 枚のカードの数の和で Bob の負けが判定できる。これだけではサンプルが合わなかったのでまだ考える。Bob が最後の１枚を決め打って温存するなら、Alice が N 枚目のカードを出したときの場の和を Bob が N 通り選ぶことができる。その N 通りに M の倍数が含まれるなら Alice を負かすことができる。Bob はその１枚を最後まで温存できるのだろうか。できるに決まってる。出してはいけないカードはあるけど出さなければ負けるカードはない。そんな当たり前のことも確認しなければわからない。提出 #58815966 (AC / 121 Byte)。かけた時間で判断すれば 300 点問題。事前知識を考慮して高めに見積もっても 400 点。<追記>できるに決まってはいなかった。２枚持っていて一方が出してはいけないカードならもう一方を出すしかない。温存できるの？</追記>■精進３。ARC185-B +1 and -1 (水 diff)。右の要素の高さを左に寄せることで右上がりの坂を作る。右に寄せられるなら何の問題にもならないけど、左にしか寄せられない。制約から判断して要素を左から見ていくことにする。二度見三度見は許されない。ネックになるのは、均した結果がある高さになるとしてその右側がへこんでしまうのがいけない。そのへんをうまくやるために４つのパラメータを記録した。すなわち、(現在の要素までの総和、均してもこれより低くできない高さの最大高さ、その位置、その位置までの総和)。提出 #58816249 (WA / 294 Byte)。A 問題から 31 分でまずは WA。提出 #58816379 (AC / 295 Byte)。その修正に 15 分。小なりを小なりイコールに修正した。文字にして初めて思ったけど、なんで小なりと equal がくっついてひとつの言葉を作ってるの？