/ 最近 .rdf 追記 設定 本棚

脳log[2024-01-22~]



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 ではないから私は平静です。


2023年12月23日 (土) [AtCoder] 今日はユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334) があった。自分のすべての提出。配点からわかる通り、B 問題と C 問題にちょっと癖があった。それぞれ 10 分と 17 分かけた。そのかわりではないだろうけど、D 問題と E 問題は手を動かすだけの問題だった。そして F 問題。40 分残していて、急がば回れということで(「Rational でサンプル1を試したらね、1/3 になるべきところが 4/3 になってることがわかってね、(略) mod の数字を見てもデバッグはできない。」)、まずは愚直解を作るところから始めた。そして TLE が出た時点で残り 10 分弱。12-14 行目がまずいのはわかっていて、どうすれば改善できるかもわかる。しかしデバッグが完了したときには終了後 14 分経っていた。あとで書くけども、ある行を2行上に移動するだけのことだった。くやしい。ではふりかえり。■A 問題「Christmas Present」。if 文が書けますかという問題。■B 問題「Christmas Trees」。負の数がいやらしいですね。負の数の整数除算の丸め方向を気にかけたくはない。M の倍数分 L と R をずらしても答えは変わらないので、L と R が A より右に来るように加算した。あとは L-A ≦ i*M となる最小の i と、j*M ≦ R-A となる最大の j を求めて j-i+1 が答え。整数除算を使った切り上げ切り捨て計算なんておなじみなのに、i と j を求めるのにもどうやって負の数を出さずに済ませられるか数分考え込んでしまった。頭がはたらいていない。■C 問題「Socks 2」。難しいよね。制約を見ると、ペアがそろってなくなることはないみたい。片足だけもしくは両足そろった靴下が隙間なく連続して並んでいる。片足-両足-両足-片足 という風に並んでいるとき、左から順番にちぐはぐなペアを作っていっても、真ん中の両足ペアを省いて両端の片足をペアにしても奇妙さの合計は変わらないみたい。じゃあ半端ものだけでペアを作ることを考えて良い(たぶん両足ともなくしてしまったことによるギャップがあるとそうはいかなかった)。そして総数が偶数のときは左から順番にペアを作っていって良い。では奇数のときはどの靴下を省くのが最良か。これって C 問題でしょ、絶対簡単な考え方があるよなという疑念に包まれたまま、左右からの累積和を使って総当たりで最良の答えを探した。■D 問題「Reindeer and Sleigh」。トナカイとスライもしくはスレイ(※読みも意味も知らない)。トナカイは匹ではなく頭で数えたい気がしました。ソートして累積和を用意して二分探索をする。■E 問題「Christmas Color Grid 1」。問題文がちょっと難しいけど、隣接する # のマスでグループを作って、. のマスがいくつの異なるグループを連結してその結果連結成分がいくつになるかを数える。実装していて気がついたけど、. のマスが新たな孤立グループになることもある。期待値を求める式に難しいところはない。すべての . マスについて、連結成分の数を数えて合計し、. マスの数で割る。■F 問題「Christmas Present 2」。DP をしたいけど線形時間で解けと制約がいっている。どうしましょう。いったん時間を忘れると、ある子供のところに行くにあたり、2通りのルートが考えられる。(プレゼントが1つ以上あるなら)直前の位置から直行して手持ちのプレゼントを1つ減らす。もしくは、サンタさんの家に寄って K 個のプレゼントを手にしてから来て、K-1 個にプレゼントを減らす。K+1 要素のデックに移動距離を記録して、shift、push、最小値の取得をすれば答えは出る。しかし TLE が避けられない>提出 #48793891 (TLE)。アイデアはある。K+1 要素の固定長ではなく、スライド最小値の要領で意味のある値だけを記録すればいい。全要素に対して移動距離を加算したり、プレゼント数を減算したりしたくなるのは、ベースとなる値をそれぞれに用意して、それとの差分を記録するようにすればいい(ベースを増減すれば全体が増減する)。提出 #48800858 (AC / 415 Byte / 305 ms)。数字が合わなくて提出が間に合わなかったのだけど、原因は 12 行目の処理を 13-14 行目の後ろに置いていたこと。基準値(d0)を加味した値と基準値からの差分とを比較してはいけない。あーあ、解けてたのになー。■それでも青パフォうれしい。コンテスト成績証。最近不調だったけど、今日のここが定位置だと自認している。次のステップは F 問題を時間内に通すことなんだよな。■F 問題を Ruby で最初に通した人はセグメント木を使っている。最小値を取得するのにセグメント木を使いたくなったのは自分も同じだけど、shift/push をどうするかがわからなくて深追いしなかった。セグメント木で解けるとわかってそういう前提でもう一度考えてみると、N+K 個くらいの要素数でセグメント木を初期化しておいて、参照する K 幅の範囲を1ずつ右にずらしていくという方法で shift/push 操作がまかなえるのではないか。セグメント木をそういう風に使ったことがないので思いつかなかった。……と思ったんだけど、セグメント木を使う2つの提出 #48799502#48806332 を見てみるとそれぞれ K+2 と N のサイズで初期化している。なんで全部違うんだ。いや、まあ、説明できないことはない。N+K と N は、最初は参照するべき値が K 個ないことを考えると実質同じようなものだし、K 要素の方は、無効になったインデックスに新しい値を詰めるようなリングバッファ的な使い方で理解できる。実際にそういう使い方をしているのかは確かめていないので知らないけども。


