週記（2023/09/18-2023/09/24）

09/18(月)

午前11時起床。今日はかねてより企画していた、ホスフィンとたいぺーとの昼食会＋家飲みの日である。待ち合わせは午前11時45分に青葉通一番町駅だったので急いで着替えた。Tシャツとジーパンで出ようとしたが、今日の店が高級中華だったことを思い出し襟付きの服を羽織って出発。

コース料理7品に加え棒棒鶏を注文した。以下では出てきた順に感想を書いておく。ツイートの写真はその順番にはなっていない。

いくつかの品が少しずつ盛り付けられて出てくるスタイルが好きなので、前菜は見るだけでわくわくする。それぞれの品が何だったかは正確には覚えていない。右から2番目の蒸し鶏のごまだれがけが美味しかった。

スープは味わい深く、量もたっぷりあって良かった。中華のスープは味に独特な濃厚さがあるように思う。そういう中華っぽさは好みである。

エビチリは他で食べるものとの違いがよくわからない。添えてあるのは中華まんのようなもっちりした蒸しパンで、中に餡がない状態でこれを食べることはなかなかないなと思った。

北京ダックは……これは今回の料理の中で唯一口に合わなかったと言ってしまいたい。ソースが下のほうに溜まっていて味がない部分と濃すぎる部分しかなかった。添えてある海老煎餅も自分には味が感じられなかった。

鯛には醤油ベースのソースがかかっており、あんまり中華という感じではなかった気がするが食べ慣れた味なので美味しかった。豆苗が油で炒められていたのはそれっぽいか。これと鯛を一緒に食べるのもかなり良かった。

炒飯に対する感想はエビチリと同じ。中華の炒飯はドカ盛りで出てくるものという偏見があったので、結構少なめだったのはびっくりした。

デザートの前に追加注文した棒棒鶏。前菜の蒸し鶏と同じ感じだろうと思って頼んだら、こちらはかかっているたれがかなり辛かった。さっぱりしていて美味しい。

デザートは杏仁豆腐とごま団子。ごま団子の餡はさつま芋だった。杏仁豆腐の味が濃厚で良い甘さ。

コースの前半4品の時点で物足りなさを感じ追加で注文することを決定したが、後半ではかなりの満腹感が得られた。炒飯が少なかったのはむしろ良かった点で、もしあれ以上盛られていたら棒棒鶏がちょっと苦しくなってしまっただろう。

店を出てアーケード街を歩きドンキまでやってきたところで、カードショップを見つけた。正確には以前から存在は知っていたが初めて入り口を発見した。酒の割り材やつまみの購入を二人に任せてフラフラと入ってみたら、デュエマのカードの分厚い束が700円で売られていたので、これ一つあれば3人でデッキを組んでデュエルできそうだと思い購入した。

午後3時くらいに帰宅して家飲み開始。

週記を書くのもそこそこにしてボドゲやデュエマに明け暮れた。「コリドール」は2人でプレイすると相手の妨害を一身に受けてひたすら遠回りさせられるのがもどかしい。「ラブレター」は基本カードでプレイすると引きが悪かった人が一瞬で抜けていくので自分がそうなったときに辛い。とりあえず強制敗北効果を持つ大臣を拡張カードに交換したら少しましになった記憶がある。

デュエマは非常に良かった。買ったカードは数えたら600枚弱あり、その大半がタマシードが出たばかりのころのカード。こういう風に統一されているとそのテーマに沿ったデッキが組みやすくて良い。特に今、そのテーマというのがタマシードとスター進化だったため、低コスト進化クリーチャーをたくさん使った速攻デッキがどの文明でもそれなりに形になってくれた。良い買い物だった。

ただ、プレイを続けるうちに「このカードが複数枚欲しい」とか「デュエマ系YouTuberが取り上げるような有名なカードを使いたい」みたいな欲求が出てくるのはどうしようもない。これを突き詰めることとデュエマを他のボドゲと同じ感覚で遊ぶことは両立しないから、どうしたものか……。ほどほどに我慢しておくことが重要。

