06/19(月)

午後3時起床。ABC305の総合1位・学生1位の商品でアマギフ75000円が届いていた。かなり現実味を帯びてきた残高7桁は一度見てみたいが、そのあとは使用期限に注意してちゃんと消費していかねばならない。

そのまま布団でスマホを弄っていたら購買に行く時間がなくなってしまった。適当なタイミングで布団から脱出し、午後4時半からインターン先定例会に参加した。

進捗報告はまあ良しなに。勉強会は大規模言語モデルに対するプロンプトハッキングの話だった。多種多様な攻撃の例ももちろん興味深かったが、一番衝撃を受けたのはbase64でエンコードした文章をデコードさせることで任意の文章を出力させるというものだった。そもそもbase64を扱えるというのが驚き。エンコード後の文字列をググっても何もヒットしなかったから、丸ごと覚えているというわけではなさそうだった。本当にbase64を「読み書き」しているのである。

学食で夕食を摂った後はずっと週記を書いていた。午後11時半に投稿。集中を切らしてハーメルンを開き、見つけた作品「今日も楽しく安価だ！」を一気読みした。

syosetu.org

やっぱり安価系は苦手らしい。主人公の行動が主人公以外によって決められるという不自由さがどうしても好きになれなかった。ただそれはそれとして、この作品は主人公がとにかく強いという点が好みだったためぐいぐい読み進めることができた。安価の要素があっても面白い作品は面白い、ということで。

先週の週記で穴あきになっていた箇所のうち、Universal Cup以外の部分を書き上げた。その後シャワーを浴びて日記を書き午前9時就寝。

06/20(火)

午後3時過ぎ起床。

先生に誘われた確率論のセミナーに出席した。午後3時半開始のところ10分ほど遅れて教室に到着し、それから午後5時までずっと聞いていたものの、何一つ分からなかった。知らない分野の話題を英語で話されると本当に無理。資料もなく真に何も得られなかった。

生協に寄ってラノベを受け取り夕食を摂って帰宅。先週土曜日に参加したDMOJのコンテストが終了していた。

DMOPC '22 June Contest - DMOJ: Modern Online Judge

1問目は使うのは1と2だけでよさそう。どちらかの使う個数を全探索する。

2問目は $i$ 項目から始まる連続部分列 $N-i+1$ 個の符号が全部一致するようにした。まず $1\dots N$ をできるだけ半々になるよう分ける。降順に見ながら貪欲に割り振っても最適になるようだ。この分け方と一致するよう $i$ に対する符号を決め、 $i=N\dots 1$ の順にその符号が達成できるギリギリの値を置いていった。絶対値に関する条件も満たせたので提出、AC。

3問目は十分大きな値に変化させることでそれより前と後で大小関係が逆転しないようにできる。なので変化させた値の直前で $A$ を分割したとき、それぞれで累積XORが広義単調増加になればよい。分割は貪欲に行えるので、1回目の分割までは実際に累積XORを見て取る。

その後は分割位置を先にずらしながら矛盾するところを探す。 $B_{i-1}\le B_i$ であることと $A_i$ の最上位bitが（あれば） $B_{i-1}$ で立っていないことは同値。つまりそうなるように直前に変化させた要素を確定させなければならず、ここで矛盾が発生しうる。

4問目も5問目も解けないまま時間切れ。300点で22位、レートは2987→2909(-78)となった。さすがに悔しいので解説を見つつupsolveした。

4問目は部屋を鏡写しに拡張してボールの移動を直線だと思うテク。これでスタート地点に戻るまでの時間を考えることはできていたが、同じ壁に2度タッチする場合が分かっていなかった。これが起こるのはコーナーで跳ね返ってから $\min(NY,MX)$ 秒後、つまり次に壁に当たるタイミングらしい。言われてみれば……という感じ。

$t$ 秒移動した場合、スタート地点に戻る条件は $(2M\mid t/X)\land(2N\mid t/Y)$ である。図を描くと $2N\mid t/Y-2D$ のような点がありそうに見えるが、実はここに行く場合必ずコーナーを経由するので無視してよい。コーナーに当たる条件は $(M\mid t/X)\land(N\mid t/Y-D)$ となる。前者は単なるLCM、後者は拡張ユークリッドの互除法で解ける。

