週記(2023/02/20-2023/02/26)

02/20(月)

午後4時半前に起床しインターン先の定例会に参加した。

1on1で認証回りを頑張ったのとバグ修正のチェックが先週の進捗。今週は認証を突破できたのでそれも含めコードの手直しをするタスクが振られている。

勉強会はマネジメントの話だった。昨年最終回の続き。何かを行う際、目標から決めていくトップダウン型とできることからやっていくボトムアップ型の対比が印象的だった。バランスが大事ではあるが、トップダウンで目標を意識する重要性が説かれることが多いのも事実。これには人間の傾向としてボトムアップ型に偏りがちということがあるのではないだろうか。少なくとも自分はそうだった。

インターンを初めてしばらくしたくらいに受けた助言で「実現できるかどうかではなく実現したら嬉しいことに取り組みましょう」というものがあった。これもトップダウン的な話である。結構感銘を受けていまだに覚えているが、自分でそのようにできているとはまだまだ思えない。

発表と質疑応答が終わったのは午後8時だった。最近この時間まで続くことが多い。別に苦痛なわけではなく、むしろかなり楽しく参加している。それから先週の週記を書き上げ、午後11時に投稿した。

ABC-EFの最短コードを読んだ。Eは\min(i,N-j+1)が面倒。数列の両側からインデックスを交互に見ることで\minの値を固定し、まだ見ていないインデックスで同じ値を持つものを数えることで係数を求めることができるようだ。

Fは答え\frac{(N^2-3)(2N-4)!}{(N-1)!(N-2)!}について、階乗をチマチマ前計算するよりa_N=\frac{(2N-4)!}{(N-1)!(N-2)!}とおいてa_{N+1}=\frac{(2N-2)!}{N!(N-1)!}=\frac{(2N-2)(2N-3)}{N(N-1)}a_N=\frac{4N-6}N a_Nのように計算してしまうのが良いらしい。昨日より縮んでいた。その後係数を4-\frac 6 Nとすることでさらに縮んでいた。

少し日記を書き、午前1時からセミナー準備を開始した。先週の残りがあるので量としてはそれほど用意しないつもりだったが、それ以上に教科書の内容がうまく把握できずかなり苦労した。4時間かけて何とか4ページほどのメモを作成した。

シャワーを浴びて午前5時半就寝。

02/21(火)

午前9時45分起床。原付で山に登り、購買で朝食を確保していつものように10分遅れでセミナーの教室に到着した。

午前中は同級生の発表だった。ある定理の証明が一か所完成していないとのことで、それに関して教科書の文言を確認したところコーナーケースがあるように見えた。自分の勘違いかとも思ったが、教科書をもっと読んでいくとやはり辻褄が合わない。その後明確な誤りを発見し発表はお開きになった。定理自体に問題はないはずで、証明がよくない。

連結なグラフを閉曲面に埋め込むと、各面についてその内部の閉曲線を連続的に1点に縮めることができる。閉曲線の内外両方にグラフがあると連結ではなくなるからだ。このような性質を持つ面の内部は開2-胞体、つまり開円板と位相同型になり、面の境界は円周と位相同型になると書かれていた。しかし境界がサイクルでないような面などいくらでも考えられるから、最後の文言は明らかに誤りである。

今書いた論理の流れのどこで間違いが犯されているのかはいまいちわからない。ただ教科書の図には境界がサイクルにならないような面が書いてあるのに、その内部も開2-胞体だと強調した上で境界が円周と位相同型などと言っているのだから、間違っているのは自分の勘違いではないはず。

正午を少し過ぎたくらいに購買で昼食を買い、教室で食べて、すぐ博士課程の方の発表に入った。相変わらず定義の少し先の命題で詰まっている。そもそもこの定義というのがあまり直感的ではないから精密に見ておく必要があるのに、添え字が1違うとか上限下限にイコールが付いているか付いていないかとかの微妙な部分が毎度毎度曖昧。正直言って腹が立つ。自分で資料をチェックする気力も失せて久しい。

今日もあまり進まず午後2時半終了。30分の休憩となった。つい先ほどまでそこそこ雪が降っていたはずだが、今見ると晴れ上がっていて良かった。何とか原付で帰れそうだ。

