/ 最近 .rdf 追記 設定 本棚

脳log[2024-05-06~]



2024年05月06日 (月) [PS5] 先週 Lords of the Fallen というゲームのダウンロード版を PS Store で購入したのだけど、キャラクリの最後で「有効な名前を選択してください」と表示され続けてそれ以上先に進めなくなっている。「プレイヤー名」みたいなプリセットが拒絶され、テキトーな日本語名が拒絶され、英数字のみの名前が拒絶され、空欄も拒絶された。ゲームが始められない。この状態が続くのであれば、俺は誰に返金を求め、誰に不当に預かられていた期間の金利を求めればいいのだ。■■■@2024-05-07 他にそういうバグ報告を見ないし、そのわりにゲーム開始不可はあまりに致命的な現象なのでちょっと考えてみた。月額課金は、していない人が無視できるほど少ないってことないだろうから、じゃあ、PSN へのログインかな。……というわけで、キャラクリの最後の瞬間にだけ PSN にログインしている状態である必要があったのでした。すんなりわかったわけじゃないよ。今日も、アップデートは……ないな、この名前だったら……ダメだな、というのをやっているうちに気がついたのだ。当たり前でないことを、「ほぼ」そうだからというだけで、勝手に当然の前提にするんじゃあないよ。どう見えるか、どうであるかではなく、どうあるべきかで行動するんだよ。漫然と現状をなぞる AI じゃねーだろ。


2024年05月04日 (土) [AtCoder] 今日は AtCoder Beginner Contest 352 があった。E 問題までの解ける問題を解きましたという感じ。たぶん精進として粘れば F 問題も解けなくはないのかなと思うけど、まずは WA がどういう思い違いから生じているのかを探る必要がある。ではふりかえり。■A 問題「AtCoder Line」。範囲に含まれるかどうか。大小関係が制約により規定されているわけではないことに注意。■B 問題「Typing」。B 問題にしてはいかつい制約(20 万)だけど、まあ、やります。T をスキャンしながら S の現在位置との比較を行う。■C 問題「Standing On The Shoulders」。肩の高さは常に答えに寄与する。頭の高さ、というか、肩より上に出る頭の高さは1つだけが答えに寄与する。合計足す最大値が答え。■D 問題「Permutation Subsequence」。結構考えました。そもそも記号混じりの問題文という時点で理解に時間がかかる。理解した内容はこう。K 幅の順列を考える。1から K とか、2 から K+1 とかの。次にそれらが入力 P の中でどの位置にあるかを考える。必要なのは最も左にあるものと最も右にあるものの差。これの最小値が答え。D 問題だからスマートな解法があるのかなと思いつつ、考える時間を惜しんで BIT でなぐりました。幅 K のウィンドウをスライドさせながら、入ってきた要素の位置を +1 し、出て行った要素の位置を -1 すると、値が1の位置(最も左にある要素の位置)と値が K の位置(最も右にある要素の位置)を BIT に尋ねることができる。■E 問題「Clique Connect」。愚直に辺を繋いでいくことはできない。扱う要素数は最大で 40 万だけど、その組み合わせは2乗の数になる。最初に最小全域木を求める操作をした。コストの短い辺から順番に、繋げられるけどまだ繋がっていない要素をどんどん繋げていった。これは組み合わせではなく、テキトーに選んだ1つの要素に他のすべての要素を繋げていく操作。それをコストの昇順に繰り返して最後に全体がひとつになっていればコストの合計を答え、そうでなければ -1 を答えにする。■■■@2024-05-05 F 問題の WA が減らないので代わりに D 問題を BIT で殴らない方法。提出 #53178338 (AC / 405 Byte / 123 ms)。配列を2本使うだけなので短いし、BIT だと付く log も付かない。スライド最小値とかいう名前がついてるのかな。初めて参加した AGC が AGC038 なんだけど、時間内に解けなかった B 問題 Sorting a Segment への他の人の提出を研究する過程で見つけたのがこれだった。ソースコードで学んだので名前は後付け。20190922p01。じゃあ昨日の ABC352-D が解ける人は青 diff だった AGC038-B も解けるね。■■■@2024-05-06 F 問題。ほんの2週間前に「重み付き UnionFind の実装は死ぬほどややこしい」と書きながら ABC314-F の精進をしていたのだけど、そのときは時間をかけながらも1発で AC になっていたのだけど、今回の問題は5つも6つも実装ミスが重なって5回も WA を出していた。すべては実装ミスだった。提出 #53204970 (AC / 1169 Byte / 174 ms)。後半にビットを埋める総当たり(メモ化あり)があるので N の制約が 16 以下と小さい。だから前半の UnionFind を定型から外れて雑に書いてバグり散らかしていたという話。制約が小さいならサイズやランクを見る必要ないもんね。そしてもちろん後半部分にバグがなかったというわけでもない。実装が下手。頭の中が散らかっている。■F 問題の解法について書いていなかった。パズルのピースを組み合わせるイメージ。相対的順位差で関係づけられたいくつかのグループがパズルのピース。3人の人が1つ飛ばしの順位だったなら、このピースは 10101 で表せる。全部で5人なら、これは 1-3-5 位しか考えられないが、全部で 10 人なら 2-4-6 位もありうる。しかし全部で 10 人いて他に 101011111 というピースがあるなら、やはり 1-3-5 位しか考えられない(※ MSB を1位としました)。こうなってくるととりあえず全部を試してみるしか答えを出す方法はないよね、という気持ちになる。1階層ごとに特定の1ピースを埋める DFS をやるんだけど、DFS の呼び出し経路には関心がない。どういうことか。1階層目と2階層目が受け持つピースがどちらも 11 という形だったとする。3階層目のピースにとって関心があるのは、そして結果に影響するのは、どのビットが空いているかということだけなので、同じ2ビットのどちらとどちらを1ピース目と2ピース目が埋めているかという情報には関心がない。むしろ積極的にその区別を捨てて結果の使い回しをしたい。メモ化です。というわけで、前半ではピースの形を確定する UnionFind を、後半ではピースを N ビットに隙間なく埋めるメモ化再帰をする2段構えの問題だった。要素技術は F 問題までで身につけているはずで、組み合わさったことで F 問題だったのかなと。G 問題ではないなと。ならこれも実装問題だったのか。突破できませんでした。腕力が足りない。■他所で見かけたのでここでも書くんだけど、置きにくいピース(※)から置くような小細工を WA だった最初の提出から行っている。これをやらなくても TLE にはならないだろうけど、とにかく答えを見つければいいという DFS の場合、優先順位を付けて早期に判定ができると劇的に実行時間が縮まることがあって気持ちがいいので、とりあえずやってみて沼にはまるのがいいと思う。その先にヒューリスティック沼があるかは知らない。この問題では、再帰を深く潜ってからやっぱりだめでしたーと判定されていたかもしれないものが、比較的浅い階層で無理だと判断できるようになる効果があったと思う。※置きにくいピースを短絡的にビット長の長いものとしたけど、ポップカウントもいい指標になりそうだと気がついた。10000011111 のどちらが置きにくいかという話。自分が明確に誤っていたのは、ビット長が同じでポップカウントが異なる 110001101111 の比較で、単純に数値比較で大きい方(最初の方)を置きにくいと判断したところ。小細工だしフレイバーなので許される手抜きだとは思うけど。