眠気が限界に達したので酔い覚ましもかねて午後7時過ぎから3時間ちょっと仮眠を取った。この間にホスフィンは夕食に出かけ、たいぺーは翌日予定があるため帰宅した。起きてから体裁だけ整えた週記を投稿し、さらに数戦デュエルをして、午後11時半からCF combinedに参加した。酔いがいい感じに抜けていて良かった。

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

Aは0\dots k-1を用意し残りをxで埋めるのが良い。x=kの場合に注意しなければならないことをサンプルに気づかされた。強くて助かる。Bはnの偶奇によって操作する度答えが大きくなるか小さくなるか決まる。よって操作しないケースとすべてのbで操作するケースを試せばよい。

Cは値ごとにそれ以上の要素で最も端にあるものを考えればよい。領域は必ず正方形になる。そもそもその値が列に存在しない場合に注意。

Dは、最も安いものを買えるだけ買って、その一部をより長いものに取り換えて、その一部を……と貪欲に変更していくのが最適。このとき考えるのは後ろから見たときに累積MINを更新するものだけである。

Eはまずすべての区間に対してMEXを求めておく。ここから普通にdpしようとするとO(n^3)かかるが、区間として極小なものは実はO(n)個しかないためそれだけ使って遷移することでO(n^2)になる。ここで極小とはそれ以上縮めるとMEXが変わってしまうという意味である。

極小な区間が少ないことの証明について、コンテスト中は左端・右端になる回数が高々1回だと考えていたが正しくなかった。公式解説でちゃんと証明されている。またXORを足し算で上から評価することで答えがどうやってもnを超えないことが分かるため、計算量には213みたいな値は現れないらしい。

Fは大変だった。桁数を固定するとその桁の数は昇順に並んでおり、その間に他の桁の数がいくつか挟まる形になるので、辞書順の番号と値の差は単調に変化すると分かる。この上で二分探索することで正しい順で並んでいる区間がわかる。よって辞書順の番号を求められれば解ける。すでに桁数の固定・二分探索でO((\log n)^2)かかっているので、O(\log n)で行いたい。

そういう問題は最近yukicoderで見たが、しかし今回は基数がバカデカいし計算量的にも余裕がない。辞書順が確定する桁を全探索する以外は定数時間で処理し、所望の計算量を達成した。あとは桁をずらそうとしてうかつにk倍したらオーバーフローしたので__int128を使ったり、二分探索の前に1回判定関数を呼んで答えが存在しない場合スキップしたりして、かなり苦労しつつ終了2分前に何とか2.3secで通った。

No.2455 Numbers Dictionary - yukicoder

結果は6完43位、2870→2903(+33)。出ることに意味がある！くらいの気持ちだったがレートが正の変動を記録してびっくり。

飲酒とボドゲに戻る。せっかく買ったBlade Rondo第4弾「Frost Veil」をまだ遊んでいないので、まるで義務かのように1回だけプレイした。今回の新能力は「凍結」。字面から妨害効果かと思っていたら自分を利するものでびっくりした。具体的には、コストを事前に支払って凍結しておいたカードの効果がその後自ターンの任意のタイミングで処理できる。使いやすくてなかなか面白かったが、今はデュエマが一番面白い……。

追加でしばらくデュエルした後はずっとアニメ等を見ていた。

「陰の実力者になりたくて！」は5話くらいまで。やはりこの作品は面白い。自分はずっと七陰を「しちいん」と読んでいたので、実際には「しちかげ」だと知ってびっくりした。なろうにはルビがなかったからわからなかった……。また1.5倍速で見ていたからかも知れないが七陰のメンバーの区別がつけられなかった。