休憩時間は机に突っ伏していた。午後3時から自分の発表。今日は2時間かけ、先週やり残した分に加え昨日準備した分まで全部発表した。昨日の部分はやはり難しい。理解はしているつもりだったので自分なりのポイントを考えながら喋っていたつもりだが、感触が悪い。似た内容を何度か繰り返したり、先生からの質問に答えたりしたので、ある程度伝わったものとは思う。

来週は大学入試の採点作業が忙しいらしくセミナーもなくなった。再来週の同級生の発表については、今日の件で教科書の信用度が落ちたため、自分が読んでいるDiestelに合流することになった。とりあえず次に控える4.4章を丸々やってもらう予定だ。

解散後、学割証の発行のため川内キャンパスに降りた。学食もそこで食べようと思ったら春休み期間で昼しか営業していなかったため、コンビニで菓子パンを大量に買い込んだ。

午後6時帰宅。2時間ほどTUPCのテスター作業をしてから布団に入り、ラノベを読んでいた。午後9時までは起きていた痕跡があるが、その後いつ寝落ちしたか定かではない。

02/22(水)

午前2時半頃目を覚ましたはず。そのままラノベを読んでいた。午前6時頃「ネトゲの嫁が人気アイドルだった」3巻を読了。

2巻を読んだのが1年以上前で内容をあまり覚えていない。この巻では新たにヒロインと同じアイドルグループに所属する義妹が登場し、主人公からは見えないアイドルとしての苦労が扱われた。その話はなかなか辛かったが、義妹は小動物的で可愛らしかったしヒロインとの交流もほんわかしていて、全体としては楽しく読むことができた。

このシリーズは1年近く新刊がないので打ち切りになってしまったのだろうと考えている。積んでいるうちに打ち切りになったシリーズを読むタイミングというのは何とも難しい。そういう情報は読む前からネガティブな影響を与えてくる。

その後も別のラノベを読んでいたが、午前9時を過ぎて布団から出た。

メールでこのブログの記事に付けられたはてなスターが合計2000に到達したことを知った。いつもいつもありがとうございます。

午後4時までTUPCのテスター作業をしていた。その間にABC287の賞品でアマギフ10000円分が届いた。以下のように当時は学生賞を逃したと思い込んでいたが、これでもギリギリ5位だったらしい。

1WA全完で19位。賞金には遠いかと思ったら上位にそれほど学生がいないようで、ペナがなければ滑り込めていたらしい。

週記(2023/01/23-2023/01/29) - kotatsugameの日記

午後4時半就寝、午後10時頃起床。またラノベを読んでいた。

集中力が切れたタイミングでTLに目をやったところ、西尾維新書き下ろし・短々編「緊急対談!戯言遣い×阿良々木暦」というのが流れてきたので開いた。短々編といってもアニメ声優による朗読形式になっていて動画時間は17分もあったが、MVも凝っているし話の内容も興味深いというか先が気になる感じで、自然と全部聴いてしまった。

www.nisioisin-anime.com

午前1時頃「ひきこもりの俺がかわいいギルドマスターに世話を焼かれまくったって別にいいだろう?」3巻を読了。相変わらずコミカルでふわふわした展開が続き気楽に読めた。クライマックスは明らかに人死にが出るような規模のクーデターだったが、それでもどこか緊張感のない描写だったのはむしろすごい。

また別のラノベに手を出した。

朝方、今後GCJが行われないことになったと知った。最近のレイオフでこれまでの担当者がいなくなったのは聞いていたが、まさかコンテスト自体がなくなってしまうとは。青天の霹靂だった。

午前5時半就寝。

02/23(木)

午後2時半起床。相変わらずラノベを読んでいた。午後6時半頃「転生したら皇帝でした」1巻を読了。

2年ほど前に読んだなろうの書籍版。1巻が出たのは1年前で、現在既に4巻まで刊行されている。内容を結構忘れていて面白かったという記憶だけが残っていたが、今読んでも変わらず面白い。真の実力を知られてはならないという緊張感が常に漂っていながらも、これはと見込んだ相手に自分の真価を見せつけて心酔させるシーンが時おり挟み込まれ、読者としてずっと我慢を強いられるわけではないのが嬉しいところ。ただこの先の展開をなろうで知っている自分としては、1巻はやはり耐える側面が強いように感じられてしまった。

布団から出てTUPCのテスター作業をした。2時間弱でまた布団に戻り、しばらくラノベを読んでいたら午後10時前に寝落ちした。