2024年04月27日 (土) [AtCoder] 今日は AtCoder Beginner Contest 351 があった。コンテスト成績証自分のすべての提出。ABCDF の5完でレートは横ばい。E 問題が難しかった。ではふりかえり。■A 問題「The bottom of the ninth」。問題文に書いてある通り、9回裏が必ずある。場合分けはいらない。1点上回るのに必要な点数。■B 問題「Spot the Difference」。唯一の相違点の座標を答える。座標が1始まりなんだよね。添字と1のずれがある。それで思いついてしまったんだけど、サイズを答えにすればずれの補正がいらない。つまり、後ろの方から一致している行を取り除いていくと、相違点のある行までが残る。残った行数がそのまま1始まりの座標になる。列番号も同様に末尾から削っていくと、残った文字数がそのまま1始まりの列番号になる。+1 とか -1 とかの補正って嫌いなんだよね。1か所も漏らさず完璧に補正できる気がしないし、+1 とか -1 とか見るたびにその意味を解釈させられるのが嫌だ。だから普段から無害な0番目を補うなどして補正の必要をなくすようにしている。メモリの方が自分の脳みそよりローコストだから、余分な1要素をケチる理由がない。入力を1回だけ補正して変換するという手もあるけど、そうすると実行結果とサンプルの解説文とでずれが生じるので避けたい。■C 問題「Merge the balls」。えっと、やるだけなの? 罠とかない? と警戒したけど、これは C 問題だった。では油断してそのままやります。2つの数を足す操作が +1 することを意味するというのがちょっとしたフックかな。掛け算が log の足し算になるみたいな。■D 問題「Grid and Magnet」。本日の実装枠でした。といって簡単というわけでもなかったと思う。基本は BFS、DFS もしくは UnionFind で連結成分の大きさを求めるんだけど、移動するとそこから動けなくなる吸い付きマスをどう扱うか。最初の UnionFind のステップでは吸い付きマスを壁として扱い、その後のステップで隣接している吸い付きマスと連結成分を一体として大きさを数えるようにした。気をつけたいのは、幅1の吸い付きマスが2つの連結成分を分断しているとき(そう、分断するんですよ。UnionFind をするときに吸い付きマスを使って連結してはいけない)、その吸い付きマスは両方の連結成分に対して寄与がある。どちらか一方だけに所属させてはいけない。前半のステップでも後半のステップでも吸い付きマスの特別扱いが罠になり得る。簡単ではないよ。■E 問題「Jump Distance Sum」。解けなかった。dist(Pi,Pj) がゼロになるのはチェス盤をイメージして2つの点が異なる色のマスにある場合。そうでない場合に dist(Pi,Pj) は X 座標の差と Y 座標の差のうち大きい方になるみたい。ある点を中心として座標空間を十字に区切ると、X 座標の差が dist になる範囲と Y 座標の差が dist になる範囲がそれぞれ2つずつ。BIT を2つ使って、ある座標までにある点の数の和と、座標の和を管理すれば、ある座標を中心として左右にある点との距離の和が効率良く求まる。ちなみに今日の F 問題がそういう問題だった。でも E 問題ではそれができなかった。点は左右だけではなく上下にもあり、X 座標と Y 座標のどちらか決まった方を dist の計算に用いなければいけないが、その分別が効率良くできない。■F 問題「Double Sum」。すごく安心感のあるおなじみの問題。もう5回も6回も書いてる気がする。BIT で値の和と値の数を管理する。Ai<=Aj を常に成り立たせるために昇順もしくは降順に A 数列を処理する。


