/ 最近 .rdf 追記設定本棚

脳log[2025-10-10～]

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

2025年10月10日 (金) まんがタイムきららって雲母にゆかりがありますか？あまりに遠すぎてまったく想像しなかったけど、きららはうんもなのだな。どちらかというとキラキラとかキキララの方がよっぽど印象が近い。ATOK できららを変換すると熊本県宇城市松橋町きららが出てきた。すてき地名。

ツッコミを入れる

2025年10月04日 (土) [AtCoder] 精進。今日あった ABC426-F「Clearance」。どうやったら効率的に処理できるかいろいろ考えた。主に BIT とセグメント木をどう使うかを。遅延セグメント木で範囲減算をしながら値が負になる要素をトラップして都合良く扱えるだろうか。できそうになかった。商品ごとに要求量を BIT に積み上げていったらどのクエリまでなら在庫が足りるかがわかるだろうか。わかる。しかしここで商品ごとに足りないクエリを個別処理することは Q×N になっていけない。エンコードした在庫を BIT に乗せたら範囲和を取得したあとでクエリに固有の値を divmod 演算で取り出せないだろうか。足してから余りを取るのでなく余りを取ってから足さないといけないのでできない。それに値が大きくなりすぎる。じゃあ商品在庫が何クエリ分あるかを BIT に乗せたら……それでうまくやれるなら最初から素直に個数単位の在庫を BIT に乗せてやれるはずなのでできない。(単位はともかく)在庫を BIT に乗せるのでなく在庫が足りるか足りないかの二値を BIT に乗せるようにしたら……うまくいった。クエリに沿って在庫の有無を更新していく。要求量が k で十分な在庫がある商品が範囲内に c 種類あるなら、k*c 個の商品が買える。要求量に満たない端数は予め処理しておける。■提出 #69886664 (AC / 1693 Byte / 1813 ms)。長さが N だったり Q だったりする BIT が２本(※３本目はいつのまにかいらなくなっていたものの消し忘れ)と、同じような長さで入出力用とは別に配列を３本使っていることからわかるように、とてもたいへんだった。問題を縦に見て横に見て最後にまた縦に見てやっと答えが出る。■■■ABCD4完で水色に戻っていてびっくりした。前回までの ABC なら間違いなく 1100 台の緑パフォでしたよ。だって自分は何も変わっておらず(最近すっかり定着してしまった冴えないパフォーマンスしか発揮できておらず)、直近の８回中７回が 1000 から 1100 台の緑パフォだったんだから、今回も同等のパフォーマンスが出るのが当然だった。■解説を読んだら遅延セグメント木だった。負になる要素はトラップできるし、トラップした後はテキトーに大きい値を設定することで以降は無視できる。在庫切れ商品がどこにあるかは別途 BIT でもセグメント木ででも管理する。できそうにないと思ったことが実はできるらしかった。■提出 #69913286 (TLE×24/AC×14)。F 問題想定解法。予想はしてた。BIT で間に合うところはセグメント木より軽い BIT を使ったのだけど、５秒あってもあかんねんて。これが通るならかなり素直に貼るだけやるだけの問題になるんだけどな。セグメント木には最小値と最小値の位置とセグメントの幅を持たせた。幅１のセグメントにおける最小値というのはある商品の在庫そのものなので別に値を持つ必要がない。そして最小値の位置を記録しているので在庫が負になった商品がすぐにわかる。■■■G 問題「Range Knapsack Query」。kotatsugame さんの動画を見ました (「【競技プログラミング】ABC426【実況】 - YouTube」)。区間を区切って予め済ませておいた DP 結果をマージするというのは自分でも考えていた。テーブルのマージが C の２乗でも２つの結果をマージするときに (重み)=C となる結果を得るだけなら正順と逆順の結果を１対１対応させる線形時間で済ませられることもわかっていた。しかし区間の区切り方としてセグメント木を想定するとしても Sparse Table を想定するとしてもテーブルのマージは対数回発生するので２乗のマージを繰り返すしかない。動画を見て Disjoint Sparse Table について初めて名前を聞きました(「Disjoint Sparse Table [いかたこのたこつぼ]」)。そんなうまい話があるんですなあ。ちなみにアイテムの重みを低く抑えたランダムな最大ケースでローカルでは十数秒かかりました。事前に CNlogN (<150メガ) かかり、クエリに QC (≦100メガ) かかるので、Ruby には桁が１つ以上大きすぎる。それでいて５秒制限でもなんでもない２秒制限なのだ。解説によると「全体の計算量は O(K(Q+NlogN)) です」「K=maxC_i」とのことなので、想定通りの計算量でこの時間らしい。１桁か２桁限定された制約に対して８割くらいの部分点が与えられたら受け入れやすいのにな。

