週記(2023/06/26-2023/07/02)

06/26(月)

午前10時半起床。まず学食で朝食を摂り、帰宅してからはずっと勉強会のスライドを作っていた。

午後4時半からインターン先定例会。進捗報告の場では今週から別のタスクに取り組む宣言をした。今回の定例会は話し合いの時間が非常に長く、いざ勉強会というときにはすでに午後7時になろうとしていて、発表は来週に延期された。スライドの内容がまだ薄かったので正直助かる。

それからは延々週記を書いていた。日付が変わる直前に投稿。今回も週末のコンテストを三つ四つ穴あきのまま残してしまっている。

眠くて布団に滑りこんだら、あっという間に寝落ちしてしまった。日付が変わってすぐのことだった。

06/27(火)

午前5時半ごろから目を覚ましていたような形跡がある。確か布団で論文を読んでいたはず。シャワーを浴びて、また午前8時くらいに寝た。

午後5時半に再度起床し、ずっと布団でハーメルンを読んでいた。「ゆるふわ芦毛のクソかわウマ娘になってトレーナーを勘違いさせたい」を読了。タイトルはチャラチャラしているものの中身は真剣なレースが繰り広げられていて非常に良かった。序盤ではなかなか勝てなかったが、後半はその鬱憤を晴らすような連戦連勝で気持ちよかった。

syosetu.org

また別のハーメルンに没頭。日付が変わる前くらいに寝落ちした。

06/28(水)

午前3時に起きて1時間ほどハーメルンを読んだ後、布団から起き上がってしばらく日記を書いていた。

朝から4時間くらいはコードゴルフをしていた。最近手を付けていなかった簡単な問題をいくつか。atgolferがAtCoderの仕様変更で止まってから、対応をサボり続けてもう2か月も経過してしまった。botが動いていないからモチベが消えているのか、モチベが消えているからbotの復旧ができないのか。昔は「コードゴルフに対するモチベは無限」などと豪語したこともあったが、今は見る影もない。

AtCoderの仕様変更でatgolferが動かなくなったことにも気づいたが、修正する時間はなかったのでissueだけ立てておいた。そのうち頑張って調べて対応する。

週記(2023/04/17-2023/04/23) - kotatsugameの日記

それからセミナー準備で演習問題と格闘していたら学食の昼の部が閉まりかける時間になっていた。雨が降っていたので行くのは諦めて布団へ。ハーメルンを読んで午後3時くらいに寝入った。その時間帯の天気はびっくりするくらいの快晴で、昼食を食べ損ねて残念な気持ちだった。

午後6時半に起床。学食の夜の部に行こうとしたらまた雨が降り始めていたため断念し、布団でハーメルンを読み続けていた。午後9時くらいに起き上がり、しばらくYouTubeを見たりして眠気を振り払ってからセミナー準備を開始。朝までかけて発表用のメモを作成した。

演習問題で探せと言われた反例を見つけるのにプログラムで全探索を行った。サイズが小さいほうから調べていった結果、見つかったものは挙動がギュッとまとまっていて思ったより複雑。実際にセミナーで紹介するならわかりやすいものがよいから、頑張って観察していい感じのものを作ろうともがいていた。ただ、最終的に閃いたものは見つけた反例とはあまり関係なかった。

合間にラノベ「あなたの事が好きなわたしを推してくれますか?」を読了。さすがに登録者数一桁から激バズりしても上手くいかないんじゃないかと思ったが、当然そんなのは話にならないので今のところは順調。ただゲームの腕前はとんでもなく良いらしいし、コメントを拾うのも手慣れた感じで描写されていたから、配信者としての素質はあったものの埋もれていたということなのだろう。そういう点では納得できるかもしれない。しかしやはりこの状況で配信者として活動を続けられているのは現実感がないな~と思いながら読んでしまった。そういう視点が芽生えてしまうくらい話に引き込まれなかったということでもある。

少し日記を書いた後ラノベを読んで時間を過ごし、午前10時前に学食に向かった。食事し、開店直後の購買でお菓子を買い込んで帰宅。午前11時就寝。