2024年04月26日 (金) ふと思ったんだけど、骨を折る重傷で全治数か月とか、くっついた骨が十分な強度を持つまで3か月かかります(※期間はテキトー)みたいなのって、骨が作られて破壊されて置換されるサイクルがそれくらいってことなんかな。それをいろいろな表現で言い換えているだけ? 鈍い頭にそんな閃きが急に降ってきたが、例によって骨のサイクルを調べたりはしない。


2024年04月24日 (水) [AtCoder] 精進。「最近解けていなかった期待値の問題」3問から2問。■ABC314-E「Roulettes」。これもループを含む試行。「素直な問題設定」だった ABC350-E「Toward 0」と何が違うというのだろう。何も違わないと思う。でも難しく感じる。ABC350-E に提出した解答を想起しながらなぞるようにしてやっと解答が作れた。提出 #52759461 (AC)。■同じく ABC314 から F 問題「A Certain Game」。見え見えの UnionFind なのはわかる。でも UnionFind をしながら期待値をどこにくっつけるのが適切か、その期待値はどういう意味合いの数字か、よくわかりません。試合をした2チームを UnionFind で併合する。その後の期待値の増減は併合されたチームメンバー間で共通なので、根っこの期待値を代表にして操作する。ではメンバー個々が保持する値は何か。根っことの差分だけど、どこで根っことの差分が生じるか。勝ったチーム負けたチームと、大きいチーム小さいチームが必ずしも一致しないのがややこしいけど、小さいチームの期待値は試合後に大きいチームの期待値を基準にした差分として表現されるので、チームの併合操作の前後で小さいチームの期待値が変化しないように、大きいチームの期待値を打ち消すようにして差分が生じる。提出 #52760322 (AC)。……ということが理解できてから実装を始めたけど、重み付き UnionFind の実装は死ぬほどややこしい。E 問題の AC から1時間 20 分ほどかかっている。それはコンテストが始まってから終わるまでの時間とほぼ同じだ。■「最近解けていなかった期待値の問題」を具体的に特定してから書いたわけではなかったけど、あと心当たりがあるのは ARC174-C「Catastrophic Roulette」。この3問あたりが最近の解けなかった期待値の問題だったと思う。もう今日は ARC-C まで考える気力がない。■F 問題。Ruby によるすべての提出を眺めてると、どうやら、前半で UnionFind をしながら必要な情報を付加して、後半で逆向きにたどる構成の解答がほとんどみたい。うーん?


2024年04月23日 (火) [AtCoder] X で見かけた。「これ出力の見た目あってるのに WA で謎 しかも出力部分を string に入れてから一気に出力にしたら AC したし 提出 #52718946 - AtCoder Beginner Contest 350(Promotion of AtCoderJobs) atcoder.jp/contests/abc35…」■ちょっとした謎解きだった。こちらの提出 #52718946 だけど、たしかにコマンドプロンプトを目視で確認すると答えは合っている。でもいったんテキストファイルに出力すると改行の前にヌル文字があった。それで WA。r の正しい初期値は n だったのでは?


2024年04月20日 (土) [AtCoder] 今日は AtCoder Beginner Contest 350(Promotion of AtCoderJobs) があった。コンテスト成績証自分のすべての提出。時間をかけて F まで解いたけど G まで解いた人が多すぎてまずまずの伸び。とはいえ Highest 更新嬉しいです。ではふりかえり。■A 問題「Past ABCs」。普通に to_i するとゼロ始まりのケースで罠があるかなと検討したけどなさそうだった。Ruby の8進数リテラルはプリフィックス 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」。最近解けていなかった期待値の問題だけど、これだけ素直な問題設定だとループのある試行でも式が立てられる。メモ化再帰で。5分かかっていないから9分かけた C 問題より簡単だったと言えるのでは。■F 問題「Transpose」。AC できただけでも嬉しいことだけど、さすがに1時間は時間をかけすぎている。何ができなかったかって、対応する括弧に囲まれた文字列を再帰的に取り出すことに苦労していた。私は再帰関数が書けません。やっと書けても TLE だった>提出 #52607490。それはまあ、文字列の配列を連結することを繰り返す代わりに、直接文字列を出力することで通ったのだけど(提出 #52610168)、Ruby での他の提出と比較すると遅いので出来の悪い解答であるらしい。たくさんのオブジェクトを new しているのが明らかに悪いが、class を使わないと頭の中の整理がつかないので仕方がない。コンテキストを分けて小さな部分問題を解くことに専念するためにクラスがある。■C 問題をやるだけと書いたけど、最初からそう捉えられたわけではない。ABC と AGC の区別がついていなかった頃に書いた日記に過程が書いてある>20190907p01