02/24(金)

午前0時半起床。布団でラノベを読んでいた。午前4時頃「転生したら皇帝でした」2巻を読了。

この巻で主人公がついに真の実力を明らかにする。なろうで読んだときはいよいよかという気持ちが強かったが、本になってみると2巻に収まってしまうくらいだったようで展開の速さに驚かされた。それでもこのカタルシスに向けた溜めは十分。クライマックスは緊張に汗を垂らしながらじっくり読んだ。やはり最高だった。

シャワーを浴びて1時間ほどインターンの進捗を産み、少し日記を書いて午前7時頃また布団に戻ってきた。ラノベを読んで午前8時半就寝。

午後1時45分に目覚ましで起床。ちょうどTLに第12回PASTの過去問が公開されたというツイートが流れてきたので、慌ててAとBだけ解いた。

第12回 アルゴリズム実技検定 過去問 - AtCoder

Aは問題文を読むのに苦労したが、答えは\min(X+Z,Y)となる。PASTのA問題はひたすら面倒という印象だったので、かなりきれいな式になってびっくり。dcで書いた。Bは何も考えず後ろ2文字を消すコードをsedで書いて1WA。N\lt 100の処理が面倒だったので、素直に100で割ることにしてRubyで出しておいた。

Cからはすぐ縮みそうになかったので切り上げ、ちょうど午後2時になったので1on1に参加した。

昨日の進捗は実はコードを少しリファクタリングしたくらいしかなく、早々に今週のタスクの説明に移った。新しい機能を一つ実装するという話だったが、導入として少しコードを書いてもらいながら説明を受けているうちにいつの間にか完成してしまったので、その周りを整備する作業だけが残った。1時間半で終了。

この後はゲーセンに行こうと思っていたが、日曜日終了のAHCにまだ1回も提出していないので、そちらに取り組むのを優先することにした。しかし仮眠によって英気を養おうと布団に横たわったところうっかりカクヨムを開いてしまい、そのまま10時間ほど読みふけっていた。2作読了。

1作目、「特級探索者、配信者となる~攻略マナーを配信してただけなのに何故かバズって困ってます~」。超強い主人公がマナー講座の動画をアップしたところ、何気なくやっていたことがあまりに凄すぎてバズるという話。設定も導入も面白かった。主人公の性格からして動画投稿にあまり乗り気でないのは自然だが、もうちょっと積極的にやってくれると目立つシーンが増えて個人的には嬉しい。

kakuyomu.jp

2作目、「推しにダンジョン産の美味いもんを食わせるために、VTuberになってみた」。これも主人公最強モノ。面白かった。話が進むごとに主人公の人間離れしている様がどんどん明かされていって良かった。際限なしの強さだ。ここまでくるとVTuber要素は別に要らない気もする。飯テロ動画をアップするのに手元しか映せないのはちょっと窮屈。

kakuyomu.jp

午前1時半に布団から脱出。水曜日の日記にGCJが終了することを書いたが、なんとTCOも今年が最後となるらしい。この最終回はすでにオンライン開催となることが確定しているそうで残念。

discussions.topcoder.com

いよいよAHCに取り掛かった。アイディア自体は先週問題を読んだときから頭の中にあったので、ひたすら実装。盤面からいくつかセルを選び、そこを掘って頑丈さを求め、それが小さい点を繋ぐというもの。

もっと具体的に言う。最初に盤面から縦横いくつかおきにセルを選んで掘って頑丈さを求め、他のセルの頑丈さを直近の選んだセルと同じ値だと推定した。次に選んだセルからグリッドグラフを作り、辺のコストをその上に乗るセルの推定した頑丈さの和で決めた。最後に、水源や家それぞれから直近の選んだセルまでの経路を掘り、グリッドグラフ上で接続する問題だと思って適当な貪欲で解いた。

最初の提出は24.5M点。これは自分の提出一覧で見られる点数を書いているので、小さくするのが目標である。とりあえず正しいコードが書けたので、手元でいくつかのケースを試しつつパラメータ調整をした。また、セルの頑丈さが推定値を上回っていた場合に追加で掘るとき、パワー100連打をやめて指数的に変化させた。以上2点の改善を行った次の提出では11.7M点になった。