2023年12月19日 (火)

最終更新: 2024-01-18T16:02+0900

[AtCoder] JOI 2023/2024 二次予選 過去問

AtCoder の問題ではないが精進。ABCE の4問。

 A 問題 カードゲーム 2 (Card Game 2)

基本的にはカードを順番にスキャンして判断をする。ハッシュ表を使って自分が一番小さいカードである場合、2番目、3番目の場合の3パターンについてカードが3枚揃っているかを確かめる。もしくは、昇順にソートして自分が一番大きいカードであるケースについてカードが揃っているかを確かめる。

 提出 #48433809 (AC / 121 Byte / 125 ms)

 B 問題 買い物 2 (Shopping 2)

N 個の商品がありそれぞれの商品は M 種類の商品カテゴリのどれかに属している。M 日間のセールがあり、セール期間のある一日にはあるひとつのカテゴリの商品が半額になる。Q 人の客がそれぞれある日に訪れ、ある範囲の連続する商品を購入する。さていくら? Q 個答えよ。

割引がなければ範囲の総和を知るのに累積和を引くだけ。しかしある日にはあるカテゴリの商品が半額になっているので、範囲内にそのカテゴリの商品がいくつあるか知りたい。カテゴリごとに位置を昇順に記録して二分探索をした。

カテゴリごとに累積和を用意しようとすると最悪の場合長さ N の配列が M 個になって、N×M は大きすぎる。更新のあったところだけ記録しようとすると、さっき書いた「カテゴリごとに位置を昇順に記録」する方法になる。

 提出 #48434188 (AC / 397 Byte / 782 ms)

 C 問題 白色光 2 (White Light 2)

難しいね。いっぱい間違えた。制限時間が1秒とやや厳しめ。

3の倍数の長さ(0,3,6,9,...)の範囲を切り取ってみれば、左端の位置と右端の位置、それと RGBRGB...RGB 文字列との不一致の数からコストがわかる。不一致を単位時間で数えるためには3種類の累積和を用意しておけばいい。すなわち、RGB...RGB..BRG...BRG..GBR...GBR.. 文字列と S との不一致を数えた3種類。

ところで、N の上限が 20 万のときに範囲の両端を自由に選ぶと 20 万の2乗(割る2くらい)で間に合いませんね。範囲の左端を総当たりすることにして最善の右端をどうやって決めるかというところで3回 WA を出した。

最初の提出 #48448208 では左端を右に移動するごとに右端を左右に移動させてみる尺取りをした。特定の制約を追加したサブタスクはクリアしたが、N の制約を甘くしただけのサブタスクで一定割合の WA がある。時間は間に合っていて(局地的に)最適な答えを見つけることもできているが、最善の答えをときどき見逃しているということ。

次の提出 #48453131 は不等号にイコールを追加するような微修正で、3割くらい WA の数は減ったけど本質的な誤りは修正されていない。

3番目の提出 #48453143 は3つのサブタスクで2つずつ WA があるという結果で、ほぼ AC と同じ。実はこれまでの2つの提出ではケアしていた、左右どちらかから全ての文字列を削除するケースに対応したコードを削った結果 WA を生んでしまっている。正しい解法を見つけたときにもういらない気がしたんだよなあ。

 提出 #48453322 (AC / 481 Byte / 224 ms)