ツッコミを入れる

2025年10月03日 (金) [AtCoder] 「生成AIの技術向上に伴うABC,ARC,AGCにおけるルール変更について - AtCoder」「AtCoder生成AI対策ルール - 20251003版 - AtCoderInfo」■この前の AGC の C 問題が解かれたらしく、とうとう ABC/ARC に加えて AGC も規制の対象になり、規制の内容もこれまでは許容されていた Copilot がダメだし、コーディング言語の変換(Python → C++ など)も、指示に従わずに(ないものを)生成するケースがあるらしく禁止。Web 検索で勝手に表示される AI による回答も見てはいけないとか。一番最初のルールではたしか問題文のコピペ丸投げこそ禁止されていたけど自分の言葉で AI に相談することは許容されていたはずで、でもそんなのはとっくに禁止されている。実効性を持たせられない規制に消極的な姿勢があると思っていたけど、建前だけでも禁止は禁止に。ずるをすることのアドバンテージが増えないかはちょっと心配。AI の性能や使い方を競う場ではなく人間が競う場であろうとすることは自分の希望に添っている。AI によるアシストは事前の学習に役立てるのがいいだろう。■自分についていえば、コンテスト中に検索して見つけたものをすぐに反映させられるほど器用ではないので、検索するというと「２点を通る直線」「直線の交差判定」「素数表ビット」ぐらいでほぼ検索しない。エディタはただのテキストエディタだし、勝手に改行したりインデントを揃えたりされるのも許せない質(たち)なので、整形をはじめ許容されているタイプの補完(IntelliSense)とも禁止された補完(Copilot)とも縁がない。「普段のコンテスト参加スタイル(20230505)」。これでいい成績が出せているなら誰にも何も言わせないでいられるかもしれませんけどね、お前は利用できるものはすべて利用して成績を上げるべきではないのか？思うんだけど、目的指向で行動を計画できることも、損得勘定で行動を選べることさえも、どちらも得がたい才能ですよ。俺は持ってない。ネットの掃きだめでは行動の理由に金銭を当てはめる発言を見かけることがままあるけども(「それをやるだけのお金をもらっていないのでは」「そうはいってもお金だけはたんまりもらっているのでしょう」)、そんなに簡単そうにお金で自分を曲げられるものかと、お金がすべての無理を引っ込めるのかと信じられないでいる。話がずれている。自分は結果を求めて問題を解いていないし、観察すれば成績をあげるために行動しているようには見えない。どのレートにいても簡単すぎず難しすぎない問題を解くことで気持ち良くなることができる。それで満足しているように見える。

ツッコミを入れる

2025年10月02日 (木) 「スズキの新型400cc『DR-Z4S』『DR-Z4SM』ついに発売！価格は119万9000円 | レスポンス（Response.jp）」■さすがのスズキでも 100 万は切れなかったらしい(一方、KTM は……「新型スズキ『DR-Z』のライバル登場か!? KTMの新型スーパーモト発表に「思ったより安い」など熱視線 | レスポンス（Response.jp）」)。海外での価格を円換算したら 130 万円台だったらしいから努力の跡は見える。

ツッコミを入れる

2025年09月30日 (火) 初耳単語２つ。添え乳(そえぢ)。貰い乳(もらいぢ/もらいぢち/もらいちち)。乳を単にチと読むのはそういえば乳飲み子(ちのみご)もそうだった。あれ、乳首(ちくび)もそうか。乳(ちち)というとき自分は白い液体とそれを分泌する胸部を区別してないけど、本来は液体の方だよなーと思って辞書を引くと、(1)が液体で(2)が胸部で予想通り。そこから(3)旗・幕・羽織などの縁につけた、竿やひもを通すための小さな輪、(4)釣鐘の表面にある、いぼ状の突起、と続くのが予想外。(3)に関連しそうな乳環という単語は見たことあるなと思ったけど、これはカーサスの乳環というダークソウル３に出てくる指輪の名称だった。乳環からのつながりで貫乳(カンニュウ。陶磁器の釉（うわぐすり）の表面に現れた細かいひび)と乾乳(カラチチ。乳汁の出ない乳房。また、その女)を発見した。乳という文字が喚起する全体像を自分はまだまだ知らない。

