/ 最近 .rdf 追記 設定 本棚

脳log[2023-01-27~]



2023年01月27日 (金) 隻狼(SEKIRO)。3年前にプレイしていて(20200113)、先月初めてクリアして(20221205)、今は3つ目のエンディングを見た。3周目の梟戦 (249 MiB!)3周目の弦一郎・一心戦 (313 MiB!)。ボス戦をやってると冬なのに手汗と腋汗がすごい。玉になって伝ってくる。デモンズもダクソもブラボも何周もしなかったから、やっぱり隻狼が一番好きだな。


2023年01月26日 (木) 法務省人権擁護局「みんなで「いじめ」をゆるさない いじめをなくすためにできること。いじめ・じんけんについて考えよう」■非常に怖い言い回し。「みんなで「いじめ」をゆるさない」。こういう全体思想、連帯思考がいじめの背後に構造的にあると思ってる。つまり、個々人がばらばらなら諍いがあってもそれは喧嘩と呼ばれるのであり、集団対集団でも別の呼び方があるとして、いじめと呼ぶときには被害者が個人であるのに対して加害者傍観者が集団として存在していることが想定されていると思う。群れがなければいじめは存在しない道理。それなのに「みんなで」と連帯を呼びかけるとは。「ゆるさない」という強い言葉で正当化される非難や暴力の存在を示唆するとは。怖いよ。いじめは人間関係の淀みなのであり人間を集団にすればそれも未成熟な人間を集団にすれば必ず生じるものだと思う。プレッシャーをかけて何が解決する。理想的には対話によって被害者の人間性が回復できればいいけど、それ以外には距離を取らせる、避難場所を用意する以外に何ができる。恐怖で支配する? 全員を均質なロボットにする? 人間の密度を下げる?(人間をふくらませるという意味ではありません)。密度を下げるのは衝突を減らすのに効果がありそうではある。


2023年01月25日 (水) [AtCoder] 精進。ARC139-B「Make N」(青 diff)。以前に原型はできていた。A 増やすに際して Y もしくは A*X の低い方を費やす。B 増やすに際して Z もしくは B*X の低い方を費やす。C=LCM(A,B) 増やすに際して C/A*Y もしくは C/B*Z もしくは C*X のうち一番低いものを費やす。C に満たない半端に対しては総当たりで間に合う。基本の考え方はこう。ところがこれだけでは一部合わない。■提出 #38315434 (AC / 274 Byte / 230 ms)。最後の決め手は6行目の nc = [n/c-1,0].max*c. N を LCM(A,B) と半端に分けて考える代わりに、LCM(A,B)1回分と半端をその他として取り分けて考える。正直よくわかりません。一晩経ってひらめいて試したら AC だっただけ。■■■@kyopro_friends「1 以上 N 以下の整数のうち、2 以上 M 以下の数を約数に持たないものの個数を求めて下さい。[制約] *1≦N≦10^{16} *1≦M≦20 *入力はすべて整数」 DP と包除原理でサンプルの2までは答えが合った>解答。M≦72 のサンプル3は TLE になる。むむむ。関連するマシュマロ質問に「素数の積」とあったので素数だけを取り出してみたらサンプルの3も合ったっぽい(先頭と末尾の数桁の一致を確認)>解答2。まだまだだなあ。■@2023-01-26 今日のお風呂での話。20230124 に中国剰余定理で解いた ABC286-F「Guess The Number 2」の反芻をしているときに、kyopro_friends さんの即興問題とのあいだの共通点に考えが広がって、もてあそんでいるときに「この問題なら、最初から割り算で計算すればオーバーフローのことを気にする必要はないけどねー」の意味がひらめいた。自分の解答2でいうと最後から2行目に N/c という式があって、c というのが素数の積。C++ のように整数型のビット長が固定の言語では c がオーバーフローするおそれが現実的な範囲にある。ここで、割る数(c)を大きくする代わりに割られる数(N)を小さくしていくのも同様にありだなーと、あのツイートはこういう意味だったのかーと、一日遅れで頭に血が巡ってきたという話。これがファイナルアンサー>解答3。割る数(a)は M 以下だし割られる数(n)は N 以下。入力を超える数がないからオーバーフローもない。