06/29(木)

午後6時半に目を覚まし、2時間くらいハーメルンを読んでからまた寝た。ちょうどこの時間帯にTechFULからTCB終了のお知らせが出ていた。

せっかくだから自分の結果をまとめておこう。TCB31-59までのうち第57回以外と新春TCB2021-2023の、合計で31コンテストに出た。このうち解けなかった問題は第43回の10問目のみであった。

新春TCB以外での順位は1位が12回、2位が4回、3位が2回、4位から10位が8回、11位と17位がそれぞれ1回ずつ。また17位を取った回では特別賞に当選したため、総獲得賞金はアマギフ85000円分となった。第38-40回と第50-52回の二度、三連覇を達成している。特に後者は理論値を3連続で出していた。

これだけ独占しておきながらTechFULを就活サイトとして使うつもりはハナからなかったのだから、TCBが終了してしまうのもしょうがないのだろうと考えた。もしこれが正しかったとしても悪いとは思わない。競プロの問題を解いてお金が貰えるなら貰いに行くし、コンテストでそんな大番狂わせが起きるわけもないため入賞者は固定されがち。

午後11時起床。半からECR151に出た。

Dashboard - Educational Codeforces Round 151 (Rated for Div. 2) - Codeforces

Aは場合分け。1だけ使って作るか、2と3を組み合わせるかしかしなくてよい。Bは二人とも上下左右への移動回数が決まっているので、4方向それぞれ回数が少ないほうに合わせて動くのが最適。Cは部分列dp。

Dは、kとしてはaの累積和の累積MAXに現れるもののみ考えるので十分。そこに現れないなら現れるまでkをインクリメントすべきだから。kを決めたら、その位置をレーティング0だと思ってx\leftarrow\max(x+a,0)を繰り返し、最後にkを足したものがn試合終了後のレーティングとなる。この変換はセグ木に乗るので計算可能。あるいは後ろから累積積を求めておくだけでもよい。

Eは、最初に1があったインデックスをa_1,a_2,\dots、操作後に1があるインデックスをb_1,b_2,\dotsとしたとき、それを達成する最小の操作回数がc:=\sum|a_i-b_i|と表せる。明らかにc\le kが必要。また余った操作を1を小刻みにずらして消費すればk-cが偶数ならちょうどk回の操作で作れることになる。

一方1回操作するたびに\sum b_iの偶奇が変化するので、k-cが奇数の場合は作れないとわかる。以上よりcを持ちながらbを決めていくdpで解けることが分かった。状態数がO(n^2k)になってしまうが、dpテーブルを上書きするような形で更新したり見なくてよい場所を見ないようにする定数倍高速化を施して出したら2secで通った。

Fは、人ijx秒後に同じ位置にいるという条件がv_ix\equiv v_jx\pmod{2l}またはv_ix+v_jx\equiv 0\pmod{2l}と書ける。これによれば正整数kによって\frac{2lk}{|v_i-v_j|}あるいは\frac{2lk}{v_i+v_j}と書ける(0,t]の数を数え上げればよい。

まず畳み込みによって|v_i-v_j|v_i+v_jを列挙し、次にループを回してその約数dを列挙する。あとは既約分数の形で\frac{k}{d}\le\frac{t}{2l}なる正整数kを数え上げればよい。\gcd(k,d)=1と制限しなければ単なる割り算で個数が求まり、それに対して除原理を適用することで既約分数のみを残せる。

Fでは約数を考えるのを忘れていたりオーバーフローしたりで2WAしてしまった。全完12位。

www.youtube.com

明日予定されているインターン先のミーティングに向け、1時間半くらいかけて自分がこれから取り組むタスクに関する資料を作った。なんだか仕事をしているという感じがあって楽しい。

シャワーを浴びて布団に入った後、1時間ほどラノベを読んで就寝……のつもりが、そこからさらにハーメルンを読みふけってしまった。結局寝たのは午前9時半だった。

06/30(金)