ツッコミを入れる

2025年09月21日 (日) [AtCoder] 精進。昨日あった AtCoder × Engineer Guild オンサイトコンテスト～集結！高レート人材～予選（ABC424）-E「Cut in Half」。K と X の上限の高さに対処する問題。問題に二等分と書いてあるからじゃないけど二分探索を考えた。何を？たとえば長さの上限を探索するとしたら……Ai を何回二等分する必要があるかがわかって、何回倍々に本数が増えるかがわかるので、増えた本数の総数が N+K を超えたかどうかで判断できる。ところで、倍々はビットシフトで計算できるけど半分半分を右シフトでやると小数部分が計算できない。右シフトして消えたはずの部分も固定小数点数みたいに保持したらソートできるかなと考えたりもしたけど、答えが小数なのだから半分半分は小数で計算することにした。自分の解答で探索する上限がストレートに長さの上限(小数)ではなくビット長の上限なのは、思考の回り道の名残か。小数を引数にした２の累乗が普通に計算できると知らなかったことも理由にある。■提出 #69507299 (WA×21/AC×15)。時間内の提出は WA だった。ミスが２つある。■提出 #69515602 (WA×2/AC×34)。１つ目のミスを修正したら WA が２つまで減った。差分は何か。倍々に増えていく棒がぎりぎり N+K を超えないボーダーを探索したあと、ちょうど N+K 本になるように長い棒から半分にしていくシミュレーション部分で慎重さを欠いていた。同じ長さの棒について何本まで折るかという判断をせずに全部折るか全部折らないかで判断していた。ちょっとくらい N+K 本を超えてもええやろの精神。あとで X 番目を数えるのだからダメです。■提出 #69515755 (AC)。２つ目のミスを修正したら AC。18 行目に長さ a の棒を半分半分にして倍々になった本数をカウントする処理があるけど、a よりも探索した上限が大きい場合は手を加えずそのままの a を１本計上するのが正しい。ビットシフトで計算する本数にはシフト数が負にならないようにリミットがかけられていたけど、a の値を増やしてしまうかのような逆二分割を防ぐリミットがなかった。こんなんでは D 問題に費やして無駄になった１時間があっても時間内に AC できたかは怪しい。■提出 #69518302 (AC / 2000 ms)。一番最初に考えたプライオリティキューを使ったシミュレーションは K の大きさを見てすぐに捨てたのだけど、実は倍々で増えていく同じ長さの棒をまとめて操作できるので K の大きさはそれほど問題ではなかったのだった。これは 10 分で書けてバグもなかった。しかし実行時間が２秒ピッタリ！制限時間は長めの３秒かなと確かめてみたら２秒！プライオリティキューにソート済みの配列を渡して初期化しているのだけど、これが空のキューに１つずつ追加していくようになっていたら間違いなく TLE だったね。Ruby だと想定解法が通らない通っても記述の違い定数倍の違いでふるいにかけられる最近の AtCoder の制約は今回も精度が高い。高精度で確実に Ruby を締め出してくる。何が想定解法かこの E 問題に関しては知りませんが。■■■F 問題「Adding Chords」。セグメント木だと見かけたので何を乗せるのか考えた。提出 #69576332 (AC / 533 Byte / 812 ms)。使ったのは BIT。線分同士の関係は何が許容されているか。交差はダメ。隣接と包含は OK。１本の線分は円を左右２つの領域に分ける。領域の境界をまたぐように新たな線分を引くことができない。しかし同一領域内に新たな線分を引くことはできる。２本の線分が作る４個の領域の関係は？一方が一方を含んでいるか交わらないかのどちらか。BIT で領域のスタックを管理する。新しく線分を引きたいとき、始点と終点の土台が構成を同じくする領域のスタックであれば既存の線分と交差なく線が引ける。領域をどのように表現し重なり合った構成を区別するか。１領域に１ビットを割り当てるとあらゆる重なりが区別できるけど、N ビットは大きすぎる。大きな素数で割った余りを領域の ID とし、(領域 A)+(領域 B) が (領域 C)+(領域 D) とたまたま一致する偶然が起こらないことに期待した。前々回の ABC422-E「Colinear」に関連して「確率的な操作を書いたことがない」と書いたけどあれは嘘だ。ローリングハッシュを２回くらい書いて提出したことがある (z-algorithm が理解できないので必ずロリハになる)。

ツッコミを入れる

