/ 最近 .rdf 追記設定本棚

脳log[2024-03-02～]

最近ひとつ現在へひとつ過去へ

2024年03月02日 (土) [AtCoder] 今日は ABC343 があった。では ABCDE のふりかえりを。■A 問題「Wrong Answer」。言われた通りにやる。だから答えを 0..9 の範囲で探したけど、２つの数字を選んだら必ずそのうちの１つ以上が答えになることには気がつかなかった。■B 問題「Adjacency Matrix」。B 問題からグラフかとびびったけど、グラフ問題を解くために隣接行列形式のグラフ表現に慣れておきましょうね、という問題だった。■C 問題「343」。N が 10**18 以下の制約。列挙はできないなと思ったけど、平方数なら列挙できるかな、いやできないなと思って、もう一度問題を読んだら立方数だった。立方数なら列挙できる。脊髄反射をやめて問題を読もう。読んで頭に入れよう。■D 問題「Diversity of Scores」。ハッシュ表で数えます。■E 問題「7x7x7」。制約の元になる数字は７と小さいけど、これが何乗にもなるので制約の厳しさが見積もりにくい。結果的にはがちがちに厳しくはないけどゆるゆるでもないという制約だった模様。自分の AC 提出はちょっとだけ工夫した脳死愚直解で 1892 ms だったけど、同じ Ruby で 81 ms の提出がある。AC が早い順に 81 ms、319 ms、1555 ms、1892 ms となっている。おかしくない？時間をかけたほど出来が悪いっておかしくない？自分の工夫は総当たりする範囲を限ったこと。１つめの立方体は C(0,0,0) で決まり。２つめの立方体の１つめの軸は 0..7 の範囲で網羅できる。２つめの軸は１つめの軸以下の範囲に限って良い。３つめの軸は同様に２つめの軸以下に限る。３つめの立方体の置き方をどうするか。最適な置き方がわかるなら全探索などしていない。V3 がゼロか正かで場合分けをして、ゼロなら１つめの立方体と重なったり重ならなかったりする範囲を列挙したが、２つめと重ならない範囲とアンドを取っても良かったか。V3 が正の場合は１つめと２つめの立方体の両方と重なる範囲を列挙した。あとは空間に１、２、３とマーキングしていってそれらの個数が V1、V2、V3 と一致しているかを確かめた。AtCoder Problems によるとこの E 問題が青 diff の一方、より配点が高い F 問題が水 diff だったらしい。報われないなあ。■F 問題「Second Largest Query」。AC がまだなので不確かだけど、セグメント木で２番目に大きい数が求められるのではないか。目当ての数がわかったら、範囲内にある個数を BIT もしくはセグメント木で数えられるなら数えたいけど、数の種類数×範囲の幅≦20万の２乗になるので工夫が必要。内部データを Hash で持つ BIT でクリアできるならお手軽だけど、ある程度運任せになるうえ定数倍も重い。SortedSet があればそれが最適だけどない。A,B-木でも良さそう？だけど以前の実装をこの問題に適合させるのが難しかった。もう内部構造を覚えていない。効率良く insert できるソート列を２本用意したら、delete 操作は実装しないで済ませられる。■F 問題。他の人の提出を覗いてみた。セグメント木だけで個数も数えられるっぽい。そうか、全部の数を数える必要はないのだ。トップ２の値と数だけ覚えておけばいいのだ。セグメント木の使いこなし術が足りていない。■F 問題。サンプル以外 TLE になった。提出 #50851673 (TLE)。完敗です。完全に何かがおかしい。■E 問題。立方体の共通部分を計算で求めると速いらしかった。３次元の重なりをイメージするのは難しいけど、やってみたら区間の共通部分を３回求めるだけだった。提出 #50880639 (AC / 948 Byte / 417 ms)。IX 関数で直方体の共通部分を求めて、V 関数で直方体の体積を求める。どちらもワンライナーで書ける程度の簡単な式。あとはテキトーに６重ループで列挙して簡単な３者の包除。だけどこれでもまだ 417 ms かかっている。81 ms は異次元じゃない？ Yes になり得る入出力を全ケース埋め込んだと思しきこちらの提出 #50846546 が 108 ms……はジャッジ起動後の第一ケースの特異例だとして次点が 57 ms なんだけど、ほとんど遜色がないよ。■F 問題。トップ２の合成をするのに Hash を使った集計をやめてネストした if 式で３分岐×３分岐=９分岐の結果をベタ書きしたら間に合った。提出 #50881793 (AC / 1063 Byte / 1670 ms)。そんなにかわるんだ。他の人の TLE/AC 提出の差分を見ていると、セグメント木の初期化を 2N でやるか NlogN でやるかでも結果が分かれるみたい。シビアだ。

ツッコミを入れる