午後0時半起床。

午後1時から1時間ほどミーティングに参加。昨日作った資料をお見せして技術的なアドバイスを頂いた。いろいろ興味深い話が聞けて、まだ何も手を付けていないのに上手くいく気がしてくる。これはシンプルに錯覚だから気を引き締めなければならない。しかし聞いたテクニックを早く試してみたいという気持ちは本当のものである。

資料を見せながら口頭で発表するとき、自分はいつも資料に書いていないことを喋ったり資料の順番を崩して説明を進めたりしてしまう。書いてあることは読めばわかると思って、細部の情報を追加したり先のことを話したくて逸ったりしてしまうのだ。しかしこれは聴衆をいたずらに混乱させるだけだと結構前から自覚している。いまだに治らないが何とかしたい。

ミーティング後にしばらく調査をした後、外出して購買でラノベやパン類を買ってきた。家で食事し、今度はセミナーのためまた大学へ。雨が降りそうなので地下鉄で向かった。

最初の1時間は海外の学生による発表で、Thm 2.1.4とそれに関する演習問題二つだった。この定理は何というか周囲から浮いた内容だったので、去年自分が2.1章を発表した際は飛ばしてしまっていた。ところが5.4章で使うことが判明したため、改めてやり直すことになった。

発表については全く問題なかった。逆に自分は書いてある内容を誤読してそれは間違っていると主張してしまいちょっと恥ずかしい。

次の2時間は自分の発表。先ほどと同様Thm 2.1.4に関する演習問題を三つ解いた。かなり苦戦した問題だったのでしっかり記憶に残っており、今日は用意した原稿をほとんど見ずに話すことができた。ただし内容については悔いが残る。発表中に考慮漏れしていたケースを発見してしまったのだ。修正のアイディアはすぐ出たが、その場でまとめ切る自信が微妙になかったし、もう2時間喋ったということで、これに関しては家で証明としてちゃんと書いてくることになった。

しばらく駄弁って帰宅。午後9時半から、10分遅刻でyukicoder 395に出た。お誕生日コンテストとあって警戒していたが普通のコンテストだった。

yukicoder contest 395 - yukicoder

AはbitDP。Bは何回かfを適用すると素因数が2と3だけになるのでそこまでは愚直に求め、以降は2回適用するたびに指数が2倍になるという法則を利用して計算した。Cは現在時刻の絶対値がN+M以下の範囲しか見なくてよい。dijkstra

ここからDで彩色多項式を求めようとしてかなり時間を消費した。諦めていったんEに移ったらこちらは解けた。a+\sqrt 2b\le cなる(a,b)の条件は、式変形によりa\le c\land 2b^2\le(c-a)^2と書ける。これを使うと答え以上で最小の整数Rを見つけることができる。R=O(\sqrt N)なので線形で探索すればよい。

次に、a=0\dots Rに対してa+\sqrt 2bがギリギリR-1より大であるようなbを求めると、a+\sqrt 2bをソートすることで具体的な答えが得られる。a=Rに対しては当然b=0であるが、そこからaをデクリメントしつつa+\sqrt 2b\le R-1となるたびにbをインクリメントするという方法で、この列挙がO(R)で行える。

残り時間はまたDの彩色多項式を考えていて終了。4完17位。

解説を見てひっくり返りながらDをupsolveした。彩色多項式に言い換えることには何の利点もなかったが、逆に言い換えたところでdpの式は変わらないから解法から遠ざかっているわけでもなさそう。シンプルに再帰的な構造の数え上げが身についていない。

コンテスト中は目を通しただけだったFもupsolve。腰を据えて読むと[x^K]\prod(1+Px)で仰天。Disjoint Sparse Tableに多項式の積を載せたら2sec弱で通ってさらに仰天。これはちゃんと取り組むべきだった……。

日記を書いて、午前5時くらいに布団に入りハーメルンを開いた。1時間程度で寝落ち。

07/01(土)

午後1時45分起床。午後2時からUniversal Cup 21回目に出た。今日はShandongセット。