2024年04月13日 (土) [AtCoder] 今日は AtCoder Beginner Contest 349 があった。コンテスト成績証自分のすべての提出。F 問題が解けませんでした。ではふりかえり。■A 問題「Zero Sum Game」。ちょっと考えるよね。プラスとマイナスの不均衡を均すのが人 N の持ち点だと直観的にもサンプルを見てもわかるけど、すこーし不安が残る。杞憂に終わったが、それは単にこれが A 問題だからなんだよね。■B 問題「Commencement」。やります。Array#tally がほとんどのことをやってくれます。■C 問題「Airport Code」。S の末尾に x をくっつけたら2番目のルールは無視できる。あとは T を元にして S をスキャンする。■D 問題「Divide Interval」。問題文が難しいよね。文というか式が。何度も読んで理解したところでは、ある2の冪乗 W があって、その2冪 W でアラインされた幅 W を持つ範囲が良い数列だと言っている。この説明でわかりやすくなったかは疑問。2つの2冪 w と W があって、w<W のとき、幅 W の良い数列の中と隣に、幅 w の良い数列はきっちり隙間なく整列するので、とりあえず最大の W を L...R の範囲内に見つけて、その左右に W 未満で範囲に収まる最大の w を再帰的に求めていけばいいように思う。考察半分実装半分でどちらもやや難しくやや大変だから、普段より高めの 450 点だったかと思う。22 分かけている。ビット演算で何かをやろうとしてあきらめて 60 通りの全探索に切り替えるまでに時間を使った。■E 問題「Weighted Tic-Tac-Toe」。メモ化再帰でとりあえずやってみたら通りました。盤面は3進数で。Takahashi と Aoki を区別するために手番を知りたくなって、どうやって知るか困ったけど、残りの白マスの偶奇で判別できた。メモ化関数の戻り値の仕様次第では二人の名前を区別する必要がないと思うのだけど、そう期待して実装を始めたのだけど、勝者の名前を返すような仕様にしてしまったので困ってしまっていた。終了条件が2つあって、一方の条件ではスコアが無関係だからそういう仕様に誘導されてしまった。24 分かけている。かけた時間から判断すると、D と E がどちらも 450 点だったのはまこと適切だったと思う。■F 問題「Subsequence LCM」。解けてないよ。愚直解法で TLE×14/AC×23。A の中の同一要素をまとめて処理すると TLE×12/AC×25。2つだけ AC が増えた。LCM でフィルタしていた部分を GCD で判定するようにして不用意に大きすぎる値を生み出さないようにも注意したけど、たぶんそれによる改善はあんまりない。これ以上のアイデアはない。■■■D 問題。最初の提出 #52331543 はせっかく定義した IJ 関数が一度しか呼び出されていなくてもったいないので、それを LR 関数として再定義してスクリプトの後半でも利用するようにした。提出 #52388999。16 行くらいあった後半部分が3行になった。while 文が2つある構成は同じだけど、ループの本体が関数を呼び出すだけの1行になった。各所で読んだのだけど、セグメント木についてはまったく頭に浮かびませんでした。セグメント木の図を思い浮かべれば問題の理解が早かったと思う。でもそれが思い浮かんだ時点でもう問題を理解してるよね。


2024年04月08日 (月) [AtCoder] 先週末にあったトヨタ自動車プログラミングコンテスト2024#4(AtCoder Beginner Contest 348)のふりかえりと精進について。■A 問題「Penalty Kick」。サンプルを出力して気がついたけど、oox の繰り返しを必要な長さ出力するだけだった。だけど各 i についてそのつど判定する方が簡単だったのでそのように。■B 問題「Farthest Point」。距離の比較をするのにルートはいらない。Ruby には Math.hypot (sqrt をとる) の2乗の値を返すメソッドがあると思ってリファレンスを見たけど見つからなかった。たぶん Complex#abs2 のことが頭にあったのだと思う。解法は愚直総当たりで最初に見つかったものを答えにする。素直に書けば「番号が小さいもの」という条件は自然に満たされる。■C 問題「Colorful Beans」。色でグループ化してグループ内の最小値の最大値を出力する。要は悲観主義者が最もましな選択肢を選んだ場合がどうなるかという話。この C 問題まではプログラミング言語の扱いが問われている。やりたいことが書けますかと。Ruby で参加しているなら、C 問題は Array#group_by を知っていますか、という問題だった。■D 問題「Medicines on Grid」。グラフですよね。S と T と薬のマスを頂点として、同じ頂点を2度通らずに S から T へ到達できますかという問題。これは訪問済み頂点を記録して DFS でやろうか。そして頂点間の繋がりがグリッドで与えられていて、探索をしなければ明らかにならない2段構えになっている。最初はきれいに2段に分けて解こうとしたんだけど、面倒くさくなった。最初のグリッド探索のついでに到達可否の判断をしてもいいじゃないか。プライオリティキューを使わずにテキトーにキューに探索地点を追加してエネルギーを記録していった。これに 50 分くらいかけたんですよ。それはダメ。■E 問題「Minimize Sum of Distances」。全方位木 DP。頭が破壊されました。こういうのは終了したあとでじっくり落ち着いて書きたい。終了3分後>提出 #52114566 (RE)。頂点番号を1始まりのままにしていたのに、0 から N-1 を処理対象にしてしまったせいでエラーになっている。終了 13 分後>提出 #52115938 (AC)。結局惜しくはなかった。今日になって全体が見通せる状態でイチから書いたもの>提出 #52179331 (AC)。最初からこれがすらすら書けないのは理解が遅いってことだよ。