2023年01月24日 (火) [AtCoder] 精進。ABC286-G「Unique Walk」(黄 diff)。おめでたいことがあったらしいです。「bk_cocoaさんのウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)での成績:248位 パフォーマンス:2111相当 レーティング:1140→1283 (+143) :) Highestを更新しました! #AtCoder #ウルシステムズプログラミングコンテスト2023(ABC286) https://t.co/043KXpCjAX」。A-EG の6完らしい。G 問題の AC 抜きでも「終了 30 秒前にようやっと5完を確保した」自分では勝負にならない。F も G も問題を読む時間さえ作れなかった時点で負けが確定している。素直にすごい。F がダメでもあわよくば G を狙うという姿勢がなければ望めない結果ですよ。■提出 #38290988 (AC / 456 Byte / 374 ms)。必ず1回だけ通らなければいけない辺がある。No になる条件は何か。最小の例はたぶん4頂点3辺の星型のグラフですべての辺を一度だけ通らなければいけないもの。条件付きの辺を一旦とりわけてその他の辺が作るグラフとの関係を考える。1回だけの辺が結ぶ2頂点が同じ連結成分に属するなら代替経路があるということで、その辺はあってもなくてもいい存在であり1回だけ通ることも自由にできる(通った後で元の頂点に戻ってくることで通った結果をキャンセルできるので)。異なる連結成分を結ぶならその辺は橋であり代替経路が存在しない。ただし代替となる橋が存在する可能性はある。ひと筆書きできるかどうかは頂点の次数の偶奇を見ればわかるというのは有名な話>「ケーニヒスベルクの七つの橋問題」。解けると信じて臨んだ結果解けました。負けないっ。


2023年01月23日 (月) 某帖で知ったのだけど「パーセントポイント」という言葉があって Wikipedia にページがあるらしい。以前から新聞で使われているのを見ていて、50 % が 40 % に下がったときにその量を 10「パーセント」と表現すると意味が曖昧か不正確だからだろうとは思っていた。便宜的な表記ではなかったのか。■■■「dir って何て読みますか?(アンケート)」 罠が存在することにすら気付けない罠だ……。ディレクトリからエクトリを除いたらディル以外に考えられなかったけど、これはカタカナ思考だったか。関係ないけど char は(頭の中で)チャーって読んでる(ない a は読めない←キャラ派の否定。シャアって読む人いるのかな)。


2023年01月21日 (土) [AtCoder] 今日はウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)があった。終了後に読んだけど F 問題「Guess The Number 2」は中国剰余定理の香りがします。今日の精進はありません。自分のすべての提出。9時半から1時間以上 E 問題「Souvenir」(スーヴェニール? フランス語っぽい? 意味は調べなかった。そんな暇はないねん)のバグ取りに費やしていて終了 30 秒前にようやっと5完を確保した。何も難しいところはなかった。ワーシャルフロイド法をやるだけ。それなのに距離におみやげの価値をエンコードする部分で一生バグらせていた。センスないよ。■F 問題の制約を緩めて(あるいは厳しくして) N の全探索で解く方法を考えてたんだけど、えっと、ある周期で循環するグループをいくつか作りたかったんだけど、k 回目で fk(i)=i になった瞬間に変化が止まるよね。循環させられなくない?■@2023-01-24 1回1回 A 数列を置き換えるとは書いてないのかな。うっかり者の役に立つサンプルをくれ。■N を探索する愚直解法と中国剰余定理を愚直に解く解法ができた。でも P = 2,3,5,7,11,13,17,23,29 としたとして P.sum = 110P.inject(:*) = 340510170 なんだけど、N の上限が 10^9 だから 10**9/340510170 = 2.93 ということで確率3割の当てもんになる。え、どうするの? 何回でも提出する? 法に合成数を使うことで何か変わる? なんでそんな意地悪するの?■提出 #38300369 (AC / 904 Byte / 78 ms)。29 を除いて 2 と 3 を 4 と 9 に置き換えることで P.sum = 108P.inject(:*) = 1338557220 > 10**9 にできた。今日の収穫は、中国剰余定理の答えを愚直に求めても許されるとわかったこと。小さい方の法の大きさを上限とするステップで答えが見つかる。これからは中国剰余定理わかりませんであきらめなくて良さそう。