2024年02月25日 (日) [AtCoder] 昨日は HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）があった。結果は知らない。ABCD のふりかえりと EF の精進を書くよ。■A 問題「Yay!」。人間はひと目で見つけて数えて答えが出せるけど、コンピュータにやらせるのが同じ程度に簡単なわけではない。Ruby には便利メソッドがあるので Array#tally だとか Hash#invert を使って見た目だけは簡潔にできるけども、さもなければ手間を惜しまず堅実にステップを刻むのがいいと思う。■B 問題「Which is ahead?」。人から位置への逆引きインデックスを作っておく。A 問題より簡単では？■C 問題「Many Replacement」。昨日の不調はここから始まっていた。前から順番に置換表を更新していってもサンプルが合わない。それは、連鎖的な変換が考慮されていないから。連鎖的、再帰的ということで UnionFind で解けるだろうとは思ったけど、どうにも無駄に牛刀を持ち出しているように思える。結局置換表を逆順に更新していくことで答えが出せたけど、12 分かかってるんだよなあ。他所で読むまで気付いてなかったんだけど、想定解は置換表(サイズ26)を毎回スキャンして置換する 26×Q≦520万ステップの愚直解法だったんだろうか。そうか、フルスキャンをしても 26 か。■D 問題「Square Pair」。いかにも D 問題らしく、シンプルに効率を求められる問題。苦手な部類。平方数を列挙しようと思ったけど、上限が A.max**2 になるのでためらってしまった。A.max は 20 万。そのループの中で A の各要素について対になって平方数を作るものの存在を確かめるとなると、A.max×N≦20万×20万になる。次は素数を列挙しようと思った。A の素因数になり得る素数は２万個以下。A を素因数分解して奇数個の素因数の積として分類し直すと、掛けて平方数を作る組み合わせは同じグループからの組み合わせに限られる。このように答えの出し方はわかっているが、果たして２万×N で間に合うだろうか。比較的遅いことはわかってるけどとりあえず Integer#prime_division を使った解答を提出してみて、それで間に合っていた。約１秒。他の人の提出を見ていたら `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 操作があるなら意味があっただろうけど、ないのでいらない。■自分のすべての提出。レート遷移は知らない。どれだけ減ったかなんて知りたくない。

ツッコミを入れる

2024年02月17日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#2（ABC341）があった。C 問題難しすぎ。では ABDEF のふりかえりを。■A 問題「Print 341」。問題文が意図的に不親切だけど、曖昧ではないので、指示された通りに出力する。■B 問題「Foreign Exchange」。0 から N-1 まで順番に処理する DP。■C 問題「Takahashi Gets Lost」。500 の３乗を計算してみて不穏な気配はあった。制限時間が長めの３秒だけど足りない。しかし Ruby で通すのが不可能というわけではないらしく、１秒、２秒、３秒程度で通している３つの提出がある。だったらしかたないね。想定解が愚直シミュレーションだとしても、それがだめなときに選ぶプランＢを持っていないのが悪い。F を通したあとに 15 分残っていたら慣れない C++ で書き直したけども。Crystal を使わないのはね、処理系がインストールできないからなんだよね。Windows Vista にどうやったらインストールできるんだろう。Rust もできなかった。■D 問題「Only one of two」。二分探索。最初なぜか二分探索を２段階に分けて実行しようとしていたんだけど、２段階目を書いているときにそれがそのまま１ステップで答えを出せることに気がついた。無駄に時間を使ったね。■E 問題「Alternating String」。反転する区間の内部では操作１の前後で状態は変わらない。BIT などで境界部分の状態を記録すると、ある範囲の境界状態の累積が対数時間で取得できる。添字でバグらせてペナルティ 10 分。■F 問題「Breakdown」。残り 10 分ぐらいで一応の解答が完成したんだけど答えが合わない。条件の２つめ「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 が３行目でやってる文字列置換も目的は同じだけど、やり方が拙くて不十分。自分は経路の冗長性を取り除こうとしているが、経路をたどった結果の到着点の重複を取り除くことで冗長性を除くべきだった。だけどそのときは方法が思いつかなかったんだよ。理由もわかる。重複を取り除くためにはいったん配列などに溜めて並べて比較する必要がある。だけど自分の解答の構成はループを回して逐次的に移動先を更新していた。同時には１つの到着点しか存在していないのだから、それらを比較して重複を取り除くという発想が自然には出てこない。全体を俯瞰して最適な構成を考えることができなかったのは、問題の理解が浅かったからにほかならない。残念だね。

ツッコミを入れる

2024年02月15日 (木) 「「Windows 11 バージョン 24H2」はPOPCNT命令を備えたCPUが必須？　化石レベルでは起動せず - やじうまの杜 - 窓の杜」■今使ってるのは PhenomⅡ X3 だから 2010 年より前だけど SSE4a には対応してるみたいなので大丈夫だな。化石じゃないってお墨付きをもらっちゃった。

ツッコミを入れる