2024年04月04日 (木) SO2R。手っ取り早い攻撃力アップ手段である、アトラスリング、バーサークリング、ルナティックピアス、メテオリングについて。アトラスリングの効果は ATK+100%。つまり物理攻撃力2倍。残念ながら2つ付けても +100% のまま増えない。参考までに、ATK+20% のファクターとは効果が累積する(複利ではなくベースの数字の 120% が加算される)。バーサークリングの効果は怒り効果でダメージ2倍。敵の防御力が高いときは ATK を増やす方が効果的だと PS 版の攻略本で読んだが確かめてはいない。PS 版ではアトラスリング+アトラスリングとアトラスリング+バーサークリングの組み合わせ比較に意味があったのだ。すでに書いたように SO2R ではアトラスリング+アトラスリングの組み合わせに意味がないので、基本はアトラス+バーサーク。メテオリングの効果はヒット数+1。1回殴るとダメージの数字が2つ出る。バーサークリングとの違いは、たぶん必殺技に効果が乗らないだろうという点。戦士キャラには向かない。ダメージ上限を 9999 から増やすスキルがあるので、ガントレットより源氏の小手を選んだほうがいい理由もない。これは FF6 の話。自分のように呪紋キャラであるレナでボコスカ殴る場合にはバーサークリングの代わりに装備してもいいと思う。ヒット数+2であるスレイヤーリングはまだ持っていないので今は考慮の外。ルナティックピアスの効果は ATK+200%。なんとアトラスリング2つ分の効果。その代わり命中(HIT)マイナス 50% の効果も付く。HIT と命中率の関係式は知らない。常に背後をとるようにすればいいんじゃないでしょうか。ピアス系のアクセサリは女性限定。そしてお子様は付けられない。実際は個別に差違があるのだけど、ルナティックピアスに関して言えばセリーヌ、チサトが OK で、レナ、プリシスが不可。不審人物ウェルチが OK なのは、17 (レナ) と 18 (ウェルチ) のあいだにお父さん的ボーダーがあるってことなの? そしてルナティックピアスは効果が重複する。なんと ATK+400%。なぜか HIT マイナス効果の方は重複しない。つまり2つ装備するとプラス効果は2倍だけどマイナス効果は2倍にならない。なにそれおいしい。これの罠は、ATK 上限が 9999 だということ。本編シナリオをプレイ中の現在でもすでに上限に当たってしまう。それならバーサークリングと組み合わせるのがいいかも。ここで、隊列効果の ATK+60% の扱いが気になったので調べてみた。つまり、ATK 9999 の状態で ATK+60% の隊列効果に意味があるのかどうか。結果は、10000 程度のダメージが 16000 程度に上がっていたので、素直に 9999 を超えた ATK の数字がダメージに反映されていると思う(あるいは ATK+60% の隊列効果とは物理ダメージ 1.6 倍という意味なのか)。こうなると、キャラクターのパラメータである ATK の上限が本当に 9999 なのかを疑いたくなる。実質の上限なのか見かけだけの上限なのか。テキトーに比較した感じ実質の上限っぽかったけども、現状では 9999 を大きく超える ATK が作り出せるわけではないので、微妙な数字を比較した結果ではある。だけど期待はしていない。


