/ 最近 .rdf 追記 設定 本棚

脳log[2024-02-15~]



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 問題らしからぬ制約にびびるけども、対数時間で底にたどりつく。1ステップ当たり2分岐あるのが不安だけど、メモ化再帰でダメなら泣いちゃう。Ruby で最短の提出 #50173926 はループなしの計算で解いている。式の中にビット長が2回出てきているのが目を引くが、意味はわかりません。■D 問題「Super Takahashi Bros.」。最初はステージ1から N-1 まで順番に処理する DP だと思った。しかしワープ土管は先へ進むだけでなく前に戻るパターンもある。D 問題でひっぱり出したくはなかったけど頭を使いたくもなかったのでプライオリティキューを貼り付けた。■E 問題「Mancala 2」。最初は前々回の D 問題 Island Tour のように、変化量をため込んでおいて最後に累積和を答えにするのかと思った。そうではない。操作のたびに箱にあるボールを数えて空っぽにしなければいけない。では愚直に操作しよう。BIT で効率良く処理しよう。自分にはめずらしくコメントが書いてある>#50168931。そうしないとややこしくて間違えると思った。1ループ当たり BIT の操作が最大8回あり、入力と出力のそれぞれで N 回の操作がある。N と M の最大が 20 万のときに、(2N+8M)logN のステップは Ruby では非常に不安。わかりやすさのために処理を刻んだけど、TLE になったらいくつかの BIT 操作をまとめるせこくて間違いやすい節約術が求められていた。幸いにも出してみたら 572 ms で余裕のセーフ。■G 問題「Leaf Color」。まず頂点数1の誘導部分グラフは必ず OK。頂点数2のパスグラフも同色の2頂点を組み合わせて問題なく作れる。3頂点から様子が異なる。2頂点を結ぶパスに3頂点目が含まれている場合、この誘導部分グラフは2頂点の組み合わせとしてもう数えてしまっている。余りの数で答えなさいという出題形式から予想できることだけど、頂点同士の個別の組み合わせ、個別のパスをひとつひとつ考慮して数を数えることは許されない。どういう特徴量によれば計算で数が数えられるのか。ある部分木について、色ごとに端点の選び方の通り数を記録した。あとは DP。ある頂点を根とする部分木について、子と子の組み合わせを数え、根と子の組み合わせを数える。提出 #50189012 (AC / 591 Byte / 1023 ms)。木 DP はコードが長くなりがちだけど、9割方は定型の処理であって、この問題に固有の部分は 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 の5完。ではふりかえり。■A 問題「TLD」。ドットジェイピーを切り出す。split してもいいし、拡張子を取り出してもいい。ライブラリにあるでしょう。■B 問題「Langton's Takahashi」。シミュレートする。添字をループし忘れて1ペナ。■C 問題「Perfect Bus」。累積和の最小値をゼロに合わせたときの累積和の末尾の値。■D 問題「Synchronized Players」。二人の位置をキーにして BFS。……なんだけど、TLE を2回出した。しょうもな。しょうもないのは、コピペによる定数倍の改善。そんなことしたくない。■E 問題「Smooth Subsequence」。1点更新のセグメント木。やりたい操作を考えて、それができるデータ構造を知っていれば、やるだけ。■F 問題「Product Equality」。値が十進1001桁になりうる以外は普通の2乗の DP。案外 Ruby だとそのままいけるんじゃね?と思って愚直解を書き始めたんだけど、時間内には完成しなかった。1の要素を特別扱いすると答えが合い、提出したら TLE にもならなかった。D で無駄に苦しんだ分、F でずるして得したかったけど、取り返せなかった。残念。


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


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 のメソッドの仕様の整合を確かめる手間で、もっと曖昧さが少ない低レベルのメソッドを使うことも現実的な選択肢ではある。低レベルとは言えないけどよく知った正規表現で書いた。文字コードを見るなら特定の1ビットで判別できる。■B 問題「Frequency」。フリークワンシィ。集計してから最初の文字を見つけた。うっかり1ステップで書こうとすると苦しむかも。max_by がぴたりとはまるらしく(#49693254)、苦しまずに解決する方法がちゃんとあったようだけど、Enumerable#max_by の暗黙の仕様に頼っていたりして(「該当する要素が複数存在する場合、どの要素を返すかは不定です」というのが明文化された仕様)、自分は思いつかなかったな。それは言い訳で、添字をペアにして比較のキーにすれば仕様に則って確実に1ステップで答えが出せた。■C 問題「Leftover Recipes」。一瞬詰まった。DP かと思わせて総当たりができる。一方の個数を決め打つ総当たり。ゼロ除算は避ける。■D 問題「Island Tour」。環状に繋がった島がある。ツアーで島から島へ移動するルートは右回り左回りの2通りが考えられるけど、どちらが右回りでどちらが左回りかはどうでもよくて、橋が1つ封鎖されていると必ず一方に固定される。封鎖する橋を決めたときの影響を単位時間で求めるために、影響の変化量を記録してその累積和を観測する。一発で通ったけど添字でバグらせなかったのはただの運。慎重に書いて祈って提出した。■E 問題「Chords」。スタックです。頂点を順番に見ていって出て行く弦、入ってくる弦を管理して交差を判定する。変数名で困った。arc は弧だから弦は何だろうと。それが問題名の chord なんだろう、きっと。自分では string かなと考えたけど、あまりに紛らわしいし、弦違いっぽくもある。code や cord に比べて余分な文字がくっついてるのがへその緒っぽさを感じさせるけど、あれは umbilical cord らしい。エヴァで聞いた音。さっき類似の過去問を紹介したけど、その問題を解いたときに「ということに気がついたら、あとはなんとかなる」と書いていた部分がなんとかならなくて2回も WA も出したのはどうかしている。あほになってんじゃねーの。■G 問題「evall」。することはすぐにわかる。それをするのがすんごく大変なだけで。考える範囲は両端が数字であるような範囲。まずは + で区切ってみる。+ の左にある数字の数と、+ の右にある数字の数がわかれば、主客転倒で + で囲まれた数(式)の寄与がわかる。次に考えるのは、範囲が + で囲まれた内部に端を発して外部に出ていく場合。範囲の内外で数字がちょん切られるので扱う値が変わってくる。だけど範囲の一方の端を決め打ったときの値とその寄与は同様に求められる。範囲の両端が + の内側にある場合の寄与は、これは累積和の問題として単独で D 問題あたりにでもなりそうな難易度の問題。ここまで触れてこなかったけど、+ で囲まれた内部は単独の数字ではなく * で連結された積の場合がある。ここまでと同じように * で分割して左右からの累積和(累積積?)で全体への寄与を求めるんだけど、このあたりからワーキングメモリが枯渇してきて全体を把握するのが困難になる。スラッシングというのかな、何をするにも復帰に時間がかかり、間違えて手戻りが発生し、ちっとも先に進めなくなる。最終的に自分はクラスを使って問題を分離して個別に対処することになった。そうするとあるレベルで考えているときに別のレベルのことを考えずに済む。メソッドを呼んで別のレベルの処理結果を得るだけにすると、大きくなりすぎたスイッチングコストがまるまる節約できる。■提出 #49805072 (G 問題 / AC / 1554 Byte / 825 ms)。サンプルが通りさえすれば他に特に罠はなかったみたいだけど、答えの突き合わせに C++ で提出が早かったこちら(#49712435)を使わせてもらった。実行結果にしか興味はなかったけど、ちらりと覗いてみた solve 関数のシンプルさがすごかったよね。しかしあまりにも最適化されすぎていて、冗長さが足りなくて、自分には書けないし理解できない。そんな簡単そうに解ける問題じゃなかったよ。この構成をあきらめたから、クラス化による問題の整理分割に行ったのだ。■コンテスト成績証自分のすべての提出。ABCDE の5完でぎりぎりの青パフォ。もう書いたけど、これで上がるのは現在のレートが下振れてるだけなんよ。■G 問題。X で(自賛を)見かけたので探してみたこちらの提出 #49757867 (tanakh さん / Rust)。class を使って構造化するならこのレベルまで突き詰めて抽象を取り出して汎化したいよね、というお手本。あと変数名も適切でかっこいい。累積和のことを prefix sum と呼ぶこともあるみたいなので、今回のように色々な累積和を扱うときにああいう呼び分けはあまりに適切。■■■G 問題。お手本にならって再構成してみた。提出 #50091522 (TLE×7)。残念 TLE。一応、数字の列を1桁ずつ分解してオブジェクトを再帰的に構築するのは避けて、* と + で分解した数字の列からループを回してオブジェクトをひとつだけ作るようにしたんだけど、演算(+ と *)のたびに新しいオブジェクトを作るのがまだまだ負担だったか。前回の提出では + の数だけオブジェクト数が節約できている。あと eval も重い。だけど evall という問題名だから eval したくなるのはしかたないよね。■提出 #50102025 (AC / 1127 Byte / 1759 ms)。通った! ネックは gsub だった(gets.gsub(/\d+/){ "Num.from_s('#$&')" })。たとえば入力が最長の1メガのとき、演算子と数値が半々なら1桁の数字が 500 キロ個ある。gsub メソッドが入力の 1Num.from_s('1') に置き換えるなら、変換後の文字列長は8メガになる。そしてそれを eval する。遅い。Num.from_s メソッドを1文字のローカル変数にキャッシュすることで文字列の全長を抑えたら、だいたい倍くらい速くなって TLE を免れた。ちなみに Object.const_missing を使うことでさらに縮めるアイデアもあった。1123N1N123 に置き換えるのだ。だけど汚い方法でありながらタイムの改善が微々たるものだったので不採用にした。+ メソッドと * メソッドをそれぞれ +=、*= メソッド相当の実装にするアイデアもあった。これもコードを歪める一方で大した改善ではなかったので不採用。せっかくきれいに再構成しているのだから、ダーティハックはお呼びでない。


2024年01月22日 (月) [AtCoder] 精進。前回の ABC337-G「Tree Inversion」。diff は F 問題より低いことになっているらしい。問題文が読めて理解できてどういう情報を集めればいいかが把握できれば、することはおなじみではある。把握できないし、実装にも時間がかかるんだけど……。さてさて。ある頂点 v を根とする部分木について、v を含むそれぞれの頂点がそれぞれの部分木に含む自身より小さい頂点の数の合計を g(v) とする。特に v が全体の根であり部分木にすべての頂点を含んでいるとき、f(v) と g(v) が等しい。あとは……解けるな? 頂点 v が0個か1個の親 p と0個以上の子 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 の中に見つかればいいかと思ったら、ABCABBCABC は 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 数列をローテーションしながらある色が新しく箱を確保したり手放したりしたときに球数をまとめて増減する。■6完が狙える問題セットで4完は残念が過ぎる。ああ繰り言。


2024年01月14日 (日) [AtCoder] 今日は ABC336 があった。コンテスト成績証自分のすべての提出。ABCD の4完でレートは横ばい。EF がどちらも難しかった。ではふりかえりと F の精進を。■A 問題「Long Loong」。ループを回せますかという問題。■B 問題「CTZ」。count trailing zeroes. zero の複数形は -s と -es が並記してあるのでどっちでもいいのかな。じゃあト・メイトウ式で。文字列化して /0*$/ でマッチさせた。ループで求めるなら、N が 0 より大きく N を 2 で割った余りが 0 である限り N を 2 で割り続けて回数を数える。■C 問題「Even Digits」。去年の年末にこの問題を解くやり方をどこかで読んだ気がする(追記:先週のことだったらしい。「まさかこの発言の一週間後にフラグ回収すると思ってなかった」 自分もその発言を読んでいましたよ)。5進数で N を数えて各桁を変換した。他の人の提出を見ると変換に String#tr を使ってる人は全然いなくて、みなさん十進数として再解釈してから×2をしているようだった。それは……かしこいなあ。■D 問題「Pyramid」。本日はこの問題で終了してしまった。書き始める前には、ピラミッドの中心に据える A 数列の値(これが k になる)とその左右にある要素数だけでピラミッドの大きさが決まると思っていたけど、サンプルの1からすでに答えが合わなかった。たとえば中心の隣の要素が中心より2以上小さかったらピラミッドとして成立しない。なので左右から独立に DP をして、左(右)の要素が左方向(右方向)に作れるピラミッドの大きさ+1を上限とした(もちろん中心の値も上限のひとつ)。■E 問題「Digit Sum Divisible」。桁和の種類はかなり少ない。桁和が固定できると各桁に配置した数字を桁和の余りで分類できるから、並べ替えを考えずに済んで考えるべき状態数が減る。だけど各桁の使用状況と現在の桁和の合計とを状態として、決め打った桁和を目指す DP が書けなかった。それで間に合うかわからないし、持つデータの型と遷移もよくわからない。制限時間 10 秒はすごい。これをどう評価するか。C++ でもそれなりに時間がかかるので定数倍で劣る Ruby ではループ回数に比例して遅れが積み重なって到底間に合わないと見るか、それとも、スクリプト言語に配慮した結果の 10 秒なのか。■F 問題「Rotation Puzzle」。半分全列挙だとどこかのツイートだったようなもので読んでしまった。BFS をするには 20 回の操作回数は多すぎるなあとはコンテスト中に実装してわかっていた。そこから半分全列挙が出て来ない。そうだとわかれば実装するだけなんだよね。提出 #49322044 (AC / 557 Byte / 2792 ms)。配列を Hash のキーにすると答えを間違える。キーにするためにつど文字列化するとコードテストで制限時間をわずかに超える。だから文字列を操作することにしてそのまま Hash のキーに使えるようにしたら間に合った。その後、やってることは同じだけど2つの改善で 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 木を知っていますか」という問題だったらしいので、最初の1問にちょうど良いかと。■提出 #49175972 (AC / 577 Byte / 125 ms)。実装中に聞こえてきたので TLE を出す前に動画の通りに二分探索で対策してしまった。あと分母が10進11桁と19桁になる2数の差と差を比較するのに何ビット必要になるかという話題も聞こえてきた。30桁の差と差を比較するのに60桁200ビットを普通は要するのではないか。もちろん GCD の分だけ減るがどれだけ減るかはわからない。普通でない方法は知らない。だから WA を出す前にこちらも必要な対策をしてしまった。入力は文字列として受け取って分子分母を分けて扱い、出力前の比較では Rational を使った。■最も新しい C++ での提出 #49139061 に普通でない方法がひとつ見られる。比較結果が 10**18 未満になるような式をまず用意して、その値をある素数の mod で求めて(式の途中の値が3数の積(10進60桁まで)になるから)、2つの素数でそれをすると中国剰余定理で実際の式の値が復元できるみたいな? コメントに全部書いてあるんだけど、「Since p/q - a/b < c/d - a/b = 1 / bd」の左辺が 1/bd より小さくなる部分がわからない。いや……わかった。そうかと思ってさっき見たときは比較するものを間違えていた。もういちど 116 ページにある木の図を確認したら、隣接する2つの分数は差が 1/bd になっていた。「なっていた」ではなくいついかなる場合でもそうなることを示して理解しろって話ではあるんだけど、つまりそうなるような操作をしているはずなんだけど、ぼんやりなので操作と結果が繋がりません。■本読みを再開したら、差が 1/bd になることが次の 117 ページに書いて示してあった。■「2つの素数」っていうのは、かつて AtCoder でよく見られた 10**9+7 と、もうひとつは 10**9+9 が使われていた。あれって双子素数だったんだ(知らなかった)。どちらも 10**9 をちょっとだけ超える数だから、掛けると 10**18 を超えるけど 60 ビットは超えないみたい。使い勝手のいい数だ。


2024年01月08日 (月) 今朝の話。あごに紙くずのようなものが付いているが根を張ったようにしぶとく取れない。なんと生えている。そんな馬鹿な。俺ってアルビノだったのか(違う)。これが老化というものか(違いますっ)。この年になるまで白髪の一本も見つけていなかったことのほうがむしろ珍しいという考え方もある(これは仮定の話)。抜いたのでもうない。存在は不確かだ。これからは気をつけて見つけないようにしよう。


2024年01月06日 (土) [AtCoder] 今日は ABC335(Sponsored by Mynavi)があった。コンテスト成績証自分のすべての提出。ABCDE の5完で青パフォ。F 問題に 50 分残していて解けなかったのが残念。DP の状態をうまくまとめられなかった。ではふりかえり。■A 問題「202<s>3</s>」。文字列操作。■B 問題「Tetrahedral Number」。辞書順に総当たり。■C 問題「Loong Tracking」。最大で N+Q 要素の配列があれば十分。末尾へのポインタを管理して最大で N 要素振り返って見る。■D 問題「Loong and Takahashi」。実装問題枠か。ぐるぐる。■E 問題「Non-Decreasing Colorful Path」。連結なので最低得点 0 は確定している。1 以上の得点を得るパスのみを考える。なので辺については A[u]<=A[v] となる u->v のみを使う。狭義単調増加が得点の条件であれば、A[i] の値が小さい頂点から順番に移動をシミュレートするだけ。自分のこの WA (#49092053) はある頂点に未達の場合を考慮していなかったせい。使う辺を限定して正の得点を得る場合のみを考えているので未達もある。実際の問題は広義単調増加が条件なので、A 数列がすべて同じ値の場合にうまく順序づけができないとぐるぐると値の更新が反復して TLE になりそう。A[i] の値が同じ頂点についてはこれまで通ってきたパスの得点が高いものから順に処理することで TLE を避ける。自分のこの WA (#49096697) は同じ A[i] を持つ頂点間の移動によって未達だった頂点に新しく到達した場合に、その頂点を処理対象に追加するのを忘れたのが原因。2つ3つの罠があったようであり、自分が単に間抜けだったようでもあるが、2つの WA を経てやっと AC (#49100939)。3つの提出にそれぞれ9分7分7分かけてペナルティ合計が 10 分なので、E 問題には 33 分かけた計算になる。案外いいのでは? しかし十分に時間をかけても F 問題は解けず。


2024年01月03日 (水) メモ帳(notepad.exe)ってコマンドラインでプリンタ名を指定してテキストファイルの印刷ができるんだけど、Windows 10 が 11 になったらレイアウトが変になった。なぜか。どうやら既定のプリンタの用紙サイズを他のプリンタを使って印刷する場合にも適用しているらしい。そうなんだ。それでどうなったか。既定のプリンタを切り替えてからプリンタ名を指定して印刷をしている。このオプション意味あるの? ついでに、「Windows10、Windows11で「Windowsで通常使うプリンターを管理する」の項目が「オン」になっている場合、通常使うプリンタはコマンドで変更されません」という事情もあるらしい。プリンタを右クリックして既定に設定するときにオフになるのでもうオフになっている。Windows にプリンタを管理してもらう意味って何があるの? そして Windows 以外の何が既定のプリンタを管理してるっていうの?■ショートカットのリンク先が無効だというので見ると、C:\Program Files (x86)\Mozilla Firefox\firefox.exe を指している。この PC の Firefox は C:\Program Files\Mozilla Firefox\firefox.exe にあるのでそれはそう。ここからが問題。 (x86) を削除して Enter キーを押した。実行するとやはりリンク先が無効だと出る。なんだよデフォルトプッシュボタンは OK ボタンのはずだろ、と思いながら今度は最後に OK ボタンを押した。実行すると変わらずリンク先が無効と出る。OK ボタンを押す前に適用ボタンを押してみたがやはり無効。修正が通っていないのかと考えてあえて無効なパスに変更してみたら、初めてリンク先が無効だとのメッセージがプロパティダイアログが閉じる前に表示された。これまで普通に OK ボタンや適用ボタンが押せていたのはパスが有効だと確認されていたからだとわかる。では有効だと確認された修正後のパスはどこへ消えてしまうのか。ショートカットファイルの中で URL パラメータを firefox.exe に与えていたのが良くなかったらしい。いやいやいや、ショートカットにコマンドラインパラメータを埋め込むのは何も悪くないよ。そういうパラメータ付きのショートカットファイルを SendTo フォルダに入れておいてもファイルを送ったときにはパラメータが無視されるという罠もかつてはあったけど、Windows Vista までにはパラメータとファイルパスの両方がコマンドラインの一部としてプログラムに供給されるようになっていたよ。■Alt キーでメインメニューにフォーカスが移るけど、矢印キーによるナビゲーションが正気の沙汰ではない。左右キーを押すとサブメニューが開く(それは直観的には上下方向の移動だし、かつては上下キーでそれを行っていた)。上下キーを押すとトップレベルの隣の項目に移動する(それは直観的には左右方向の移動だし、かつては左右キーでそれを行っていた)。メインメニューを完全に無視してすべてがコンテクストメニューと同じ配置だと想定するとそうなるか。■エクスプローラーで一度 Alt キーを押してフォーカスがメニューに移ると、もう一度 Alt を押しても Esc を押してもフォーカスが戻ってこない。Vista なら元の場所に戻ってきたし、見失ったときでも Ctrl+E、↓で必ずリストビューにフォーカスが戻せたけど、タブキー連打以外の方法がまだ見つからない。7以降キーボード軽視が目立つけど、それが加速して止まらない。アクセシビリティはどこにある。自分だって専ら使うのはマウスだけど、マウスしか使えないのとキーボードが併用できるのとでは手間が断然違う。それぞれに使い所がある。だがどんどんキーボードが使えなくなる。■フォルダのプロパティの共有タブで共有設定をしてネットワーク越しに見えてはいるけどアクセスが拒否されて中が見えないとき。パスワード保護共有だって無効なのにアクセスさせてくれないとき。セキュリティタブで Everyone にアクセス権を与えないといけないみたいですよ。共有タブですでにそのように設定していたとしてもね。■右クリックがジャックされていて識別困難な全角1文字サイズのラベルなしアイコンと、アクセスキーのない厳選されたメニュー項目だけが表示されるので、App キーでメニューを出し直すまでがルーティーン。■何もスタートできないという評価を確立している Windows 10 のスタートメニューだけど、11 はさらにひどくしてきた。一番有用なショートカットアイコンがデフォルトで表示されない。追加してもラベルがない。1クリックを要するのが不満だけどラベルが展開できた 10 が優秀に見える。すべてのプログラムを表示するのにも追加の1クリックを要する。そのボタン。まるで現在すべてのプログラムを表示しているかのように見えるプルダウンリストのようなものが右上にあるが、それが切り替えボタンだった(ここの画像)。そういう風に表示を切り替えるときは「タブ」を使えばいいと思うんだよね。ユーザーの意表を突いて何かうれしいことある? デスクトップ左下の一等地が天気(!)だったからスタートアイコンを左下に移動したけど、たしか Vista よりあとのどれかではもうスタートボタンが左下方向に無限の大きさを持ってはいなかったのだったか。もう一等地ではなかったかもしれない。■ノート PC に外部モニタをつないで蓋を閉じたらスリープしてしまって外部モニタに何も映らない。Web を検索してここにあると示されている設定項目がちょうど抜けている。やっと見つけた正解はスタートメニューで「cont」と入力するとコントロールパネルが見つかるので……というものだった。■スリープしない設定にしているのに翌朝になるとマウスやキーボードに反応しなくて電源ボタンを押す必要があるという。これも正解はスタートメニューで「cont」だった。そこには「休止状態にするまでの時間」という設定アプリにはない設定があって、そこに有限の時間が設定されていたのが原因だった。確かにスリープはしていませんでしたけどね。■あるプログラムで F1 キーが効かないことがあって困ってしまったが、デスクトップで F1 を押して Edge が出てきたあとでは効くようになっていた。よくわからない。■ここまでが一週間以内に起こったこと。もうね、すんごい。すべての Windows ユーザーの生産性を下げることに全身全霊を傾けているとしか思えない。過去を断ち切って破壊的な変更を企てているけど、破壊するばかりで秩序をもってデザインされたユーザーエクスペリエンスがどこにもない。未完成のがらくたで覆い尽くされていて無限に時間を奪われる。これが自分の PC ではないから私は平静です。