require 'prime'、Integer#prime_division とか、約数列挙とか、素数を列挙してからの試し割りとか、だいたい通らない。だけど絶対に通らない問題というのは数えるほどしかないし(少ないけどあります)、うまいやり方で余裕で通す人もいたりするものだから、結局は己の至らなさにはね返ってくるのであって、不満のはけ口はありません。残念。精進しような。■D 問題。Ruby で一番最初の AC であるこちらの提出 #73307835。答えの座標が X と Y のどちらか一方が１に固定されている。なんでそれでいいのかわからなくてスクリプトに手を加えてピース番号をグリッドにプロットしてみたけど、番号に重なりはなかった。全然わからない。……。お風呂でイメージしてきた。(1,1) から遠いところから切り落としては全体のサイズを縮めていく、という過程を考えれば、どのピースも (1,1) から右または下にどれだけ離れているかという尺度で特定できる……らしいですよ。■E 問題。Ruby で最初の AC がこちら (#73334218)。require 'prime' しないで素数の倍数に素因数をメモすることで素数を列挙している。自分は素数を判定する方法としてこのやり方を知っているけど、素因数を列挙するための情報源としての利用法は知らなかった。素数ではない(合成数である)数のスロットには素数のひとつが記録されていて、それにより自身が素数ではないことが知れる。それだけではなかった。ここで合成数を n、記録されていた素因数を p として、n = n/p を繰り返して n が 1 に至るまでには素因数の指数の和と同じ数のステップが存在し、その過程ですべての素因数を指数個分ずつ拾い集めることができる、ということらしい。すご。■まねしたのに通らへん。提出 #73350310 (TLE×2)。書き方か。step メソッドを while ループに書き換えたら通った。提出 #73350361 (AC / 1830 ms)。やはり while。while 文は(ブロック付き)メソッドより速い。■F 問題 Exactly K Steps 2。何重にも重なったループを書こうとして書き切れなかったけど、行列の文字が見えたら行列の掛け算をイメージしてループを書く助けにできる。提出 #73353560 (TLE×22/AC×21)。ダメです。行列計算は N の３乗だったような気がしますが、log(K)N^3≦3000万で通りませんか。F 問題で行列計算やるだけは考えが甘いですか。■E 問題の高速素因数分解に関連して ABC177-E の解説が挙げられており、それがまさしくさっき言及した Coprime の問題だったんだけど、えっと、自分はまだこの緑 diff の問題を通しておりませんでした。緑埋めをしているときに埋め切れず、水埋めをしているときにも何度もふりかえってははね返され、そして現在に至る。もう諦めて忘れてしまったみたい。■精進。ABC177-E「Coprime」。Coprime と名の付く類題に至るまで苦手意識を植え付けられたいわくつきの問題。Coprime 恐怖症の元凶。今日最初に書いた解答は ABC445-E にならって素因数分解をしてからそれを使って判定をするものだったが、これは全く望みがなかった。なぜって pairwise coprime を判定するのに全組み合わせを考えると O(N^2) になるから。N の上限が 100 万だというのにそれは無理。５年前の自分ですらそんな馬鹿はやっていなかった (#19442249)。あらためて考えると、各素数について、それを因数とする A 数列の要素がいくつあるかを数えて、その最大値がいくつかを見れば良い。最大値が 0 なら A 数列はどの要素も素因数を持たない(すべて１)ということ。最大値が１なら、どのペアをとっても共通の素数を因数に持つことがないということなので pairwise coprime。最大値が N なら全要素に共通の素因数が存在するということなので not coprime。残る２以上 N 未満の場合が setwise coprime になる。提出 #73355090 (AC / 560 ms)。たしかに実装内容だけ見れば緑 diff だけど、書き方がひと通りでなく、他のどの書き方をしても Ruby では通らないということで、見た目以上の難易度になっていたと思う。■他の人の提出を見ると、素数列挙は require 'prime' でも良いらしい。pairwise coprime を判定するのに全組み合わせを考えるのではなくセグメント木のようなピラミッドを考えると Bignum を頼ることになりそうだけど log(N) ステップで判定ができて間に合うらしい。なんだ AC をとるのに色々やり方があるじゃないか。お前があほなだけやったか。だって今日初めてある１つの値が 0 から N の範囲のどこに位置しているかによって分類できるという問題の構造に気がついたわけなので、ぼけなのは間違いない。N 人の参加者が一列に、全員同じ方向（右向き）を向いて並んでおり」 右向きとやけに具体的に書かれているけど、前後左右どちらを向いているとしても同じことなので意味のない情報。さらに、これだけでは情景が想像できない。同じ向きを向いて横隊を作っているのか縦隊を作っているのかがわからない。だからその後の「
全員が同じ方向を向いて一列に並んでいるため、隣り合う2人の参加者が握手をするとき、左側の参加者（番号が小さい方）の右手と、右側の参加者（番号が大きい方）の左手が触れ合います。」という論理がナンセンスに基づいている。むしろ２番目の文の前半部分はなかった方が、追加の情報から逆算して実際の並びはこうだったのだなと補完することができた。そして、ここで説明される行為を握手とは呼ばない。握手とは(直前までどちらを向いていようとも)向かい合ってするものだ。慣れていれば競プロ的な設定(隣り合った人が右手と左手をつなぐ。１番の人の左手と N 番の人の右手は余る)の肉付けに失敗したのねと了解できるけども、まじめな初心者ほど困惑するのでは？ 世の中には文字とみれば先頭から末尾まで１文字ずつなめるようにしか読めない人間がいるのです。そういう人を指してまじめと表しました。■■■４日目の「バッテリー残量」についてはソースコードにコメントとして書いた。「与えられる時刻に単位がないが、放電速度は mAh/s で与えられている。s が second (秒) の略であるとしても、「時刻(無単位)」との換算をどう考えるか。すなわち以下で具体的な式が与えられているので解けるが、まったくすなわちではない。これは定義であり、すなわちより前には何もなく、今この式でこうと決めたのだ。」■ではどういう表現ができたか。単位時間という言葉が使われていたように思う。時間の１つ分。時刻が１つ進んだときの間隔。「単位時間当たり Bi mAh バッテリー残量が低下する」みたいな。具体的な時間の単位が時間なら１時間当たりだし、分なら１分当たりになるところが、単位を特定しない場合には単位時間当たりになるのではないか。子供のときはよくわからん表現だと思っていたが、他にはなかったのかなと今では納得できる。単位という言葉に内包されているからか１という数字は明示されていない(１単位時間当たりではなかった)。そのこともよくわからん原因のひとつだったと思う。単位という言葉にそこまで明確な輪郭がまだ与えられていなかったので(単が一だとかもまだ意識していない)。
全て 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 には)あったらしく、すっきりした解法はなかったのだった。