「お隣の天使様にいつの間にか駄目人間にされていた件」は12話が体育祭の話だったので、そこだけ。あんまり絵が好みでない。「ホリミヤ」は1話と主人公がイメチェンして登校してくるところだけ。大昔にWeb漫画で読んで以来久しぶりに触れたが大変良かった。

「岸部露伴は動かない」は「富豪村」の話を実写ドラマとアニメの両方で見た。非常に面白かった。続けざまに見ると表現の違いなどいろいろ気づけて面白い。自分は実写ドラマのほうが好み。主人公自身が窮地に陥っても、なお余裕のある態度を崩さない様にかっこよさを感じた。

自分に酔いの限界が来たため午前8時半くらいに解散。腹を壊して布団で唸っていたがしばらくしたら落ち着いた。

アニメの「ホリミヤ」が非常に良かったのでWeb漫画の「堀さんと宮村くん」を読み直そうとしたら止まらなくなった。結局午後0時半くらいになって就寝。

読解アヘン

書く：JAG夏合宿day3の話

09/19(火)

午後4時半起床。祝日でずれたインターン先定例会に参加しようとしたら今日だけ午後5時半開始になっていた。思いがけず空いた1時間で二度寝しようとしたが何となくスマホを触っていたら過ぎてしまった。

いざ定例会。先週は全く進捗がない。勉強会はAHC023の解法についてだった。まともに参加していないのであまり得られるものがないかと思ったが、障害物のあるグリッド上に通路となる木を作る方法はかなり参考になった。始点から1マスずつ伸ばしていくのではなく、ランダムに始点と終点を選んで一気に作るのを繰り返すとよいらしい。こういう木が必要になることは何度かあり、いつも1マスずつ伸ばす方法でいい感じの形が作れず難儀していた。

強い眠気を覚えつつぼんやりとなろうの更新をチェックしていたら、「玉葱とクラリオン」に更新が来ていてひっくり返りそうになった。いつの間にかHJ小説大賞を受賞しており書籍化が決定したらしい。めでたい。読んだのがかなり昔で終盤の雰囲気しか覚えていないため、1巻がどんな内容なのか全くわからない。このまま新鮮な気持ちで楽しみたい。

https://ncode.syosetu.com/n0632db/

午後10時就寝。

09/20(水)

午前2時半起床。眠れずネット小説を読んでいた。

今日から4日間に渡り東北大学で日本数学会の秋季総合分科会が開催される。特に今日と明日はグラフ理論の発表があるらしい。指導教員の先生から聞きに行ってはどうかとメールが来ていたので、せっかく朝から起きているのだからと参加を決めた。

2023年度秋季総合分科会

結局二度寝できないまま午前9時過ぎに家を出て、微妙に遅刻しつつ会場の教室に到着。午前の発表を聞いた。

プログラム情報

「辺着色グラフの連結性について」の冒頭では「（2辺連結）無向グラフの辺を向き付けて強連結にするにはどうすればいいか」という問題が出された。競プロerとしてはdfs木を取ってその辺と後退辺を逆に向きづける方法が思いついたが、急に耳分解と言われてびっくりした。そういうサイクルとパスへの分解からいろいろ発展するらしい。以降詳しくはわからず。

「A constructive characterization of 4-connected 4-regular graphs」は規則がなかなか複雑でお腹いっぱい。それぞれの規則が必要であることを示す反例をポンポンと見せられたが、どれも天才構築っぽくて大変そうだなあという気持ちになった。

「3-連結平面的グラフの2-連結全域部分グラフ」はそれを考えるモチベーションの説明が丁寧で、動機とはこういうものなのだと非常に参考になった。

以降の発表はどれも量子ウォークというものについてで、初見の対象だったのでほとんど何もわからなかった。ただ、「Mixed strongly regular graphs to induce periodic quantum walks」でシンプルかつ強そうな必要条件が紹介された後、そこからいろいろな結果が出ていたのは印象深い。