2024年04月03日 (水) 9年ぶり2度目にお風呂で死にかけた話。お風呂で 15 分ほど本を読んでから湯船を出て歯を磨いていた。胸がずんずん苦しくなってきて吐きそう。吐いたら楽になるかなと考えるけど吐けない。床に倒れ込んで楽になりたい気がするけど、楽になるはずもない。だけどひたすらに胸が重苦しいので、どうにかして解放されたいのだ。さっきから便意があるのも吐き気と連動しているのだろうか。お風呂に入る前にもう出してるんだけど。ここで、あ、これ脱水でのぼせてるんだと気がついた。経験があるから今度は少しだけ気がつくのが早かった。15 秒くらい。のどの渇きはないけどシャワーのお湯を3口飲んで様子を見る。楽にならない。倒れ込みそう。倒れる前にうんこを出しておきたいと思った。体を拭いてトイレへ。出したあとたぶん5分くらい朦朧としていた。なかなか良くならないので飲んだのが3口では足りなかったかと不安になる。でももう動けない。水分が減っているということは血圧が低いだろうと思って、頭を下げるために肘をついて床を眺めていた。上半身に支えが必要だったということもある。そうしているうちに徐々に頭のもやと胸の苦しさが晴れてきた。濡れた肌に夜の冷気が心地よい。そのあとはお風呂に入り直した。寝る前に飲むためのお茶をお風呂に入る前に淹れていたのだけど、飲むタイミングが間違っていたね。だけどのどは渇いていなかったのだ。■今日は朝からいつもと違っていた。いつもは遅い朝食を用意するときに急須に 500 mL ほどお茶を淹れる。食後にココアも作る(300 mL くらい)。ココアを飲んだあとの口直しにティーバッグでコップ半分くらい(140 mL)のお茶も淹れる。それがどういうわけか今日に限って 140 mL だけで満足していた。今日一日それだけで満足していた。感覚がバグっていたのだろうか。数字で管理しないといけないのだろうか。■しかし、この日記を書くにあたって検索してみたら、前回(20150115)がもう9年前だったということが驚きなんですよ。感覚に従えば3から5年前くらいというのが妥当。年をとればとるほど体感時間は短くなるらしいが、それは生きてきた時間を尺度にして時間を計るからなのか。年の数で計る余命より体感する余命はずっと短い。


2024年03月30日 (土) [AtCoder] 今日は AtCoder Beginner Contest 347 があった。コンテスト成績証自分のすべての提出。CDE が緑 diff で、その次の F が黄 diff の壁だったらしい。緑 diff の問題を解いて青パフォをもらって自己ベストにあと6のところまで戻ってきた。なんだかなー。AC までの所要時間が A=1分程度、B=1分ちょっと、C=15分、D=19分+ペナルティ5分、E=11分。■A 問題「Divisible」。% 演算と / 演算。Array#filter_map がぴったり。■B 問題「Substring」。制約が小さいので全探索。文字列を切り出して重複を除く。ところで、前回の B 問題 Piano も同じような全列挙、全探索だったのだけど、Ruby で一番最初の提出だったこちら(#51548594)が WA だった原因は、間違いがあるとわかって探してもなかなか見つけられないのではないかと思う。実際二度見三度見しても見つからなかった。対処法の1つは #51616574 のように、combination に代えて repeated_combination を使うこと。もうひとつは今日の B 問題への提出 #51816314 で採用したように、文字を切り出す範囲を表すのに .. (終端を含む) に代えて ... (終端を含まない) を使うこと。要するに、長さ1の部分文字列を表現する方法が確保されているかどうかが WA と AC を分けている。一般的な文字列検索と正規表現検索との違いで顕在化しがちな問題として、特定の位置の空文字列を表現する方法があるかどうかというものがある。普通のテキスト検索では長さ0の文字列を探すことも見つけることもないので、表現能力の不足に気がつけないことがある。C++ のイテレータが開区間ではなく半開区間なのは、こういう理由からもよくできてるなと思う。いいものはどんどんまねしよう。そしてこれはトリビアだけど、サイズ N の配列 A があるとき、A の末尾の要素は A[N-1] であり A[N] の読み取りは不正だけど、A+N が A+N-1 より大きいことが C 言語の規格で保証されているらしい。でないと範囲が表現できないもんね。■C 問題「Ideal Holidays」。配点が +50 の 350 点ということでやや難しめだと予想できる。実際その通り。予定が A+B 周期で何日目に当たるかを求めてソートして、順番に各要素が休日の1日目にあたると仮定して N 個後ろの予定が A 日目までに収まっているかを判定する。提出直後に同じ日に複数の予定がある場合に正しく判定できないことに気が付いたのだけど、今見ると制約によって重複が排除されていた。優しい。そして今一度よく考えると、D%(A+B) したときに重複が生まれる可能性がある。重複する予定が3つあったとして、最初に処理する予定に限って正しく判定ができるので、結果的に問題がなかったのだ。■D 問題「Popcount and XOR」。C は最大で 60 個のビットを持っており、立っているビットを X または Y のどちらかに割り振る。割り振るのはどちらでも良いが、popcount(C)<a+b のときは C のビットが立っていない位置で X と Y の両方にビットを割り振って打ち消し合わせる必要があるので、a と b の大きい方に 1 のビットを割り振るのがよい。最初に WA×1/RE×1 を出したが(#51837959)。7分後に AC (#51842648)。両方の提出でやっていることは同じ。ただ、RE/WA を出した方では、不可能なケースを最初に判定するようにしていた。一方の AC 提出の方では、操作をしたあとで、結果が満足しているかどうかで出力を切り替えた。要するに、不可能なケースの判定に漏れがあったのだ。おそらく C の0のビットが a, b の大きさに対して不足している場合を弾き損ねていた。最初に提出する前に不安はあった。だから普段書かない assert、……はないから raise を埋め込んで前提が間違っていないかを確かめていた(その結果 RE が出ている)。残念。■E 問題「Set Add Query」。所要時間によれば CD より簡単でしたよね。まず、各時点での集合のサイズというのが操作をシミュレートすることで予め求めておける。次に、各 x (1≦x≦N) について集合に含まれていた区間を調べる。これはクエリを順番になぞりながら値 x からクエリ番号の列を逆引きできるように記録をとればよい。クエリの列から2つずつ取り出したものが x が集合に含まれていた区間。■今回は水 diff と青 diff が問題セットに含まれていなかった。今日の自分は緑 diff 以下の簡単な問題に滅法強いマンとしてレートを稼いでいる。仮にここに水 diff の問題がプラスされると、水 diff の問題にはそこそこ時間がかかるので、水 diff 以下の問題に滅法強い人にタイム差をつけられて相対的にパフォーマンスが下がる。さらに青 diff の問題がプラスされると、自分は青 diff の問題は時間内にほとんど解けないので、青 diff が解ける人に点差をつけられて、やはり相対的に自分のパフォーマンスが下がる。しかし水も青もなかったから、自分を含めて黄 diff が解けないグループがひとまとめにされて、緑 diff の問題で優劣が判定された。それで青パフォをもらうのは、なんだかなーだよね。