ただし後者については注意が必要。 $ax\equiv c\pmod{b}$ なる $x$ を求めるのに $ax+by=g:=\gcd(a,b)$ なる $(x,y)$ を求めた後 $c/g$ 倍するが、その後 $b/g$ で割った余りを取らなければ最小にはならない。ランダムケースを試して気づくまでここでもやられ続けていた。中国剰余定理は思いつかなかった。

5問目は、最初にできるだけ多くドミノを置いた後、隣接するまだ埋めていないマスと合わせてトリオミノにすればよいと思っていた。これは二部マッチング2回で計算できる。ところが合わない。しばらく考えていたら以下のようなケースでは最初のドミノの置き方が悪いとうまくいかないことに気づいた。

##.
###
.#.

そのほかグリッドから二部グラフを作って長さ1または2のパスで全頂点をdisjointに覆えればOKということも考えたが、実現できなかった。終盤は二部マッチングの計算時に辺を見る順番をランダムにして何度か投げていたものの、どうしても突破できないテストケースがあってダメだった。

最初から短いパスで覆うのは計算できないが、全頂点の次数が1か2になるように部分グラフを選び、連結成分それぞれを改めて分割するとよいらしい。これも言われてみればそうだが自力ではなかなか思いつけないだろう。二部グラフなので次数の制限は最小流量付き最大流で表現できる。

コンテスト中読みもしなかった6問目は、5問目に関する構築だった。5問目で自分が書いていたWAコードを使い縦横5マスで全探索したら見事に見つかって残念。ちゃんと目を通せばよかった。

先週日曜日に参加した三つのコンテストの動画を投稿した。

【競技プログラミング】Codeforces Round #879 (Div. 2)【実況】 - YouTube

【競技プログラミング】ARC162【実況】 - YouTube

【競技プログラミング】Codeforces Round #880 (Div. 1)【実況】 - YouTube

今日出たコンテストのうち内部コンテスト以外の三つは動画を撮っていたものの、DMOJ参加時のコードや入力サンプルが映り込んでしまった。編集で消せばよいのだが、安全のため来週火曜日のDMOJ終了まで塩漬けにしておくことにした。
週記（2023/06/12-2023/06/18） - kotatsugameの日記

しばらく日記を書いて、午後11時半からCR #881 div.3に出た。

Dashboard - Codeforces Round 881 (Div. 3) - Codeforces

Aはcostのことを要素に+または-の符号を割り当てて足し合わせた値だと思うことができるので、大きいほうから半分を+、もう半分を-とするのがよい。 $n$ が奇数の時は真ん中の値を無視する。

Bは操作する区間がdisjointだとしてよい。負の数を見つけたらそこから次に正の数が出るまでひっくり返す、という操作が最適。これで0が適切に無視できている。

Cはセグ木のindexingと同じ。やるだけ。Dは各頂点について部分木の葉の数を数えておき、掛け合わせたものが答えになる。Eは二分探索。

Fは重みが $\pm 1$ なので連続的に変化すると思える。つまりクエリで指定された列について、その連続部分列における重みの和の最大値・最小値を求め、 $k$ がその間にあるか判定すればよい。F1は $u$ が根に固定されているため、木を構築しながらすべての $v$ に対してこの値を管理できる。

ところでこの最大値・最小値の計算はセグ木に乗るから、F2は木をあらかじめ構築しHLDを使うことで解ける。モノイドの積が可換でない点に注意。 $\log$ が二つ付くし計算に必要な値が多く定数倍も悪いからちょっと心配していたが爆速だった。

全完、5位。F2の実装では最初メモリ使用量の削減のためshortを使っていたが、値が収まらないことに気づきintで出しなおした。結果だけ言ってしまえばopen hacking phaseでHackされなかった。ラッキー。Hackを避けるため動画は次の日に投稿した。

www.youtube.com

また日記を書いていたが、眠すぎて全然進まない。耐えかねて午前3時過ぎに寝た。

06/21(水)

数度の中途覚醒を挟みつつ午後8時まで寝ていた。睡眠負債を解消できた気持ちになった。

昨日のCF div.3のopen hacking phaseが終了していたので、動画を公開した。その後少し日記を書いて眠気を振り払った後、午後11時くらいからTCB59に取り組んだ。

https://techful-programming.com/user/event/4419