そこからパラメータ調整で少しずつ点数を下げていたが、経路を連続的に掘る際にひとつ前に掘ったセルの頑丈さをパワーとして使って次のセルを掘るようにしたらそこそこ大きく下がった。10.3M点。

最後に、グリッドグラフの辺を一気に掘るとき、端点のうち使おうとしているパワーが小さいほうを掘って一つ縮めるという操作を繰り返すようにしたら10.1M点となった。先ほどの掘り方だと頑丈さの累積MAXを使っていることになって、辺の真ん中に頑丈さのピークがある場合に損していた。これを解消したつもりだ。

この時点でギリギリ400位を切ったくらいだったはず。アイディアを温めていた時間は長いのに全然うまくいかなくて残念だった。温めていたといっても別に考察していたわけではないので当然か。

提出の待ち時間などにまたカクヨムを読んでいた。午前7時頃「RDA.com ~死を恐れないRTAダンジョン探索者、現代ダンジョンにてゲームと同じ挙動を再現し、物理法則ガン無視無双~」を読了。

導入はいわゆる追放モノであまり好みではなかったが、その後は非常に面白かった。単純に主題となる最強格主人公の無双が面白いし、それにダンジョンとかタイムアタックとかバトロワとか、果てには妖怪・神話・都市伝説の要素が無理なく組み合わさって目くるめく世界観が心地よい。

kakuyomu.jp

シャワーを浴びて日記を書いていた。途中でパックご飯を食べようとしたとき、温め時間2分のところを冷凍弁当のときの手癖で7分にしてしまった結果、全体的に縮んで硬くなり、一部は噛み切れなかったため泣く泣く捨てた。この失敗は2回目。

午前11時に布団に入り、ハーメルンの更新をチェックしていたらすぐ寝落ちした。普段通りなら午後2時からのUniversal Cupに備えもっと早く寝なければならなかったのだが、今回はチームメイトがゆるふわ競プロオンサイトに参加するので日曜日午前3時からの枠で参加することになっていた。

02/25(土)

午後8時半起床。急いで食事して午後9時からARC157に出た。

AtCoder Regular Contest 157 - AtCoder

Aは|B-C|\le 1である必要がある。逆にこれが満たされていればXXXに置き換えるなどしてADを好きに揃えられるので十分……ではない!1WA。B=C=0がコーナーケースだった。

Bは結構難しい。Xの個数をcとする。c\ge KであればわざわざYXにする必要がないため、XからK個を最適に選ぶ問題となる。c\lt Kの処理で詰まっていたが、全体を1度置き換えてからN-K個をもう一度置き換えると考えれば、XN-c個となってN-c\gt N-Kが満たされ最初のケースに帰着できる。

あとはc\ge Kで解ければよい。Yが1文字もない場合は\max(K-1,0)が答え。そうでないとき、すでに存在するYの隣のXを選ぶようにすると、基本的には1文字置き換えるごとに答えが1増える。連続するXで左右にYがあるものを全部置き換えればボーナスで答えがもう1だけ増えるので、このボーナスを最大化する問題となって、置き換える必要のある文字数が少ないものから貪欲に使うとよい。

CはPのスコアを「Y同士が隣り合う箇所を2回選ぶ場合の数」と捉えることで、逆に上下・左右に隣り合うYの寄与を考える問題にする。同じ所を2回選んだ場合、それを含むPはcombinationで普通に計算できる。そうでない場合も2箇所のうち先に出現するところから後に出現するところまでをdpでまとめて計算することでPを数え上げることができる。

Dは面白かった。Yの個数をcとする。柵によって行がh分割、列がw分割されると、区画はhw個できるので2hw=cが成り立つ。この(h,w)を全探索する。柵の置き方について、例えば行に置いた柵だけ見たときはh個の区画に2w個ずつYが含まれるはずなので、上にY2w個ある位置に一つ、4w個ある位置に一つ、という風になっているとわかる。

この時点でまだ柵の置き方が確定していないのは、Yを含まない行・列をどの区画に入れるか決まっていないというだけの話だから、実のところなんでもよい。適当に選んだ置き方が正しく分割できていれば、可能な選び方すべてをまるまる答えに加算できる。(h-1)+(w-1)本の柵について置ける位置は被らないので、それぞれに対して数え掛け合わせることで足すべき場合の数が求まる。c=0で1ペナ。