2025年09月19日 (金) 「「大動脈解離」と言う病気を、専門医が子どもから医師まで５段階に分けて140文字以内で説明した投稿が分かりやすい - Togetter [トゥギャッター]」■初めて名前以外の具体的なことを聞きました。剥がれる裂けるって何が？３層ある血管の最も内側が裂けて内側の外側に血が流れ込んでいる状態。最も内側の血管壁がダメージを受けている。その結果１層減った２層で血圧に耐えていて(中膜が２層に裂けると書いてあるから 1.5 層かも)、血管から血が噴き出すまでのカウントダウンが進んでいる。また、変なところに流れ込んだせいで主要な枝への血流がバイパスされれば臓器が死にかけている。３つ目の致死要因である心タンポナーデというのは心臓を包む膜の中にたまった液体が心臓の働きを阻害している状態らしいが、大動脈解離からどう繋がるのかはまだイメージできていない(どこからどのように流れ込むのか、すでに破滅が訪れた後というわけではないのでしょう？)。A 型って何？解離の部位によって深刻度がかなり違う。上行大動脈がスタンフォード A 型で下行大動脈がスタンフォード B 型。上行というのは左心室から出てすぐの頭の方に向かっている部分のことで、下行というのはそこから折り返したあとの胸部腹部にある部分のことらしい。心臓に近い A 型がより起こりやすくより深刻だというのは負荷を考えればまあそうか。まず半数以上が生きて病院にたどり着かないし、治療が遅れると遅れただけ、1 時間に 1 % ずつ２日(48時間)で半分が死ぬ。こちらのページも参考にした。「大動脈解離が起こるとその生存率は？（前編） - 高齢者の病気いろは」とにかく手術をして血管を補強するのが A 型で、B 型はまずは内科的治療が主だとか。

ツッコミを入れる

2025年09月18日 (木) 自分の(初＆現)スマホが Xperia 10 (初代) なので。「ニュースリリース | 「即撮りボタン」を搭載したスマートフォン『Xperia 10 VII』を商品化」■ニュースサイトを見てからリリースまでさかのぼっても同じ表現で困惑しているのだけど、「発売されたタイミングから起算して最大4回、最新OSへのバージョンアップが適用されます。適用回数は購入タイミングによって異なります。」が意味わからん。後半はわかるよ、買うのが発売後しばらく経ってからだと購入時点ですでにアップデート済みだったりするのでしょう。わからないのが「最大４回」の部分。これは何も保証してないよね。「６年間のセキュリティアップデート※8と最大４回のOSバージョンアップ※9に対応し、長く愛用できます」とあるけど、アップデート回数の上限を定めることと長く使えることが繋がらない。好意的に不確かな解釈をするなら、６年間セキュリティアップデートをします、その間に OS アップデートがあれば４回までに限って対応します、ともかく６年間は安心して使用できる環境を提供します、という意味なのかなと思うけど、不確かだ。だって６年間はセキュリティアップデートに関する言及であって、OS アップデートへの言及ではないからだ(注を読めば何が何を修飾しているか区別がはっきりする)。１年目に OS アップデートがあってそれに対応しなくてもリリースは嘘にならない。最大４回は３回や２回や１回はもちろん０回も含むのだから。「最大４回」と宣言されてもこちらとしては何の意味もなさない。後でアップデートをサボったときの言い訳に使えるというそちら側にとっての意味しかない。それが本意ではないなら日本語と論理を学んでくれ。■「※8 発売されたタイミングから起算して最長6年間、セキュリティアップデートが適用されます」あらためて読めばセキュリティアップデートも最短６年間が保証されているわけではなかったな。最長６年と言わず最長100年とはったりを効かせてくれても意味がないという点で変わりがないので全然かまわへんかってんで。こちらにとって有益な意味を込めたのなら、伝わるように日本語と論理を学んでくれ。勝手に都合のいいように解釈したら詐欺に遭うのが今の世の中だ。

ツッコミを入れる