これが AC。右端を見つけるのにスライド最小値(?)だと思うものを使った。実装はしなかったけど三分探索も検討していた。知っている解法を総当たりして正当性の判断をジャッジに委ねるのはやめようね。

 E 問題 高速道路の通行料金 (Highway Tolls)

時間に依存したコストをどう扱うか。t=0 となる位置を1から N へのパスの中のどこに置くかでコストが変わる。パスの外に置いても得をしないので考えない。どこに置くのが最善で、どうすれば最善が見つけられるか。

t=0 となる地点をあるパスの中のある辺に置くとする。1がある方のパスに A 個の頂点が、N がある方のパスに B 個の頂点があるとして、A<B なら t=0 の地点を辺上で N の方に近づけるのが良い。A=B なら辺上のどこにあっても同じ。なので、t=0 の地点をどこかの頂点から選んで良い。

t=0 となる頂点を決め打って、1からの最小コストと、N までの最小コストが求まれば良い。1からは順方向に探索し、N からは逆方向に探索すれば、2回の手間で答えが求まる。N 頂点全てを始点にして N 回の探索をすることは時間的に許されない。

 提出 #48650001 (AC / 635 Byte / 113 ms)

提出日の開きを見るとわかるけど、この AC はほぼ一週間がかりだった。

探索は BFS。移動コストが固定値の C と、パスに含まれる頂点数に比例する L×K なので、BFS によって頂点数が単調増加だと想定できると、単純にコストの総和を比較するだけで最短経路が見つけられるし、頂点数に比例したコスト計算もやりやすい。

サンプルの4、5、6あたりの答えがいつまでも合わなくて、ああでもないこうでもないと試行錯誤していた。さっぱり見えていなかったのは AC 提出の 22 行目、頂点 N までのコストを探索する D 関数に与える初期値(DN = D[ヨ[N].group_by{|s,|s}.map{|s,stcs| [s,stcs.map{_3}.min] }.to_h,ヨ])。1からのコストを求める 21 行目(D1 = D[{1=>0},E])と比較すると長さだけ見ても段違いなのがわかる。この違いがさささっと把握できる人はすごすぎると思います。

N から逆向きにコストを計算するのに N の隣接頂点を始点にすればいいとはなかなか……全然わからない。そこにやっと気がついても N とその隣接頂点 V を端点とする辺が複数あるということがまた思い出せない。

たいへんだった。これ予選なんですって。

今3ページくらい E 問題の AC 提出があるんだけど、Ruby の 113 ms が最速だった。おもしろ。ただ、前回の言語アップデートから AtCoder のジャッジは、言語ごとに最初の1ケースだけウォームアップ時間が計測に含まれるみたいな雰囲気があるので(このときの話の関連>20230807)、ワースト1ケースのタイムが特異例である場合の比較に意味はない。

こちらの提出 #48433529 を見ると N×M のループを順方向と逆方向の2回回してるだけに見える。辺を端点ごとにまとめたりもしていない。どういうことなの? 結局 L[j]*K(i+1) を掛けるか i を掛けるかというだけの違いだったの? そうみたい。

 提出 #48653380 (AC / 566 Byte / 108 ms)

頂点数を1減らしてコスト計算する試みはけっこう初期にやっていて、でもたぶん他の部分のバグのせいで答えが合うところまでいかなかった。AC コードがある今同じ方針でやってみるとふつーに、よりシンプルに、答えが出た。なんだよもー。さっき書いた 21、22 行目だけど、こうなった。

D1 = D[1,1,E]
DN = D[N,0,ヨ]

そう、これくらい単純に順方向と逆方向の探索ができると思っていたし、実際できるのに、どうして1週間も沼にはまりこむ結果になったのか、謎だ……。