2024年03月29日 (金)

最終更新: 2024-04-03T08:25+0900

[AtCoder] パ研合宿2023 第1日「SpeedRun」

AtCoder をプラットフォームとして利用する有志コンであり、AtCoder の問題ではないけども、競プロカテゴリとして AtCoder に分類しています。

リアルタイム参加はしていない。ABCDFHIE をこの順に解いたのでふりかえって書く。

 A - Kazuate Game (100 点)

出現数を数える。Array#tally そのもの。

 提出 #51702284 (AC / 67 Byte / 103 ms)

 B - Cutting Circle (100 点)

2本の線が一致することはないので、必ず3つか4つに分割される。ソートするなりしてうまく分類する。

 提出 #51702526 (WA)

うまくできませんでした。

 提出 #51702670 (AC / 146 Byte / 51 ms)

 C - Infinity (200 点)

数列が a,1,b であるとする。そうすると、b=a+1、a=b+1、b=a+1 と操作を繰り返すことで無限に大きな要素を作ることができる。A[1]=1 の場合であっても、A[1] を無限大にすることができる。初期数列が1以上の要素を含んでいることが必要十分条件だと思いました。証明は知りません。

 提出 #51702806 (WA)

間違えました。最初は、2つの要素を足して1以上になることが必要十分条件だと思ったんだよね。証明は知らないとか言ってっからだよ。

 提出 #51702871 (AC / 62 Byte / 100 ms)

 D - Bishop (200 点)

すごーく難しかった。4回間違えた。順番に WA×13WA×3WA×2WA×1

まずは問題を理解する。X 座標と Y 座標について、正負どちら方向に移動することもできるけど、移動量の絶対値が一致していなければいけない。

どういう操作を構成するか。最初からずっと想定していたのは、まずは X 座標もしくは Y 座標の、ずれが小さい方の数字を一致させる。その後はずれが大きい方を、偶数回の操作で一致させる。偶数回というのは、先に合わせた方の座標をずらしたくないので、移動量を等分して打ち消し合わせるということ。

この考え方で WA×1 まで行ったのだけど、一方のずれに対して他方のずれが非常に大きい場合に答えが微妙に合わなくなる。

結論を書くと、最初に目指すべきポイントは近い方の座標ではなかった。偶数回の操作の折返し点を目指すべきだった。要するに、X 座標のずれが DX、Y 座標のずれが DY だとして、DX<DY なら最初に目指すべき点は DX+(DY-DX)/2 だったということ。DX だけ移動してから DY-DX を偶数回で移動するのではなく、DX+(DY-DX)/2 移動してから (DY-DX)/2 移動する操作を構成するのだった。

 提出 #51722059 (AC / 124 Byte / 127 ms)

ARC で 400 点ぐらい配点してもいい問題だと思います。400 点というのは、数学的センスがある人は瞬殺するけども、自分は1時間以上苦しむという、そういう問題。

 F - Mean Median Construction (300 点)

任意の部分列について成り立たなければいけないので、一番極端なケースを想定する。つまり、N=1 のケースと N=2 のケース、そして中央値に対して極端に平均を下げるような列を。

N=1 のケースでは中央値と平均値が一致する。N=2 のケースでは a1<a2 なる列の中央値が a1 なので平均値が必ず中央値を上回る。N>=3 の場合で N が偶数のとき、中央値より大きい値の数が小さい値の数より1つ多くなるので、平均値は大きくなりがち。だから N が奇数の場合だけを考える。もっといえば、N=3 で成り立つなら N=5 でも N=7 でも成り立つと思うんだけど、そんな気がするだけ。

