. を数えるか @ を数えるかして、D を足すか引くかする。■B 問題 Daily Cookie 2。後ろから書き換える。愚直に N^2 の時間をかけて大丈夫。String の場合は検索開始位置が渡せるのでケチって線形時間にもできる。Array で検索開始位置が指定できないのはスライスを使えってことなのかなと思うけど、添字の調整が面倒くさいからやらない。■C 問題 Kaiten Sushi。配点がちょっと高い。上流にいる人が食べたいものをすべて食べてしまうという容赦ない設定は流し索麺を思い出す(Somen Nagashi)。あちらは離席して食べる時間があるけども、こちらは容赦なき総取り。人の列が減少列になるように間引いてから二分探索をしたけど、寿司の方をソートしてしまえば二分探索はいらなかった。計算量のオーダーは変わらないので実装はお好みで。■D 問題 Keep Distance。すべて出力しろと言っているのだから、愚直に列挙して間に合う制約になっている。DFS が書けますかという問題。あ、嘘嘘。愚直に列挙したら最大ケースが終了しなかったので先を見て予め列挙範囲を限定する必要があった。無駄なく列挙しないといけなかった。■E 問題 Expansion Packs。２乗の DP が許される制約(？)。解答形式が小数だからサンプルも小数で書かれているし、サンプルの２が自己ループを含むものになっているおかげでデバッグが捗って助かった。何をしたか。現在持っているレアカードの枚数 R とそこに至る確率をベースとして、今開ける１パックの期待値(＝１パック×確率)を答えに足し、レアカードが R+X 枚になる確率を配っていきたい。そうすると１パックあたり X 枚のレアカードを得る確率を予め計算しておく必要がある。そうすると１パックにレアカードが０枚で足踏みしてしまう場合があることに気がつく。こういうのは具体的にどうするとうまくいくかを考えた。１パックあたり３分の１の確率でレアカードが０枚に終わるケースで考えると、１回に２分の３パック開ければレアカードが期待できる。レアカードが入っている前提ではレアカードが X 枚入っている確率は、分母(全体の場合の数)が減っているのだから最初に求めた数字より大きくなるはずで、1/(1-1/3) の式で倍率を表すと丁度いい大きさになるなと考えた。要はレアカードが０枚の場合を含む全事象からレアカードが１枚以上の全事象への分母の減少率の逆数。しかし！ TLE が解消できなかった。C++ で書き直したものはループの範囲を限定したりといった小細工なしでも 39 ms で AC だったけど(#60354761)、時間内には間に合わなかった。制約に泣かされた。Ruby で通している人が１人いたので、これは泣き言なんだよなあ。■F 問題 Falling Bars。消えない回らないスライドしない、落ちるだけのテトリス。区間更新区間取得のセグメント木の最も基本的な使い方がわかりますかという問題。残念ながら区間更新ができるセグメント木を持っていないので、即座に撤退して E 問題の TLE 解消に戻った(解消できなかった)。あまりにもストレートな問題なので、区間更新ができるセグメント木を書くいい機会かなと思った。以前読んだ競プロに関する翻訳された PDF (現物をなくしてダウンロード元も不明) のおかげで、トップダウン式のトラバースが自分の実装に欠けていることがわかっている。セグメント木を最初に雰囲気で実装したときに、末端から LCA までを辿るようなアクセス方法になった。だけど遅延された(区間)更新が伝播するのは根から末端に向けてなので、ボトムアップ式のアプローチはまったく役に立たない。トップダウン式の辿り方をでっちあげて区間更新ができるものをがんばって実装したけど、TLE だった(#60355045)。もうちょっと実装を洗練させたり無駄を省いたり手抜きをしたりする余地がないか考えてみたいけど、とりあえずここまで。■F 問題。通った！ 提出 #60379219 (AC / 1143 Byte / 1869 ms)。さっきの TLE で再帰呼び出しをしていた４行を直接インスタンス変数を書き換えるように変更したら間に合った。今は 0 とか max とかをあちこちにrequire 'numo/narray' していた。うん、それはね、Rust も Crystal も numo/narray もローカルに、古い Windows にインストールできなくて試行錯誤できないから捨ててるんだ。あきらめがついてすっきりした。■E 問題。あきらめたと書いたそばから通っちゃったね。提出 #60486554 (AC / 355 Byte / 1966 ms)。しょうもないなあ。コードテストで判断すると、制限時間が３秒なら TLE だった提出も TLE ではなかった。TLE と AC の違いはアルゴリズムの違いではなく、スクリプトの記述の違いでしかない。だからしょうもない。でも飛び道具なしのピュア Ruby でも不可能な制約ではなかったと自分で証明してしまったんだよな。なんだよくやしいなあ、あきらめがつかないじゃないか。■■■@2024-12-18 ABC357-F の精進について 20241218 に書いた。ついでに書くけど、さっき通ったと喜んでいた ABC382-F への自分の提出 #60379219 (AC) にはバグがある。61 行目のセグメント木の初期化サイズが間違っているので、N が W よりたっぷり小さいときエラーが出る。1*/2* を拾い出してからスラッシュの位置を探して計算した。なんでか 10 分かかっている。■D 問題 1122 Substring。やることが多いよね。まずペアの列を複数切り出したんだけど、同じ値が３つ以上連続している場合に注意が必要。その部分でペアの列を切って新しい列を始めるのだけど、どちらの列にもペアを登録することになる。たとえば 1 1 2 2 2 3 3 が与えられたとき、得られるペアの列２つは 1 2 と 2 3 になる(同じ数字の繰り返しは省略)。2 と 2 のペアが前後のどちらの列にも属している。その次にペアの列に対して同じ値を含まない最長の範囲を求める。現在の値を右端とするとき左端がどこまで伸ばせるかを考えた。最初は値ごとに直前の位置を記憶しておくだけでいいかと思ったけど、そうではないのだな。たとえばペアの列が 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 なりの文字を拾い出して構わない。ということを理解すると、スラッシュの位置ごとに左に１がいくつあって、右に２がいくつあるかということだけが重要。クエリで範囲が与えられたとき、どのスラッシュにとっても同じ数だけ１と２の利用が制限される。範囲内のスラッシュに対して二分探索で左右の１と２の均衡点を探る。こういう二分探索は少し前に初めてやった(ABC364-D「K-th Nearest」、20240727)。２つの均衡点(m0, m1)を取り違えるタイポで WA を１回出しつつほぼ１時間かけた。終了５分前に WA が出たときは目の前が真っ暗になる思いがしたけど、上から読み直して運良く見つけられた。F 問題を考えていた時間とセグメント木を使っていた時間が無駄になった。3、40 分で解きたかったね。■F 問題 1122 Subsequence。A の値域が 20 以下という制約からどういう DP がやれるか考えてしまって考えが深まらなかった。D 問題でやった DP と、E 問題で気がついた「都合の悪い要素を飛ばして伸ばせる」という点がヒントになると思うんだけど、未だまとまらず。現在の要素を右端として直前の同値の要素からどれだけ左に伸ばせるかを考えたいんだけど、それをするのに何をキーにして状態を記録するのかが不明。■値が 20 種類しかないということは、最長でも 20 までしか伸ばせないということだ。ということは？ 何ができる？ 長さが問題にならないなら幅が 1<<20 でも問題ないということで、bit DP か？■五線譜ならぬ 20 線譜があって、隣接する同値の２要素を繋いだ区間が線上に乗っていて、20 本の線からオーバーラップのない区間を選んで繋ぐ。同じ線からは１つの区間だけ。■■■精進。F 問題。O(AN) の方針に行き詰まって O((2^A)A) の ビット DP に方針を定めたとして、遷移がわからなかった。ところで、状態のキーがこれまで使用した値ペアだとして、何を記録するのか。これは N 要素のどこまでを使用してその状態に至ったかの最小値。ということを整理しているうちに TSP が降ってきた。巡回セールスマン問題と同じ遷移で解ける。提出 #60111625 (TLE) のち 提出 #60113392 (AC / 612 Byte / 1405 ms)。やっぱり今日の１問レベルの歯ごたえがあった。Crystal での提出を見てると E 問題の AC から７分半でこの F を通している人がいるけども(#60070912)、それは頭がおかしい。自分はこの問題を反射では解けないし、指を動かすだけでもそれ以上の時間がかかるのは間違いない。TSP 問題は３問ほど解いたことがある(だけど未だに苦しむんだよ)。たとえば ABC180-E「Traveling Salesman among Aerial Cities」(20201018p01.02)。これ水 diff 下位の難易度しかないことに驚く。この F 問題は青 diff 下位だったけど、目くらましが目くらましとして機能しないレベルの人にとっては、青も水も変わらず典型パターンを当てはめるだけの問題になってしまうのか。それも難なくやってのける。■■■A 問題。ややこしいし効率が悪いしやる意味はないんだけど、あえての正規表現。提出 #60163766。パターンは ^(1\g<1>2|/)$。Ruby ならできます。同じパターンを C 問題でも使おうとしたけど、N≦200000 では TLE が不可避だった(提出はしていない)。■■■F 問題。それとさっき挙げた ABC180-E Traveling Salesman among Aerial Cities。遷移まで含めて bit DP と呼ばれてるみたい？ 「集合 S をビット表記により 0,1,…,2N−1 までの自然数にエンコードしてしまうと、S=0,1,2,… 順にループするだけでトポロジカル順序が守られることなどから、実装が簡潔になります。この実装方法から bit dp とも呼ばれることの多い手法です。」([AtCoder 参加感想] 2020/10/17:ABC 180 | maspyのHP)。自分が bit DP と認識しているものはメモ化再帰とよく結びつくもので、状態をビットフラグで表すことで順序に関する情報を落として再計算を省くというもの。遷移はそのつど再帰関数を書くときに考えている。だけど bit DP というだけで今回のような遷移が引き出せるべきなんだろうか。
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 がくっついてひとつの言葉を作ってるの？