2023年12月16日 (土) [AtCoder] 今日はトヨタ自動車プログラミングコンテスト2023#8(AtCoder Beginner Contest 333)があった。自分のすべての提出。ABCDE の中では C 問題が一番難しかった、というか、N 進数を使ったきれいな解き方がありそうで、でも見つけられなくて、芸のない全列挙をするまでに時間をかけてしまった。E まで簡単。F も解けて然るべき難易度だと思ったけど解けなかった。ではふりかえり。■A 問題「Three Threes」。JavaScript だと文字列に乗算が定義されていないので暗黙的に数値化されるところだけど、Ruby の文字列は乗算が繰り返しになる。■B 問題「Pentagon」。線分の長さは2種類。だけど意外に隣接頂点を見つけるのが難しかった。なんでだろうね。■C 問題「Repunit Trio」。E までで一番時間を使った。制約が小さいから答えが見つかるまで全列挙すればいい。でもしたくなかった。結局列挙したんだけど。敗北。■D 問題「Erase Leaves」。最初は頂点1が葉なら1が答えで、そうでないなら頂点1から生える部分木のうち最もサイズが小さいもの+1が答えだと思った。これはサンプルの3が合わない。そりゃあそうだ。1から生える1つの枝をすべて取り除いてもまだ1から複数の枝が生えているなら1を取り除くことはできない。1から生える最大サイズの枝1本分だけ削除操作が省けるというのが正解。これだと場合分けもいらない。■E 問題「Takahashi Quest」。E 問題にしてはあまりに簡単素直な解法が見えたから、どんな罠を見落としているのか考えてしまったよね。罠などなかった。逆から見てモンスターがいるということを知ってからポーションを拾えばいい。所持数 K を最小化するためにトリッキーな拾い方をする余地があるかと考えてみたけど、そんなものはなかった。結局のところモンスターの直前で対応するポーションを拾うよりましな拾い方はない。■F 問題「Bomb Game 2」。自分が先頭にいて後ろに○人いるときの確率というのを、後ろに0人から順番に求める DP をするのだと思った。元の状態に戻ってくるループがあるなと思った。サンプル1すら合わせられなかった。■■■@2023-12-21 F 問題。Rational でサンプル1を試したらね、1/3 になるべきところが 4/3 になってることがわかってね、計算式に欠けてる項にすぐ気がついてね、そうしたらサンプルの1も2も合うようになりましたね。一度は TLE (#48681588) を出したけど、コンビネーションの計算式を分解してループのあいだ変化しない定数項を外に出したら AC になりましたよ。提出 #48681702 (AC / 574 Byte / 619 ms)。詰めは甘かったけど問題の考え方は間違ってなくて良かった。■ちなみに mod 998244353 の世界において 1/3 は 332748118 で、4/3 は 332748119 なのです。1差。mod の数字を見てもデバッグはできない。


2023年12月10日 (日) [AtCoder] 今日は ABC332 があった。ではふりかえり。■A 問題「Online Shopping」。言われた通りにやります。■B 問題「Glass and Mug」。K がべらぼうな数だと相当にややこしい問題になる。操作1が最も数が少なくてサイクルの起点になりそうだけど、そのときにマグが空とは限らないのがいやらしくて、操作1から操作1までのサイクルごとに初期状態の変遷を考えないといけない。操作1と操作1のあいだに操作2が何回繰り返されるか、そのあいだ、操作2と操作2のあいだに操作3が何回繰り返されるかは固定だけど(追記:マグの初期状態が違うんだから違うか)、最後の操作3の繰り返しだけは少なくなるかもしれない。二分探索をして最後の1サイクルだけシミュレートするとかかな。でもこれは B 問題なので K(≦100) 回操作をシミュレートします。■C 問題「T-shirts」。休日ごとにリセットされるので split(/0+/) した結果の 12 文字列について考えた。1の数を c1、2の数を c2 として、[c2,c1-M].max の max を答えにしたら WA だった。たぶん c2+[c1-M,0].max の max を答えにすべきだった。今以て確信はもてない。2パスの別方針の解答をでっちあげたらそちらはミスがなかったらしくそれで AC をとったので。■D 問題「Swapping Puzzle」。制約が5以下とささやかなので階乗の2乗に2乗を掛けても大丈夫。たぶん賢く操作を構成しようとすると、同じ値を持つマスの扱いが問題になりやすいと思う。すべての並べ替えを列挙して盤面が一致しているかを確かめるのが確実。■E 問題「Lucky bag」。解けてないよ。15 15/1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 という入力に対して3秒弱かかるのでは TLE が避けられない。勘違いする人がいるみたいだけど、3秒弱っていうのはコードテストで 2778 ms (<3秒) かかったって意味だよ。俺は勘違いしてないよ。■F 問題「Random Update Query」。区間適用のセグメント木の香りがします。もっとも、仮にそれが手持ちの道具箱に入っていたとしても関数の合成が書けたわけではない。どこかで読んだけど、Ax+B の A と B を覚えておくだけで合成できたのかな。