1問目はよい。2問目は適当な範囲、例えば $-10^4\le x\le 10^4$ を全探索。3問目は $1\le k\le 10^4$ で全探索。4問目は2点固定して、残りの点がその2点を結ぶ直線上にあることをチェックした。5問目は $(M/\gcd(M,A_j))\mid A_i$ と変形できるので、 $A_i$ たちの約数を列挙してカウントしておけば数えられる。

6問目は大変。 $a\le b$ とする。長さ $n$ の文字列を数えると、 $1\le n\lt a$ では周期が関係ないので $26^n$ 通り、 $a\le n\lt b$ では周期 $a$ なので $26^a$ 通り、 $b\le n\lt a+b$ では一致する箇所が微妙に増えて実験により $26^{a+b-n}$ 通り、あとは周期1なので $26$ 通りとなった。これを頑張って足し合わせる。15分かかって-3pt。

7問目は人 $i$ の快適さが $c$ 以上であるような並べ方を考えた。人 $i$ の前 $c-1$ 人が人 $1\dots i-1$ なので ${}_{i-1}\mathrm{P}_{c-1}\times(N-c+1)!$ 通りとなる。Wolfram|Alphaに $i=c\dots N$ における和を聞いたら閉じた形になった。それを $c=1\dots K$ で足し合わせると $K$ に対する答えになる。

8問目も大変だった。6問目のときの観察から、 $a\le b$ として $b\le N\lt a+b$ における答えが求められればよい。例えば $N=b+1$ のとき、0文字目と $b$ 文字目つまり $c:=b\bmod a$ 文字目が一致する。 $N=b+2$ のときは追加で1文字目と $c+1$ 文字目も。同様にして、 $0\le i\lt N-b$ に対し $i$ 文字目と $c+i$ 文字目が一致するようになる。

すると問題が $(N,a,b,x)\leftarrow(N-b+c,c,a,x\bmod a)$ に書き換えられる。ただしこれで $N\le x$ となる場合の答えは $x$ とする。 $(a,b)$ がユークリッドの互除法のように変化するため、この再帰は十分高速。40分かかって-22ptとなった。

9問目はさらに大変だった。 $I=\emptyset$ を許す場合の凸包を求める問題は見たことがある。点 $(X,Y)$ を追加するたび凸包が $(X,Y)$ だけ伸びるが、伸びるとは凸包の辺をぐるっと一周して得られるベクトルに $\pm(X,Y)$ が追加されるのと同じであるから、これらのベクトルを集めて偏角ソートすると最終的な凸包の辺が反時計回りに得られる。あとは適当に1点、例えば $Y$ 座標が最大である点のうち $X$ 座標最小のものを構成して、そこから一周することで具体的な点たちを計算できる。

ここから $I=\emptyset$ つまり原点を適切に取り除かねばならない。単に取り除くだけではダメで、そうして凸包から1点消えるとき減った三角形領域内に他の点が存在するケースがある。

凸包の頂点に原点が含まれるなら、与えられた点はすべて偏角180度未満の区間に収まっている。このとき「どんな2点の和もその2点を結ぶ直線を挟んで原点と反対側にある」ということが任意の個数に拡張できて、 $P_I$ たちのうち減った三角形領域をカバーするのに考えるべき点が最初に与えられた点たちだけだと言える。

まとめると、上に述べた方法で $I=\emptyset$ を許した場合の凸包の頂点を列挙し、そこから原点を削除して代わりに入力で与えられた点を全部追加し、改めて求めた凸包が答えである。4WAと59分かかって-78pt。

10問目はすごい問題。非自明なステップをいくつも踏む必要があって、解けた時の快感はとんでもないものだった。

問題を整理すると、求めるものは「宝石の魔力の総積（に適切に符号を付けたもの）」の「すべての置き方を渡る和」、つまり $\sum\prod$ である。ここで宝石 $i$ の魔力は働きかけ $i\rightarrow j$ の重み $A_{j-i}$ の和だから $\sum\prod\sum$ と書けて、宝石の魔力の積と働きかけの和を入れ替えることで「宝石の魔力の総積」を「働きかけの重みの積」の「働きかけを各 $i$ につき一つずつ選ぶ方法を渡る和」とできる。つまり $\sum\sum\prod$ 。

二つの $\sum$ を入れ替えてみる。つまり働きかけ $i\rightarrow p_i$ を各 $i$ について選び、 $\prod A_{p_i-i}$ に選んだ働きかけが存在するような置き方の分だけ係数をつけて足し合わせてみる。

