/ 最近 .rdf 追記 設定 本棚

脳log[2024-05-22~]



2024年05月22日 (水) 驚異(キョウイ)脅威(キョウイ)が区別されていないと感じる文章が少なくない。自分は驚異=wonder、脅威=threat と結びつけることで区別している。この対応自体が Wonders of the World (en.wikipedia.org) の訳は世界の七不思議 (ja.wikipedia.org) じゃないよね、七大驚異だよねという認識から来ている。細かいことをいうとこの用例での Wonder は自然や人が作り出した絶景(驚嘆すべき構造物)という限定された意味を持つらしいので驚異では不十分なのだけど、そこの事情は英語でも変わらないっぽい? つまり、wonder が特にそういう限定された意味を持つというわけではなく、限定された意味を持たされた用例が存在しているだけなのだろうということ。元はギリシャ語にあって「眺めるべきもの」を意味する言葉だったがラテン語を経由するときに意味が足りなくなり英語を経由したときに意味が転んでしまったみたいな経緯が日本語のウィキペディアに書いてある。人間は概念を直接やりとりすることができず概念に与えた恣意的な輪郭である言葉をやりとりしているがゆえに異言語間ではずれが生じる、みたいな。異なる人間と人間のあいだに共通概念が存在できるのかどうかもわかりませんが。ともかく、脅威に対しても wonder に対しても驚異って単語が出て来ないせいで誤ってしまうのは認知度が低すぎるので、意識して脅威≠驚異=wonder の関連付けを行っているという話。


2024年05月18日 (土) [AtCoder] 今日はパナソニックグループ プログラミングコンテスト2024(ABC354)があった。8時半をまわってから2回もハードウェアエラーでブルースクリーンが出て、Rated で参加するのをためらったけど、コンテスト中に再起動が必要になることはなくて助かった。ていうか、再起動してもダメなんだよ。ブートデバイスが見つからないって出る。つまり、起動中にいつの間にか C ドライブを見失っていて、それがスリープ移行中や復帰中に発覚するとブルースクリーンが出る。それ以外のタイミングだと IO 待ちで一部のプログラムがフリーズするのみで何もできなくなるまでにわずかの猶予がある。いずれにしろ再起動しても C ドライブを含む SSD は見つからないまま。SATA ケーブルを抜き差ししてお茶を濁すということを1年以上前から続けている。数回のブルースクリーンでパーティションが飛んでいた FAT32 と比べて一度も壊れたことがない NTFS の堅牢さは素晴らしい。もちろん、ファイルシステムが壊れていないからといって個々のファイルが壊れないわけではないのだけど。という話はもういいや。結果がまだなのでふりかえりから。■A 問題「Exponential Plant」。やります。朝と夜の区別が地味にやっかい。脳のリソースが奪われる。サンプルの解説文に何を判断基準にするか、何を答えるかが書いてあるのでそれを素直にコードにする方が早かった。■B 問題「AtCoder Janken 2」。やります。A 問題より素直。■C 問題「AtCoder Magics」。強さの順もしくはコストの順に処理をする。今見ているカードを基準にして捨てるカードを捨ててから追加する。スライド最小値の要領。■D 問題「AtCoder Wallpaper」。前回の F 問題 Tile Distance と似た見た目の図があるけれど、D 問題ということで素直に計算できるのかなと期待する。2倍した面積を答えるのだから、三角形の数を数えればよい。X 軸方向の周期は4で、 Y 軸方向の周期は2だから、単位面積当たり計8通りのパターンがある。あとはそれぞれの数を数える。自分は頭より先に手が動くタイプなので、スマートな式を考え出すよりも case 式で場合分けをいっぱい書いた。場合分けの数だけバグが潜む場所が増えるのでリスキーではあるが、考えても答えが出て来ないリスクも無視できない。■E 問題「Remove Pairs」。先に F 問題までひと通り目を通してから実装を始めることにしている。泥沼にはまりかねない D 問題に対して E 問題は素直にメモ化再帰をするだけだと思ったので先にこちらを解いた。6分半で書いた最初の提出が TLE で、そこからペナルティ込みで 17 分余計にかかったのが残念。ABC349-E Weighted Tic-Tac-Toe が解けたら解ける。■F 問題「Useless for LIS」。左右から LIS をやって自分の左の増加列と右の増加列の長さ+1が、自分を含む増加列の長さ。これが最長と一致しているかを確かめる。LIS のやり方を忘れていて思い出しながらの実装だった。でも、LIS というのはトランプ挿入ソートを解いていたこのとき(20200602p01)に、名前も実装方法も知らないで解法を考え出した経緯があるので、思い出せないはずがない。忘れてもでっちあげられる。■日記を書いていたら結果が出た。コンテスト成績証自分のすべての提出。1895 の青パフォで +33、レートは 1631 (青色) になりました。初めて青色になりました。ここ3回の ABC、ARC、ABC で +52、+24、+33 というのはできすぎた結果なので、すぐに水に落ちた後で水青の反復ができるとも思ってないよ。


