N 人の参加者が一列に、全員同じ方向（右向き）を向いて並んでおり」これだけでは情景が想像できない。同じ向きを向いて横隊を作っているのか縦隊を作っているのかがわからない。だからその後の「
全員が同じ方向を向いて一列に並んでいるため、隣り合う2人の参加者が握手をするとき、左側の参加者（番号が小さい方）の右手と、右側の参加者（番号が大きい方）の左手が触れ合います。」という論理がナンセンスに基づいている。そして、ここで説明される行為を握手とは呼ばない。握手とは(直前までどちらを向いていようとも)向かい合ってするものだ。慣れていれば競プロ的な設定(隣り合った人が右手と左手をつなぐ。先頭の人の左手と末尾の人の右手は余る)の肉付けに失敗したのねと了解できるけども、まじめな初心者ほど困惑するのでは？ 世の中には文字とみれば先頭から末尾まで１文字ずつなめるようにしか読めない人間がいるのです。そういう人を指してまじめと表しました。
全て 6000000 以下である」が難しい。電気毛布をオンにしたお布団があったかくて寝落ちしているあいだに終わっていました。今日は積もる勢いで一日中雪が降っていて帰り道が怖かった。信号で止まろうとしている車が黒い地面をひっかきながら 30 cm ほど滑って前の車にゆっくり迫っていくのが見えた。ノーマルタイヤのこの自転車ならどうなる。白い歩道がサクサク音を立てている。■自分のすべての提出。コンテスト成績証。AB どちらも灰 diff で(ABC の diff と ARC の diff はそのまま比較できない印象)、茶パフォもありうるかと思ったけど、意外に昨日と同じような結果だった。つまり良くはない(「ぼちぼち」)。実際の diff は知らないけど、簡単な問題しか解けないのが自分です。
どの 2 つの要素も差が D 以上である」という条件を満たすか否か。満たすんですね。あぶなかった。Array#all? メソッドと Array#any? メソッドでは初期値が異なっていて空配列に対して呼び出したときの結果が違うんですよという(論理的に正しい)ことを私は知っています。問題が理解できたところで、全連続部分列の累積和を列挙する的な処理がしたい。要素を左から見ていって、それまでの始点の累積に対して現在の要素が終点になる場合を考え、また、現在の要素を始点として累積に追加する。単一要素の部分列も対象だから、順番としては現在の要素を始点として追加してから現在の要素が終点となる場合を数える。何を記録しますか？ 各要素ごとに有効な区間の右端が決まっている。右端をキーとしてそこまでの範囲を有効な区間とする始点の数を記録した。ところで、有効な区間の右端は区間に含まれるすべての要素によって制約される最小の値になります。現在の要素に照らして、期限を越えた区間を取り除き、長すぎる区間を切り詰めるように累積情報をメンテナンスすると、現在の要素を終点としうる区間の数が数えられる。これを BIT で数えたい。数えたいんだけど、現在の要素が有効な区間をどれだけ右まで伸ばせるかということがすぐにはわからなくて、BIT に区間を計上したり区間を切り詰めたりするための情報が足りなかった。結局それも BIT で予め求めることになった。BIT を使った２段構えでとてもたいへん。たぶんだけど問題を無駄に複雑にしていると思うんだよね。もっとすっきり解けたんじゃないかという気がする。使える頭がないので実装をがんばりました。■30 分残しても F 問題はさっぱり。順位表を見ると F と G を両方解いている人がとても少なく、F を飛ばして G を解いている人がそれなりにいる。今日の F は鬼門ですか？ (難しいケースと面倒くさいケースが考えられます。その後わかったことは、G 問題と AI の親和性が高いケースも考えられます)■自分のすべての提出。コンテスト成績証。４桁順位で水パフォ +21 レート。ぼちぼちなんだよなあ。■■■E 問題。尺取りというワードをよく見る。各始点ごとにどれだけ範囲を右に伸ばしていけるかということを、範囲内の値を SortedSet で管理しながら調べるらしい。値の範囲が大きすぎるので BIT でこれをやるには座圧が必要。偶然だけど自分の解法では可能な範囲を値ベースではなく添字ベースで管理していたので座圧なしで BIT に情報をのせることができていた。書いていたように別の解法はたしかにあったけど、そちらにはそちらの面倒が(SortedSet がない Ruby には)あったらしく、すっきりした解法はなかったのだった。
|| とか)が省けるかを考える。今日は c==?i||c==?j (c は各文字) を一度書いてから 'ij'.index(c) もありだなと思ってからの 'ij'[c] で提出した。■B 問題 Music Player。珍しく長い変数名 playing と volume を使ったものだから、タイプしながら volume は長すぎるせめて vol にすべきだったと後悔していた。他の人の変数名が気になります。■C 問題 Peer Review。エルデシュ数とかベーコン数をイメージしながら UnionFind の雰囲気を感じていたけど、直接の利害関係しか関係がなかった。Hash を使って重複を除いたけど、制約で予め除かれていたので無駄だった。Hash を使うだけで目に見えて実行時間が増えるので、本当に必要なとき以外は使うべきでない。必要なときでもある数までは配列の線形スキャンの方がましなのである。■D 問題 Swap and Range Sum。隣接項の交換なら累積和を２点更新するだけだと思って書き始めたら、実は１点更新だということがわかった。添字で間違えないように{参照/更新}する可能性のある項をすべて列挙してから実際の処理を書いた。順番に並べて前後の位置関係をヒントにすればたぶん取り違えないだろう。■E 問題 Laser Takahashi。「すなわち、モンスターは大きさを持ちません」 偏角ソートして累積和の差分を答えるだけなんだけど、角度を逆引きする関数をリファレンスから探してきても誤差で殺されそう。私はもう Rational を使う楽ちんさを知っています。傾きを分数で持つ。分母がゼロの場合を irb で確かめると例外が飛んだ。じゃあその場合だけ小数の無限大で (Float と Rational の比較は Ruby におまかせできる)。求める累積和の区間が円環の切れ目を含むと面倒なので例によって２周分の累積和を用意した。傾きが等しい点を累積和でうまく扱えるように座圧(傾きを傾きの序列で代替)もした。サンプルが合わない。デバッグ出力を見てよく考えると Rational で表現した傾きでは原点で対称な点を区別できない。どうする、今からベクトルの扱いが思い出せるか？ どの象限にあるかという数字と傾きのペアでソートすることでなんとかなった。でも WA×5。象限によっては X=0 のときの値を負の無限大にしないといけなかった。これの修正に６分。全体では 25 分(+ペナルティ５分)かかった。■F 問題 Diagonal Separation 2。5000 の２乗は嫌な感じ。でも他には 600 点の G 問題しかないのでやるしかない。行単位で DP をするのかと思ったけどサンプル２が合わない。k の値を前の行から引き上げるとき、列方向の制約によって追加コストが必要になるのだった。そして日記を書いている今どうしてもサンプルが合わなかった理由がわかったのだけど、コストは追加されるだけではなく削減されることもある。１時間残していても問題を理解するのに足りなかったんだな。■■■F 問題水 diff 下位マジ？ なら解けたなあ、とは思えない。
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 に変更すると期待通り余計なスペースが選択されなくなった。めでたし。