2024年02月10日 (土) [AtCoder] 今日は鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）があった。では ABCDE のふりかえりと G の精進を。■A 問題「Arithmetic Progression」。やるだけなんだけど、step メソッドでうまくやりたかったね。ループを回してしまった。■B 問題「Append」。配列が扱えますかという問題。■C 問題「Divide and Divide」。C 問題らしからぬ制約にびびるけども、対数時間で底にたどりつく。１ステップ当たり２分岐あるのが不安だけど、メモ化再帰でダメなら泣いちゃう。Ruby で最短の提出 #50173926 はループなしの計算で解いている。式の中にビット長が２回出てきているのが目を引くが、意味はわかりません。■D 問題「Super Takahashi Bros.」。最初はステージ１から N-1 まで順番に処理する DP だと思った。しかしワープ土管は先へ進むだけでなく前に戻るパターンもある。D 問題でひっぱり出したくはなかったけど頭を使いたくもなかったのでプライオリティキューを貼り付けた。■E 問題「Mancala 2」。最初は前々回の D 問題 Island Tour のように、変化量をため込んでおいて最後に累積和を答えにするのかと思った。そうではない。操作のたびに箱にあるボールを数えて空っぽにしなければいけない。では愚直に操作しよう。BIT で効率良く処理しよう。自分にはめずらしくコメントが書いてある>#50168931。そうしないとややこしくて間違えると思った。１ループ当たり BIT の操作が最大８回あり、入力と出力のそれぞれで N 回の操作がある。N と M の最大が 20 万のときに、(2N+8M)logN のステップは Ruby では非常に不安。わかりやすさのために処理を刻んだけど、TLE になったらいくつかの BIT 操作をまとめるせこくて間違いやすい節約術が求められていた。幸いにも出してみたら 572 ms で余裕のセーフ。■G 問題「Leaf Color」。まず頂点数１の誘導部分グラフは必ず OK。頂点数２のパスグラフも同色の２頂点を組み合わせて問題なく作れる。３頂点から様子が異なる。２頂点を結ぶパスに３頂点目が含まれている場合、この誘導部分グラフは２頂点の組み合わせとしてもう数えてしまっている。余りの数で答えなさいという出題形式から予想できることだけど、頂点同士の個別の組み合わせ、個別のパスをひとつひとつ考慮して数を数えることは許されない。どういう特徴量によれば計算で数が数えられるのか。ある部分木について、色ごとに端点の選び方の通り数を記録した。あとは DP。ある頂点を根とする部分木について、子と子の組み合わせを数え、根と子の組み合わせを数える。提出 #50189012 (AC / 591 Byte / 1023 ms)。木 DP はコードが長くなりがちだけど、９割方は定型の処理であって、この問題に固有の部分は 20 行目と 25 行目ぐらいのもの。その式が見えるまでは何度も何度も合わないサンプルに苦しむんだけど。やっと見えても最初は TLE (#50187841) だったりした。マージテクが使えるように数える数を工夫して、別口で行っていた集計もすでにある数を流用するようにしたら AC だった。こういう解ける G 問題を得点にしたいなあ。正直、木の問題はボーナス問題だと思っている。自分のレート帯を基準にしてだけど、知っているべきことは全て知っているし、解けない問題はないと思っている。こういう強気の姿勢大事。気持ちが負けていると解けない理由を探してしまって解けるものも解けなくなる。そしてあえて水をさすことを書くと、気持ちだけでは解けない問題は解けないのもまた事実。■F 問題「S = 1」はさっぱりです。これが水 diff ってまじなのですか。青じゃないということは、目の付けどころ次第であっさり解けるタイプの問題なのかな。あっさりとさっぱりは似ているけど通じていないよね。私はさっぱりの方でした。三角形の面積の公式を検索して `|XB-AY| = 2` の式までは出ていた。しかし探索ができる制約ではなく、そこから何も手が出なかった。高校数学の演習課題でよくあったパターン。手段は授業で教わっているので、ヒントをもらえば最後まで書ける。だけど最初のとっかかりが何もなくて途方に暮れる。それはつまり、知識はあれども理解するには至っていないということなんだろう。そういうようなことが『技術の創造と設計』(畑村洋太郎) などに書いてある。

ツッコミを入れる

2024年02月03日 (土) [AtCoder] 今日は日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339）があった。D 問題で無駄に定数倍に苦しんだり、F 問題で多倍長整数によるチートが可能だったりと、Ruby で参加している自分と C++ で参加している人とでは見えている問題が違っているコンテストだった。惜しむらくは F 問題の愚直解法を完成させることさえ時間内には間に合わなくて、損するばかりで得をし損ねたこと。結果は ABCED の５完。ではふりかえり。■A 問題「TLD」。ドットジェイピーを切り出す。split してもいいし、拡張子を取り出してもいい。ライブラリにあるでしょう。■B 問題「Langton's Takahashi」。シミュレートする。添字をループし忘れて１ペナ。■C 問題「Perfect Bus」。累積和の最小値をゼロに合わせたときの累積和の末尾の値。■D 問題「Synchronized Players」。二人の位置をキーにして BFS。……なんだけど、TLE を２回出した。しょうもな。しょうもないのは、コピペによる定数倍の改善。そんなことしたくない。■E 問題「Smooth Subsequence」。１点更新のセグメント木。やりたい操作を考えて、それができるデータ構造を知っていれば、やるだけ。■F 問題「Product Equality」。値が十進1001桁になりうる以外は普通の２乗の DP。案外 Ruby だとそのままいけるんじゃね？と思って愚直解を書き始めたんだけど、時間内には完成しなかった。１の要素を特別扱いすると答えが合い、提出したら TLE にもならなかった。D で無駄に苦しんだ分、F でずるして得したかったけど、取り返せなかった。残念。

ツッコミを入れる