教室には昨年受けたグラフ理論の集中講義の先生もいらっしゃっており、ご挨拶した。自分のことを覚えておられたらしく感激。

昼食は指導教員の先生と、混雑を避けて文系のキャンパスまで向かって取った。食後に少し話し合いをしたが自分の進捗がなく、そのうちなぜか就職のほうに話が逸れていった。自分はまだ就職する気がなく知識も少ないので大した話はできていない。

午後2時くらいに解散。午後の発表はタイトルからして知らないことだらけだったので参加しないことにした。

仙台駅で来週末に迫ったオンサイト用の切符を購入した後、少しカードショップを冷かしつつゲーセンに向かった。今日は新曲を埋めつつ来週木曜日のアップデートまでのクエストを終わらせた。眠くてまともなスコアが出なかったがなんだかんだ15クレほどプレイした。

ブックオフに行ってデュエマを眺めた後つけ麺を食べ、久しぶりに本屋へ。新刊チェックから漏れていた本を2冊ほど見つけ、買うか迷っていたラノベと合わせて購入した。

午後9時帰宅。シャワーを浴びて午後10時には寝ていた。

09/21(木)

午前8時起床。

自分がチューターをする留学生が今日、日本にやってくるらしい。寮まで送り迎えしようと思って何時に仙台駅に着くか聞いていたのだが、午前という早い時間かつシャトルバスが用意されているとのことだったので取りやめた。

今日も学会へ。昨日のように遅刻しつつ教室に向かい、午前中だけ発表を聞いた。楽しみにしていた「Coqによるマッチング理論の形式化」がキャンセルになってしまい、以降は昨日と同じく量子ウォークに関する発表が延々続く。計算がメインだったため昨日に輪をかけて何もわからなかった。

空き時間で生協でラノベを買いつつ帰宅。何もやる気が出ずしばらくなろうを読んだ後、午後3時から3時間ほど仮眠を取った。

留学生とメールをやり取りし、公共交通機関の定期券を買うなどのために明日の午後2時半に寮で待ち合わせる予定を立てた。

しばらくセミナーの準備をして午後11時半からCF #898 div.4。

Dashboard - Codeforces Round 898 (Div. 4) - Codeforces

Aは怠い。abcと食い違う文字が全部ではないことを確認した。Bはインクリメントする値以外の積を最大化すればよいので、最小値を選ぶべき。Cは外周までの距離を表していると思えば\min(i,j,9-i,9-j)+1と書けて簡単。Dは貪欲。Eは二分探索で、答えが2\times 10^9くらいになり得るため何も考えずmidの計算をするとオーバーフローする。

Fはlを降順に固定すると選べるrの最大値も同時に管理できるので、あとはその範囲でaの累積和を見て二分探索。upper_boundで書いたがどういう範囲で何を探索しているのかよくわからなくなってoff-by-oneに苦しんだ。ちょっと捻った形になったらもうその場で書いたほうが良いのかもしれない。

GはBAA...AをCBB...Bにしたりその左右反転のことができる。そういう部分列を交差しないように選ぶ問題だと思い、遷移を列挙してdpした。実は制約をよく読んでおらずsには文字Cも含まれると思い込んでいた。AとBしかない今、Aの連結成分を数えてBがそれより1個少ないなら最も小さい成分を無視する、という方法で解けるらしい。

Hはとにかくループに逃げ込むのが良い。bから最も近いループ上の頂点について、そこから見てbのほうがaより近いなら逃げ切れる。面倒そうな問題に見えてなかなかシンプルな条件になったのが面白かった。

全完7位。

www.youtube.com

セミナー準備を続け午前4時過ぎに完成。先週の日記で書いたように、明日のセミナーでは論文を1本読む。シャワーを浴びてゴミを出し午前6時半就寝。

09/22(金)

午前9時半起床、午前10時からセミナー開始。自分が適当に立てたGoogle Meetでのセミナーだったが1時間以上の会議ができないらしいので途中で先生にZoomを立ててもらって移った。