2025年09月15日 (月) 『ホロウナイトシルクソング』をプレイしている。前作はエクストラステージやエクストラボスまで全部やったけど、それでも今作は難しい。それも良くない難しさ。延々と続く下段切りジャンプ。いつまでも死なない敵。複数で押し寄せてきて接触ダメージで削られる。ふわふわとこちらのレンジ外を漂い一方的になぶられる。当たり前にできてほしいことを補うだけのアクセサリ。常にストレスをかけられ続けていて忍耐力を試されている気分。俺はもちろんブチギレて PS5 の電源を切る。でも次はうまくできる気がしてすぐにまた始めてしまう。で、ブチギレですよ。それでもなんだかんだ進捗はある。序盤はまったくたまらなかったロザリーもいまは使い道がなくて余っている(代わりに破片が足りないが破片は無限に掘れる。じゃあなんで消費制にした？)。序盤は地図買えない地図に情報が足りないベンチ使えない駅使えない攻略しているエリアの敵がロザリーを落とさないマップで拾ったなけなしのロザリーをロストするでひどかった。いろいろとやりすぎてるんだよな。エクストラステージや闘技場はおまけだからそれでいいのに、開発者がプレイヤーのいじめ方を知りすぎている弊害。ホーネットはかわいい(設定で声を消したりはしない)。アートワークもいい。音楽も音響効果もすばらしい。でも不利なルール不利な状況でなぶられてなにがおもしろいん？こっちは気絶してひっくり返ってる大型の敵に触れるだけで２ダメージなんよ(こちらのライフは１増えて６)。それにプラスして小型の敵中型の敵がふわふわふわふわと迫ってきたらなにができる？なにがおもしろいん？ (ブチギレて今はネットをしているらしい)■L1 ２回押しでエリアをまたいだマップが表示されるの便利だよ。■漢数字の「二」を使うべきところでカタカナの「ニ」を使っているらしいところが少なくとも２か所あったと思う。同じ画面内の「三」(明朝体)にはあった止めの三角がなかったので、カタカナだったのではないかと。■■■DualSense の左スティックが壊れました。ある瞬間にぬるっと滑る感触があって、以降はずっと軸がぬるぬる回転する。これはかなり深刻で、スティックを倒し続けていたいのにぬるっと指がスティックの向こう側に行きすぎてしまいそうになる。原因はスティックの頭にかぶせてあるゴムキャップの固定が外れたことみたい。親指の腹を乗せる部分に浮きがあるなと思っていた。爪でゴムを剥がしてプラスチックをむき出しにしたらぬるぬるするよりずっと使いやすい。買い直すと１万円以上するからこれでいいや。DualSense Edge だとスティック部分だけ簡単に交換できるし値段も 2500 円程度なんだけど、コントローラー自体が３万円するので追加ボタンがあったりキーマップの切り替えができたりするらしいとはいえありえない高さだと思う。重くてバッテリー持ちの悪い高級コントローラーを望んだことはない。軽くてバッテリーフリーモーターフリーのチープなコントローラーの選択肢があってもいいと思う。実は原因が明らかになる前にコントローラーを分解していた。スティックを抜き取って初めてゴムキャップが滑っていることに気がついた。使用頻度を考えて右スティックと左スティックを入れ替えてゴムなしの方を右スティックにしてますよ。分解するときにマイク付近のフレキシブルケーブルをちぎってしまったくさいので、たぶんマイクが使えない(まだ具体的な不具合には直面していない)。■■■第２章に入ってから印象が変わってきた。ボスを後回しにしてあちこち探索できるし、アクセサリがそろってきて場面に合わせて最適化できるし、アクションの幅が広がって敵に対処もしやすい。ライフと糸巻きは初期から３つか４つ増えた。どうして１章がこうではなかったんだ。■■■@2025-10-25 第３章、達成率99%、残りは漆黒のレースと記憶のロケット(１個どこ？)といくつかのメメントだけという状態。２章は明らかに１章よりぬるかった。倒せないボスも釘を強化して再挑戦したらなんとかなった。３章でもやっぱりフィールドアスレチックはやりすぎで、フラストレーションがたまる場面があったけど、後回しにして他のマップの探索をしてホーネットを強化する選択肢があったのが１章との違い。印象的なボスが多かった。一番好きなのは踊り子のカーメリタ。押し引きする敵の動きに対応して攻撃を加えるホーネットの動きは、カーメリタと一緒になって踊っているかのようで、つまりプレイヤーがまんまと踊らされているというわけで、見事にデザインされた攻撃モーションだったと思う。楽しかった。劇場のドロッピオも印象に残っている。あいだを空けて２回戦ったのだけど、初回撃破時の芝居気たっぷりのやられモーションを見て、あ、こいつは殺しても死なねーやつだな、絶対また出てきて戦うなと思ったもので、果たしてその通りになったのだった。２回目の撃破時もやはり死ななかった。シルクの憤怒をくれる最初の罪に問われし者も、いっぱい死んだし釘を強化してからやっと倒したけど、無理という感じはしないし挑戦しがいがあった。実はぼうっと立っている時間が長くて攻撃チャンスがいっぱいあって、見かけ倒し疑惑がある。ワープ直後にフックショットで距離を詰めるとしばき放題なんだよね。体力が多いだけ疑惑。あとシルクがたまりやすいのかな。それもあって戦い易さがある。反対に３章から出てくる黒く染まった敵はしばいてもシルクが貯まらないし逆に手持ちのシルクを溶かしてくるので非常に戦いにくかった。でもこの敵がいたから、２章で十分強化したホーネットでも３章のマップを緊張感を持って探索できたのであって、作業感なく変わってしまったファールームを再探索できたのだった。アスレチックは二度とやりたくないけど、それ以外、特にボスは、緑の王子も良かったし、印象に残る個性的なボスがよく作り込まれていた。