The 1st Universal Cup. Stage 21: Shandong - Dashboard - Contest - QOJ.ac

書く:UC

月が変わったので読書記録をツイート。このときのツイートは間違っていたので、以下に貼ったのは修正したものである。6月も全然本を読めていない。またしてもハーメルンに全力投球してしまったせいだろう。6月は自分の中でウマ娘の二次創作が熱かった。

しばらくハーメルンを読み、午後9時からABC308に参加した。

AtCoder Beginner Contest 308 - AtCoder

Aはあまり短くならなさそう。素直にC++で書いた。後から知ったが、この問題は新しくなったABCの配点の法則を表現していたようだ。

Bは入力の順番が面倒だが、やるだけ。Cは分母を払って比較する関数をsortに渡す。Dはこれまで訪れたマス数\bmod 5も持ってBFS。Eはjを固定し、(A_i,A_k)を全探索した。対応するikのカウントは前計算しておける。

Fは使ったクーポンのDの和を最大化する問題だと思える。Pを昇順に見ると使えるクーポンの集合は単調に大きくなっていくから、今使えるクーポンのうちDが最大のものを貪欲に使ってよい。

Gは、クエリ3に対する答えの候補がソートして隣り合う数のXORのみである、という事実をつい最近TLで見た。黒板に書かれた数と、それをソートしたとき隣り合う数のXORを、それぞれmultisetで持ちながら差分更新。変数名をtypoして1ペナ付けてしまった。

Exは面倒。Qは次数3の頂点を一つ持つので、その頂点uとそこから出る辺でサイクルに含まれるもの二つ(uvuw)を固定して考えることにした。この時点でO(N^3)かかっているので、残りは定数時間で求めたい。

サイクルに含まれない1本については、uvuw以外の辺のうちコストが最も小さいものを使えばよいから、適当に前計算したりすることで求められる。よって問題はvuwを含むようなサイクルを考える部分である。

単純にvからwへの最短距離とすると、vuwそのものが候補に入ってしまいうまくいかない。サンプル3で落ちる。そこで、vからwへの最短距離と共に2番目に短い距離も求めることにして、もし最短距離がvuwと一致すれば2番目のほうを使うことにした。しかしこれも単純な実装ではサンプル3で落ちる。vuvuwと同じ辺を往復するものを考えてしまっていたらしい。

そこで遷移の際に往復を許さないようにした。判定は距離を見て行った。例えばxからyにコストcの辺があったとして、xまでの最短距離d_xによってd_y=d_x+cとなっていた場合、xへの2番目に短い距離としてd_y+cは候補に挙げないことにした。

yに対して別の頂点から同じく距離d_x+cで辿り着ける場合は、yまでの2番目に短い距離が同じくd_x+cとなっているので、そこからxに遷移するのはOKである。これでうまくいくはず。不安になりつつサンプルが合ったということで出したら通った。サンプル3が強くて助かる。計算量は、始点ごとにdijkstraをしているのでO(N^3\log N)であった。

53分全完、1ペナ。順位表を見たら1位でびっくりした。Exはかなり手間取ったなという感覚だったが、みんな手間取っているらしい。5分待っても結局全完が出なかったため、ペナを消化して無事優勝が確定した。

www.youtube.com

急いで動画を投稿し、午後11時からTROC #33に出た。

https://tlx.toki.id/contests/troc-33

Aは頑張って問題文を読む。Bは最小値がほとんど常に0で、最大値は\min(A,B)。Cは手で実験したところNが10の倍数のときだけ後手勝ちらしい。実際、10の倍数でない場合は下一桁の数字を引くことで10の倍数にできる。Dは計算するとZ\equiv\prod A\pmod{k}になり、これがどんなkでも成り立つのだから\equiv=でなければならないと言える。

Eはスタートプレイヤーを固定するたびに山の一番上にあるカードの候補を持って遷移を繰り返してみた。カードが置かれるたびに数は倍以上になるから、遷移は高々O(\log NK)回である。これはつまり各iについてC_{i,\ast}からC_{i+1,\ast}に遷移する回数も全体でO(\log NK)回だということである。