最初2時間は昨日準備したものの発表。定義と命題ばかりずっと説明していたら先生に具体例についても計算してくださいと言われた。基本的な対象だと競プロチックな考え方で定義から一瞬で導けてしまい、基本的でない対象は煩雑すぎてその場では不可能。結局命題についての説明にはならなかった。

その後さらに1時間半ほど修論についての話し合いをした。一応いくつか試してみたい計算を考えてきたのだが、やる前から手法の有用性だとか評価、他の研究に対する位置付けを聞かれた。筋が良いかを見ていると思えば競プロの考察でもそういうことはするから理解できるが、とりあえずやってみてから考えるべきでは……と思ってしまう。しかし「とりあえずやってみる」が可能なのにまだ手を付けていないのは自分の怠惰さが問題なので何も言えない。

準備して留学生との待ち合わせのため出発。徒歩で向かうことにして、何かの参考になればと時間も測ってみた。途中に大きな寺があって、歩行者と自転車は駐車場の通り抜けを許可されているらしい。なかなかわかりにくい道だった。

無事合流に成功。寮のエントランスで大学まではバスを使用する人が多いと聞き、バス定期券を買うことになったのだが、調べてみるとまだ学生証を持っていないため通学用のものが買えないらしい。仕方ないのでとりあえず近くの駅に行ってicscaだけ買い、そのまま仙台駅前に出て観光としてアーケード街を練り歩いてみた。道中でLINEを交換した。メールでやり取りするのは面倒。

ゲーセンで太鼓の達人をプレイしたら1プレイ2クレ設定でびっくり。日本のアニメをいくらか知っているとのことだったから、有名そうな曲のイントロを聞かせてこの3曲を選曲した。最後は二人で「難しい」に特攻し惨敗。このとき一緒に「難しい」をやりませんかと言ったら「Why not!」と返ってきて、いかにもネイティブっぽい言い回しに感動した。

ガストで食事し、仙台駅で二人で写真を撮り、寮に戻って解散。自宅から寮までも結構距離があるし寮から駅もそこそこ遠いし、さらにアーケード街でもひたすら歩いていたので足が疲れ果てた。英会話については大変だったが、相手が気を使ってくれたのか短い文章で受け答えしてくれたので、まあ何とかなったかなという印象。

シャワーを浴びた後月曜日の残りである梅酒を飲んだらしたたかに酔っ払った。

午後8時半から仮眠を取り、ギリギリで起きて午後9時20分からyukicoder 405。

yukicoder contest 405 技術室奥プログラミングコンテスト#7 Day1 - yukicoder

Aは\lfloor\sqrt S\rfloor^2を貪欲に引いていけば良いと思ったらWAが出た。証明していないので個数が多すぎたかと思い適当に探索してみたら今度はMLEが出た。いろいろ試すうちに\lfloor\sqrt S\rfloorを求める部分がバグっていたと判明。sqrtの結果を微調整して求めたのだが、値を増やす方向にしか調整しておらず、真の値より大きな値が返るケースがあった。修正したら通った。

Bは登場する数がaとa+1、列の長さがLだとすると、0\lt l\lt Lに対しN=La+lと書けなければならない。この式を見るとl=N\bmod Lなので、LとしてはNの約数でない正整数がvalid。

CはM=1の場合先手勝ち。それ以外は基本的には真似っこ戦略で相手が言った単語を反転したものを言うのが強い。問題は先頭と末尾が同じ文字の単語で、そのようなものはN^{M-2}個あるから、この値が偶数なら真似っこ戦略が成立して後手勝ち。奇数なら先手がまず一つ言ってしまうことで同じ戦略が先手勝ちをもたらす。