2024年01月31日 (水) 今年に入ってから遅れてエルデンリングをプレイしている。実況動画を見ているときには気付かなかったけど、いびつなゲームだなと思う。そして少なくないクソ要素。何度「おもんねー」と罵ったか。いびつというのは、エスト瓶やスタミナといったシステムが、デモンズソウルをはじめとするステージクリア型のアクションゲームのためにデザインされているところ(実際はデモンズとブラボは草と血なんだけど、そのために敵のドロップアイテムが草と血まみれになったり、攻略のために回復アイテムマラソンが必要になったりするので、ダクソのエスト瓶は発明だったと思ってる。そのエスト瓶が今作では、という話)。これはマップ探索には向かない。序盤が特に顕著だけど、回復回数が５回程度に制限されていて、回復量も短い HP ゲージのさらに半分程度だったりする。敵を１体倒すのに３回４回と斬りつける必要があって、その間に１回２回と反撃を食らい、回復のためにグビグビグビグビとエスト瓶をがぶ飲みすれば、残りの回復回数は１回だ。これでは探索が続けられない。祝福に戻ってリセットすれば回復回数とともに敵も復活している。早々にマップ探索は霊馬を使って敵のあいだを駆け抜けてアイテムだけかっさらっていくのが最適だと学習してしまった。特に聖杯の雫と黄金の種子を広範囲に集めてエスト瓶の回復量と使用回数を高めるのが重要。対策がなされていないわけではなくて、敵の目がないときはダッシュをしてもスタミナが消費されないし(そのせいで武器を素振りしてスタミナ消費を確かめることができなくて)、敵を倒していればいつの間にかエスト瓶の使用回数が回復しているという仕様もある(敵の集団を撃破することで回復するとチュートリアルにあった)。祝福がこれでもかと大量に配置してあったりもする。だけど付け焼き刃のパッチだし、ある目的のためにデザインされたシステムを無効化するシステムであり、いびつだねと感じる。クソ要素がいくつもある。敵集団に蹂躙されて何もできないまま殺されて面白いことある？仕返しに敵を数や圧倒的攻撃力で蹂躙したとして面白いことある？少なくとも後者で鬱憤はたまらないだろうけど、どちらも望んだものではない。注意しても即死する崖下りや落下ポイントも望んだものではない。ひとつふたつならいいだろう。ああ不注意だったなと反省を促されるものだったらいいだろう。だけど、どれだけ注意しても即死する飛び降りアクションを望んではいない。チャリオット。ミケラの聖樹。自分が気持ち良くなることしか考えていない。フェアネスがない。神託の使者たちの遺灰を拾ったけど、使わない。絶対に許さない。知っていればリトライが容易、は美点だけど、最初から雑な駆け抜けを強要されたくない。行為として同じだからってはき違えないで欲しい。そもそも自分はリトライであっても敵を殲滅して進んでいる。後顧の憂いを残しては前進できない性分。だから安全地帯から一方的に遠距離攻撃を浴びせられる、こちらの弓の射程と同等の索敵範囲を持っているのでスナイプできません、後ろに回り込むための迂回路へは落下死に注意しながら飛び降りなければいけない、ただしそこも射程範囲内だからゆっくり狙いを定めていると被弾する、という状況が許せない。駆け抜けを強要するな。次のエリアにいた大量の王族の幽鬼もクソだった。駆け引きがないんよね。クソ攻撃力とクソ体力とクソ強靱でブンブンブン。こっちは 100% 相手の都合に合わせて壁を延々殴るが如し。一回だけならお付き合いもしよう。モブだから復活するんよね。それが何体もいる。駆け抜けを強要するな。あとの不満は、ワールドマップに断崖絶壁が多すぎる。単純に落下死する危険がそれだけ多いということだし(実際よく死ぬ)、ここは通さない、ここは通してやろうという、神の恣意があまりにもあからさまで、その強制手段としての断崖が興ざめでもある。ただ、通さない通さないばかりでなく、迂回路や転送門や人形の転送魔法など複数の経路で各地が繋がっていたのはとても良かった。今はローデイルの地下と雪原を探索してるけど、まだマルギットとストームヴィル城を放置している。自由にマップを埋める楽しみがあるのは良い。ところで、配置できるマップアイコンが 100 個までに制限されてるんだけど、攻略済み撃破済み未撃破の強敵がいるとアイコンを置いていっていたら、この前 100 個を使い切ってしまった。少ないよ。最後に右スティック。自分の PS5 はまだまだ新しい方だと思ってるけど(買ってから半年ちょっと)、カメラがいつもいつでも地面に向かっていく。右スティックをしばけばその時だけは解消するけどすぐにカメラが下を向く。他のゲームではこんなことないので、しっかりデッドゾーンをもうけてほしい。右スティックで思い出したけど、右スティック押し込みによるロックオンもクソ要素のひとつ。なんで目の前の襲いかかってくる敵を無視して攻撃が届きもしないはるか遠方の敵をロックしてんの？しかもそれが無害な獣だったり。スティック操作による切り替え対象から外せという話ではなくて、押し込みによる最初のロックオン対象の選定基準が馬鹿だということ。コントローラーがプレイヤーとシンクロしていない。ゲームシステムに殺されて面白いことなんかねーよ。まだあった。死に方が無様だよね。うるさい。何度も何度もあれを聞かされるのが苦痛だから、一番うっとうしくない音声(若年女性１)を、うっとうしいけど一番ましだという理由で選んだ。■以前にダークソウル３の武器遍歴を書いたので今回も。初期武器であるハルバードをレベル100を超えた今も使っている。今作は目立って強い武器弱い武器というのはなくて、もちろんカテゴリごとに特性が、重さに比例して傾向があるとしても、カテゴリ内では差をつけず横方向に色んな武器があるというのを目指してるっぽい。初期武器が今まで通用しているし、重めの初期防具が余裕で装備できるように持久力を伸ばしたら、特別重い防具を除いてどんな防具も余裕で装備できる。数字のインフレがない。戦技はローレッタの斬撃を付けている。ダイナミックで優美な技と名前だと思って気に入っている。サブの打撃武器としてグレートスターズを２本鍛えている。大きいところと出血が付いているところがいい。初期装備にパリィができる中盾を持っていたのでチュートリアルで試してみて、それ以来パリィは封印してガードカウンターに頼っていたけど、カーリアの返報を付けて以来パリィが楽しい。ぶんぶんパリィが通用してしまうし、早めに置いておきさえすれば持続が長くてよく成立する。武器はこの２種類だけ。他は持ちたいと思っても知力が足りなかったり信仰が足りなかったり神秘が足りなかったりする。それぞれ 12 と 10 と 7 しかない。ステータスを振ってまで持ちたい理由もない。何かある？鍛えるのに大量のルーンと鍛石が必要になるし、ルーンを費やしても鍛石に制約されて一線級までは鍛えられないし、十分に鍛えたところで強武器ということもない。武器を持ち換えるよっぽどの理由ある？魔術は使わない。祈祷は毒の回復だけ。遺灰はたたみかける狼３頭、固定砲台のラティナ、無差別弓兵２体、囮ゾンビ４体、滞空のディーネあたりを使い分けている。ワールドマップで FP の限り無制限に遺灰が呼び出せたらマップ探索に時間をかけてもいいと思えたかもしれないね。目が合ったほぼ全ての人、ほぼ全ての獣が襲いかかってくる殺伐とした世界で、共闘してくれる他者の存在は大いに心強かったろうと思う。ノクローンの星空。写し身の雫の祝福から高台を馬で移動しながら眺めていると、視差というのか、遠景と近景がずれる速度が思いのほか大きい。普通の星空のようにすべてが遠景というわけでなく、すべてが近景ということもないようで、つまり？地下世界なのだから、てっきりプラネタリウムのような星空なんだと思っていた。■防具は勇者の肩鎧が上半身の露出が多くていい感じ。ランタンをつけると肌の光沢が映える。下半身は調香師の腰布が、生足が長く見えて良い。そしてプレイ動画を見ていて知ったのだけど、忌み鬼のマントが他とはちょっと違っている。アイテムの説明文がこうなのだ。「ボロボロの毛皮を、裸体の上に纏うもの忌み鬼、マルギットの装束」。すべての防具を外しても胸と股間を覆う布は残るのだけど、このマントを身につけると、逆に胸の露出が増えるのだ。なにせ「裸体の上に纏うもの」だから。横乳探しと下乳探しが捗ります。防御力なんてどうでもいいんです、HP さえあれば。■■■武器について。筋力が 60 に達したのでひとまずこれを上限とした。これ以上上げてもごく一部の重厚な武器にしか恩恵がないし、それよりは装備したくなるかっこいい武器を装備するためにパラメータを振りたいなと。そういう武器っていうのは筋力によりすでに十分な補正を受けていて、それでいて技量知力信仰に振れば振っただけ補正値が増える、これから伸びる武器なので、レベルアップの目的になり、目に見える成果にもなる。そういう武器っていうのが、夜と炎の剣、フランベルジュ、冒涜の聖剣、黄金律の大剣、剣接ぎの大剣、神狩りの剣、エストック、血のヘリケー、アステールの薄羽、落とし子の星々、ホスローの花弁あたり。ファンシーな例外があるけど短剣と斧と槌とフレイルと鞭と拳と爪を装備したくはならないな。神秘武器が入ってるけど神秘まで振る余裕はないかな。それを除くと夜と炎の剣が最後に装備できる武器になりそうで、ひとまずそこがレベルアップの目標。■遺灰について。現在のお気に入りは夜巫女姉妹。しっかり付いてきてくれるところがパーティーっぽくて良い。とんがり帽子とネコミミ帽子がずるい。ずるいというのは、見え見えの萌え記号であってあざといんだけどその魅力にあらがえるはずがない必勝のデザインがずるいという意味です。かわいい声が漏れ聞こえるのも良い。不意に押し殺した声が聞こえてくるん。もっと被弾させていじめたくなる。声といえば、一番良いのはハイータさん。２番目くらいにヒロイン力が高い。すごく……あられもない感じがして心を奪われます。「ブドウ」を食べてえずいていた人だよ。■■■@2024-03-03 やっとマレニアを倒した。何日も詰まっていて、他のゲームをやりたくもなったんだけど、今やめると次にやるときはもっと難しいのに決まっているので、日に数回だけ挑戦することを続けていた。産まれ直しで体力を 45 から 60 に増やして、左手にツヴァイヘンダー、右手に神狩りの剣を持って。二段階目にいけたのが今日で２回目。体力を吸われるから一気に優勢に持ち込まないと倒しきれない。どれだけエスト瓶を持っていても敵を回復するのに使っているようでは勝てない。そういうミスが許されない操作は極めて苦手。おおざっぱなんだよ。防具は重さに対して物理カット率が優れている貴腐騎士装備一式で。体力を増やすよりダメージを減らしたい。ところで、二刀特大剣の L1 攻撃は出が遅くて痛み分けになりがち。ステップで間を取られて片方が空振ってダメージが半減することも多い。だったら神狩りの剣を両手持ちしてもそんなに実ダメージは変わらないのではないかと思った。そうしたらなんとも戦いやすい。相手の攻撃の出端を一方的につぶせる、ローリング回避後にどんどん差し込んで怯ませて攻撃を中断させられる、怯んだ相手に R1 攻撃がつながる、攻撃が続くので体勢崩しからの致命チャンスが何度も生まれる、といいことずくめ。両手持ちにしたら２回目で倒せた。体力を吸われる仕様から遺灰が機能しないこともあって、一対一で集中して向き合える大満足のボスだった。■サカサカサカッと切先でほじくってくる攻撃憎らしいよね。音と光でしっかり予告してくるんだけど、なんなら予兆の前から間合いと直前の行動から、あ、来るな、と７割くらい予想して待ち構えてるんだけど、予兆を見てから攻撃を置いておいても無傷で突進を遮れるわけではない(二刀特大剣の L1 攻撃です)。ローリングでの回避も、離れるように転がると３番目の判定に引っかかる。すれ違うように回避しないといけない。だけどそれが難しいのは、HP を吸収されたくないから、攻撃することよりも攻撃を食らわないことを優先したいから、距離をとって大きな隙に確実にダメージを与える戦法を選んでいるからなのであって、それを咎めてくるこの攻撃の餌食にされるのは、まあ、憎らしいよね。だけど、予想ができて、予告があって、対処法も少なくとも３通りはあって(先制攻撃、前ロリ、パリィ)、あとは自分がうまく行動できるかだけなので、食らっても清々しいということは言える。■前の方で「まだマルギットとストームヴィル城を放置している」と書いたけど、今日ストームヴィル城に向かったら「忌み鬼、マルギット」の祝福がすでに現れていて戦闘ができなかった。実は「忌み鬼、マルギット」のトロフィーがすでに取得済みなのは知っていて、日付とスクリーンショットは「破片の君主、モーゴット」と完全に同一なのだった。どういうことなの？ドロップアイテムの「お守り袋」も、どちらか最初に倒した方からもらうことになっていたりする。二人は同一人物なの？それを言うとアルター高原だかローデイルだかでまるでモブのような大きさで現れて戦闘になったマルギット系のリスポーンしない敵がなんだったのかという疑問も湧く。どういう設定があるのか。忌み子、忌み角、忌み潰しについてのテキストは読んでいる。マルギットとモーゴットの位置づけと役割に確信がない。