約数・倍数の関係にあるペアは全部でO(NK\log NK)個だから、あらかじめチェックして遷移の前計算をしておくことで、計算量がO(NK(\log NK)^2)になるとわかる。うっかり要素ごとに遷移していこうとすると計算量が押さえられないはずで、候補を全部持てばよいということに気づくのに結構時間がかかった。

Fは難しい。Kが偶数のときは直径を往復すればよいから、スタート地点はどこであってもよい。K=3のときは正三角形を描くしかないだろう。この場合スタート地点は「円に内接する正三角形」に内接する円の外側になければならない。こう考えると、Kが偶数のときは正二角形を描いているようにも見える。つまりKの最小素因数pを用いて正p角形を描けばよい。

「単位円に内接する正p角形」に内接する円の半径は\cos \pi/pだから、求める確率が1-\cos^2\pi/pと計算できた。しかしWA。さらに最初の提出ではK=1の場合を忘れていたためもう1ペナ付けている。

改めて考えてみるとK=5のときは正五角形を描くのではなく星形を描くことで内接する円をより小さくできる。多分こちらが正解。

ボールの反射の入射角を\thetaとすると1回の反射で方向ベクトルが\pi-2\theta回転することになり、K回反射することでぐるっと一周するのでK(\pi-2\theta)2\piの倍数。よってKが奇数の場合\theta=\pi/(2K)が最小となる。このとき円の半径は\cos(\pi/2-\theta)。あとは先ほどと同様の式で計算することにして出したら通った。

G。i\lt j\lt kについて辺(i,j)(i,k)が存在するなら辺(i,j)(j,k)に組み替えたほうが良い。このことから答えとなるグラフは頂点番号が順に並んだパスグラフになる。よってPをソートした後各iについてP_iP_{i+1}を繋ぐという問題に言い換えられた。

P_iからスタートしてどこまで伸ばしたかを状態に持つdpを考える。辺の端点を決めるとLCMが同じ値になる区間が計算できるので、そこから貰ってくることにすれば区間MINのセグ木に乗る。答えの上界として\sum A_iA_{i+1}\le(2\times 10^5)^3があるので、考えるべきLCMもそこまででよく、LCMが変化するなら倍以上になることを思えば区間\log個しか見なくてよい。その区間と対応するLCMはstackで管理しながら更新していった。

Hは解けず。クエリを平方分割し、見ている範囲のクエリに関わる頂点とそうでない頂点で扱いを分けた後、マージテクなどで計算するというコードを書いてはみたものの、計算量が押さえられていない。当然のようにTLEだった。

7完10位でレートは2856→2868(+12)。あまり出来が良くなかったのに上がってびっくりした。インドネシアで4位というのは相変わらずである。Hはこれを解けるライブラリがあったらしい。

suisen-kyopro.hatenablog.com

ABCのコードゴルフを少しだけ。AはとりあえずRakuで書いておいた。テストケースハックとして、25の倍数ではなく5の倍数か判定しても、また最小値を10にしても通るらしい。BはPerlで書いたがRubyに負け。やはりP_0の扱いが難しい。CはRuby有理数型でsort_byする解法が通っていた。安定ソートではなかったはずだが……。粗探ししたら縮んだ。以降は手付かず。

TwitterAPI制限が話題になっていて、自分もすぐに新しいツイートが読み込めなくなった。幸いTweetDeckは問題なく使えるが、他の人のプロフィールページに飛んでツイートを見ることができなくなったのは苦しい。自分はよくその方法で通知に出現したアカウントのツイートを眺めていたからだ。

朝まで日記を書いていた。それから布団に転がってハーメルンを読み、午前11時頃寝落ち。

07/02(日)

午後8時起床。TweetDeckも使えなくなっていた。正確にはHomeとMentionsとMessages以外Loadingが終わらない。これにはさすがに困り果ててしまった。