実は置き方はそれほど多くない。大杯に入る宝石の集合を決め打つと、そこから $p_i\rightarrow i$ という辺に沿って距離を求めることでほかの宝石がどの小杯に入るか決まるからだ。 $i\rightarrow p_i$ というfunctional graphは各連結成分に一つループを持つが、このループのうち少なくとも1頂点は大杯に入らなければならない。逆にそれさえ満たせば置き方がちょうど一意に定まる。

例えば連結成分が一つだとして、ループ上の頂点が $a$ 個、それ以外の頂点が $b$ 個あったとしよう。このとき置き方による係数は魔力の符号も込めて $\sum_{i=1}^a\sum_{j=0}^b\binom{a}{i}\binom{b}{j}(-1)^{i+j}=((1-1)^a-1)(1-1)^b$ となる。つまり $b\gt 0$ なら係数は0であり、無視してよい。 $a$ は必ず正なので $b=0$ なら-1となる。

連結成分が複数あった場合はこれの積になる。つまり掛ける係数は、functional graphがループに含まれない頂点を持つなら0、持たないなら連結成分数を $c$ として $(-1)^c$ となる。ちなみに、ここまで来ても重みのせいでまだ指数時間から抜け出せていない。かなり心が折れそうだった。

ここで二つの事実を思い出す。まず、functional graphがループのみから構成されることと $p$ が順列であることは同値。次に、このとき上で定めた $(-1)^c$ は $(-1)^N\mathrm{sgn}(p)$ と一致する。ここで $\mathrm{sgn}$ は置換の符号を表す。

以上より、求める値は $(-1)^N\sum_{p}\mathrm{sgn}(p)\prod A_{p_i-i}$ と分かった。これは $(-1)^N$ を除いて $(i,j)$ 成分が $A_{j-i}$ であるような行列の行列式と一致する。このような対称性のある行列を「Circulant Matrix」と言い、検索すると行列式の公式が出てきた。

Determinant of a General Circulant Matrix | Problems in Mathematics

$\zeta$ を1の $n$ 乗根、 $f(x):=A_0+A_1x+\dots+A_{N-1}x^{N-1}$ として、行列式は $\prod_{k=0}^{N-1}f(\zeta^k)$ と表せるらしい。ここまでくれば見覚えがあるどころの話ではなく、 $f$ を離散フーリエ変換して積を取れば求まる。 $N$ が2べきである制約が見事に回収された。99分かかって-56pt。

4時間弱かかって終えたのは午前3時だった。そこから3時間日記を書いた後インターンの作業をした。

不要ファイルの削除を行うためコードの依存関係を調べた。pydepsを使ったら不要なまでに深い依存関係まで表示されてしまって、必要なところだけ抜き出すのもうまくいかず、結局手作業で1ファイル1ファイル見ていった。

またドキュメント整備のためコードを読んでいるときにバグを発見した。意気揚々と報告したがコミット履歴から過去の自分が埋めたバグだと指摘されて愕然。ほとんど同じ行が2か所に出現していて、書き間違えたままコピペしてしまったのを、当時片方だけ指摘されたのだった。

購買が開店したくらいで切り上げ、パン類を買い込んできた。一部を昼食とした後正午くらいに就寝。

06/22(木)

午後5時前に起床。すぐ1on1に臨んだ。

昨日調べたことをもとに不要ファイルを削除するプルリクを出してマージしてもらったり、バグ修正をしたりした。またpydepsが使いにくいという話をして、1on1中に二人でいろいろ試した結果表示したくないファイルを丁寧に指定することで必要な範囲だけ取り出した画像を生成することに成功した。結構時間をかけたので1on1中にやるべきことではなかったかもしれない。

最近やっていたコードの整備は後片付け的なものであり、これですべて終了。自分の次のタスクは全く別のところの話になる。1年弱の間1on1をしてくださった感謝を伝え、解散した。

今日は自分がインターンを始めたころに1on1をしてくださった、日記ではずっとメンターと書いていた方と、自分が次に取り組むタスクについての話をした。
週記（2023/06/05-2023/06/11） - kotatsugameの日記

今日は午後10時からSRMがあるという話だったが、確認すると明日の午前10時からだった。このずれは公式サイトが開始時刻の午前と午後を間違えていたからで、それを見たclist.byにも違う時間で入ってしまったというわけ。終了時刻は正しかったため、注意深く観察すれば14時間コンテストになっていて何かおかしいと気づけたらしい。