Eも面白かった。Yを書き込んだ頂点について、それに隣接する頂点にはすべてXを書き込む必要があるので、親の数がBに、子の数がCに寄与する。この寄与を具体的に見ると(B,C)に対し(1,0)(1,2)(0,2)の3通りしかない。これらによってBCが達成できればA+B+C=N-1より自動的にAも達成できるので、以降Aは無視する。

3種類の寄与のうち(0,2)は根だから使うか使わないかを両方試せる。残りの頂点に隣り合わないようにYを書き込んで、対応する(1,0)または(1,2)を足し合わせて(B,C)(あるいは(B,C-2))を作ることを目指す。

各頂点がO(N^2)状態持つ木dpに見えるが、片方を使う回数を固定したときもう片方が最大何回使えるかさえ求まれば判定は可能。例えば(1,0)を使う回数を固定すると、これは葉にYを書き込んだ回数だから、各ノードではそれ以下にある葉の数だけしかdpを計算しなくてよく、全体で2乗の木dpになる。遷移のミスで1WA。

Fは解けなかった。共通部分列なので「Sの何文字目とTの何文字目がマッチ」のような遷移のdpを書きたくなるが、文字の入れ替えで困る。そこでSTを1文字ずつ同時に見つつ、それぞれ共通部分列の何文字目まで取ったかを管理する方針を考えた。

当然STで取り出せた文字数には偏りが生じるから、長いほうがどちらか・長さにどれだけ差があるか・もう片方からまだ取り出されていない文字列は何かを状態に持つ必要がある。この差というのは普通に考えればN/2まで到達しうるが、実は最適解はもっと小さくなるのではないかと思った。

どんな値になるかわからないまま適当に上限を定めてdpを書き始め、長さに関しては正しい答えが出せるようになったが、復元が複雑すぎた。どうしようもないままコンテスト終了。

5完7位。なかなか全完できない。Fは考察の道筋が全くできていなかったが、差が十分小さいというのは合っていたらしい。しかしこの「十分」というのはギリギリdpできるくらいという意味なので、復元は文字列を一緒に持つなどせず真面目にやらないと間に合わなそうだった。

今日も動画を撮っていた。コンテスト終了後念入りに各問題の振り返りをするところまで録画し、すぐYouTubeにアップした。

www.youtube.com

実は今日はCFでコンテストがあったらしい。完全に見逃していた。気づいたのは午前0時頃でExtra Registrationすら終了していたが、問題は読んで解けるところまで解いておいた。CF #853 div.2。

Dashboard - Codeforces Round #853 (Div. 2) - Codeforces

Aは先頭2項の\gcdが2以下である必要があって、逆にこれさえ満たしていれば残りはどうでもいい。先頭2項を全探索する。

Bはsを真ん中から二つ折りにし、重なった文字が異なる位置を考える。どんな操作も、この重なった文字の一致・不一致をある区間でflipすることになるから、異なる位置がちゃんと一つの区間になっているかチェックすればよい。sが最初から回文でもよい。

Cは数列ごとに値がdistinctなので、A_iA_jを連結した数列の要素の種類数は2nからA_iA_jに共通して現れる要素の種類数を引けば求まる。これを分解すると、まず2nm(m+1)/2回答えに足され、1\le v\le n+mに対しvが出現する数列の個数をc_vとして答えからc_v(c_v-1)/2引くということになる。

数列のインデックスごとにクエリによる値の変化を記録することで「インデックスiA_lからA_{r-1}まで値v」という情報が合計n+m個得られるので、それぞれについてc_v\leftarrow c_v+(r-l)とすることでcが求まり、答えが計算できる。

Dは面倒だった。k=0が許されていないので、操作によってa\ne 0の状態からa=0にすることはできない。逆も当然できない。このケースを処理すると、abはそれぞれ少なくとも1bitずつ立っている状態になる。その右端の位置が揃っているとしたら、そのbitを使って左にあるbitを右から順に合わせていくことができる。1bit合わせるのに高々1回の操作が必要。

なので問題は右端をどう揃えるか。aの右端がbより左にあれば、1回適当な右シフトをXORすることで揃えられる。右にある場合は、まずbの右端と同じ位置のbitを立て、その後aの「左端の」bitを使ってbの右端より右にあるbitを消していくことで揃えられる。