ツッコミを入れる

2024年01月30日 (火) PS5 ではトロフィーの通知を切ってしまった。PS4 で手間であり不満であった、なぜそのトロフィーが得られたのかを知るために、トロフィーを獲得した記念すべき瞬間にゲームを中断してトロフィー画面に遷移するという、そしてゲームによってはムービーを見逃してしまったりするという台無しなゲーム体験が、PS5 では一応改善されているらしい。ボタンを押すとトロフィー通知に追加情報が出るみたいな？すぐに設定で切ってしまったのでよく知らないけど。PS4 でも PS5 でも通知は切るといいよ。あとで、へー、こんなトロフィーをもらってたんだ、というのをテキトーに眺めるくらいでいい。切ればそれがどれだけゲームの邪魔をしていたかがわかるし、再度邪魔をさせる選択も出て来ない。■PS5 のましな点がもうひとつ。電源を入れたときに最後にプレイしていたゲームを覚えていてフォーカスを合わせているところ。画面が出ていなくても✖ボタンを押しておけば直前のゲームが始まっている。PS3 でこれができていたかできていなかったかはもうよく覚えてないけど、PS4 ではできなかった。PS4 はゲーム機であることを忘れたコマーシャル端末だった。PS5 もアップデート次第であって、いつまでこうかは知らんけど。■トロフィーから意義を奪うひとつの要因があの恣意的なパーセント表示。なんの指標でもない。無視すべき数字が添えられていることがトロフィーから目をそらす理由になる。ないほうがまし。■■■@2024-10-13「PS5 もアップデート次第であって、いつまでこうかは知らんけど」と書いて危惧していた通りのことが起こった。ログインしていないと何の役にも立たない Welcome という項目が起動して最初のフォーカスを得るようになっている。ゲームの続きがしたいのに、ゲームから気を逸らせるあれやこれやのゴミを突っ込んでくる愚かさ。

