require 'faster_prime' しているものを見つけた。なにそれ知らない。■E 問題「Last Train」。これは精進。パラメータが多くて頭が壊れてしまった。解法はすんなり出てくる。ゴールの N に到着する最も遅い電車を始点にしてプライオリティキューでダイクストラ法をする。しかしパラメータが多いのと、最短ではなく最遅を求めるというので、普段と勝手が違って無限にバグを生み出し続けて時間切れになってしまった。キューに入れるのは時刻と街のペア。たくさんあるパラメータはキューに入れる次の時刻を計算するために使う。あとはがんばって頭の中を整理すれば答えは合う。だけど昨日は、列車の運行を逆向きにたどっていることが合わさって、出発時刻と到着時刻の前後関係がどうあるべきなのかとか、判断をするその時刻に k 項ある等差数列の先頭末尾どちらの数字を使うのかとか、およそすべてのポイントで間違えた。■F 問題「Black Jack」。これも精進。昨日も今日も WA を出したがやっと AC が出た。まず、ディーラーの値 y が L≦y の範囲でどういう確率で分布しているかを知るために 0 から N まで DP をする。E 問題もそうだったけど、この問題も考えることが多くてこんがらかる。y<L の範囲ではサイコロを振るけど、L≦y の範囲では振らない。今 DP で求めようとしているある場所にいる確率というのは、同時に、サイコロを振って次の場所にいる確率を求めるために使う値にもなるのだけど、L を境界として両者が異なる値を取るということ。そこをきっちり区別しなければいけない。ところで、サイコロは D 面あり、DP のためには D 個の値の合計が知りたくなるが、愚直に合計するには D の数が大きすぎることがある。こういうことを１つのループの中で全部考えながら整理するのは非常につらい。今回も evall のとき(20240128)と同じように class を使った別解(#50640033)を書いた。解答の後半は前半とは逆に N から 0 に戻る逆順の DP をした。N にいるときがスタート。サイコロを振れば必ず負け、サイコロを振らないときは y=N の場合を除いて勝つ。y=N の場合の確率は前半の DP ですでに求めている。後半の DP でもサイコロを振った場合の勝率を求めるために D 個の値の合計が必要になるので、前半と同じ class を使って楽ができる。そのクラス(LastNSum)を読み直していたら、@first が完全に無意味なことに気がついてしまった。pop 操作があるなら意味があっただろうけど、ないのでいらない。■自分のすべての提出。レート遷移は知らない。どれだけ減ったかなんて知りたくない。x に隣接するいくつかの頂点からなる（空でも良い）集合 S であって、∑y∈SWy<Wx であるものを選び、S に含まれる頂点それぞれに 1 個ずつコマを置く」のシグマを見落としていて、Wy<Wx なるすべての y∈S にコマを配置できるものだと思っていた。残り 10 分でこの思い違いは厳しいが、幸いにもある頂点を選ぶ選ばないの愚直２乗 DP が許されていたので間に合った。うれしい。何番目まででいくつ選んだときの最大がいくつという DP が求められていたら無理だった。解法は、W が小さい頂点から順番に答えを計上する。それは配置されているコマ数×倍率。倍率を決めるために W が小さい頂点から順番に DP をしているし、ある頂点の倍率を決めるためにも W 未満の範囲でまた DP をしている。■自分のすべての提出。C 問題が解けていないことを除けば上出来。コンテスト成績証。1400 に復帰しました。1500 にもう一度のせて青を窺いたいところ。■C 問題。提出 #50395575 (C++ / AC / 637 Byte / 93 ms)。提出 #50396690 (Ruby / AC / 259 Byte / 66 ms)。Ruby が速すぎる！ コンテスト中にこれが通せないのはお前が抜けてるからだってはっきりわかんだね。■C 問題。Ruby で最初の AC であるこちらの提出 #50356929 を見ると、18 行目の
uniq! がポイントかなと思った。自分の TLE 提出である #50356164 が３行目でやってる文字列置換も目的は同じだけど、やり方が拙くて不十分。自分は経路の冗長性を取り除こうとしているが、経路をたどった結果の到着点の重複を取り除くことで冗長性を除くべきだった。だけどそのときは方法が思いつかなかったんだよ。理由もわかる。重複を取り除くためにはいったん配列などに溜めて並べて比較する必要がある。だけど自分の解答の構成はループを回して逐次的に移動先を更新していた。同時には１つの到着点しか存在していないのだから、それらを比較して重複を取り除くという発想が自然には出てこない。全体を俯瞰して最適な構成を考えることができなかったのは、問題の理解が浅かったからにほかならない。残念だね。|XB-AY| = 2 の式までは出ていた。しかし探索ができる制約ではなく、そこから何も手が出なかった。高校数学の演習課題でよくあったパターン。手段は授業で教わっているので、ヒントをもらえば最後まで書ける。だけど最初のとっかかりが何もなくて途方に暮れる。それはつまり、知識はあれども理解するには至っていないということなんだろう。そういうようなことが『技術の創造と設計』(畑村 洋太郎) などに書いてある。ボロボロの毛皮を、裸体の上に纏うもの 忌み鬼、マルギットの装束」。すべての防具を外しても胸と股間を覆う布は残るのだけど、このマントを身につけると、逆に胸の露出が増えるのだ。なにせ「
裸体の上に纏うもの」だから。横乳探しと下乳探しが捗ります。防御力なんてどうでもいいんです、HP さえあれば。■■■武器について。筋力が 60 に達したのでひとまずこれを上限とした。これ以上上げてもごく一部の重厚な武器にしか恩恵がないし、それよりは装備したくなるかっこいい武器を装備するためにパラメータを振りたいなと。そういう武器っていうのは筋力によりすでに十分な補正を受けていて、それでいて技量知力信仰に振れば振っただけ補正値が増える、これから伸びる武器なので、レベルアップの目的になり、目に見える成果にもなる。そういう武器っていうのが、夜と炎の剣、フランベルジュ、冒涜の聖剣、黄金律の大剣、剣接ぎの大剣、神狩りの剣、エストック、血のヘリケー、アステールの薄羽、落とし子の星々、ホスローの花弁あたり。ファンシーな例外があるけど短剣と斧と槌とフレイルと鞭と拳と爪を装備したくはならないな。神秘武器が入ってるけど神秘まで振る余裕はないかな。それを除くと夜と炎の剣が最後に装備できる武器になりそうで、ひとまずそこがレベルアップの目標。■遺灰について。現在のお気に入りは夜巫女姉妹。しっかり付いてきてくれるところがパーティーっぽくて良い。とんがり帽子とネコミミ帽子がずるい。ずるいというのは、見え見えの萌え記号であってあざといんだけどその魅力にあらがえるはずがない必勝のデザインがずるいという意味です。かわいい声が漏れ聞こえるのも良い。不意に押し殺した声が聞こえてくるん。もっと被弾させていじめたくなる。声といえば、一番良いのはハイータさん。２番目くらいにヒロイン力が高い。すごく……あられもない感じがして心を奪われます。「ブドウ」を食べてえずいていた人だよ。■■■@2024-03-03 やっとマレニアを倒した。何日も詰まっていて、他のゲームをやりたくもなったんだけど、今やめると次にやるときはもっと難しいのに決まっているので、日に数回だけ挑戦することを続けていた。産まれ直しで体力を 45 から 60 に増やして、左手にツヴァイヘンダー、右手に神狩りの剣を持って。二段階目にいけたのが今日で２回目。体力を吸われるから一気に優勢に持ち込まないと倒しきれない。どれだけエスト瓶を持っていても敵を回復するのに使っているようでは勝てない。そういうミスが許されない操作は極めて苦手。おおざっぱなんだよ。防具は重さに対して物理カット率が優れている貴腐騎士装備一式で。体力を増やすよりダメージを減らしたい。ところで、二刀特大剣の L1 攻撃は出が遅くて痛み分けになりがち。ステップで間を取られて片方が空振ってダメージが半減することも多い。だったら神狩りの剣を両手持ちしてもそんなに実ダメージは変わらないのではないかと思った。そうしたらなんとも戦いやすい。相手の攻撃の出端を一方的につぶせる、ローリング回避後にどんどん差し込んで怯ませて攻撃を中断させられる、怯んだ相手に R1 攻撃がつながる、攻撃が続くので体勢崩しからの致命チャンスが何度も生まれる、といいことずくめ。両手持ちにしたら２回目で倒せた。体力を吸われる仕様から遺灰が機能しないこともあって、一対一で集中して向き合える大満足のボスだった。■サカサカサカッと切先でほじくってくる攻撃憎らしいよね。音と光でしっかり予告してくるんだけど、なんなら予兆の前から間合いと直前の行動から、あ、来るな、と７割くらい予想して待ち構えてるんだけど、予兆を見てから攻撃を置いておいても無傷で突進を遮れるわけではない(二刀特大剣の L1 攻撃です)。ローリングでの回避も、離れるように転がると３番目の判定に引っかかる。すれ違うように回避しないといけない。だけどそれが難しいのは、HP を吸収されたくないから、攻撃することよりも攻撃を食らわないことを優先したいから、距離をとって大きな隙に確実にダメージを与える戦法を選んでいるからなのであって、それを咎めてくるこの攻撃の餌食にされるのは、まあ、憎らしいよね。だけど、予想ができて、予告があって、対処法も少なくとも３通りはあって(先制攻撃、前ロリ、パリィ)、あとは自分がうまく行動できるかだけなので、食らっても清々しいということは言える。■前の方で「まだマルギットとストームヴィル城を放置している」と書いたけど、今日ストームヴィル城に向かったら「忌み鬼、マルギット」の祝福がすでに現れていて戦闘ができなかった。実は「忌み鬼、マルギット」のトロフィーがすでに取得済みなのは知っていて、日付とスクリーンショットは「破片の君主、モーゴット」と完全に同一なのだった。どういうことなの？ ドロップアイテムの「お守り袋」も、どちらか最初に倒した方からもらうことになっていたりする。二人は同一人物なの？ それを言うとアルター高原だかローデイルだかでまるでモブのような大きさで現れて戦闘になったマルギット系のリスポーンしない敵がなんだったのかという疑問も湧く。どういう設定があるのか。忌み子、忌み角、忌み潰しについてのテキストは読んでいる。マルギットとモーゴットの位置づけと役割に確信がない。
PS5 もアップデート次第であって、いつまでこうかは知らんけど」と書いて危惧していた通りのことが起こった。ログインしていないと何の役にも立たない Welcome という項目が起動して最初のフォーカスを得るようになっている。ゲームの続きがしたいのに、ゲームから気を逸らせるあれやこれやのゴミを突っ込んでくる愚かさ。
+ で区切ってみる。+ の左にある数字の数と、+ の右にある数字の数がわかれば、主客転倒で + で囲まれた数(式)の寄与がわかる。次に考えるのは、範囲が + で囲まれた内部に端を発して外部に出ていく場合。範囲の内外で数字がちょん切られるので扱う値が変わってくる。だけど範囲の一方の端を決め打ったときの値とその寄与は同様に求められる。範囲の両端が + の内側にある場合の寄与は、これは累積和の問題として単独で D 問題あたりにでもなりそうな難易度の問題。ここまで触れてこなかったけど、+ で囲まれた内部は単独の数字ではなく * で連結された積の場合がある。ここまでと同じように * で分割して左右からの累積和(累積積？)で全体への寄与を求めるんだけど、このあたりからワーキングメモリが枯渇してきて全体を把握するのが困難になる。スラッシングというのかな、何をするにも復帰に時間がかかり、間違えて手戻りが発生し、ちっとも先に進めなくなる。最終的に自分はクラスを使って問題を分離して個別に対処することになった。そうするとあるレベルで考えているときに別のレベルのことを考えずに済む。メソッドを呼んで別のレベルの処理結果を得るだけにすると、大きくなりすぎたスイッチングコストがまるまる節約できる。■提出 #49805072 (G 問題 / AC / 1554 Byte / 825 ms)。サンプルが通りさえすれば他に特に罠はなかったみたいだけど、答えの突き合わせに C++ で提出が早かったこちら(#49712435)を使わせてもらった。実行結果にしか興味はなかったけど、ちらりと覗いてみた solve 関数のシンプルさがすごかったよね。しかしあまりにも最適化されすぎていて、冗長さが足りなくて、自分には書けないし理解できない。そんな簡単そうに解ける問題じゃなかったよ。この構成をあきらめたから、クラス化による問題の整理分割に行ったのだ。■コンテスト成績証。自分のすべての提出。ABCDE の５完でぎりぎりの青パフォ。もう書いたけど、これで上がるのは現在のレートが下振れてるだけなんよ。■G 問題。X で(自賛を)見かけたので探してみたこちらの提出 #49757867 (tanakh さん / Rust)。class を使って構造化するならこのレベルまで突き詰めて抽象を取り出して汎化したいよね、というお手本。あと変数名も適切でかっこいい。累積和のことを prefix sum と呼ぶこともあるみたいなので、今回のように色々な累積和を扱うときにああいう呼び分けはあまりに適切。■■■G 問題。お手本にならって再構成してみた。提出 #50091522 (TLE×7)。残念 TLE。一応、数字の列を１桁ずつ分解してオブジェクトを再帰的に構築するのは避けて、* と + で分解した数字の列からループを回してオブジェクトをひとつだけ作るようにしたんだけど、演算(+ と *)のたびに新しいオブジェクトを作るのがまだまだ負担だったか。前回の提出では + の数だけオブジェクト数が節約できている。あと eval も重い。だけど evall という問題名だから eval したくなるのはしかたないよね。■提出 #50102025 (AC / 1127 Byte / 1759 ms)。通った！ ネックは gsub だった(gets.gsub(/\d+/){ "Num.from_s('#$&')" })。たとえば入力が最長の１メガのとき、演算子と数値が半々なら１桁の数字が 500 キロ個ある。gsub メソッドが入力の 1 を Num.from_s('1') に置き換えるなら、変換後の文字列長は８メガになる。そしてそれを eval する。遅い。Num.from_s メソッドを１文字のローカル変数にキャッシュすることで文字列の全長を抑えたら、だいたい倍くらい速くなって TLE を免れた。ちなみに Object.const_missing を使うことでさらに縮めるアイデアもあった。1 や 123 を N1 や N123 に置き換えるのだ。だけど汚い方法でありながらタイムの改善が微々たるものだったので不採用にした。+ メソッドと * メソッドをそれぞれ +=、*= メソッド相当の実装にするアイデアもあった。これもコードを歪める一方で大した改善ではなかったので不採用。せっかくきれいに再構成しているのだから、ダーティハックはお呼びでない。ABC との一致を確認するだけかと思ったら、空文字列も拡張 A 文字列だって書いてある。じゃあ squeeze した文字列が ABC の中に見つかればいいかと思ったら、A、B、C、AB、BC、ABC は ABC の中に見つかるけど AC が見つからない。これは罠だ、実に示唆的な。■C 問題「Lining Up 2」。配列の添字と値を使ってリストを作る。そしてリストを順番にたどって出力する。■D 問題「Cheating Gomoku Narabe」。今回の実装枠かな。この提出 #49483745 (AC) を見てもらうと、29 行目から 68 行目まで使われていない変数が定義されている。てっきり斜めに揃えるのもありなんだと思っていたら、縦横の並びしか考えないんだって！ 無駄に実装時間を使わされたぜ。判定は尺取りで。■E 問題「Bad Juice」。パリティの問題だってのはわかる。どこにヒントがあるのかも知っている。この日(20170620)の日記からリンクしている論理幼女のページだ。「超難問論理クイズ「2人の幼女とチェス盤の部屋」が本当に難しすぎた - 明日は未来だ！」。コンテスト終了後にじっくり読んで提出したら off-by-one エラー(#49513582)を出してから AC (#49513739) だった。提出時刻を見ると最初に提出するまで 11 分しかかかっていない。コンテスト中の時間のプレッシャーの中で新しい知識を仕入れるところから始めて AC まで持っていくのは無理なんだよなあ。■F 問題「Usual Color Ball Problems」。コンテスト中は E よりこちらに取り組んでいた。時間が厳しそうで難しいデータ構造が必要になるかと思いきや、必要なデータを整理して更新していけば順番に答えが出てくる。これも尺取りか。提出が間に合わなかったのは実装が完了してサンプルを試すときまで違う問題を解いていたことに気がつかなかったから。残り数分で軌道修正はできない。しかし落ち着いて考えれば修正でなんとかなる範囲だった。扱うデータは 箱数 と 球数 と 色ごとの球数。あとは C 数列を見ながらがんばってボールを数える。何色のボールが何箱確保しているかがわかれば、答えるボールの数が決まる。箱数×K とその色のボールの総数のうち小さい方。箱数が M を超えない範囲で尺取りをしながら C 数列をローテーションしながらある色が新しく箱を確保したり手放したりしたときに球数をまとめて増減する。■６完が狙える問題セットで４完は残念が過ぎる。ああ繰り言。Since p/q - a/b < c/d - a/b = 1 / bd」の左辺が 1/bd より小さくなる部分がわからない。いや……わかった。そうかと思ってさっき見たときは比較するものを間違えていた。もういちど 116 ページにある木の図を確認したら、隣接する２つの分数は差が 1/bd になっていた。「なっていた」ではなくいついかなる場合でもそうなることを示して理解しろって話ではあるんだけど、つまりそうなるような操作をしているはずなんだけど、ぼんやりなので操作と結果が繋がりません。■本読みを再開したら、差が 1/bd になることが次の 117 ページに書いて示してあった。■「２つの素数」っていうのは、かつて AtCoder でよく見られた 10**9+7 と、もうひとつは 10**9+9 が使われていた。あれって双子素数だったんだ(知らなかった)。どちらも 10**9 をちょっとだけ超える数だから、掛けると 10**18 を超えるけど 60 ビットは超えないみたい。使い勝手のいい数だ。