右端を合わせる前も後も、どちらも1回の操作で1bitずつ揃えていると思えるから、操作回数は明らかにn回以下となる。シフトの左右と符号の対応がうまく認識できず、混乱しながら実装した。

E。s_ns_n-1の商列挙で、\lfloor s_n/x\rfloor=a\lceil s_n/x\rceil=bとなるようなx区間O(\sqrt{s_n})個に分解する。この後はpa+qbという形で表せるs_iをそこそこ高速に数えられればよい。pqが負になれないので単に\gcd(a,b)の倍数が全部作れるというわけではなく、b=aまたはb=a+1となることを利用して頑張る必要がある。

b=aの場合は簡単で、aの倍数を数えればよい。aの倍数を全部見てsに存在するかチェックするという方法でも、全体でs_nの約数の総和と同じ回数しかループが回らないので十分高速。あるいは調和級数O(s_n\log s_n)と思ってもよい。

b=a+1の場合、s_iは[tex:a2]以上であるか、ある1\le k\lt aについて区間[ak,bk]に含まれている。kを全探索しあらかじめ求めておいた累積和でカウントするとO(a)だが、こちらは今度こそ調和級数による評価ができて、全体でO(s_n\log s_n)となる。

Fは解けず。T'が4文字以下のケースは全探索して、5文字以上はk素数として全探索することを考えたが、後者がどうやってできるのかわからなかった。コンテストに最初から参加していたとしても解けたとはあまり思えない。

システス後にAからEまでのコードを提出したら全部一発で通った。

ARC-Aのコードゴルフをした。dcで頑張る。|B-C|\le 1についてはスタックにNoYesが積まれた状態でB-Cを使ってRを行うことでうまく判定できた。B-C\le -2なら先頭の要素が後ろに、B-C\ge 2なら後ろの要素が先頭にrotateされてくる。B+C=0のチェックはB-2C=0でも通った。これは単純なテストケースハック。

午前3時からUniversal Cup 5回目。今日はOsijekセットだった。先週に引き続きほとんどの問題文が短くて読みやすかった。

The 1st Universal Cup. Stage 5: Osijek - Dashboard - Contest - QOJ.ac

チームでIFGJAを解き5完41位。自分はすべての問題に関わった。

最初にIが解かれた。ぷらさんが読みに行ったが微妙に詰まっているようだったので自分も一瞬読みに行き、操作が数列のreverseとrotateになっていることを指摘した。これによりほとんどのケースで2nが答えになるとわかる。小さいケース、具体的にはn\le 2に注意してほしいというところまで伝え実装は任せた。しかし自分もぷらさんもn=2の時の答えが2になると思い込んでおり、二人で確認してから提出したのにWA。実際は1であった。

ここからしばらく何も解けない時間が続いた。自分はDに、ぷらさんはFに、かっつさんはGに取り組んでいたはず。解けずに唸っているとFからHELPが来て、読んで喋っていたら解けた。

出現する文字の種類数を\sigmaとする。真ん中を固定し、左右2文字ずつについてどんなものがどれだけ出現するかを数えたい。一方は真ん中をずらしながらdpできて、更新がO(\sigma)箇所なのでTLにも収まる。しかしもう一方はdpを戻しながら計算する必要があり、単純に書き換えたO(\sigma)箇所を保存するとメモリが足りなくなった。ここで、実はその時点のdp配列から直接計算できるのに気付いた。

答えを計算する際は左のdp配列と右のdp配列の各点積のようなものが必要になるが、dp配列を更新しながらこの値も差分更新することで同様にO(\sigma)で計算できる。実装はぷらさんに任せた。

Gも捗っていないようだったので、かっつさんと喋りながら手でいろいろ試していた。n=3で壁8枚を達成した後、n=4n=5を適当に作っているうち、外周を全部埋めてn-2のケースに帰着するのが最適じゃないかと思い始めた。

外周に限界まで壁を作ると2n枚置けるが、このとき外周に接する辺はもう使えない。よって外側1マスを無視して考えることができ、n-2に帰着できるというわけ。nが3以上の奇数なら最後3\times 3だけ手作業で埋める。別のアイディアがあるわけでもなかったので試しに提出してみたら通った。実装は自分。