ツッコミを入れる

2024年01月28日 (日) [AtCoder] 昨日は ABC338 があった。当たり前に解ける問題を当たり前に解いてレートが上がっても微妙な気持ち。それって現在のレートが下振れているだけだから。F も G も解けない問題ではなかった。F はどうやって典型に落とし込むかだと思った。@chokudai さんが以前に書いていたように、負辺を前処理で取り除けると思う。それができるための負閉路がないという制約。必ず終わりがある。だけど前処理がすっきり見通せないから、大変でもすることがわかりやすい G 問題に、時間内は主に取り組んでいた。G を通してからふりかえりを含めて書き足す予定(以降更新されないフラグ)。■E 問題ではこの問題を思い出していた。ARC076-E「Connected?」(20211112)。昨日の水 diff に対してこちらは黄 diff だけど、同水準の知識で解ける。■■■@2024-01-30 フラグを折っていく。ABCDE のふりかえりと G の精進を。■A 問題「Capitalized?」。Ruby には String#capitalize メソッドがあるので……。だけど問題の定義と Ruby のメソッドの仕様の整合を確かめる手間で、もっと曖昧さが少ない低レベルのメソッドを使うことも現実的な選択肢ではある。低レベルとは言えないけどよく知った正規表現で書いた。文字コードを見るなら特定の１ビットで判別できる。■B 問題「Frequency」。フリークワンシィ。集計してから最初の文字を見つけた。うっかり１ステップで書こうとすると苦しむかも。max_by がぴたりとはまるらしく(#49693254)、苦しまずに解決する方法がちゃんとあったようだけど、Enumerable#max_by の暗黙の仕様に頼っていたりして(「該当する要素が複数存在する場合、どの要素を返すかは不定です」というのが明文化された仕様)、自分は思いつかなかったな。それは言い訳で、添字をペアにして比較のキーにすれば仕様に則って確実に１ステップで答えが出せた。■C 問題「Leftover Recipes」。一瞬詰まった。DP かと思わせて総当たりができる。一方の個数を決め打つ総当たり。ゼロ除算は避ける。■D 問題「Island Tour」。環状に繋がった島がある。ツアーで島から島へ移動するルートは右回り左回りの２通りが考えられるけど、どちらが右回りでどちらが左回りかはどうでもよくて、橋が１つ封鎖されていると必ず一方に固定される。封鎖する橋を決めたときの影響を単位時間で求めるために、影響の変化量を記録してその累積和を観測する。一発で通ったけど添字でバグらせなかったのはただの運。慎重に書いて祈って提出した。■E 問題「Chords」。スタックです。頂点を順番に見ていって出て行く弦、入ってくる弦を管理して交差を判定する。変数名で困った。arc は弧だから弦は何だろうと。それが問題名の chord なんだろう、きっと。自分では string かなと考えたけど、あまりに紛らわしいし、弦違いっぽくもある。code や cord に比べて余分な文字がくっついてるのがへその緒っぽさを感じさせるけど、あれは umbilical cord らしい。エヴァで聞いた音。さっき類似の過去問を紹介したけど、その問題を解いたときに「ということに気がついたら、あとはなんとかなる」と書いていた部分がなんとかならなくて２回も WA も出したのはどうかしている。あほになってんじゃねーの。■G 問題「evall」。することはすぐにわかる。それをするのがすんごく大変なだけで。考える範囲は両端が数字であるような範囲。まずは `+` で区切ってみる。`+` の左にある数字の数と、`+` の右にある数字の数がわかれば、主客転倒で `+` で囲まれた数(式)の寄与がわかる。次に考えるのは、範囲が `+` で囲まれた内部に端を発して外部に出ていく場合。範囲の内外で数字がちょん切られるので扱う値が変わってくる。だけど範囲の一方の端を決め打ったときの値とその寄与は同様に求められる。範囲の両端が `+` の内側にある場合の寄与は、これは累積和の問題として単独で 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` に置き換えるのだ。だけど汚い方法でありながらタイムの改善が微々たるものだったので不採用にした。+ メソッドとメソッドをそれぞれ +=、*= メソッド相当の実装にするアイデアもあった。これもコードを歪める一方で大した改善ではなかったので不採用。せっかくきれいに再構成しているのだから、ダーティハックはお呼びでない。