Dは結構難しかった。砂時計の組をひっくり返すのは砂時計のswapになるが、そう思ってもすぐには解けない。とりあえずこれでT秒後の砂の量が多重集合として求まるので、それぞれどの砂時計と対応しているか分かればよい。砂の量を1次元にプロットしてイメージしていたら大小関係が変わらないことに気づき、ようやく解けた。こうやってAntsを問われると反応できない。

solved数を見てFに行った。長さiのprefixにインクリメントする操作と長さN-iのsuffixにインクリメントする操作を同時に考える。その回数の差はBから決定できて、余りは全体へのインクリメントだと思える。その回数を全探索して、とりあえずprefix・suffixへの操作回数を状態としたdpを考えた。

そうして行った操作によって全体が何回インクリメントされたか、またあと何回全体をインクリメントしないといけないかは、実は算数で特定できて、残りの操作の回数が一意に定まる。多項係数になるようにdpを遷移することで操作列が数え上げられるが、この遷移は畳み込みになっているのでO(NM\log M)で解けた。実はGも同じ計算量で間に合ってしまう。

Eはaを直接考えようとしてかなり悩んでいたがbを考えたらすぐ解けた。Mと2進数で同じ桁となる数のうち最大のものXを考える。基本的にbは0\dots Xから部分列を取り出してきたような列になれるが、初項がM以上だったり途中にXORがM以上となる隣接する2項があるものは取り除かなければならない。前者は簡単。

後者について、最上位bitは列の中で1回までしか変化できないことを考えると、そのような2項も高々一組しかないことがわかる。よって組を固定するごとに列を数え上げればよい。この数え上げは2べきの積なのでbitごとにバラすことができて、組を固定するのと合わせ桁dpで求まる。

全完9位。Aで詰まって点数が低めになってしまった。

夜は日記を書いて、集中が切れてきてから10月のラノベ新刊チェックをした。今回は33冊予約。積読の増加に歯止めがかからない。

午前5時半就寝。

09/23(土)

午後2時半起床。先週行われたJOI一次予選の過去問が公開されていたのでコードゴルフをした。全部Nibbles。

Aは各行1個しか整数が存在しないので_で全部一気に取れる。これでdcよりも短くなり4B。Bは昇順にソートして2引数関数-@$でfoldr1すると最後の要素から残りを引いたものが得られる。0をこの値で累乗すればよい。Cは入力全体をtransposeし末尾の文字が他に存在しないような行を数えた。Nを構成する数字が紛れ込んでいても構わない。Dはuniqとsortをそれぞれ行う。

JOI 2023/2024 一次予選 (第1回) 過去問 - AtCoder

昨日届いたABC317の記念品を開封。ポストカードのポケモンはナゾノクサだった。

初めて届いたという報告をTLで目にしたのは結構前のことだったと思う。自分は順位特典での当選を確信していたため喜び勇んでポストを確認しに行ったが、その時は届いておらず、登録にミスでもあったかと不安になった。なぜか届くタイミングがバラバラらしくそれからも五月雨式に報告ツイートが流れてきて、ついに自分の手元にも来てくれた。安心。

午後3時過ぎに両親が来た。結構前から決まっていた予定だが夜のABC以外コンテストのない日になってくれてよかった。しばらく自分も手伝いつつ部屋の掃除をして、午後5時前に買い物と夕食のため外出した。

Webカメラの接続を良くできないかと駅前のヨドバシカメラで新しいUSBハブを買ってもらった後、そのまま同ビルの飲食店フロアで食事も済ませようとした。しかしちょうど何かの試合の帰りとぶつかってしまったようで、飲食店はどこも大混雑。45分ほど並んでお好み焼きの店に入った。

お好み焼きは焼くのに時間がかかるらしいので焼きそばを注文。実際、近くの席に同じくらいのタイミングで入った客は、我々が食事を終えたくらいでようやくお好み焼きが焼き上がったようだった。