次は全員でJと格闘していた。n=2,3,4が不可能なことは手で確認できて、そのままペンシルパズルを進めているとn=5,6,7,8が構成された。しかしそれらからは規則性が見つからない。このまま続けていてもキリがないと感じたので、小さいnを考えるのではなく一般に適用できるパターンを探し始めた。

すると、9\times 9マスにおいて左上からスタートして右下でゴールするような手順が見つかった。この手順はいくらでも延長できるので、nn=9+8kという形をしていれば対応できる。よってn\bmod 8で分類し、それぞれこれまでに見つけた盤面と組み合わせて作れないかを探ろうとした。

これはうまくいかなかったが、7\times 7でも同様の手順が構築され、n\bmod 6で分類したら見事全通り作ることができた。7\times 7の手順で最後に踏むマスを取り除くと6\times 6にできるというのがポイントだった。実装はかっつさんに任せ、ぷらさんはDに、自分はAに行った。

Aは最初に読んだときは直接木dpすることを考えていて解けなかったが、bitごとに考えればすぐわかった。つまり、例えばANDなら0\le i,j\lt 25に対してvibit目とjbit目が立っている頂点だけを使うパスを数え、2^{i+j}を掛けて答えに足すと求まる。ORはほぼ同様で、XORもi,jが固定されていれば22状態の木dpで求められる。

Jが通るのを待って書き、提出。しかしTLEした。どこが遅いのかわからない。パスを数えるのにUFを使っていて、もしかしてこのO(\alpha(N))が効いているのかと思いdfsに書き直すもまだTLE。いくつか定数倍高速化してもずっと通らない。最終的に、最初に頂点番号をdfs順に振り直し、以降のdfsはforループで処理できるようにしたら通った。

確かに自分の解法ではO(N)頂点のdfsを延べ975回行っているから、再帰呼び出しのオーバーヘッドも無視できない回数嵩んでいるようだ。確か手元のパスグラフだと1.6secから0.8secとほぼ倍速になったはず。それにしてもこういう定数倍高速化を問う問題は初めて見た気がする。

残り40分でDを考えていた。ランレングス圧縮した後のdpを多項式で表現すると、あるブロックを計算するときはその二つ前までのブロックに対応する多項式さえ分かればよいことになった。ここから、最初の2ブロックをfgとしてその先を多項式cdによってcf+dgという形で表現し、適切なタイミングで(f,g)を取り直すという方針が立った。ABC281-Exでも用いた方法。しかし実装は間に合わなかった。

Editorial - AtCoder Beginner Contest 281

感想戦。今日は全員で取り組んだ問題が多かったので、改めて話すことは少なかった。Aも自分がTLEに苦しんでいる間に全員問題概要とコードを把握していた。そういえばこれは他参加者のツイートを読んで気づいたことだが、頂点番号の振り直しはdfs順ではなくbfs順のほうが良かったらしい。木dpで子を舐めるときのアクセスがシーケンシャルになる。

問題の振り返りもそこそこに雑談に移行し、ゆるふわ競プロオンサイトの問題について話したりしていた。

https://www.hackerrank.com/yfkpo4

午前9時半に解散。それからしばらく格闘してDを通した。基本的には上で書いた方針だが、(f,g)を具体的に計算するのを止めた。

もっと具体的に書く。答えを求めるために、各ブロックに対応する多項式の総和を計算していた。これは当然(f,g)によって表現できないので、最近のブロックの値だけそのように表現しておいて(f,g)を取り直すタイミングで具体的な多項式を計算し足すということをしていた。このために(f,g)の具体的な値を知る必要があった。

しかし現在の(f,g)による表現が分かっていれば、(f,g)を取り直す際の変換行列を使って一つ前の(f,g)による表現が計算できる。この状態だと一つ前で答えに足したかった多項式とそのまま足し合わせられるので、同様にして最初まで遡っていくことで途中の(f,g)を計算することなく答えの多項式が求められる。これでTLEが取れた。

実のところ、答えとして計算した多項式のうち必要なのはx^kの係数のみなので、毎回直接計算すれば十分高速らしい。後から提出してみたら通ってしまった。

午後3時頃まで日記を書き、就寝。

02/26(日)

午後8時起床。AHC018が終了していた。結局金曜日以降は何一つ取り組まなかった。

KoP 4thのチュウニズム部門決勝まで終了していたので、ライブ配信を巻き戻して決勝戦と他いくつかを眺めていた。