来月刊行される新刊をチェックした。今回は23冊注文。米澤穂信さんの新作が出るらしい。

books.bunshun.jp

来週月曜日のインターン先勉強会の発表に向けて調べものをしたり、布団でラノベを読んだりして過ごした。午前4時就寝。

06/23(金)

午前9時半起床。午前10時からSRM847に出た。

https://community.topcoder.com/stat?c=round_overview&er=5&rd=19638

Easyは $i$ ターン目までに逃げることのできる馬を $c_i$ 頭として $i/c_i$ の最小値が答え。 $c_i$ を求めるためには各マスから囲いの外まで何手かかるか計算する必要がある。メモ化再帰を書いたらstack overflowして途方に暮れたが、実は上下左右どれかの方向に距離2ずつ進んでいくことだけ考えるので良い。よって単純な割り算で出る。

Medは $S_j-S_i\le 10(j-i)\Leftrightarrow S_i-10i\ge S_j-10j$ より $A_i\leftarrow A_i-10i$ とした列を広義単調減少にすればよい。最大で何個そのまま残せるか計算することになって、これはLISである。

Hardは $g:=\gcd(A,B)$ を全探索。 $(a,b)$ の候補は $g$ の約数の2乗個ある。 $(A/g,B/g)$ の候補は $\gcd(A/g,B/g)=1$ かつ $N/g\ge A/g\ge B/g$ より $\sum_{n=1}^{N/g}\varphi(n)$ 個である。約数の個数と $\varphi$ のどちらも $O(N\log N)$ 時間で前計算できる。

30分で全完。しかし見直しをしていると、Easyにおける $c_i$ の計算が「ちょうど $i$ ターン目に逃げることのできる馬の数」となっていることに気づいた。サンプルが合ってしまったのだからもしかしたらこれでも答えは変わらないのでは！？と願ってチェックしたが、当然ながら盛大に間違っている。泣く泣くリサブした。

チャレンジフェーズではEasyで自分と同じミスをしている人を探し、一人落とすことに成功した。これで少し点数が上がったのと、あとは自分の上でシステス落ちが少し出たため、順位は4位。しかしレートは2824→2831(+7)としょぼい変化しかしてくれなかった。

布団に戻ってラノベ。「異世界でチート能力を手にした俺は、現実世界をも無双する」14巻を読了した。新しく大量の設定が生え、いくつかはこの巻の中で消化されいくつかは次巻への引きとして残された。話がポンポン進んでいくので読みやすくはある。

午後3時前に外出。まず大戸屋で食事した。記憶している限りでは初めて入ったが、青葉通り一番町駅の近くにあってなかなか行きやすい。健康のためにこれからはここをリピートするようにしたいと考えた。

食事 pic.twitter.com/I9xvI5D8ih
— こたつがめ (@kotatsugame_t) 2023年6月23日

それからゲーセンで遊んだ。今日もアップデートで増えた新曲を埋めたが、それよりはアイマスとのコラボイベントのマップを走る日だった。205マス×9というとんでもない状態になっている。イベント終了まで時間的余裕がない。イベントアイテムはできるだけ全回収したいのだ。

無慈悲な集金マシーン pic.twitter.com/nQ7pzxixGE
— こたつがめ (@kotatsugame_t) 2023年6月23日

午後8時半ごろ退店。ブックオフに寄りつつ帰宅し、午後9時20分にほんの少し遅刻してyukicoder 394に出た。

yukicoder contest 394 - yukicoder

Aはわからなかったので1手目を全探索して2手目で区別できるかチェックした。当然だが1手目の結果に応じて2手目で聞く $x$ は変えなければならない。

Bは大小関係を固定して……など考えそうになったが、冷静になると $xy\le N$ を全探索して $z=(N-xy)/(x+y)$ とすればよい。 $O(N\log N)$ 。

Cはすべての $1\le A\le 10^5$ について一気に解いた。各 $(L,R,X,Y)$ について、 $X$ が大きいなら $O((R-L)/X)$ 個しか該当する $A$ が存在しないため愚直にカウント、 $X$ が小さいならimos法で後からまとめて処理する。閾値は $\sqrt{10^5}$ くらいにしておけばよい。