2024年05月13日 (月) 呼び出し元と呼び出し先の境界たる関数のシグニチャは、引数の型は、プリミティブなものを第一にすべきだという考えを持っている。関数の本体で高機能で高コストな便利クラスが使いたい? 使えばいいよ。でもそれは実装の詳細であって、呼び出し元の知ったことではない。逆についても言える。新しく関数を定義してコンテクストを分けるとき、関数の内部が特定の、現在は唯一のでもあるかもしれないがそうであっても、呼び出し元の影響を受けすぎるべきではない。呼び出し元は便利クラスの殻をむいてプリミティブな実体を渡すように努めるのが良い。何がプリミティブかという部分で、判断のすりあわせが必要になるかもしれない。■呼び出し元に無駄にオブジェクトをコンストラクトさせるなという話であり、呼び出し先が必要としないオブジェクトを無理に押しつけるなという話であり、関数の内と外が DLL という形でバイナリ境界をまたぐときに malloc/free に互換性があると思うなよという話。


2024年05月12日 (日) [AtCoder] 今日は AtCoder Regular Contest 177 があった。コンテスト成績証自分のすべての提出。AC までの所要時間が、A=5分、B=8分半、C=20分。計34分で3問解いておしまい。昨日に続いて Highest 更新は嬉しいんだけど、焦らしますねえ。あと +2 で青タッチだよ。青になって青を維持するためには ABC-F が半分以上の確率で得点できないと無理だと思ってるよ。今は精進で6割埋められるくらいかな。得点にできていない。ではふりかえり。■A 問題「Exchange」。DP でさえないし、愚直に1枚ずつカウントして許される制約。日本の硬貨は5倍2倍5倍2倍5倍と規則正しく増えていって完全に小が大をかねるので、使いにくい大きい硬貨から貪欲に使っていく。■B 問題「Puzzle of Lamps」。左からしか操作ができないので、一番右から目当ての状態を作っていく。■C 問題「Routing」。赤の道と青の道が X 字に交差するので、どちらの色でもある紫色を最低限だけ配置する。最初はちょっと難しく考えすぎていた。赤にとっての最善というのは、(1,1)が属する赤の島と(N,N)が属する赤の島を赤の島を経由しながら紫の道で連結していくことで求められる。それは 01BFS でできる。青の道の最善も同様にできる。で、考えすぎていたのは、それぞれにとっては必ずしも最善ではないけども、共通部分を大きく取ることで全体として紫の数を最小化できるケースがあるのかなと思ったこと。そんなケースはない。赤にとっての紫の道は必ず青を変化させているし、逆に、青にとっての紫の道は必ず赤を変化させている。お互いの紫の道に共通部分はない。じゃあ 01BFS を2回やってコストの和を答えにするだけ。■D 問題「Earthquakes」。DP ですよね。前からの値と後ろからの値を突き合わせて答えを出すのかなと。2^N 倍した数を答えにするというから、確率ではなく場合の数を足し合わせていったものがそのまま答えになるのかなと。正しい答えが出て来ませんでした。


