週記（2021/01/11-2021/01/17）

01/11(月)

先週の週記を投稿してから寝るまでの話。これ毎週書いてる気がするな。

実は、「前に1進む確率がpなら期待値は1/p」と「後ろ向きならx_i-x_to+1のコストで戻ってこれると考えてよい」でO(N)で計算できるらしい。

週記（2021/01/04-2021/01/10） - kotatsugameの日記

これに関して、じゅぴろさんのブログ・ソースコードを読んだり教えを乞うたりして一通りの理解が得られた。自分の考察とともに書き記しておこう。dp_iはiまで行くときの期待値、p_jはjが出る確率、また以下ではiがfixされていて、dはiからi+1に進むための出目とする。

まず、自分が考えていた、左辺と右辺に同じ文字を置かない計算方法について。iからi+1に進む確率がp_dのとき、その回数の期待値は1/p_dである。つまり、1/p_d-1回はどこか別の場所に戻ってから再度iまでたどり着いていることになって、 dp_{i+1}=dp_i+1+(\frac{1}{p_d}-1) \sum_{j\ne d} \frac{p_j}{1-p_d} (dp_i-dp_{戻る位置}+1)が得られる。

次に、じゅぴろさんから教えてもらったもの。戻ったところから直接i+1に行くための式を立てることにより、 dp_{i+1}=dp_i+p_d+\sum_{j\ne d} p_j(dp_{i+1}-dp_{戻る位置}+1)が得られる。

どちらも\sum p=1を用いて式変形すると同じ式になる。以下にじゅぴろさんのブログへのリンクを貼っておく。

jupiro.hatenablog.com