ツッコミを入れる

2025年09月14日 (日) [AtCoder] 精進。今日あった ABC423-E「Sum of Subarrays」。累積和３つと累積和の累積和１つで解いたけど、絶対何か無駄な回り道をしてると思うんだよね。提出 #69368469 (AC / 1424 Byte / 662 ms)。■いろんな累積和という意味で印象に残ってるのは ABC338-G「evall」。たぶん言及するのはこれで３回目。E 問題を累積和でやると決めてから、求めるものがストレートには得られないので区間の始点と終点を分類し包除を考え累積和を組み合わせ１時間以上のあいだに何度も頭を抱えたことをふまえると、G 問題の方が難しかったとは言えない。ただ、適切な道具を適切に組み合わせればすっきり解けるのではないか、無駄にこねくりまわして自分で問題を複雑にしているのではないかという懸念はある。■どうやら累積和が３つで解けるみたい？■■■F 問題「Loud Cicada」。累積和と累積和の逆という説明と図がわかりやすいこちらのツイート「フェネック「このメビウス変換っていうのはゼータ変換の逆のことで、ゼータ変換っていうのは累積和をとることだねー。例えばセミ1,2,3がいたとき「少なくともセミ1,2が発生」は「1,2が発生＋1,2,3が発生」っていう"累積和"をとった状態だから、それを戻してるよ」」を参考にして書いたものはサンプルが合うものの N=20 の最大ケースで数分かかってしまった。累積和の逆を計算するときに各要素ごとに添字の補集合の部分集合を列挙しているのが良くないのだと思う。うまい計算手順があるのだろうか(ゼータ変換、メビウス変換について調べない)。■E 問題。累積和３つがどのようにして導かれるか。「アライグマ「求めたいのはΣ(A[x]×(x-Li+1)×(Ri-x+1))だから、xxA[x],xA[x],A[x]の累積和を求めておけばO(1)で計算できるのだ！この問題に1点変更クエリもありにしたのがだいたいABC256Fと同じなのだ！」」おかしいな、簡単な問題に見えるぞ。

ツッコミを入れる

2025年09月08日 (月) 信号無視をした話。■渋滞している道路を走っていて赤信号で自分が先頭になった。その少し前、そろそろ赤になるな自分は抜けられないなと思っていたときにどこかから救急車の音が聞こえてきて、ミラーに赤色灯が見えたので後ろから来ているとわかった。なので一応左端に寄りつつ、赤信号なので停止線で止まった。ミラーで車体が確認できるくらい、救急車はたぶん４、５台後ろまで近づいてきていた。右車線はあいにくとダンプが３台連なっている。そもそも工事をしていて車線が減っているから渋滞しているという背景がある。ダンプも渋滞も偶然ではない。救急車は右折レーンに入って抜けようとしたようだけど、中央分離帯に寄ってあいだを開けようとしたダンプと動きがかぶって進路を塞がれたかたち。自分の直後の車は今になって左端に寄ろうとしている。しかし前が詰まっていて思うように寄れない。さあどうする？交差点に車の動きはない。サイレンの音が聞こえているからか歩車分離で歩行者信号のみが青だったからかは確認していないので知らない。普通のドライバーは赤信号を安全に無視するためにどこに注意を向けるべきか知らない。とにかく交差点は空いていた。横断する勇気はないので左端に寄ったまま交差点に進入して、そこで止まって様子を伺おうか一瞬迷ったけど左折して走り去ってしまった。本当は直進する予定だったのだけど。このことで切符を切られることがあっても行いは行いとして仕方がないなと思ってるけども、交通ルールを守るために救急車を無視するのは仕方がないことではないというのが自分の優先順位だった。現場の創意工夫はだいたい東海村臨界バケツ事故で黙らされるイメージがあるけども、自分は自分が納得したルールのみに従い意味がわからないルールは無視ししがちな、軽率な側の人間です。