午後8時半くらいに帰宅して親と別れた後、新しいUSBハブを設置した。ACアダプタが大きかったのでスペース確保のために他のアダプタを抜き差ししたらそれがちょうどPCの電源ケーブルで顔が真っ青に。幸い壊れはしなかったが、そのようにバタバタしていたら午後9時になっていた。手元の撮影の準備が間に合わないままABC321へ。

SuntoryProgrammingContest2023（AtCoder Beginner Contest 321） - AtCoder

焦りすぎてAの問題文が頭に入らない。とにかく何も考えず問題文の条件を実装した。Bがちょっと面倒そうだったので改めて準備を整え、ここから録画を開始した。

BはNラウンド目のスコアを全探索することにした。多分場合分けを使うもうちょっと計算量の良い解法があるはず。Cは9876543210の部分列を全列挙してソート。肝心のその数だけint型に収まらなくてオーバーフローで1WAしてしまった。

DはBをソートしておくとAを固定するごとにA+B\ge Pとなる境界が決まるので、その左右それぞれで計算。Aもソートしておいて順に見れば、その境界は尺取り法みたいに求まる。

EはCF #896 Cを少し簡単にしたような問題。求める点とのLCAごとに数え上げる。XがLCAから見て左右どちらの子以下にあるかで求める範囲が異なることに気づいておらず、しかもサンプルで落ちなくて1WAした。

https://codeforces.com/contest/1868/problem/C

Fは一目見てdpの巻き戻しをする問題だと思ったが、そのためには列を途中で打ち切らずちゃんと5000Qくらいまで管理しなければならないと勘違いしてしばらく別の方法を探してしまった。冷静になって遷移を確かめるとどちらの操作でもある項はそれ以降の項にしか寄与しないため、管理するのはKまででよい。

Gは部品の部分集合を固定し、それが連結成分をなす場合の数を求める。集合の1点を固定してそれが属する連結成分が今固定した集合の真の部分集合になっているケースを引けばよい。下位集合に対する答えと、それ以外の部分のつなぎ方つまり適切な階乗の積で求まる。ここが単純な除原理になっていることに気づかずゼータ変換をしてみたり、階乗でいいのに気づかず謎の和を取ってみたりと合わせるのに苦労した。

全完2ペナで16位。速度的にも賞金圏内ではなかった。今日は簡単セットという印象だが、それ以上に頭が回っておらず落ち着きもなかった。

www.youtube.com

コードゴルフはAとCのみで、両方Nibbles。Aはそのまま書けばソートしてuniqして比較だが少し面倒。group byがソートもしてくれるので、それをtransposeするといい感じになる。文字列のリストなので比較にindexも使えてさらに良い。Cは部分列全列挙の関数があるのでそれを使う。それぞれ10進数として解釈し、順序がぐちゃぐちゃなのでソート。

急激に眠くなって午前1時くらいに布団に入った。このまま寝たら朝の変な時間に起きるんだろうなと思っていたがなんだかんだ午前4時前に目を覚まし、それからはずっと日記を書いていた。少しラノベを読んで午前11時就寝。

09/24(日)

午後3時起床。涼宮ハルヒシリーズの続刊が制作中らしい。

AHC024が始まっていたので慌てて参加した。正直眠いのでそこそこにして寝るかなと考えていたのだが、なんだかんだ4時間フルで取り組んだ。

Marubeni Programming Contest 2023 (AtCoder Heuristic Contest 024) - AtCoder

まず削除できる行・列を貪欲に削除するのと外側から1マスずつ削り取ってみるのを実装。これで230709点だった。

区の境界がデコボコしていると行・列の削除が難しいので、そこを山登りで均してみることにした。遷移は1マス選んでその周囲の色で塗るというもの。評価関数としては選んだマスの周囲3マスが同じ色だった時に大きく加点・減点し、またL字に並んだ3マスで真ん中だけ色が違うようなものにペナルティを付けてみた。これでそこそこいい感じになって251304点。