www.youtube.com

午後8時半に布団から脱出し、食事して午後9時からABC291。

AtCoder Beginner Contest 291(Sponsored by TOYOTA SYSTEMS) - AtCoder

AはRubyで、正規表現によるマッチングがマッチした位置を返すことを用いて解いた。そのあと数分コードゴルフしたが全然縮まなかった。BCは特に言うことなし。Dはdp。

EはX\rightarrow Yという辺を張ったN頂点の有向グラフをトポロジカルソートすればよい。途中で使える頂点が2個以上同時にある場合ソート順が一意でなくなり答えはNo。そうでない場合、トポロジカルソートで得られた順列の逆順列がAとなる。コンテスト中はグラフにループがあるかも判定していたが、制約をよく読んだらそのようなケースはなかった。

Fは都市1からの最短距離と都市Nへの最短距離を前計算しておくと、kごとに都市kをまたぎ越す辺を全探索することで答えが求まる。そのような辺はO(M^2)本存在するが、今M\le 10なので十分少ない。

Gはシフトの回数を全部試すことができる。和にA_i|B_jが寄与するのはシフト回数が(i-j)\bmod N回の時なので、0\le a,b\le 31を固定してA_i=aとなるiB_j=bとなるjを集め畳み込むことで、シフトの回数に応じてa|bがどれだけ和に寄与するかを一気に計算できる。これは昨日話していたゆるふわ競プロオンサイトのE問題と一緒なので、かなりタイムリーだった。

そのまま実装しNが最大のケースで全然終わらないなあと言っていたが、当たり前。322回畳み込みするのが間に合うわけがない。冷静になると桁ごとに考えればよく、1桁につき(a,b)=(0,1),(1,0),(1,1)の3回畳み込む合計15回の解法を実装して1secで通した。後から(a,b)=(0,0)だけ計算して引くことで畳み込みを5回にできることに気づき、出してみたら500msを切った。

Gで少し手間取ったがここまでいいペースだな、と思って順位表を確認したら1ページ目が全完で埋まっていてひっくり返った。慌ててExを読むと重心分解せよと書かれており、検索して出てきたライブラリを写経したら通った。

1時間弱でノーペナ全完し38位。今日も動画を撮っていて、残り40分はかなりじっくりと各問題を振り返っていた。コンテストが終了してすぐに投稿。

www.youtube.com

コードゴルフはABCG。AをRubyで書く際、マッチした位置に1足して1-indexedにするのが面倒。入力を直接マッチングの左辺に持ってくると足す前に全体を括弧でくくる必要があるが、いったんgetsを実行してから~/[A-Z]/と書いて暗黙的に$_とマッチさせるとそのまま1足せるらしい。これで縮められた。

その後さらにVimで縮んでいた。大文字を探してそれ以降を削除した後wcコマンドに投げると、「改行文字込みの」文字数が取得できる。つまり見つけた大文字の前にある文字数に改行の分1増えた値が得られて、見事に1-indexedでの答えとなるようだ。

BはRakuが今のところ短いらしい。

Cは虚数単位iを「LRUD文字コードを15で割った余り」乗すると見事に複素平面での4方向に対応する値が得られたので、これを利用するRubyコードを書いた。しかし別のところで縮められ、さらにPerlでもっと短いコードが出て負け。

今のRubyの短縮ポイントは入力の2行目を得るのに[*$<][1]ではなく$<.maxが使えるというものだった。1行目は数値、2行目は英大文字なので、2行目のほうが辞書順で大きくなる。これは新手で、他にも2問ばかり縮んでいた。

Gは解説の定数倍の軽い方法をCPythonで実装したものが最短になっている。畳み込みした後添え字\bmod Nごとに値を集計していたが、長さNの巡回畳み込みができれば一発というのは目から鱗だった。ただNが2べきでないため、長さを変えずに高速フーリエ変換・逆変換するのは面倒。ライブラリに投げられる言語を使えば辛うじて、という感じだ。

午前8時まで日記を書いていた。AHCの自分の提出がシステスを終えており、確認すると2ケースでWAが出ていた。原因に心当たりがない。

布団に入り、寝る前にハーメルンの更新をチェックした。以下の作品に今日投稿されていた話がかなり長く、しかも非常に面白くて、じっくり読んでいたら寝るのが午前9時半になった。

syosetu.org