ツッコミを入れる

2025年09月07日 (日) [AtCoder] 精進。昼間にあった AtCoder Beginner Contest 422。■A 問題「Stage Clear」。ステージ数が倍のスーパーマリオブラザーズ。がっぴの処理と同じ。０始まりに文字列置換して８進数にして１足して文字列にして１始まりに置換するのは書いてて嫌になるほど無駄なのでやらない。じゃあなんで書いた？一瞬やろうとしたから。■B 問題「Looped Rope」。サンプル図を見た感じ、１本のひもが交差するのは許されるけど折り返して接するのは許されない、というのを表した問題名らしい。そんなのは関係なく全マス目について「黒マスではないか、隣接する黒マスが２個か４個であるか」を判定する。最初に書いた条件は「黒マスであって、隣接する黒マスが２個か４個であるか」だったけどサンプル実行前に修正したからセーフ。■C 問題「AtCoder AAC Contest」。A と C の少ない方に合わせて AXC を作ったあとで、余っている A_C を崩して AAC/ACC を何個作るかが問題。単に文字の数を数えて３で割るだけなんだけど、解説によると最初に AXC を作るパートを飛ばしてそういう計算をしていいらしい。飛躍が過ぎてわかりません。■D 問題「Least Unbalanced」。想像通りであるしサンプルの通りでもあるように平らに均します。再帰的に分配する過程が操作の逆再生になっている。■E 問題「Colinear」。時間内には解けなかった。過半数っていうんだからテキトーに選べば当たるのはわかります。でもそういう確率的な操作を書いたことがないし、決定的な方法を探して諦めてしまった。翌日に２か所で乱択の文字を見かけたので、そっち方面に突っ込んで考えてみた。半分が同じ直線に乗っているなら、テキトーに選んだ２点が乗っている確率は４分の１。点の数が最大で 50 万なので、線形時間の処理が 20 回で 1000 万。Ruby の限界は数千万のところにあるので試行回数は数十回が限度か。仮に 20 回試行するとして、外れのペア(が定義する直線)を引き続けるのは (3/4)^{20} で 0.3 % くらいらしい。不安だけどまあ。提出 #69170329 (AC / 455 Byte / 1034 ms)。やっぱり 20 回の試行でもけっこう時間がかかっている。lazy が遅い？それはあると思う。以前から常々思ってるんだけど、find_map メソッド欲しいよね。find が目的だから map{}.find{} だと一度全要素を変換するのに抵抗があるし回りくどくも感じる。かといって find{} で返ってきた値に find の条件ブロックで判定に利用するために施したのと同じ変換をもういちどかけるのも冗長で嫌だし nil 判定はもっと嫌だ。そういうわけで今回は lazy.map{}.find{} になった。でも遅そう。■F 問題「Eat and Ride」。ゴールから BFS をすればゴールまでのステップ数(増加する一方)が揃うので、同一ターンではイコール条件になり前後のターンでは優劣がはっきり決まることになり、ウェイトにゴールまでのステップ数を掛けて消費燃料に換算した値が比較可能になる。毎ステップ各頂点においてゴールまでの消費燃料の最小を更新したもののみが次のステップに進める。ダイクストラ法と違って燃料消費の最小値が更新されることがあるので最悪で２乗のオーダーになるが N≦5000 なので２乗は通る。だからこの問題は各 i をゴールにしたときの最小燃料を問うている。２乗が３乗になった。やるだけの問題にはしないということだ (TLE)。じゃあ唯一のスタート地点である頂点１からたどりますか？そうするとゴールまでのステップ数が不明なために、(ここまでに消費した燃料,消費燃料の増加量=ウェイト) という２つのパラメータが関わってきてダイクストラ法の基準になるコストが一意に定まらない。提出 #69169539 (AC / 1003 Byte / 117 ms)。パラメータを２つ持ってダイクストラ法をしたらけっこうな速さで通った。消費燃料を基準にしつつそれを絶対条件にはしないで消費燃料の増加量の最小を更新するものにも可能性を残している。それはプライオリティキューを使ったダイクストラ法ではない何かですね。通るとは思っていなかった。というのは、キューに入れるときに消費燃料最小か燃料増加量最小のどちらかを更新する可能性があるかを調べてから入れてるんだけど、そのときに基準値を更新していない。基準値を更新するのはキューから取り出したときに限っている。そうしないと答えを間違えると思ったからそうしているのだけど、結果としてキューが取り出してすぐに捨てられるダメな要素で膨れ上がって出し入れに時間がかかり過ぎるおそれがある。これはダイクストラ法を実装するときの罠であり勘所だから、それをしないのでは TLE になると思ったがならなかった。想定解法はなんだろう。Ruby での F 問題へのすべての提出を見たら想定解法は通らないっぽい？最近の制約はまじでクソだと思う。３乗が通らない N=500 と２乗が通らない N=5000 と NlogN が通らない 5×10^5 のことだよ。俺は Ruby を書くために AtCoder をやっているので、Ruby お断りの AtCoder につまらない思いをさせられたらできることがない。■オンタイムで参加していないので E, F が解けなくても平穏だ。Rated だったら入緑していたね。■■■F 問題。想定解法がようやく理解できた気がしたので書いてみた。提出 #69198045 (TLE×26/AC×25)。かなり気を使って普通でない書き方をしたけど TLE が 26 個。他の人のを見ると、提出 #69146527 (TLE×29 / tinsep19 さん)、提出 #69145173 (TLE×23 / fumta さん)。Ruby では全然見込みがなさそう。一番 TLE が少ない fumta さんの提出はちょっとおもしろくて、辺を頂点ごとにまとめずにそのまま DP の遷移に利用している。そうするとループの回数がちょうど半分になる。ループ１回の処理は往路、復路で２倍になっているので全体の処理量は変わらないけど、ループを回す負担は半分になる。Python で一番速い提出を見てみたらたこつぼのページでたびたびお世話になっている ikatakos さんの提出 #69123541 がコンテスト中に提出されていて、解法が自分のなんちゃってダイクストラ法と同じに見える。Python の層の厚さはすさまじい。Ruby でからくも TLE を免れた遅延セグメント木の問題でも、２人か３人の人がそれぞれの手法を突き詰めてどんどんとタイムの「桁を」縮めていく様子が提出一覧からうかがえたりもした。何をやって縮めてるのか全然わからないんですよ。見た目が違うからたぶん採用している手法は異なってるんですよ。