Dは各 $A$ の寄与を考えたが重複を取り除くのが結構面倒だった。向きを込めた辺 $u\rightarrow v$ について、これを含むパスに対する $A_u$ の寄与を考える。パスの始点は $v$ から見た $u$ の子孫の数だけ候補があって、これはそのまま係数になる。パスの終点は $A_u$ が現れる桁に関わり、その係数は全方位木dpで計算できる。あとはパスの終点を考慮すればよく、シンプルに $N\sum A$ である。

Eは面倒。Suffix Array+LCPを構築しておく。まず $L$ をSuffix Array上で最も先頭に近いものとして取り直す。つまり、 $L$ から始まるsuffixとその一つ前に並んだsuffixのLCPが $R-L$ 未満になるようにする。こうすると $L$ より前に並んだ $i$ について $(i,j)$ は必ず条件を満たす。この部分の数え上げは単に $N-i+1$ の和を取ればよい。

$L$ 以降の $i$ については、切り出す文字列の長さ $j-i+1$ が $R-L+1$ 未満かつ $L$ と $i$ のLCP以下になっていることが条件。つまり $L$ から後ろに見ていったときのLCPの累積MINを考えることになるので、 $L$ をSuffix Arrayにおける降順に舐めてLCPの累積MINをstackで管理しつつ、長さに対する $i$ の個数を区間ADD区間SUMの遅延セグ木で持った。

Fは何もわからず、6位。

ゲーセンで撮った手元を2本ツイートした。「To：Be Continued」は今回かなりうまくいったが、相変わらずラストが何もわかっていないため崩壊。どうせすぐ疲れて連奏できなくなるのだから座学する気も起きない。

LAMIA 6-2 手元 pic.twitter.com/1MS913DqoE
— こたつがめ (@kotatsugame_t) 2023年6月23日

しばらく日記を書いた後ラノベを読んで、午前5時半くらいに就寝。

06/24(土)

午前9時から4時間ちょっと目を覚ましてハーメルンを読んでいた。二度寝後次に起きたのは午後7時。

ICPC模擬国内予選が終了していた。先週内部コンテストとして参加していたので、今ここに感想を書いておく。

午後2時から3時間、模擬国内予選の内部コンテストに出ていた。
週記（2023/06/12-2023/06/18） - kotatsugameの日記

Aはよい。Bは二分探索の上限を「運用して得られる増分が $c$ 以上」ということで $100c$ にしており1WA。最初に $c$ 引かれるので $101c$ にしなければならなかった。

Cは $A$ が大きいもの二つしか遊ばなくていいんじゃないかと思い試してみたら通った。ところが何を思ったか11111121212...という遊び方をしており、後でテストケースが更新された際に落ちていた。逆になぜ一度は通ってしまったのか……。

Dは内部コンテストから問題が少し変わっているのでよく知らない。ただFPSのべき乗で表現できることは同じで、自分は元の問題でも最初にそれを書いていた。二分累乗法をするのではなく、あらかじめ十分な長さでDFTした列を持っておき、テストケースごとに各点をべき乗してからIDFTすると定数倍が結構良いだろう。

Eは点と直線の距離なら $|ax-by|$ の最小化で、extgcdは $|x|$ が最小の値を返してくれるからそれだけで解けそうに見える。実際は線分なので微妙に異なるはずだが、 $\pm(x,y)$ のうちサンプルが合う方を出力するようにしてとにかくサンプルを合わせたら通ってしまった。よくわかっていない。

Fは2次元BITをその場で書いて二分探索、 $O(hw(\log(h+w))^3)$ 。爆速だった。

Gは取り組んだものの解けなかった。映画を見ていない時間を最小化しようとすると、映画の上映終了と別の映画の上映開始をうまくマッチングする問題になる。各時刻の入次数と出次数を数えて貪欲に繋いでみたがWAだった。解説で言う連結性に違反してしまったようだ。Hは読んですらいない。

またハーメルンを読んで過ごし、午後9時からABC307に出た。

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307) - AtCoder

A、Bはよい。Cでどん詰まりした。実装を頑張るだけの問題だろうと思い、コーナーケースを踏まないことを優先して30x30の盤面の上で $A,B,X$ の位置を全探索する方針を考えたが、これは30⁶通りにチェックの時間もかかるので間に合わない。まさか計算量改善を要求されるとは思わず思考が停止してしまい、 $X$ を固定して $A,B$ は相対位置で全探索すればよいということに気づくまで時間がかかった。