2023年12月09日 (土) [AtCoder] 今日は estie プログラミングコンテスト2023 (AtCoder Regular Contest 169)があった。なにか参加者が普段より多かったらしいという話を読んだけど、ABC と間違えた人がいくらかいたんだろうか。自分もすっかり定期開催が当たり前になった今になって開始時刻が 21 時でないことがあると見逃しそう。日記は B 問題のふりかえりのみ。■A 問題「Please Sign」。難しいよね。何を言っているのかわからないからサンプルを頼った。これが 400 点問題。300 点よりは難しいことになっているけども。10 の 100 乗回くりかえすとか、答えが正負ゼロのどれかでいいということから、雰囲気で答えを出していいのかと思ったよね。10 回とか 50 回とか時間が許す限り操作をシミュレートして、A[1] の値の変化量の変化量が正負ゼロのどれかを調べて、正負なら A[1] の値が行き着く先は正負そのままだし、ゼロならどの値で停滞しているかを調べればいいかなと。ダメなんです。無限大無限小に発散していくときはたぶんそれでいいけども、操作によって A[1] が定点を周回するようなとき、打ち消し合わない有限の寄与の軽重を二項係数で計算して合計して、A[1] の値がどこにあるかをしっかり確かめないといけないらしいです。たぶん。これも雰囲気で書いている。■B 問題「Subsegments with Small Sums」。早々にゼロ完を覚悟したけど B 問題が普通の DP で助かった。A 問題があまりにつれなくて 20 分くらいで見切りをつけられたのも運が良かった。連続部分列に切り分けるわけだから、たとえば左から切っていくとして、中途半端に左端に要素を残して得をすることってたぶんない。端から貪欲に切り分けて良さそう? 確信は持てないけどそういうことにして考えた。範囲をだいたいいくつの部分列に切り分けることになるかは累積和で見当がつく。両端を決めてそのあいだにある要素の和が S の何倍であるか。かといって、両端の組み合わせはおおよそ 25 万の2乗通りあって、範囲をひとつひとつ考えることはできないし、範囲のひとつひとつについて、S の倍数をまたぐ境界付近で区切りの位置を確かめることもできない。ところで、異なる2つの範囲について、実は似たようなシチュエーションが現れることがありますね。左端から貪欲に区切りを置いていったときに、同じ位置に区切りを置いたらそれ以降に起こることは共通している。そしてそれっていうのは、共通の区切りを左端とする範囲についての f 値がわかれば計算できる。というわけで数列の右端から、その要素を左端とするすべての範囲について f 値の和を記録していった。範囲の左端を決めたとき最初の区切りがどこにあるかだけ累積和を使って調べた。難しすぎるテストは時間が余って困る法則によって時間には余裕があったので、累積和を二分探索していたのを尺取りに書き換える落ち着きを見せて一発 AC だった。提出 #48318193 (AC / 194 Byte / 119 ms)。べつに尺取りが二分探索でも TLE にはならないんだろうけど、解ける問題を時間内に解くためにシビアなタイムアタックが求められる(そして時間切れになる) ABC との、取り組む姿勢の違いの現れ。■■■A 問題について眠たいことを書いていた。ここに重要な予想していなかった観察結果が書いてあった>「estie プログラミングコンテスト2023(AtCoder Regular Contest 169)参加記 - devgenjin77’s blog」。A 問題が AC できるのはまだ先になりそう。


2023年12月05日 (火) ゲームディスクが出てくるかと期待して漁っていたけど攻略本しか出てこなかったな。体験版をプレイして SO2R をやりたい欲がすごく高まってるんだけど、本をめくってあらためて感じるのは、面倒くさいしもういいか、という気持ち。当時もうやりきっちゃってるので今やっても中途半端なものにしかならない。それでは満足できない、でももう当時のまめさではやりたくない、という葛藤。ピックポケットとかなくなっていた方が嬉しかった。それでもそのうちテキトーにぬるいプレイをすると思う。当時と同じようにレナで敵を殴りまくると思う。だってそれ以外のキャラを操作する理由がないよね。攻撃呪紋と必殺技と剣のリーチがなくてもいいよね(だが CPU にやってほしい回復役を奪っているのが問題)。■@翌日。ディスクを見つけてしまった。disc3 はアストロノーカの体験版だ。アストロノーカは自分のメモリスタックの最大階層を教えてくれる名作……(クリア前に作物のサプライチェーンの管理がオンメモリの限界を超えて投げたという意味)。蒼天の白き神の座とかサガフロンティアとかグランツーリスモ2とかベイグラントストーリーとか FF9 とかガンバァールとかと一緒に出てきた。あるのは知ってたよ。