週記を公開したところ、`の使い方が気になるという言及があった。僕は僕の感覚で使っているので、厳密にソースコードに該当する箇所以外でも多用している。特に直すつもりはない。あと、普通の改行が存在せず常に段落分けしていることも気になるが、これは普通の改行を書くのが面倒（空白2個を入れる必要がある）だからである。

午後2時に就寝し、午後6時起床。目覚ましによるものである。昨日立てたIssueについて、良さそうというコメントと修正の方針をもらった。書いておいたコードもそういう修正をしていたので、プルリクを送る。

github.com

サークル解説会の準備が一切できていないので、する。ABC187のD-F問題の解説スライドを作成したところで午後8時になり、Google Meetを開いて参加者を待ったが、10分くらい誰も来なかったので終了した。せっかく作ったスライドは来週に回す。もしかしたら大学はすでに期末テスト・課題ラッシュなのかもしれない。いまだに中高生時代の感覚のままなのでそういうものは2月の終わりにあると感じてしまい、わからない。

ラノベを読んでいたら送ったプルリクがマージされた。

先週の週記を受けて、sugarknriさんから(a+sqrt(b))^nを求める問題を3問紹介されていたので、うち2問だけ解いた。Google Code Jamの問題はあまり解く気がないので無視した。

https://projecteuler.net/problem=721

https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/WUPC/3162

水曜日提出のレポートがあるがやる気が一切出ない。いやになって布団に転がる。次のようなツイートをしたりハーメルンを読んだりしていたら、午前2時のツイートを最後に寝てしまった。

01/12(火)

午前8時半起床。外を見ると雪が降っていてびっくり。

昼頃チュウニズムの大型アップデートの告知が来た。これまではPOPS&ANIMEのフォルダからしか曲が消えていなかったのに、今になって初めてVARIETYにジャンル分けされていたコナミ音ゲーからの移植曲が消え始めた。曲に興味はないが、未AJの譜面が消えるのはちょっと嫌な気もする。せっかくなので消える前にAJ称号を狙っておきたいが、それまでにゲーセンに行く機会はあるだろうか。

途中午後4時半から午後8時くらいにかけて意識を失っていたが、結局この日は午前1時までずっと布団の上でハーメルンを読んでいた。1作読み終わった。

syosetu.org

「古代スタート」というタグで検索したものから1つ。非常に面白かった。「主人公が世界で一番長生き」という設定だけでパスタが3皿くらいいける。主人公の男オリキャラに原作キャラが好意を寄せる描写は、二次創作でも読む人を選ぶのかもしれないなと感じた。東方Projectの原作に特に思い入れはないため、僕は積極的に受け入れることができた。

「古代スタート」タグのハーメルンは大体東方Projectの二次創作であるように見える。また別の作品をあさりそうになったが、強い意志で布団を這い出てレポートに着手しようとする。しかし食事をしたり淫夢実況を見たりしてしまい、提出期限の正午まで9時間くらいしかなくなった。

www.nicovideo.jp

たいぺー曰く、今回はそれほど難しくないとのこと。講義スライドは6回ぶんあったが、ざっと眺めて問題になっている場所だけ抜き出したところ、1つを除いて証明問題だった。先にそれを片付ける。

1つは定義式を見てもよくわからないし、講義の録画を聞いても「やるだけ」としか言われてなかったので、よくわからない式を書いてお茶を濁してしまった。しかし他の2問はすんなりできたので拍子抜け。

このあたりで午前5時になり、レポートも3題書けたことだしいったん寝ようかとも考えたが、このまま徹夜することにした。徹夜することにしたら一気に時間に余裕ができたため、ハーメルンを読みつつレポートの最後に残した1問に手を付ける。

離散フーリエ変換をΘ(N^2)とΘ(N log N)の2つのアルゴリズムで実行し、計算時間をグラフにして考察せよという問題。Θ(N log N)のほうはnumpy.fftで実装されている関数を用いる。Nは2べきだったので、多分Θ(N log N)だろうが、ドキュメントを読んでも明言はされていなさそうだった。よくわからない。

Θ(N^2)のほうも適当に実装したが、速いPythonの書き方を知らないので、効率は悪いのかもしれない。ただグラフにするとピッタリy=ax^2（aは適当な定数）と一致したのでかなりびっくりした。

午前11時過ぎに家を出て東北大学に向かう。たいぺーと一緒に提出して昼食を食べようと思っていたが、僕が大学に向かっている最中に起きたらしくてヤバそう。結局合流できたのは午前11時50分のことで、そこから急いで提出場所の研究室前まで行ってレポートを出した。セーフ。その後一緒に食事し、購買を冷やかし、図書館でハーメルンを読んだ。

午後1時過ぎに分かれて数学棟の資料室に行き、来年のゼミの希望を出すために教科書を眺める。最初は公理的集合論がよさそうだと考えていたが、整数論の教科書にメビウスの反転公式とかが書かれているのを発見して一気に興味を惹かれる。これを第一希望にすることにしよう。第三希望まで出す必要があるが、三つ目に悩む。正直どれも興味がないが、ホスフィンに2つおすすめされたので、そのうち1つを選ぶことにする。そんな適当な決め方をして、もしそれに振り分けられたらことだなと思った。

帰ってきて布団に倒れこみ、ハーメルンを読む。午後3時くらいに寝落ちした。

01/13(水)

午後10時に起きる。ハーメルンを読み続ける。かなり文章がカスでセリフのノリもキツく、さらに後書きでキャラクターと作者が掛け合いしたりしていて、ネット小説の悪いところを凝縮した感じになっている。しかし設定や展開は好みなのでそれを頼りに読んでいる。

150話くらいまで来て、ようやく半分。僕は小説を書いたりしたことがないので文章力と言ってしまうのはちょっと気が引けるが、ともかく文章が読みやすくなっていることは確か。キツいノリもほとんど見られなくなった。誤字・誤用は相変わらず多いままだが、このあたりまで来ると展開に集中できて、ストーリー上の大きな山場を乗り越える際主人公が弱体化してしまったことに心を痛める。

午前10時くらいになったので、シャワーを浴びて学食に向かう。そういえばそろそろ共通テストがあるので学食の営業時間が変更になっているかもしれない、と考え調べてみたところ、今日も変わらず営業しているどころか朝の8時から開いていたことを知って愕然とする。待つ必要はなかった。デザートとして薄い青もしくは緑色をしたクリームの小さなケーキを購入したが、これはチョコミントと呼ばれるものだったらしい。思っていたより歯磨き粉でびっくりしてしまった。

帰宅して面談。このとき↓にセッティングされたもの。

年明けに人事の方がまた面談をセッティングしてくださったので、そこで明らかになるだろう。

週記（2020/12/21-2020/12/27） - kotatsugameの日記

30分くらいで終了した。まず自分の院進学周りのことを聞かれたが、何も決めていないし何も調べていないので、うまく答えられない。次の夏のインターンに関しても、院試で参加できない可能性が無きにしもあらず……など不明瞭なことを言う（そのあと調べたら東北大学の院試に限っては特にかぶっていなさそうだった）。また、数学で院に進むのか、どういう専攻を考えているのかなど進路相談みたいな質問が続くが、どれも全く考えていないため何も言えない。

結局、イベント（アルバイト等）の情報や職種に関して継続的に人事の方とコミュニケーションをとっていきましょう……みたいな感じになった。それと、自分の進路に関していろいろ調べておいてくださいとも。競プロも頑張ってくださいと言われた。具体的なことは何も決まらなかったが、これ自体はまあ僕が将来のことを何も考えていないせいなのでどうしようもない。ひたすら主体性・当事者意識がなくて困る。

またハーメルンを読み、午後2時半くらいに寝落ち。

01/14(木)

午後10時起床。コンテストに参加できない感じの生活リズムでヤバい。

1時間ちょっとハーメルンを読んで、えでゅふぉ102に出る。5完。

ABは自明。Cは難しい。後ろ2(n-k)+1個の山はどういう順列を持ってきても転倒数が変化しないため、そこを上に凸の山ではなく下に凸の山にするのが辞書順で最も大きくなる。Dも自明。

Eがわからず、Fに行ってもわからず、再度Eに戻ってきて解いた。コスト2倍の辺を1回とコスト0倍の辺を1回通るときの最短経路を求めればよくて、例えば0倍にする辺を2倍にする辺より先に通るとすれば、多点スタートのdijkstraを3回やるとできる。逆も同様。コンテスト後のTLを見て気づいたが、これは拡張dijkstraとして見ることができた。

Fは最後の最後で燃やす埋めるに気づいたが、MLE。フローが悪いのではなくて、辺を減らすことができるのが本質だったらしい。かなり悔しい。

そのあともハーメルンを読み続け、午前4時半に1作読み終わった。約1,500,000文字を2日弱で一気読みした。ストーリーが非常に良かった。序盤の文章が壊滅的なのでおススメはしにくい。

syosetu.org

「古代スタート」タグに東方Project二次創作が多い（調べると247/264だった）ことについて、少し考えた。最近読んだ2作品について、まず最初に八意永琳や蓬莱山輝夜と出会い、次に洩矢諏訪子と八坂神奈子に出会うことが共通している。これは原作の設定（ピクシブ百科事典調べ）にあるイベントのうちこの2組に関するものが他を引き離すほど古い時代の出来事だからだろうが、このように非常に古い時代の話でも大まかな出来事がわかることが影響していると考えられる。ほかに、妖怪や神様など長命種がたくさん出てくることも関係していそう。

溜めていた日記を書く。久しぶりに記事中にtexで数式書くかと思ったら、_をエスケープしないとならない罠にハマってちょっと辛かった。ちなみにそれはこの記事の月曜日の箇所であるから、木曜日も終わりになってから4日ぶん一気に書いているということだ。こういう適当なことができるのも週ごとの更新の利点。

世間的には金曜日の朝である。午前9時くらいに寝ようとしたら、ちょうど「午前11時半から小テストをしますよ」という通知が来てキレながら起きる。今セメスターのはじめから課題を締め切りの当日に投稿していたことで有名な代数学概論Aである。さすがにちょっと勉強しないとヤバいので、ここ数回分の講義PDFに目を通しておく。最新まで追いついて、しばらくハーメルンを読んでいたら小テストの時間になった。

小テストの具体的な内容は書かない。どういう道具が存在するのか知らないが、何とか全列挙できるくらいのサイズの対称群の問題だったので、全部書いた。置換の表記法には上下に並べるものと巡回置換の積を書くものの2種類あることが知られているが、特に巡回置換のほうはどういう記法なのかよく覚えていなかったので、ひたすら上下に並べるやつを書きまくった。置換の積の計算方法に関してもあんまり自信がない。どちらが先に来るのかとか、何を見て入れ替えるのかとか。これらはすべて自分の演習不足に帰着されるが、演習する気がないのでこのままだと一生扱えないんだろうなという気分になった。

小テストが終わって正午、布団に入ってすこしハーメルンを読み、就寝。午後1時半であった。

01/15(金)

午後9時起床。yukicoderに出る。全完。

A問題はtrコマンドが最も良い。FAかつ最短コード。B問題はa op b=ab+a+b=(a+1)(b+1)-1をよく見ると交換法則・結合法則が成り立つことがわかる。よって操作の順番によらず最終的な値は一定。まれによく見る。

C問題はギャグ。1円ずつ動かせることがわかる。D問題はやるだけ。E問題は難しかったのでいったん飛ばし、F問題に行った。F問題は行列累乗。何も考えずに書いてしまったが、andとorが普通の積と和のような性質を満たすことについて一切注意を払っていなかった。見たことある気がしたのでスキップしたが、見たことがあったのはandとxorである。

Gは難しい。よく見ると最小費用流で解ける。普通に辺を張るとO(N^2)本必要になるが、頂点を4倍くらいにするとO(N)辺で再現できる。この辺りもなかなか面倒で、(A,C)をペアにした状態でAでソートして隣接する頂点に辺を張り、Cでソートして隣接する頂点に辺を張るなどインデックスがややこしい。自前のライブラリでは通らなかったが、ACLだと通った。速すぎる。

Eに戻る。Wikipediaなどを見る限り10^n-1がNで割り切れるような最小のnを求めればよさそうで、これはオイラーのφ関数の約数を全探索すれば求まる。最初カーマイケル関数を実装したが答えが合わず、一度消して書き直したのだが、実は素因数分解の途中で値が変わった変数をずっと使っていたのが悪くて、カーマイケル関数の実装には問題がなかったようだ。

All ACも含めて一面が濃い緑で埋まったので、再度ツイート。毎日虚無を10ACくらいするのが日課になっていて、意識的に止めない限りずっと続いてしまうだろう。Streakとかも同じ要領で、ちょっとした努力による継続が必要なものは一度軌道に乗ると今度は止めにくくて仕方がない。日記はコストが高いのですぐに溜めてしまうが。

試験管の黄色diffが10問ちょっと残っているので、埋める。最初に埋めようとした問題で必要になったので、良い機会であるとBaby-Step Giant-Stepのライブラリを作ろうとする。うしさんのライブラリを参考にしようと思ったら、思っていた実装よりだいぶ面倒そう。これは合成数modにも対応しているらしい。読めなかったのでTLに投げたらsugarknriさんに教えてもらえた。感謝します。

x^k \equiv y \pmod Mを満たすようなkを求めたい。まずm=\lfloor \log_2(M) \rfloorまで全探索する。xとMに共通の素因数がある場合、k>=mについてx^kは十分大きいため、Mとの共通の素因数は全部出そろっている。つまり、\gcd(x^{k+1},M)=\gcd(x^k,M)がこの先ずっと続くということだ。この段階でg=\gcd(x^m,M)を求め、割っておく。x^mは適宜mod Mしながら計算してもよいことが、互除法を考えるとわかる。

この段階でyがgの倍数でなかった場合、kは存在しないため終了。倍数だった場合はこれもgで割る。以降は\frac{x^m}{g}\times x^k=\frac{y}{g} \pmod{\frac{M}{g}}を求めればよく、ようやく普通のBSGSみたいな見た目になった。ここで逆元を求めるのに拡張ユークリッドの互除法を使ってもよいが、それより\frac{x^m}{g}\times x^{at}=\frac{y}{g}\times x^b \pmod{\frac{M}{g}}としてm+at-bを答えるようにすれば、逆元の計算が必要なくなる。かなり頭がいい。

自分のライブラリのリポジトリにプッシュして、oj-verifyが回り始めたが、すぐ落ちてしまった。エラーメッセージを見ると存在しないCargo.tomlを探して死んでいる。otherlangというフォルダを調べているようだったので、かなり嫌な予感がしたが、的中。otherlangというフォルダに入っていたverifyするつもりのないRustのコード片を解析しようとして落ちていた。対処法として別のリポジトリに移したところ、ちゃんとテストが回った。

そのあと朝までやって試験管黄色diffを7問くらい解いた。昔見たときは苦労した覚えがあったのに、今見るとバッサバッサと倒せて非常に爽快。

寝ようとしたらTechFULからメールが来た。年始のコンテストの商品は、上位者から順番に好きなものを取っていく方法で割り振られるため、自分がこのまま無視して寝ると僕より後の人に迷惑がかかる。残っている商品は6つ、商品名を見てもよくわからないので布団から出てそれぞれ調べ、結局マウスを選択した。トラックボールのマウスらしい。6つの商品の中では群を抜いて興味を惹かれた。

メールを返信して就寝。午後0時半であった。

01/16(土)

午後3時くらいに目覚ましでいったん起きて、生協の弁当の配達を待つ。午後3時半くらいに届いたのに何とか気づき、受け取りに成功。そのあとすぐ寝なおして、午後8時に起きた。今日はARC。

ABCEの4完だった。Dに見切りをつけるのが速かったので大失敗は避けられて、パフォーマンス2549、レートは2704→2690(-14)。

Aは難しいが冷静になると解ける。Bも解ける。Cはそこそこびっくりしたがシュッと解けた。移動するときに、通らなかったマスが左か上にあるから、そこを考慮して係数に掛ける。文字が書き込まれていないマスを毎回数えていると到底間に合わないので、累積の配列を持って更新しつつ遷移していく。解説の2/3を掛ける方法は天才みがある。言われてみれば……といった感じ。

Dは難しい。結局解けなかった。録画を確認したところ、15分考えて何もわからなかった時点でEに移っていた。偉い。Eはすぬけ君の操作を遅延させることで区間DPができて、区間を広げていこうとすると初期位置に応じてN+1回計算する必要があるが、区間を狭めていくことで一気に計算できるようになってAC。

Dに戻り、プログラムを書いてN==3の場合を構築した。この時点で0の位置を固定してしまったが、これをすると解法にたどり着く道筋が限られてしまうようだ。具体的には、popcountでなんやかんやする解説の方法。popcountがどういう文脈で出てくるのかいまだにわからないが、うまくいく理由は理解している。つまり人iとjが同じグループになる回数がiとjによらないことを示せばよくて、これはparityを取ることから二項係数の半分の和が出てきて、結局全体の半分くらいになる。

コンテスト終盤は、N==3の場合の解を直接検索欄に打ち込んで検索し、出てきた結果を眺めていた。Symmetric BIBDという単語が出てきて、これは問題で問われていることの一般化となっている。画像検索のほうをいくつか見てみたらアダマール行列に触れているものがあったので、もしかしたら検索で辿り着けた可能性もある。

ところで、現在のD問題の最短コードはアダマール行列を利用した解法になっている。

atcoder.jp

hadamard(N)でNxNのアダマール行列を生成している。言語機能で殴っている感じでかなり面白い。

C言語で埋める作業をし、200ACくらいした。これで1000ACの言語は10個。

埋めている最中にARCのA問題が縮んだ。

atcoder.jp

ずっとコードゴルフをしていた。今はARCを古いものから順に見ている。

週記（2020/08/31-2020/09/06） - kotatsugameの日記

実はこの後すぐコードゴルフから微妙に離れてしまい、結局ARCは全然見ていない。もちろん言語アップデート後に1周はしたが、そこから数か月で得られたテクニックについてはまだ確認していない。今回の更新もそれなので、そろそろちゃんと見ておかないといけないなという気分。

昼になって、今から寝るのもな～という気分になっていたら、yukicoderでコンテストがあるのに気付いたので、出る。6完。

Aは解法が降ってきた。Bは難しいが、シュッと思いつけてハッピー。こういうのハマる人はめちゃくちゃハマると思うんだけど。Cは全然わからないので1e8個くらい調べたら通ってしまった。嘘解法だと思っていたが、これが正当な解法らしい。理論保証もある、どころかTLで見たことのある話だった。

https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

Dは普通のDP。Eはかなり面倒な実装。Fは似たような問題をちょっと前のyukicoderで見たことあるなと思ったが、そちらはNORだった。こっちのAND/ORだと後ろから貪欲に決まってびっくり。Gにチャレンジしたが全然合わなくてあきらめた。これがFPSになるのかなりびっくり。また、階差をとるとOEISにあったらしい。それでもオーダーを落とす作業が入るらしいが。

午後6時くらいになって寝ようかな～としていたところ、TROCがあることに気づく。午後10時から。せっかくの赤チャンスだしできれば出たいなと思い、とりあえず目覚ましを午後9時半にセットして就寝。

01/17(日)

午後9時半起床に成功。TROC18に出場し、全完7位でレートは2439→2528(+89)。このコンテストサイトは2500から赤なので、達成。

後半の微妙な難易度の問題はそこそこ面白いが、前半のギャグad-hocがかなり嫌らしい。full-feedbackなのは非常に素晴らしい。

Aはやるだけ。Bは4x4が埋められて、埋めてよさそう。Cは全然わからないのでプログラムを書いて全探索したところ、ソートして2番目を末尾にもっていけばいいらしい。意味不明。

Dは非常に難しい。答えは3または4になる。最初はNが平方数のとき3を出力してWA。正三角形を4つに分割することを考えると、N==kで3ならばN==k+3でも3。N==1とN==6は見つかって、N=2 mod 3が見つからなかったので出すとWA。もうちょっと考えると、16枚のタイルで作る正三角形のうち9枚分のタイルを1つにまとめることで、N==8が達成できる。よってNが2または3または5なら答えは4、それ以外は3。

Eはサンプルがサイレント修正されて最悪だった。まず普通に書いてセグフォ、原因を調べると謎の数列が入力されているので、これは最初Cの初期値も入力で与えようとしてたな？と思ってそのようにプログラムを書き直す。今度はサンプルが合わなくなったので、ふと気づいてページを更新したら入力から数列が削除されていた。プログラムをもとの状態に書き直して、さらにいくつかデバッグをして提出。

Fは最近のARCで見たことがあるなと思ったが、どうも合わない。答えが0かどうかの判定をデバッグするためにARCに提出しに行ったりした。もうちょっとしっかり考察すると、結構自由度があることが分かって、謎のDPを頑張ってAC。

Gも最初は全然わからなかったが、上のbitから決めていくとかなり自由にできることがわかる。自由にできない場合は次のbitを見ればよくて、これは高々log A回。残り8分でACして一安心。

月曜日の午前8時50分が期限のレポートがある。今から再度寝ると起きられない可能性があるので、今のうちに出しておこうとして解いた。さらに勢いづいて4年次ゼミの希望も出す。月曜日提出のレポートはほかにもう1つあって、せっかくだしそれもどんなものか見てやるか、と思ったら全然わからなくて途方に暮れてしまう。

あきらめて布団に入り、ハーメルンを読んで就寝。午前3時半だった。