2023年01月20日 (金) [AtCoder] 精進。ABC244-F「Shortest Good Path」(青 diff)。当日はなんか色々アドホックに短いパスを作る方法を考えるも提出に至らなかったんだけど、今日は愚直に頑張って探索をした。半分全列挙の反省から(「半分全列挙の問題が半分全列挙だと教えられる前に解けたためしがない。強いて言えば制約の数字に特徴が現れるが、手掛かりがなさすぎる」)、指数時間が通る制約だなと意識できたのが解答の方針を決めるヒントになった。提出 #38176946 (AC / 412 Byte / 3920 ms)。問題を作る方が難しそう。制約、制限時間、停止すること、最悪時間。解く方は祈って出すだけ。


2023年01月19日 (木) [AtCoder] 精進。昨日「次に埋まりそうなのがあと6問(279/285)である ABC-C」と書いたので6問を埋めた。5問は灰 diff だったけど ABC025-C「双子と○×ゲーム」が青 diff だったのでそれついて。■提出 #38160016 (AC / 941 Byte / 73 ms)。過去に埋め損なっているとはいえ今ではこの型の問題は何度か経験がある。とりあえず1手指したふりで相手方の得点を占ってから手を選ぶ。メモ化再帰で、盤面は3進数で。■数だけでいえば次に埋まるのはあと 10 問(97/107)の ARC-B なんだけど、黄水橙水橙黄緑水青水はきついでしょ。■本当は今日は「「競技プログラマーハンドブック」(Antti Laaksonen氏著)を翻訳・公開しました 基本的テーマから発展的テーマが300ページ超に渡って記載されており目次を見るだけでも興味深いハンドブックです。 「こんなのあるんだ!」という皆様のわくわくの助けになれば幸いです。 PDF: https://t.co/in2H7x6QdW https://t.co/QaaXOvs7yc」の本を読み進めていて、何度か名前だけは見かけたことがある(でも一度も調べなかったんだね) Z-Algorithm が出てきたので、前々回の ABC284-F「ABCBAC」(水 diff)を解こうとしていたのだけど、頭が爆発して書ききれなかったのだった。