ARCまではハーメルンを読んでいたが、ちょうど一区切りついたところで放棄することにした。自分にとっての地雷描写が多くて耐えられなかった。魔法科高校の劣等生は達也と深雪の関係を抜きにしては成り立たない作品だと思っているので、オリ主であっても深雪が惚れてしまうのは看過できなかった。

syosetu.org

「男性キャラが自由奔放に振る舞うのを女性キャラが折檻して止める」というシーンはこの作品に限らず主人公最強モノで本当によく見る。これも好きではない。なぜこれだけ流行っているのか一切理解できない。特に作中最強格の人物に対してこれをされると一気に冷めてしまう。折檻で止められるような人間は最強ではないのだ。

午後9時からARC163に出た。

AtCoder Regular Contest 163 - AtCoder

Aはギャグで、k=2でよい。しかも愚直のO(N^2)が通る。Bもほとんどギャグで操作するのはi=1,2だけでよい。A_3\dots A_Nをソートして連続するM個を全探索し、それが[A_1,A_2]に収まるように増やしたり減らしたりする。

CはN=4を作ろうとRuby有理数型で実験していたら気づいた。1/2+1/3+1/6=1にもう一要素付け加えるため6の代わりに7を入れてみたところ、値が1/2+1/3+1/7=41/42となった。ここに1/42を付け加えるとN=4に対する解が構成できる。

ちゃんと計算すると、\sum 1/AなるAに対しA':=A-\{A_i\}+\{A_i+1,A_i(A_i+1)\}とすることで|A'|=|A|+1かつ\sum 1/A'=1とできるらしい。これを用いてA=\{1\}からどんどん増やしていけば答えが得られそう。要素の重複がちょっと怖いが、とりあえずN=500まではそうならないように選ぶことができた。Rubyでチェックして提出しAC。

Dは余計な知識に引きずられてかなり迷走してしまった。トーナメントグラフに関しては以前次数の観点から出題されたことがあったのだが、それが強く印象に残っていた。しかしこの問題を解くのに必要なのは「SCCに分解するとパスグラフになる」という性質である。

トーナメントグラフをSCCに分解するとパスグラフになるので、その始点と言ってもよい。出次数で降順ソートするとSCCと同じ順番で並ぶ

週記(2023/01/02-2023/01/08) - kotatsugameの日記

解法としては、SCCそのものではなくSCCとSCCの切れ目を数え上げる。パスグラフなので切れ目がSCCの数引く1と一致してくれるのだ。すべてのグラフに対して切れ目を数え上げるためには、逆に切れ目として頂点集合をABの二つに分割し、Aの頂点とBの頂点を結ぶ辺がすべてAからBの方向に向きづけられたグラフを数えるとよい。

ABへの分割とそのとき向きが確定した辺のうち「頂点番号が小さい方から大きい方へ向けられた辺」の数については、dpで場合の数を計算できる。計算量はO(N^4)。その後ABの内部の辺のうち何本かを小さい方から大きい方へ向ければよく、ここは単純に組み合わせを掛けることで計算できる。

Eは実験するもほとんど何もわからず。コンテスト終了間際になって、最上位bitの位置によっては勝ちが確定していそうだということに気づいたのみである。4完35位。

AとBのコードゴルフをした。BはまあRubyで適当に。Aはなかなか上手くいったと思う。Perl正規表現内にはコードが書けて結果をパターンに埋め込めるので、分割位置を正規表現で試しながら辞書順比較を行いダメだったらそのマッチを失敗させるという方法が取れる。失敗したら正規表現は次の分割位置を試しに行き、最後まで試し終わったらマッチ全体が失敗したという結果になる。分割位置は「文字と文字の間」すべてで、これはつまり/\B/である。

www.youtube.com

昼前までYouTubeに気を取られつつ日記を書いていた。学食で食事した後、帰ってきてから2時間弱インターン先勉強会の準備を行った。月曜日はスライドの内容が薄いと言っていたが、この時間で2ページ追加できたのでまあ最低限の状態にはなったかなという印象。午後1時就寝。