ツッコミを入れる

2024年01月22日 (月) [AtCoder] 精進。前回の ABC337-G「Tree Inversion」。diff は F 問題より低いことになっているらしい。問題文が読めて理解できてどういう情報を集めればいいかが把握できれば、することはおなじみではある。把握できないし、実装にも時間がかかるんだけど……。さてさて。ある頂点 v を根とする部分木について、v を含むそれぞれの頂点がそれぞれの部分木に含む自身より小さい頂点の数の合計を g(v) とする。特に v が全体の根であり部分木にすべての頂点を含んでいるとき、f(v) と g(v) が等しい。あとは……解けるな？頂点 v が０個か１個の親 p と０個以上の子 c を持つなら、最初のステップで g(c) を、次のステップで親子を逆転した木について g(p) を求めたら、v-1 を足して f(v) にする。g(v) を効率良く求めるためには、DFS の行きと帰りで自分より小さい頂点の数の差分を求めることにして、その記録に BIT を使えば累積和の更新が対数時間で済ませられる。■提出 #49587091 (AC / 870 Byte / 913 ms)。実装するのにとくに罠もなく、しかし時間はかかった。ふりかえりつつ、立ち止まって先を考えつつ、じっくり丁寧に書く必要があった。手に対して頭の方が遅れをとっている。それでいて手が書く量も 870 バイトと少なくない。時間がかかります。

ツッコミを入れる

2024年01月20日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2024#1（AtCoder Beginner Contest 337）があった。自分のすべての提出。繰り言は言うまい。以下 ABCD のふりかえりと EF の精進を。■A 問題「Scoreboard」。ループを回して集計します。そんな原始的な道具は使いたくないので目的に適った便利メソッド(transpose と sum)を呼び出します。■B 問題「Extended ABC」。String#squeeze で `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 数列をローテーションしながらある色が新しく箱を確保したり手放したりしたときに球数をまとめて増減する。■６完が狙える問題セットで４完は残念が過ぎる。ああ繰り言。

ツッコミを入れる