N=3 のケース。a1<a2<a3 としても構わないのでそうする。平均を下げたいので a1 は最低の 0。a3 がいくつなら平均が a2 以上になるだろうか。2×a2 が最低ライン。N の制約が 20 万以下ということだけど、要素が倍々に増えていくなら ai≦10^9 の制約から実質的な上限は 30 程度になる。

 提出 #51724886 (AC / 114 Byte / 97 ms)

 H - Winter Road (400 点)

問題文の表現にひっかかりがありますね。「氷の張ってある道をなるべく通りたくないです」「氷の張ってある道を通る時間を最小化して街 N に移動するとき」。要するに氷が張っている道を通ることもあると言っている。01BFS みたいに、氷が張っている道を0回通る場合の最小値、1回通る場合の最小値、2回の場合の……、を N にたどり着くまで繰り返して求めれば良さそう。うまくやればいらないかもだけどプライオリティキューを使ってダイクストラ法をした。

 提出 #51749960 (AC / 1166 Byte / 674 ms)

01BFS ということでこれは2本のキューを切り替えながら使った。

 提出 #51755608 (AC / 968 Byte / 704 ms)

氷の上を何回通ったかと経過時間とを1つの値にエンコードすることで、キューを1本だけ使う普通のダイクストラ法になった。

 I - Swap and Sort (400 点)

まずは問題を理解する。ある要素を1つ後ろに移動し、その際に K を加算する、というのが操作。

最初は後ろにある要素に操作を繰り返して大きくすることで昇順の列を作ることを考えた。最低2つの要素があれば、交互に操作対象に選ぶことで任意の回数 K を加算することができる。2つの要素の初期の差を解消したり拡大したりすることはできないけど、1回の操作で昇順にできるので問題ない。

これの問題は K=1 で Ai が上限の 10^9 に近いとき。初期数列が A1=10^9、A2=1、A3=1 だったとして、A2 と A3 に操作を繰り返して A1 以上にすることは可能だけど、操作回数が 50 万を超えてしまう。

次に考えたのは、最小値を列の前に持ってくること。i 番目に最小値があるとして、i-1 から 1 まで下りながら操作することで A1 から A_{i-1} にそれぞれ K を加算しつつ、Ai を先頭に持ってくることができる。以降これより後ろの数列に対してどんな操作を繰り返したとしても、Ai より小さい値が後ろに出現することはなく昇順が保たれる。

初期数列が降順にソートされている場合が最悪ケースだけど、N*(N-1)/2 回くらいの操作で昇順になる。N≦1000 だからちょうど操作上限の 50 万回を下回るくらい。

 提出 #51750508 (WA)

しょうもないミスをした。

vector の任意の位置から値を追い出すときに、末尾の要素とスワップしてからポップするというテクニックがある。順番に意味がないときは使って損がない。

順番に意味はあったのだ。順番が保存されていないと正しい操作対象が選べない。いや、自分は壊れた順番の中で正しい対象を選んでいたのだけど、そのせいで勘違いしたのだけど、ジャッジが正しさを検証できなければ意味がない。

 提出 #51750693 (AC / 224 Byte / 278 ms)

 E - Thin Ice (300 点)

300 点だけど難しかった。これが解けたのが嬉しくて今日の日記を書いているところがある。

  1. K=1 ならひと筆書きということで、ケーニヒスベルクの逸話で有名な、次数に着目した判定法がある。
  2. でも K>=2 の場合は?
  3. たとえば1つの頂点から3つの頂点が出ているテトラポッド型のグラフの場合、ひと筆書きはできないけど、K=2 なら全ての辺を2回通ることができる。
  4. 2つの丸が1本の辺で繋がっているメガネ型のグラフはどうだろう。
  5. 円に直径を引いたような日型のグラフはどうだろう。
  6. 頂点数が最大 20 万個あるときに個別具体的な判定はできないよ。
  7. 最近の ABC-G で、グラフだけど木なんだと、木として考えていいんだというコメントを聞いた。
  8. 木だったら簡単に判定できますか?
  9. すべての辺をちょうど2回通ることで、木の根をスタートしてすべての頂点を訪れ木の根に戻ってくることができる。DFS のルート。オイラーツアーと辺の関係を maspy さんが書いていた。
  10. グラフを木+余分な辺と考える。なんなら余分な辺は余分な木かもしれないし、余分なグラフかもしれないが話は変わらない。余分な辺に寄り道をして戻ってきてまた DFS を再開することで、どんなグラフでもすべての辺をちょうど2回ずつ通って、任意の頂点をスタートして同じ頂点に戻ってくることができる。
  11. K が偶数の場合の答えが出た。
  12. K が奇数の場合、K=1 が Yes なら Yes だ。
  13. 提出 #51755274 (AC / 127 Byte / 291 ms)
  14. K=1 が No でも K=3 なら Yes になるケースがないとは確認できていないんだけど、どう考えたらないと納得できるんですか?

とある赤い亀さんの日記を読みました。

  1. 「K 倍してオイラー路」ってどういうことだろう
  2. K 回通る、ではなく、K 本の辺を1回ずつ通る?
  3. あー!
  4. 答えを聞いても理解できない鈍さが嫌になるね

学びのある問題だった。