均すのと削除を1回ずつではなく交互に繰り返すようにしたら269811点が出て、あとはずっとパラメータ調整をしていた。最終結果は270514点で135位、パフォーマンス1800、レート2235→2239(+4)。

TLでツイートを眺めつつ感想戦。山登りを焼き鈍しに書き換える気力が出なかったのはしょうがない。行・列を全部削除する他にも一部を削除して間を詰めるのができればもっと伸びたようだ。それが効きそうな盤面を観測してはいたが、実装が難しそうで諦めてしまった。あとは、均してから削除なんて悠長なことはやらず、最初から削除も近傍に入れて遷移させるべきだった。これは完全な方針ミス。

MHCのPractice Roundが開催中である。昨年まではこれはQualification Roundという名前で次のRound 1進出には1問以上解くことを求められていたはずだが、今年はそういうことはないようだ。ただそれで無視してしまうのもなあ、ということでこのタイミングで参加した。来週火曜日までなのでここに感想は書けない。

Meta Hacker Cup - 2023 - Practice Round

しばらく日記を書いた後、午後10時前から1時間半の仮眠を取った。ギリギリで起きて午後11時半からECR155。

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

Aはw=s_1だけ試せばよい。Bはすべての行に置くかすべての列に置くかしなければならないので、それぞれ最も安い列・行を選んで埋める。Cはdpで消す文字数の最小値を求め、同時にそれを達成する選び方を数え上げる。操作手順は消す文字としてどれを選びどの順番で消すかと一対一対応するので、適当に階乗を掛ければよい。Dはbitごとに見ればあとは典型。

Eは大変。根以外のすべての頂点について、親への辺は唯一の色で塗られている必要があり、またその色を特定しなければならない。まず木の深さが1のとき、またそのときのみ全部の辺を1で塗ってよい。また深さ\bmod 3を塗ることでも親の辺を特定できる。あとは2色で塗り分けられるか判定すればOK。

2色で塗り分ける場合親に向かう辺と子に向かう辺は必ず違う色になる必要がある。それで親への辺が特定できないのは子をちょうど一つ持つ場合。そこで、このとき親への辺を色1で塗ってみる。そこから他の辺の色も決まっていくが、どこかで矛盾が生じればアウトとなる。ただし根だけは子への辺がどんな色で塗られていてもよいことに注意。特に、色と深さの偶奇が完全に対応するわけではない。

Fも大変。xを固定するとヒーローは\lceil a/x\rceil\times hラウンド後に死ぬので、これのTop 2が求まればよい。商列挙すれば解けそうだと思ってからが長かった。まずTop 2取得に\logを付けないためxの降順に探索することにした。こうすると値が単調に増加するためうまくいく。また最初に商を列挙してしまうとメモリが足りないので、ある区間を見終わってから次の区間を計算するという感じにした。

あとは定数倍バトル。ランダムケースで商列挙の計算が行われる回数を調べたら108回を超えており、これが10ケースもあるとさすがに間に合わない。商の計算と区間の計算でそれぞれ除算を1回ずつ行っているのが重いので、xが適当な閾値を下回ったら毎回全部見て計算することにした。すると同じxでN回除算を行うことになるから、適切な前計算で乗算に置き換えるのが効く。閾値を1000くらいに設定したら5sec強で通った。

コンパイラによる整数除算最適化の証明 | nu50218 blog

Eで3ペナ、Fで4ペナ出したが全完者が少なく9位となった。Fはxに対して商を決め打つと対応するaの区間が出るが、このような見方をすると区間の数が全体で調和級数となり高速らしい。この計算量改善は商列挙あるあるだとは思うものの、なかなか難しい。

www.youtube.com

朝まで日記を書いた後2時間くらいインターン関連のコーディングを行い、機械学習を実行できるところまで進めた。GPUをぶん回しながら布団に入り、しばらくラノベを読んで午前10時半就寝。