2024年05月11日 (土) [AtCoder] 今日は AtCoder Beginner Contest 353 があった。コンテスト成績証自分のすべての提出。E までの問題を読んでから A から順番に書き始めた。A 問題の AC が9分30秒時点だから、だいたい9分くらい問題を読んでいた。それぞれの問題の実装時間が、A=30秒、B=4分、C=11分、D=5分、E=11分、F=36分(読解含む)。C 問題が難しかったよね。ではふりかえり。■A 問題「Buildings」。ループを回せますかという問題。Ruby を使っているなら、ループという汎用的で原始的な道具ではなく、ループを使って何がしたいかという目的別に特化したメソッドを選んで使う。意図が明らかなコードを書く。C++ でも <algorithm> の中に何があるかひと通り調べておいて、使う機会を常に窺っておくのがいい。■B 問題「AtCoder Amusement Park」。前から順番に K 人を超えない範囲でグループを作っていくといくつになりますかという問題。やるだけではあるんだけど、テストがないと不安がぬぐえない。祈って提出しました。K を超えた数を数えていた場合、最後のグループを数え忘れるというのが、考えられる罠かな。■C 問題「Sigma Problem」。CDE と続く Sigma Problem の第一弾。二重のシグマは見慣れていないとびっくりするけど、シグマのそれぞれの範囲を見れば、考えられるすべての組み合わせについて足し合わせるという意味だと読める。基本的には answer += a*A.size+A.sum while a = A.shift なんだけど、2要素の和が 10^8 を超えるときは 10^8 を引かなければいけない。A 数列の順番には意味がないので、予め A 数列をソートしておいて、何個の要素が 10^8 を超えるかを効率良く数えられるようにする。二分探索なら log が付くけど間に合うし、尺取りっぽい操作をするなら log は付かない。あっ。自分の提出 #53343786 で 10**8 に付けた名前が P(rime number) というのは嘘だ。■D 問題「Another Sigma Problem」。今度は2要素を文字列として連結してから数値として評価をする。順番に意味があるので並べ替えてはいけない。右側にある要素について、数の和と、下駄の和がわかればいい。下駄というのは、3桁の数字であれば 1000、4桁の数字であれば 10000 を計上する。これを全要素について数え上げておいて、更新しながら答えの計算に利用する。■E 問題「Yet Another Sigma Problem」。かかった時間だけ見れば C 問題と同じなんだけど、配点通り CD より難しかったと思う。自分は Ruby の記述力におんぶにだっこで効率の悪い解答を書いた。まず、N 個の要素について、先頭の文字を見ます。同じ文字だったもの同士をグループにして再帰的に次の文字を見ます。その過程で、グループの大きさを見ます。大きさが Z なら、作れるペアの数(Z*(Z-1)/2)がそのまま答えに寄与します。■F 問題「Tile Distance」。わかりやすい図が付いていてたいへん助かります。K=1 は簡単。マンハッタン距離が答え。それ以外はどうしましょう。最初はフラクタル的に考えてみようとした。スタート地点とゴール地点が隣接していると見なせるまで K を定数倍してみる。で、視点をズームインしながら移動コストを足していけないかと。できなかった。次は大きいタイルと大きいタイルのあいだの移動コストを数えようとした。横方向の移動コストだけを考えてみる。K が大きいなら、上下にあって頂点で接している大きいタイルを経由することで、必ずコスト4で真右にある大きいタイルへ移動できる。K=1 のケースはさっき除外した。K=2 の場合は小さいタイルをそのまま突っ切って移動する方がコスト3なので安い。そういう計算をしているうちに、斜めの移動コストが特に安いと気がついた。K マスを1と数える大きいタイルの座標系で考えてるよ。例えば右に2、下に2の位置にある大きいタイルに移動したいとする。右に移動してから下に移動するなら、さっき計算したコストを使って 3+3 (K=2 のとき) か 4+4 (K>2 のとき) になるけど、ありがたい図を使って数えてみると、たったの4で右下の右下にある大きいタイルに移動できることがわかる。というわけで、まずは斜めに移動して、それから縦もしくは横に移動すると考えると、最適な大きいタイル間の移動コストが求められる。あとは1または4通りと、1または4通りの総当たり(1x1 または 1x4 または 4x1 または 4x4 通り)でほぼ答えが出る。1と4が何かというと、スタート地点ゴール地点から最寄りの大きいタイルの数。「ほぼ」が何かっていうと、スタートとゴールが小さいマスにあってすぐ近くにある場合。これは K=1 の場合のマンハッタン距離と同じだから、提出 #53370051 では K=1 の場合を分けるのをやめて雑に一体化した。全部混ぜ混ぜして最小値を取れば自ずと答えが出てくる。■G 問題「Merchant Takahashi」。今日の G 問題は F 問題と配点が同じ。F 問題を通してから G 問題を読んで、することがなくなったので順位表を見たら F より G の方が通されていたね。自分は G 問題がさっぱりだったけど、データ構造で一発なぐるだけの典型だと仮定して眺めてみれば、移動コストによる報酬の減殺が組み込めるなら、セグメント木が使いたい形だと思った。もちろん組み込めないのだけど。■Highest を更新したけど、明日の ARC の参加費は何レートかな。何レート吸われるんだろう。3-4-5-(略) という配点は水色の自分向けド真ん中なので出ないわけにはいかないんだよな。■■■精進。G 問題。セグメント木を2つ持つんだと2か所で読んだ。それでどうやって距離による減殺を組み込めるかを考えた。左右の端、頂点1と頂点 N にいると仮定したときの所持金のポテンシャルをセグメント木の各要素の値とすると、イーブンな条件で大小比較ができて最大値が取り出せる。提出 #53408933 (AC / 849 Byte / 1999 ms)。2秒制限で 1999 ms は神がかっている。だめだったらセグメント木にブロックを渡す代わりに max メソッドの呼び出しを直に埋め込むだけ(手動インライン展開)。■実際の値の代わりにイコール条件のポテンシャルを扱うのは ARC120-C Swaps 2 でやったことがある。20211022p01。なんでそんな名前で呼んでるのかは自分でもわからない。なんとなくふさわしいような気がしただけ。


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行になった。各所で読んだのだけど、セグメント木についてはまったく頭に浮かびませんでした。セグメント木の図を思い浮かべれば問題の理解が早かったと思う。でもそれが思い浮かんだ時点でもう問題を理解してるよね。