P...P+100 と Q...Q+100 の範囲と比較する。■B 問題 Two Languages。難しかった。まず読み取るべきは「wi は高橋語か青木語のどちらかの単語」という制約。そうすると単語が高橋語のアルファベットで構成されているか、青木語のアルファベットで構成されているか、あるいは共通部分で構成されているかを判定すれば良い。
共通部分 ? 'Unknown' : 高橋語 ? 'Takahashi' : 'Aoki' という論理。ところが実際に問題を解いたときはそんなにすっきりとした区分けができていたわけではないから、入力を加工して共通部分を用意するということをしなかった。その場合は 高橋語ではない ? 'Aoki' : 青木語ではない ? 'Takahashi' : 'Unknown' という否定混じりの論理にならざるを得ない。それは難しい。■C 問題 Sake or Water。B 問題より素直。カップ数を最小化しつつある程度以上のお酒を飲みたいのだから、ソートして量の多い方から、最悪の場合を想定して飲んでいく。■D 問題 Paid Walk。出次数が４以下で、L が 10 以下。スタート地点は 1 で固定。4 の 10 乗が 100 万程度だったから、全部試せばいい。過去２回拍子抜けした経験からもうわかってきたけど、D 問題で DFS をやるときは、DFS 自体が課題という判定なのか高速化の工夫が求められない傾向にある。今日のこれは DFS に限らず BFS でも良かったのかもしれないけど、DFS で書きたくなる問題ではあったと思う。■E 問題 A > B substring。問題文に嘘が書いてありました。「S の空でない連続する部分文字列は N(N-1)/2 個ありますが」と書いてあって、これは S から 2 つの文字を選ぶ組み合わせだから、１文字だけの部分文字列がカウントされていない。半開区間で文字列を表すなら末尾の次の位置までをありうる区間として、空でない部分文字列の数は N+1 から 2 つを選ぶ組み合わせだから、(N+1)N/2 になるけども N(N-1)/2 にはならねーな。空でない連続する部分文字列の数をあらためて考えると、始点ごとの終点の数が 1 から N までだからその和で N(N+1)/2 になる。指を使って N=5 の場合を２回数えたから間違いない。ということをたどたどしく念入りに確かめてからリロードをしたら、目の前でしれっとマイナスがプラスに変わりました。やめてほしい。これでやっと問題に取りかかれる。A を +1、B を -1 としたときの累積和が正になるものの数を数えたい。Hash 表を使って愚直にカウントすることが許されない制約なので BIT を使うことを考えた。できそう？ できた。BIT で負の添字を扱うために N 程度の下駄をはかせてゼロの位置をずらした。その添字の操作を何度も繰り返すと間違えるので BIT 操作を関数でラップする丁寧さを見せた。■F 問題 Must Buy。DP です。N+数回 DP をすることが許されるならなんとかなる。ところが１回だけの DP をするのにも 5000 万のオーダーの処理になってしまう。時間制限を見るとちょい長めの 2.5 秒。Ruby だと苦労して工夫しても不可能な可能性があります。G 問題を読みましょう。■G 問題 Takoyaki and Flip。誤読をしていた。タイプ３のクエリではたこ焼きの合計を答えるのだと思っていたが最大値だった。図解で max とばっちり書かれていたけど、最初の実装を終えるまで見なかった。まだ誤読していた。タイプ２のクエリによって各お皿は１回だけ裏返されるのかと思っていたがそうではなかった。問題を正しく理解してからも、遅延セグメント木に何を乗せるか、不足に気が付いては足すということを繰り返した。区間演算について。たこ焼きを足すだけではなく裏返しもある。そして裏返しの裏返しは何もしないことではない。たこ焼きがゼロになっている。最終的に「表になっている面に足す」「裏返して０にする」「(裏の裏で)そのままの面で０にする」という３つの状態を考え合わせることになった。セグメントに保存する値について。裏向き無効と表向きの最大値のいずれかだけではなかった。ある範囲に表向きの皿と裏向きの皿の両方がある場合は、裏返しても裏返しても有効な最大値がある。最終的に表向きの無効値最大値と裏向きの無効値最大値を記録した。nullable integer のペアを記録したということ。提出 #72566496 (TLE×38/AC×27)。でも TLE です。しかも TLE の中に WA が隠れているのがほぼ確実。でも全然しっぽを出さなくてやっかい。■G 問題。レアなバグの原因がわかった気がする。Op::Abs2 と Op::Abs1 をセグメントに適用するときに、一度でも裏になったことのある面の最大値を、最大値がある場合はゼロにリセットするのを忘れている。どうせ TLE だから高速化のアイデアが出るまで再提出はしない。■E 問題。解説に O(N) 解答があるらしい。それは考えてみたい。■B 問題。昨日は大まじめに書いていたんだけど、解答の論理は否定も共通部分セットも使わずに
高橋語&&青木語 ? 'Unknown' : 高橋語 ? 'Takahashi' : 'Aoki' でも良かったのだな。横着して１文字あたりの判定を線形時間で書いて、判定結果を変数に保存もせず、だけど同じ判定を２回繰り返すまでは横着しきれなかったと見える。■■■動画を見ていたらブラウザからのコピペで Takahashi という風にスペースがくっついていたけど AC だったという話が聞こえてきた。これは自分もコンテスト中に気が付いていて、以前にそうならないようにした設定が失われているなと思ったのを思い出したので、改めて設定をし直した。Firefox で about:config を開いて space を検索するとまず editor.word_select.delete_space_after_doubleclick_selection = false という設定が見つかって、でもこれを true にしても期待した効果を発揮しなかったので下にスクロールしていくと layout.word_select.eat_space_to_next_word = true という設定が見つかって、これを false に変更すると期待通り余計なスペースが選択されなくなった。めでたし。