2024年01月14日 (日) [AtCoder] 今日は ABC336 があった。コンテスト成績証。自分のすべての提出。ABCD の４完でレートは横ばい。EF がどちらも難しかった。ではふりかえりと F の精進を。■A 問題「Long Loong」。ループを回せますかという問題。■B 問題「CTZ」。count trailing zeroes. zero の複数形は -s と -es が並記してあるのでどっちでもいいのかな。じゃあト・メイトウ式で。文字列化して /0*$/ でマッチさせた。ループで求めるなら、N が 0 より大きく N を 2 で割った余りが 0 である限り N を 2 で割り続けて回数を数える。■C 問題「Even Digits」。去年の年末にこの問題を解くやり方をどこかで読んだ気がする(追記：先週のことだったらしい。「まさかこの発言の一週間後にフラグ回収すると思ってなかった」自分もその発言を読んでいましたよ)。５進数で N を数えて各桁を変換した。他の人の提出を見ると変換に String#tr を使ってる人は全然いなくて、みなさん十進数として再解釈してから×２をしているようだった。それは……かしこいなあ。■D 問題「Pyramid」。本日はこの問題で終了してしまった。書き始める前には、ピラミッドの中心に据える A 数列の値(これが k になる)とその左右にある要素数だけでピラミッドの大きさが決まると思っていたけど、サンプルの１からすでに答えが合わなかった。たとえば中心の隣の要素が中心より２以上小さかったらピラミッドとして成立しない。なので左右から独立に DP をして、左(右)の要素が左方向(右方向)に作れるピラミッドの大きさ＋１を上限とした(もちろん中心の値も上限のひとつ)。■E 問題「Digit Sum Divisible」。桁和の種類はかなり少ない。桁和が固定できると各桁に配置した数字を桁和の余りで分類できるから、並べ替えを考えずに済んで考えるべき状態数が減る。だけど各桁の使用状況と現在の桁和の合計とを状態として、決め打った桁和を目指す DP が書けなかった。それで間に合うかわからないし、持つデータの型と遷移もよくわからない。制限時間 10 秒はすごい。これをどう評価するか。C++ でもそれなりに時間がかかるので定数倍で劣る Ruby ではループ回数に比例して遅れが積み重なって到底間に合わないと見るか、それとも、スクリプト言語に配慮した結果の 10 秒なのか。■F 問題「Rotation Puzzle」。半分全列挙だとどこかのツイートだったようなもので読んでしまった。BFS をするには 20 回の操作回数は多すぎるなあとはコンテスト中に実装してわかっていた。そこから半分全列挙が出て来ない。そうだとわかれば実装するだけなんだよね。提出 #49322044 (AC / 557 Byte / 2792 ms)。配列を Hash のキーにすると答えを間違える。キーにするためにつど文字列化するとコードテストで制限時間をわずかに超える。だから文字列を操作することにしてそのまま Hash のキーに使えるようにしたら間に合った。その後、やってることは同じだけど２つの改善で 891 ms になった(#49349630)。

ツッコミを入れる

2024年01月09日 (火) [AtCoder] Stern-Brocot 木の名前を最初に目にしたのはこのとき。「格子点の数え上げの高速化 - memo」(リンク切れ)。ABC172-D「Sum of Divisors」に関連してだった>20200628p01.06。最近では ABC333-G「Nearest Fraction」に関連して目にしたし耳にした。たまたま今日ページをめくっていた『コンピュータの数学』の 116 ページにも名前と、具体的な木の図と操作が載っていた。その操作はこのときの驚きとともに覚えている。「なにこれ！分数を初めてならった小学生が必ず間違える分数の足し算(通分せずに分母どうし分子どうしを加算する)にこんな意味があるとか！」 Project Euler の Problem 71 Ordered Fractions に関連してだった。「Project Euler Problem #71 | KeyZero Conversation」ここでのキーワードは Farey sequence (en.wikipedia.org) だったけど、See also のセクションに Stern–Brocot tree (en.wikipedia.org) の名前を見つけた。そうと知らず 10 年以上前に出合っていたのだ。でもまだ木については知らないし使えないよ。だけど何回も目にするうちに怖くはなくなってきたかな。たかだか数年前まではフィボナッチ数列も謎の怖い存在だったのだ。「フィボナッチ数？「競プロ典型 90 問」でも見かけたが、この数列がどうして頻繁にあちこちに登場するのかわからない。限りなくありふれたジェネレータなのか」外国人の名前を付けるのが概念を謎のベールで覆ってしまって良くないと思うな。それがただの名前であり他と識別するための符号に過ぎないことさえ明らかではなくなってしまうのだから。■■■精進。ABC333-G「Nearest Fraction」。さっきリンクを張った動画によるとこの問題が「あなたは Stern–Brocot 木を知っていますか」という問題だったらしいので、最初の１問にちょうど良いかと。■提出 #49175972 (AC / 577 Byte / 125 ms)。実装中に聞こえてきたので TLE を出す前に動画の通りに二分探索で対策してしまった。あと分母が10進11桁と19桁になる２数の差と差を比較するのに何ビット必要になるかという話題も聞こえてきた。30桁の差と差を比較するのに60桁200ビットを普通は要するのではないか。もちろん GCD の分だけ減るがどれだけ減るかはわからない。普通でない方法は知らない。だから WA を出す前にこちらも必要な対策をしてしまった。入力は文字列として受け取って分子分母を分けて扱い、出力前の比較では Rational を使った。■最も新しい C++ での提出 #49139061 に普通でない方法がひとつ見られる。比較結果が 1018 未満になるような式をまず用意して、その値をある素数の mod で求めて(式の途中の値が３数の積(10進60桁まで)になるから)、２つの素数でそれをすると中国剰余定理で実際の式の値が復元できるみたいな？コメントに全部書いてあるんだけど、「Since p/q - a/b < c/d - a/b = 1 / bd」の左辺が 1/bd より小さくなる部分がわからない。いや……わかった。そうかと思ってさっき見たときは比較するものを間違えていた。もういちど 116 ページにある木の図を確認したら、隣接する２つの分数は差が 1/bd になっていた。「なっていた」ではなくいついかなる場合でもそうなることを示して理解しろって話ではあるんだけど、つまりそうなるような操作をしているはずなんだけど、ぼんやりなので操作と結果が繋がりません。■本読みを再開したら、差が 1/bd になることが次の 117 ページに書いて示してあった。■「２つの素数」っていうのは、かつて AtCoder でよく見られた 109+7 と、もうひとつは 109+9 が使われていた。あれって双子素数だったんだ(知らなかった)。どちらも 109 をちょっとだけ超える数だから、掛けると 10**18 を超えるけど 60 ビットは超えないみたい。使い勝手のいい数だ。

ツッコミを入れる

最近ひとつ現在へひとつ過去へ

ここをクリックしてカテゴリ一覧を表示