answer += a*A.size+A.sum while a = A.shift なんだけど、２要素の和が 10^8 を超えるときは 10^8 を引かなければいけない。A 数列の順番には意味がないので、予め A 数列をソートしておいて、何個の要素が 10^8 を超えるかを効率良く数えられるようにする。二分探索なら log が付くけど間に合うし、尺取りっぽい操作をするなら log は付かない。あっ。自分の提出 #53343786 で 10**8 に付けた名前が P(rime number) というのは嘘だ。■D 問題「Another Sigma Problem」。今度は２要素を文字列として連結してから数値として評価をする。順番に意味があるので並べ替えてはいけない。右側にある要素について、数の和と、下駄の和がわかればいい。下駄というのは、３桁の数字であれば 1000、４桁の数字であれば 10000 を計上する。これを全要素について数え上げておいて、更新しながら答えの計算に利用する。■E 問題「Yet Another Sigma Problem」。かかった時間だけ見れば C 問題と同じなんだけど、配点通り CD より難しかったと思う。自分は Ruby の記述力におんぶにだっこで効率の悪い解答を書いた。まず、N 個の要素について、先頭の文字を見ます。同じ文字だったもの同士をグループにして再帰的に次の文字を見ます。その過程で、グループの大きさを見ます。大きさが Z なら、作れるペアの数(Z*(Z-1)/2)がそのまま答えに寄与します。■F 問題「Tile Distance」。わかりやすい図が付いていてたいへん助かります。K=1 は簡単。マンハッタン距離が答え。それ以外はどうしましょう。最初はフラクタル的に考えてみようとした。スタート地点とゴール地点が隣接していると見なせるまで K を定数倍してみる。で、視点をズームインしながら移動コストを足していけないかと。できなかった。次は大きいタイルと大きいタイルのあいだの移動コストを数えようとした。横方向の移動コストだけを考えてみる。K が大きいなら、上下にあって頂点で接している大きいタイルを経由することで、必ずコスト４で真右にある大きいタイルへ移動できる。K=1 のケースはさっき除外した。K=2 の場合は小さいタイルをそのまま突っ切って移動する方がコスト３なので安い。そういう計算をしているうちに、斜めの移動コストが特に安いと気がついた。K マスを１と数える大きいタイルの座標系で考えてるよ。例えば右に２、下に２の位置にある大きいタイルに移動したいとする。右に移動してから下に移動するなら、さっき計算したコストを使って 3+3 (K=2 のとき) か 4+4 (K>2 のとき) になるけど、ありがたい図を使って数えてみると、たったの４で右下の右下にある大きいタイルに移動できることがわかる。というわけで、まずは斜めに移動して、それから縦もしくは横に移動すると考えると、最適な大きいタイル間の移動コストが求められる。あとは１または４通りと、１または４通りの総当たり(1x1 または 1x4 または 4x1 または 4x4 通り)でほぼ答えが出る。１と４が何かというと、スタート地点ゴール地点から最寄りの大きいタイルの数。「ほぼ」が何かっていうと、スタートとゴールが小さいマスにあってすぐ近くにある場合。これは K=1 の場合のマンハッタン距離と同じだから、提出 #53370051 では K=1 の場合を分けるのをやめて雑に一体化した。全部混ぜ混ぜして最小値を取れば自ずと答えが出てくる。■G 問題「Merchant Takahashi」。今日の G 問題は F 問題と配点が同じ。F 問題を通してから G 問題を読んで、することがなくなったので順位表を見たら F より G の方が通されていたね。自分は G 問題がさっぱりだったけど、データ構造で一発なぐるだけの典型だと仮定して眺めてみれば、移動コストによる報酬の減殺が組み込めるなら、セグメント木が使いたい形だと思った。もちろん組み込めないのだけど。■Highest を更新したけど、明日の ARC の参加費は何レートかな。何レート吸われるんだろう。3-4-5-(略) という配点は水色の自分向けド真ん中なので出ないわけにはいかないんだよな。■■■精進。G 問題。セグメント木を２つ持つんだと２か所で読んだ。それでどうやって距離による減殺を組み込めるかを考えた。左右の端、頂点１と頂点 N にいると仮定したときの所持金のポテンシャルをセグメント木の各要素の値とすると、イーブンな条件で大小比較ができて最大値が取り出せる。提出 #53408933 (AC / 849 Byte / 1999 ms)。２秒制限で 1999 ms は神がかっている。だめだったらセグメント木にブロックを渡す代わりに max メソッドの呼び出しを直に埋め込むだけ(手動インライン展開)。■実際の値の代わりにイコール条件のポテンシャルを扱うのは ARC120-C Swaps 2 でやったことがある。20211022p01。なんでそんな名前で呼んでるのかは自分でもわからない。なんとなくふさわしいような気がしただけ。10101 で表せる。全部で５人なら、これは 1-3-5 位しか考えられないが、全部で 10 人なら 2-4-6 位もありうる。しかし全部で 10 人いて他に 101011111 というピースがあるなら、やはり 1-3-5 位しか考えられない(※ MSB を１位としました)。こうなってくるととりあえず全部を試してみるしか答えを出す方法はないよね、という気持ちになる。１階層ごとに特定の１ピースを埋める DFS をやるんだけど、DFS の呼び出し経路には関心がない。どういうことか。１階層目と２階層目が受け持つピースがどちらも 1 と 1 という形だったとする。３階層目のピースにとって関心があるのは、そして結果に影響するのは、どのビットが空いているかということだけなので、同じ２ビットのどちらとどちらを１ピース目と２ピース目が埋めているかという情報には関心がない。むしろ積極的にその区別を捨てて結果の使い回しをしたい。メモ化です。というわけで、前半ではピースの形を確定する UnionFind を、後半ではピースを N ビットに隙間なく埋めるメモ化再帰をする２段構えの問題だった。要素技術は F 問題までで身につけているはずで、組み合わさったことで F 問題だったのかなと。G 問題ではないなと。ならこれも実装問題だったのか。突破できませんでした。腕力が足りない。■他所で見かけたのでここでも書くんだけど、置きにくいピース(※)から置くような小細工を WA だった最初の提出から行っている。これをやらなくても TLE にはならないだろうけど、とにかく答えを見つければいいという DFS の場合、優先順位を付けて早期に判定ができると劇的に実行時間が縮まることがあって気持ちがいいので、とりあえずやってみて沼にはまるのがいいと思う。その先にヒューリスティック沼があるかは知らない。この問題では、再帰を深く潜ってからやっぱりだめでしたーと判定されていたかもしれないものが、比較的浅い階層で無理だと判断できるようになる効果があったと思う。※置きにくいピースを短絡的にビット長の長いものとしたけど、ポップカウントもいい指標になりそうだと気がついた。1000001 と 1111 のどちらが置きにくいかという話。自分が明確に誤っていたのは、ビット長が同じでポップカウントが異なる 110001 と 101111 の比較で、単純に数値比較で大きい方(最初の方)を置きにくいと判断したところ。小細工だしフレイバーなので許される手抜きだとは思うけど。0o なので。意外すぎる観測結果なんだけど、ABC000 が罠になるってことある？■B 問題「Dentist Aoki」。やります。T[i] = 1-T[i] で更新したけど、T[i] ^= 1 の方が参照の繰り返しがなくて良かった。T.sum を答えにしたかったから数値配列にしたけど、真偽値配列にしたなら T.count が使える。そして、いつも期待を裏切られるのだけど、無引数の T.count は T のサイズを返す。自分の期待は false と nil を除いたものの数なんだけど、そうではない。そのことを irb で確かめるまでは今日もまた、もしかしてと期待していた。■C 問題「Sort」。N 個の順列は N-1 回のスワップでソートできるので、やるだけではある。でも添字と値が入り交じるのでややこしいんだ。コメントで頭の中を整理していた痕跡がある>提出 #52573395。ちゃんと効果があって、コメントに教えられて提出前にバグが見つけられた。■D 問題「New Friends」。知っている問題ですね。前回解いたときは UnionFind をしながら辺の数も管理するような解答を書いたのだけど、辺の数の総数が M として与えられているので、別に数える必要はないのである。それを覚えていたので今日は M が使えた。■E 問題「Toward 0」。最近解けていなかった期待値の問題だけど、これだけ素直な問題設定だとループのある試行でも式が立てられる。メモ化再帰で。５分かかっていないから９分かけた C 問題より簡単だったと言えるのでは。■F 問題「Transpose」。AC できただけでも嬉しいことだけど、さすがに１時間は時間をかけすぎている。何ができなかったかって、対応する括弧に囲まれた文字列を再帰的に取り出すことに苦労していた。私は再帰関数が書けません。やっと書けても TLE だった>提出 #52607490。それはまあ、文字列の配列を連結することを繰り返す代わりに、直接文字列を出力することで通ったのだけど(提出 #52610168)、Ruby での他の提出と比較すると遅いので出来の悪い解答であるらしい。たくさんのオブジェクトを new しているのが明らかに悪いが、class を使わないと頭の中の整理がつかないので仕方がない。コンテキストを分けて小さな部分問題を解くことに専念するためにクラスがある。■C 問題をやるだけと書いたけど、最初からそう捉えられたわけではない。ABC と AGC の区別がついていなかった頃に書いた日記に過程が書いてある>20190907p01。x をくっつけたら２番目のルールは無視できる。あとは T を元にして S をスキャンする。■D 問題「Divide Interval」。問題文が難しいよね。文というか式が。何度も読んで理解したところでは、ある２の冪乗 W があって、その２冪 W でアラインされた幅 W を持つ範囲が良い数列だと言っている。この説明でわかりやすくなったかは疑問。２つの２冪 w と W があって、w<W のとき、幅 W の良い数列の中と隣に、幅 w の良い数列はきっちり隙間なく整列するので、とりあえず最大の W を L...R の範囲内に見つけて、その左右に W 未満で範囲に収まる最大の w を再帰的に求めていけばいいように思う。考察半分実装半分でどちらもやや難しくやや大変だから、普段より高めの 450 点だったかと思う。22 分かけている。ビット演算で何かをやろうとしてあきらめて 60 通りの全探索に切り替えるまでに時間を使った。■E 問題「Weighted Tic-Tac-Toe」。メモ化再帰でとりあえずやってみたら通りました。盤面は３進数で。Takahashi と Aoki を区別するために手番を知りたくなって、どうやって知るか困ったけど、残りの白マスの偶奇で判別できた。メモ化関数の戻り値の仕様次第では二人の名前を区別する必要がないと思うのだけど、そう期待して実装を始めたのだけど、勝者の名前を返すような仕様にしてしまったので困ってしまっていた。終了条件が２つあって、一方の条件ではスコアが無関係だからそういう仕様に誘導されてしまった。24 分かけている。かけた時間から判断すると、D と E がどちらも 450 点だったのはまこと適切だったと思う。■F 問題「Subsequence LCM」。解けてないよ。愚直解法で TLE×14/AC×23。A の中の同一要素をまとめて処理すると TLE×12/AC×25。２つだけ AC が増えた。LCM でフィルタしていた部分を GCD で判定するようにして不用意に大きすぎる値を生み出さないようにも注意したけど、たぶんそれによる改善はあんまりない。これ以上のアイデアはない。■■■D 問題。最初の提出 #52331543 はせっかく定義した IJ 関数が一度しか呼び出されていなくてもったいないので、それを LR 関数として再定義してスクリプトの後半でも利用するようにした。提出 #52388999。16 行くらいあった後半部分が３行になった。while 文が２つある構成は同じだけど、ループの本体が関数を呼び出すだけの１行になった。各所で読んだのだけど、セグメント木についてはまったく頭に浮かびませんでした。セグメント木の図を思い浮かべれば問題の理解が早かったと思う。でもそれが思い浮かんだ時点でもう問題を理解してるよね。oox の繰り返しを必要な長さ出力するだけだった。だけど各 i についてそのつど判定する方が簡単だったのでそのように。■B 問題「Farthest Point」。距離の比較をするのにルートはいらない。Ruby には Math.hypot (sqrt をとる) の２乗の値を返すメソッドがあると思ってリファレンスを見たけど見つからなかった。たぶん Complex#abs2 のことが頭にあったのだと思う。解法は愚直総当たりで最初に見つかったものを答えにする。素直に書けば「番号が小さいもの」という条件は自然に満たされる。■C 問題「Colorful Beans」。色でグループ化してグループ内の最小値の最大値を出力する。要は悲観主義者が最もましな選択肢を選んだ場合がどうなるかという話。この C 問題まではプログラミング言語の扱いが問われている。やりたいことが書けますかと。Ruby で参加しているなら、C 問題は Array#group_by を知っていますか、という問題だった。■D 問題「Medicines on Grid」。グラフですよね。S と T と薬のマスを頂点として、同じ頂点を２度通らずに S から T へ到達できますかという問題。これは訪問済み頂点を記録して DFS でやろうか。そして頂点間の繋がりがグリッドで与えられていて、探索をしなければ明らかにならない２段構えになっている。最初はきれいに２段に分けて解こうとしたんだけど、面倒くさくなった。最初のグリッド探索のついでに到達可否の判断をしてもいいじゃないか。プライオリティキューを使わずにテキトーにキューに探索地点を追加してエネルギーを記録していった。これに 50 分くらいかけたんですよ。それはダメ。■E 問題「Minimize Sum of Distances」。全方位木 DP。頭が破壊されました。こういうのは終了したあとでじっくり落ち着いて書きたい。終了３分後>提出 #52114566 (RE)。頂点番号を１始まりのままにしていたのに、0 から N-1 を処理対象にしてしまったせいでエラーになっている。終了 13 分後>提出 #52115938 (AC)。結局惜しくはなかった。今日になって全体が見通せる状態でイチから書いたもの>提出 #52179331 (AC)。最初からこれがすらすら書けないのは理解が遅いってことだよ。.. (終端を含む) に代えて ... (終端を含まない) を使うこと。要するに、長さ１の部分文字列を表現する方法が確保されているかどうかが WA と AC を分けている。一般的な文字列検索と正規表現検索との違いで顕在化しがちな問題として、特定の位置の空文字列を表現する方法があるかどうかというものがある。普通のテキスト検索では長さ０の文字列を探すことも見つけることもないので、表現能力の不足に気がつけないことがある。C++ のイテレータが開区間ではなく半開区間なのは、こういう理由からもよくできてるなと思う。いいものはどんどんまねしよう。そしてこれはトリビアだけど、サイズ N の配列 A があるとき、A の末尾の要素は A[N-1] であり A[N] の読み取りは不正だけど、A+N が A+N-1 より大きいことが C 言語の規格で保証されているらしい。でないと範囲が表現できないもんね。■C 問題「Ideal Holidays」。配点が +50 の 350 点ということでやや難しめだと予想できる。実際その通り。予定が A+B 周期で何日目に当たるかを求めてソートして、順番に各要素が休日の１日目にあたると仮定して N 個後ろの予定が A 日目までに収まっているかを判定する。提出直後に同じ日に複数の予定がある場合に正しく判定できないことに気が付いたのだけど、今見ると制約によって重複が排除されていた。優しい。そして今一度よく考えると、D%(A+B) したときに重複が生まれる可能性がある。重複する予定が３つあったとして、最初に処理する予定に限って正しく判定ができるので、結果的に問題がなかったのだ。■D 問題「Popcount and XOR」。C は最大で 60 個のビットを持っており、立っているビットを X または Y のどちらかに割り振る。割り振るのはどちらでも良いが、popcount(C)<a+b のときは C のビットが立っていない位置で X と Y の両方にビットを割り振って打ち消し合わせる必要があるので、a と b の大きい方に 1 のビットを割り振るのがよい。最初に WA×1/RE×1 を出したが(#51837959)。７分後に AC (#51842648)。両方の提出でやっていることは同じ。ただ、RE/WA を出した方では、不可能なケースを最初に判定するようにしていた。一方の AC 提出の方では、操作をしたあとで、結果が満足しているかどうかで出力を切り替えた。要するに、不可能なケースの判定に漏れがあったのだ。おそらく C の０のビットが a, b の大きさに対して不足している場合を弾き損ねていた。最初に提出する前に不安はあった。だから普段書かない assert、……はないから raise を埋め込んで前提が間違っていないかを確かめていた(その結果 RE が出ている)。残念。■E 問題「Set Add Query」。所要時間によれば CD より簡単でしたよね。まず、各時点での集合のサイズというのが操作をシミュレートすることで予め求めておける。次に、各 x (1≦x≦N) について集合に含まれていた区間を調べる。これはクエリを順番になぞりながら値 x からクエリ番号の列を逆引きできるように記録をとればよい。クエリの列から２つずつ取り出したものが x が集合に含まれていた区間。■今回は水 diff と青 diff が問題セットに含まれていなかった。今日の自分は緑 diff 以下の簡単な問題に滅法強いマンとしてレートを稼いでいる。仮にここに水 diff の問題がプラスされると、水 diff の問題にはそこそこ時間がかかるので、水 diff 以下の問題に滅法強い人にタイム差をつけられて相対的にパフォーマンスが下がる。さらに青 diff の問題がプラスされると、自分は青 diff の問題は時間内にほとんど解けないので、青 diff が解ける人に点差をつけられて、やはり相対的に自分のパフォーマンスが下がる。しかし水も青もなかったから、自分を含めて黄 diff が解けないグループがひとまとめにされて、緑 diff の問題で優劣が判定された。それで青パフォをもらうのは、なんだかなーだよね。