2023年01月18日 (水) [AtCoder] 精進。107 問ある ARC-A のうち最後に残った1問 ARC128-A「Gold and Silver」(茶 diff)。コンテスト当日も(#26588127 WA×6)今日も(#38133790 WA×6)、現在持っている金と銀の量を保持して、金を銀に(銀を金に)交換した方が得をする場合に金(銀)の量と取引履歴を更新していった。なんか今日の方が遅いしメモリ消費も多いし同じケースで WA になってるし、バカなの?■今日の2個目の提出 #38134402 (TLE×5)。小数の代わりに有理数を使ったら WA が1減って残りの WA が TLE に化けた。TLE の背後に WA が隠れている可能性はあるけど、たぶん考え方は間違ってないんだと思う。交換レートである A の値の上限が1ギガであるときに愚直に金銀の量を変化させていってはいけないのだ。■提出 #38140604 (AC)。現在持っている金の量と現在持っている銀を金に交換した場合の大小関係が問題なのだから、現在持っている金の量を1に固定して銀の量を金の量に対する比率で保持しても問題がない。そこから整理すると過去のある時点の A の値と現在の A の値の大小を比較するだけになって、小数や有理数で比率を保持する必要もなくなった。あとは取引履歴を記録するのに配列を複製する非効率を避けるなどした。■これが茶 diff とは信じがたい。たぶん見えていないものがあって遠回りな考え方をしてるんだと思う。たとえば過去のある時点の A と現在の A の比較ではなく隣接する2つの A の比較だけでいいらしいけどその理由とか。ともあれ現時点で ARC-A が全部埋まった。他に埋まっているものはない。次に埋まりそうなのがあと6問(279/285)である ABC-C。


2023年01月15日 (日) [AtCoder] 今日は ABC285 があった。自分のすべての提出。A-E の5完。かけた時間が A=2分 / B=15分 / C=6分 / D=8分 / E=(21+27)分。■やるだけの B 問題「Longest Uncommon Prefix」の問題文が難しすぎた。パラメータが i,k,l と3つもあるのが良くない。1つを固定して2つ目を動かしているうちに3番目のパラメータに目移りしてその隙に固定していたはずの1つ目が動き出す。その繰り返し。■C 問題「abc285_brutmhyhiizp」は桁数を固定して 26 進数を足していった。■D 問題「Change Usernames」は「お前が名前を変更するのを待ってるぜ」行列を作って変更できる人からどんどん変更していった。グラフ用語で Functional Graph というらしいというのをちょっと前のなもりグラフの問題の時に読んだ気がする。このとき>20220827。解答に際してはグラフとか閉路とかは考えずに単にシミュレートしただけ。待ち行列を配列にしたのは失敗で、1人の改名を複数人が待てるべきではなかった。入力制約のきれいさに助けられた。■最後は E 問題「Work or Rest」。曜日がループしているのでとりあえず1日目を休日にする(最低1つある休日を1曜日と定めたともいえる)。問題文をわかりやすいように解釈すると、休日どうしが近傍の平日の生産性を早い者勝ちで取り合う構図になる。i 日目を休日にしたときの生産性の合計の最大値を記録する DP で、i-1 日目が最後の休日だったら、i-2 日目が最後の休日だったら、と考えていく。係数が2分の1なので N^2 = 2500万でも通るはずだと思ったけど TLE だった>提出 #38064073。ループの回数が2分の1でもその中で配列参照1回に関数呼び出しが3回、関数呼び出し1回につき配列参照2回で、ループ1回当たり 10 の処理をしていたのでは足が出る。Ruby にとってはそういう厳しい制約。これが通っていれば E にかけた時間は 21 分だったけど、TLE 解消に 27 分かかったよね。提出 #38078419 (AC / 1026 ms)。改善ポイントは2つで、1つ目は P (生産性)関数を予め計算してメモしたこと。2つ目は DP で記録する値に i に固有の値を加算していたせいでその値を利用するときには減算していたこと。加算をやめれば減算もいらない道理。なお、この改善はコンテスト終了後のものであり、コンテスト中は C++ で AC を取った。サンプル2の答えが 33 ビット整数だったから 64 ビット変数を使ったらローカルでは実行時エラーになった。コードテストでは通ったので提出したら AC だったけど、慣れないものは使いたくないものだ。■Ruby で自分の改善バージョンより倍ちょっと速くなるらしい>「ABC_285_E "Work or Rest"をrubyで解く」。■F 問題「Substring of Sorted String」はセグメント木で範囲内が昇順かどうか判断できる気がしたけど RE に加えて WA もあるのではお手上げ>提出 #38082557 (WA×8 / RE×1)。一部に AC もあるけどこの提出 #38074190 の AC と一致しているのでは価値がない。この提出は隣接する2文字の転倒関係だけに注目した勘違いの産物だから。■転倒位置の管理が意図に対して誤った手段、というわけではなく、いつもの手抜きセグメント木を修正してモノイドを載せる試みが(RE×1を除いて)失敗というわけでもないとしたら、そもそもの考えが足りていないために AC が9個足りない結果になっている可能性がある。なんだろ。■「S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。」 折りたたまれた用語の説明を読んでいなかった。今回の「部分文字列」は連続部分文字列と呼ばれることもあるものだった。やつあたりに聞こえるだろうけど、知らない人のための用語解説なら折りたたむのも結構だけど、問題の一部としての定義なら隠してはいけないと思う。■F 問題。提出 #38104204 (AC / 1984 Byte / 634 ms)。ソースを見るに余裕のなさが窺える。「脳みそに余裕がなくなるとクラスや日本語変数がソースに現れる傾向があるみたい」。日本語をクラス名にするために Class オブジェクトを明示的に new しているとはずいぶんな余裕のなさ(※日本語は小文字扱いなので(=定数ではないので) class 構文が使えなかった)。間に合うみたいだったのでセグメント木はやめて転倒位置をソート済み配列で管理する当初の方式に BIT 26 本の利用を付け加えた。これを時間内に解くのは無理だよ、量的にも。青 diff でした。青 diff ならもう射程に入ってないといけないんだよなあ。■経緯を忘れてあらためて考えると、転倒位置の管理に BIT を使わない理由がないなあ>提出 #38325205 (AC / 1645 Byte / 593 ms)。BIT 27 本。


2023年01月14日 (土) [AtCoder] 精進。今日あった ARC153-C「± Increasing Sequence」(青 diff)。コンテスト中は場合分けをして簡単なケースから答えを作っていた。たとえば、N=1 なら答えは 0 しかない。A 数列が 1 のみまたは -1 のみだった場合は、1個だけ符号を反転させて項数 N-1 の等差級数と打ち消し合わせればいい。幸い N の2乗より大きい値を使うことが許されている。他には 1 の列と -1 の列が混じり合わず隣り合っているケースの答えなどを作った。そんな具合に特殊ケースを捌いていって、最後に残ったのがサンプル1のケース。つまり、2個以上の 1 と -1 が混じり合ったごく一般的なケース。ここで手が止まって時間を迎えてしまった。■提出 #38021545 (AC / 673 Byte / 194 ms)。最後に残ったケースを考えた結果、そのケースの解法がその他の場合をすべてカバーしてしまっていた。なんじゃそら。考える前に書き始めるからこういうことになる。いみじくも1番目に示されていたサンプルを1番に考えるべきだったのだ。解法はこう。いったん A 数列に 0,1,2,...,N-1 の重みを割り当てて合計を計算する。合計が0ならそのままそれが答え。合計が正なら、重みの後半を後ろにずらしたり、前半を前にずらしたりしてバランスを取る。そのためには A 数列の後半部の累積和が負だったり前半部の累積和が正だったりしなければいけない。合計が負の場合も同様に。■(80 分も残していたのだから)時間内に解けたはずだよ。くやちい。■書ける対象が少ないんだから A と B についても書く。A 問題「AABCDDEFE」(灰 diff)。とりあえずメモに書き出してみた。11、22、33、...、99。そして3桁目からは数字を使うと紛らわしいので 11abccded という感じ。じゃあ 0 を除くという例外規定はあるけども1桁目もアルファベットを使って aabcddefe と表せるな。スクリプトの1行目にコメントとして書き込んでそれを見ながら考えよう。提出 #38005488 (AC / 174 Byte / 64 ms)。提出して WJ のときに問題名が目に入った。最後にタイトルに回帰する見事な伏線回収では。それかお前の目が節穴か。末尾が EFE であることに何か罠があるかと疑ったけど何もなく。灰 diff でした。Ruby で2番目に早く提出されたこちら #38003727 があざやか。自分はこうしたら1桁目が求まるな、次にこうしたら2桁目が求まるなという手探りの手続きを書いて提出したけど、この提出は完全に見切ってから書かれている、しかも時間をかけずに。正直なところ 99999 を足すとどうなるのか自分はわかっていない。■B 問題「Grid Rotations」(水 diff)。慎重に問題文を読んでからサンプルの図解と照らし合わせて誤読がないように努めた。ありがたい図解を眺めていれば、1度の操作で abcde 行がどのように並べ変わるかわかるし、2度の操作でも並び順が入り乱れることがないことが確認できる。行と列の並べ替えが独立していることも容易に推測できる。提出 #38009253 (AC / 378 Byte / 711 ms)。緊張してるのかしらないけど、括弧の対応を間違えたり + を * とタイプミスしたり、まあまあサンプルを合わせるのに苦労した。添字配列を作って Array#values_at を呼び出すのは効率が悪いみたいで、他の人の提出よりいくらか余分に時間がかかっている。Array#rotate を完全に失念していた。


2023年01月11日 (水) ちょっと古い新聞を読んでいたら、交通教本にこういうことが書いてあるらしい。「見えないことは存在しないことではない」■これはまったくその通りで、周囲を見回して人がいないことを確認する、車が来ていないことを確認するというときに、いる・いないの二値ではなく、いる・いない・陰になっていて確認できていないの三値で景色を塗り分けないといけない。いるの否定(=いることが確認できなかった)がいないではないことを認めなければいけない。しかし、すべての免許保持者が NULL を正しく取り扱えるとあなたは信じられますか。私には無理です。


2023年01月10日 (火) デスストランディングの耐えられないところ。デスストが悪いというのではなく、プレイヤーの性質に関わること。何か。BT への対処と優良な配送への努力(時雨、転倒による荷物の劣化対策)を同時に求めるのをヤメロ。荷物は1つも落としたくないし劣化させたくないしバイクからも降りたくない。でも BT がいるところ雨が降っていてケースが劣化する。劣化はリペアスプレーで対処できるけどバイクを降りたらその後の配送がだるいから駆け抜けたいけどほぼ成功しない。捕まれば荷物が落ちて劣化する。最近は素直に捕まって流されて大型の BT を退治すれば晴れ間が訪れてすっきりだと了解していたのだけど、廃墟で回収物を集めているうちにまた雨が降り出して BT が現れたじゃない。同時に対処させるのをヤメロ。俺は一度に2つのことはできない。荷物を回収して届けたいんだから BT は引っ込んでろ。一度の対処でもうたくさんだ。という愚痴を PS4 の電源を切って書いているのが今。することがあるときに横槍を入れられるストレスに耐えられませんでした。