Dはstackとそこに積まれている開き括弧の数を管理。ところが管理に失敗して1ペナ生やしてしまった。

Eは $N$ 頂点のサイクルの $M$ 彩色を数え上げる問題。サイクルから1辺消したときは $M(M-1)^{N-1}$ 通りで、そこから消した1辺の両端点の色が一致するケースとして $N-1$ 頂点のサイクルの $M$ 彩色を引けばよい。以下同様にして $N=2$ にまで帰着したら終わり。この方法は1辺削除したグラフにおける場合の数から1辺縮約したグラフにおける場合の数を引いていて、彩色多項式の求め方をなぞっている。

Fはちょっと詰まった。 $D=1$ なら感染させられる距離の残りを持つdijkstraで解ける。これを拡張して、今の日付も一緒に持つことにしたら解けた。比較関数は日付を先に見るものとする。辺を通る際は、距離が足りていればその分を引き、足りなければ足りる日を探す。探すのは区間MAXを取得できるセグ木上で二分探索すればよい。

Gは操作によって全体の和が変わらない。よって各要素が $A$ もしくは $A+1$ となるようにする場合 $0\le\sum A_i-NA\le N$ が必要で、高々2通りの $A$ について計算すればよい。正確には2通りあるのは $A$ だけ使う場合と $(A-1)+1$ だけ使う場合なので全く同じものだが、いずれにせよ定数倍の問題なので気にしないことにした。

各要素について $A$ と $A+1$ のどちらにするか決めると、操作は先頭から貪欲に行うのが最適となる。このとき各要素にはそれより前の要素を揃えた時のしわ寄せが来るので、それを加味しながら操作回数を考えればよい。つまり、 $A_1\dots A_i$ を変化させた後の和が $S$ だとすると、その時 $A_{i+1}$ は $(A_1+\dots+A_i)-S$ だけ増えているということ。

$S$ を求めるにはこれまでいくつ $A+1$ にしたかがわかればよいから、 $i$ とその情報を持つことでdpできる。最終的には全体で $A+1$ を $\sum A_i-NA$ 個使った場合の操作回数の最小値を求めればよい。

Exはずらしながらのマッチングなので畳み込みを使うのだろうとすぐわかって、あとは具体的にどうするか。 $S$ の後ろに $W-1$ 文字の.を追加すると、 $S$ の $i$ 文字目が電光掲示板の $j$ 文字目に表示されるのが $k=(i-j)\bmod{(L+W-1)}$ の時だと表せる。つまり $S_i=P_j$ なる $(i,j)$ の個数を $(i-j)\bmod{(L+W-1)}$ に対してカウントし、それが $P$ の_でない文字の数と一致したものを数え上げればよい。

自分は53種類の文字それぞれに対して $S$ と $\mathrm{rev}(P)$ を01列に変換し畳み込むことでカウントした。制約が微妙に大きいがまあ間に合うだろうと出したら3285ms。さすがに最大ケースも試さなかったのは危ない行為だったなと感じた。

1ペナ全完で8位。上二人とは1分も差がないため、つくづくDのペナが悔やまれる。Exはワイルドカードありマッチングとして昔やったことがあるのに頭から出てこなくて残念。通ったからよかったものの……。

?（任意の1文字）を含む文字列のマッチングがFFTでできるという話を覚えていたので、試した。
週記（2020/11/30-2020/12/06） - kotatsugameの日記

コードゴルフは少しだけ。Aはbashの28Bがあって、Rakuで書いても28Bだった。Eはdcで縮めてみたが負け。他は手付かず。

www.youtube.com

午後11時からCF combinedに出た。

Dashboard - CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

書く：CF

CodeTON Round 5
oooooooo- 9th
2870 -> 3003 (+133) highest

Legendary Grandmasterになりました pic.twitter.com/hIGHuRs9sN
— こたつがめ (@kotatsugame_t) 2023年6月24日

www.youtube.com

動画を投稿した後は昼前までずっとハーメルンに熱中していた。日記を書き、正午を過ぎてから就寝。AHCまでに起きるため30分おきに目覚ましを設定しておいた。

06/25(日)

午後3時前に気合いで起床。AHC021に参加した。

TOYOTA Programming Contest 2023 Summer（AtCoder Heuristic Contest 021） - AtCoder

前回の経験を踏まえ、今日は最初の1時間は絶対に貪欲しかしないと決めていた。強い貪欲なんてなんぼあってもいいですからね。