ツッコミを入れる

2025年09月06日 (土) [AtCoder] 今日は AtCoder Regular Contest 205 (Div. 2) があった。div.2 に Rated でいつまで参加できるのか先行きが怪しいこの頃ですが、まだ Rated です。■A 問題「2x2 Erasing」。与えられた矩形の中の白４マス四角の数を素早く数えたい。右、下、右下がすべて白マスである白マスを１と数える２次元累積和で数えられそう。提出 #69078973 (AC / 640 Byte)。枠で区切られた部分の調整で無駄なことをしてる気がする。SR と SC は不要で、i1,j1 をそれぞれ -1 するだけでよかったのではないか。■B 問題「Triangle Toggle」。解けない B 問題に残り時間をすべて奪われました。時間さえかければ解けた C 問題、D 問題に着手したかった。■C 問題「No Collision Moves」。制限時間が３秒と長めなんだけど、何が難しいのかわからなくてなんの罠を見落としているのかと疑心暗鬼だった。S に基づいた人の並びと T に基づいた人の並びが異なっていれば、必ずどこかで移動の交差が起きるので答えは No。じゃあ Yes のときは端から整列させていけばいいんちゃうの？その通りなんだけど、端の人を移動させる前にその先の人を移動させる玉突きを処理する必要があった。サンプルがその例。でもそれだけだった。提出 #69089475 (AC / 486 Byte / 550 ms)。■D 問題「Non-Ancestor Matching」。全方位ではない木 DP。どうしても残ってしまう白色頂点の数を子を頂点とする部分木ごとに数えたら、それをうまくマージして白色頂点を最小化する。提出 #69091151 (AC / 670 Byte / 1192 ms)。うまくない場合というのは、１つの子の下にペアを作れない白色が大量にぶら下がっていて、他のすべての子の下にある白色の頂点と黒色のペアを解消して用意した頂点を使い尽くしても余ってしまう場合のこと。■5×10^5 の制約はまじで良くないよ。ARC はもちろん ABC でも見たくないよ。■日曜の昼は毎週ほぼ確実に時間がとれないので明日の ABC はお休み。

ツッコミを入れる

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

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