最初から焼きなましをするのは良くなかった。ちゃんと貪欲→山登り→焼きなましというステップを踏み、それぞれで工夫を入れるべき。
週記（2023/06/05-2023/06/11） - kotatsugameの日記

適当に書いて最初の提出が20分時点。しかしすでに上位と差がついている。いろいろ試してみたが自分の順位は落ちていく一方だった。よく見ると13426585点を出している人が何人もいる。まったく同じスコアが何度も出されるということはランダム性のない貪欲によるもので、しかも序盤から出ているのだからかなり簡単な方針のはず。これを再現するのを最初の1時間の目標にした。

解法ガチャを回し続けた結果、1時間4分時点の提出でようやく再現することに成功した。小さな数のボールから順に、直上のボールとのペアが条件に違反している間上に持ち上げていくというもの。この時直上のボールは二つあるので書かれている数の大きいほうを選ぶ。

この解を検討していて気付いたのだが、 $i$ 段目に $i(i+1)/2\dots i(i+1)/2+i$ のボールが並んだ状態でなくても条件に違反するボールのペアを0個にできるらしい。問題の誤読……というのも少し違うか。嘘の性質を示してしまっていた。だから序盤の貪欲がどれも振るわなかったのだと納得。ちなみに問題ページのGIF画像をよく見ることでも気づけたようだ。

また同時にこの貪欲がかなり強いことを実感した。ここからどう改善すればよいかアイディアが全く出てこない。操作の途中で何かするのは難しそうだから、貪欲を発動する前を弄ることにした。ランダムな操作を入れて山登り法を行うと思ったより改善されて、7万点アップの13498450点が出た。

もう何もわからないので焼きなましを初めてしまうことにした。忘れていた操作の削除を近傍に加え、温度はずっと1。実験してみた感じ下手に温度を変化させても良くならなかったのだ。これで13533820点。

あとは2時間近くずっと高速化をしていた。assertを外すと途端に3万回ほど多く回ってびっくりしたりしつつ、最終的には14万回ほど回っていたはず。ここでの最高値は13537765点だった。最後の0.2秒で最高スコアの解の山登りによる改善を試みたものが最終提出となり、13540250点を出して終了。

結果は13位で過去最高順位。予選を突破できたのも嬉しい。貪欲の13426585点は最終的に156位から199位までを占めており、これだけでオンサイトに進めたようだ。

TLで感想戦を見ながら振り返りをした。今回のコンテストは13426585点を出せるか出せないかで大きく明暗が分かれたようで、ヒューリスティックとしては異質かもしれない。最初の1時間を貪欲に捧げるという当初の方針がこのコンテストにピッタリだったのは運が良かった。強い貪欲を生み出せたのも運。アルゴの問題を解くのとはちょっと違った感覚だったから、単にレートが高ければ分かるというものでもなさそうだ。

焼きなましについて。温度1というのはつまり微妙な改悪を許しながらどんどん別の解を作っていくということで、最高スコアの解でも山登りで改善できる余地があるかもしれないというのは早めに気付くべきだった。というかそういう探索をするならビームサーチとやらを使うべきではなかっただろうか。

自分は貪欲の内部を一切改造せずに使ったが、「直上のボールは二つあるので書かれている数の大きいほうを選ぶ」に変化の余地があったらしい。ここは気付きたかった。13426585点が出た時点で満足してしまい、まともに考察できていなかったような感覚がある。

今回は動画を撮っていた。予選を突破できたら投稿しようくらいの気持ちだったが、思いがけずかなり良い順位のコンテストを記録できて嬉しい。

www.youtube.com

投稿作業を終え、いよいよ明日に迫ったインターン先勉強会の発表準備に取り掛かった。しかし眠気が強くまともに集中できない。ハーメルンなどに結構な時間を奪われていた。

日付が変わりTCB59が終了した。今回のセットは非常に難しかったためもしかしたら唯一の全完者かもしれないとワクワクしていたが、なんともう一人いらっしゃった。その方にはペナルティで大きく差をつけられており、2位。9問目の4ペナがひたすら痛い。9完に負けなかったのは良かった。

それからはもうほとんど発表準備が手につかなかった。眠気というよりは単にやる気が失せている。埒が明かないのでいったん寝て、起きてから頑張ることにした。午前5時就寝。