週記（2021/11/15-2021/11/21）

11/15(月)

先週の週記を投稿してからはすぐに布団に入った。30分ほどなろうを読んでから、午前4時就寝。

午前10時起床。微妙な眠さで二度寝ができそうだが、勉強会の準備にどれくらいかかるかわからないので、起きておきたい。しばらく布団でモゾモゾしてから起き上がり、学食に行った。

帰りに購買で予約していたラノベを5冊受け取った。これも先月末にまとめて予約したものの一部だ。正直もうどれを予約して、どれを受け取って、どれが未発売なのか自分でも把握していない。予約すると受付メールがバラバラに届いてしまうのでちょっと不便である一方、特に気にしなくても予約商品の入荷メールで新刊発売を知れるのは便利だった。そろそろ以前予約した分は打ち止めだろうから、また11月下旬～12月発売のラノベを予約しておこう。

以前から生協では一気に10冊以上購入したりと特徴的な行動をしていたが、冊数よりは頻度が重要だったのか、今日ついに声をかけられた。「何日くらいで読まれるんですか？」……実はほとんど読んでいないのだ。ただまあ、そういうことを事細かに説明するとオタク早口になってしまいがちなので、ただあいまいに「すべて読み切ることは考えていない」というような返事をした。今日買ったラノベは転生ものとハーレムものばかりだったので、微妙な恥ずかしさがあった。

帰宅して勉強会のスライド作成を開始。題材は「競プロでシェルスクリプトを使う」というものだ。この題材の発想自体は一か月ほど前からあったが、決め手になったのは、最近行われたマラソンコンテストで複数のケースを手元実行するのが難しかったという話をTLで見聞きしたからだった。というわけで、シェルの操作をほぼ知らず、サンプルをコピペして貼り付ける方法しか使えないくらいの競プロerを想定してスライドを作成することにした（というかそれ以上の人間に対して発表できるほどの自信がない）が、よく考えると勉強会の聴衆は普通に職業プログラマなので、釈迦に説法。

リダイレクト回りの話を念入りに書いて一段落ついたと思ったが、やはり内容として初歩的なものが多い。あまりに丁寧に書きすぎて内容が希釈されてしまっている感じもする。残りの部分は競プロで使えるシェルスクリプトの実例を取り上げて解説を加えるつもりだったが、もうちょっとテンポよく進められるよう、細かいことまでは書かないことにした。罠にも触れない。厳密でない表現を自分だけが気にしていても、知っている人は勝手に補完してくれるだろうし、知らない人には混乱させなくてむしろ良いだろう。シェルスクリプトの実例については、自分の引き出しがないので、online-judge-toolsのサブコマンドのhelpで表示されるものをいくつか拾ってきた。

定例会直前に勉強会のスライドが完成した。進捗報告のスライドを超特急で生やして臨む。進捗報告では、もうちょっと現実に即したことを、というような意味合いの指摘をされた。行っている学習は結果をビジュアライズしてもあまり出来が良くないため、Lossの値だけ出して比較することをずっと続けていたが、進捗報告としてはあまり良くなかったらしい。何かビジュアライズの結果を見せるか、見せられないような絵にしかならないなら、いっそ進捗なしと言い切ったほうがわかりやすいのかもしれない。

その後、勉強会。ただでさえ定例会で話す内容が多かったため普段より遅めのスタートだったが、さらに自分の話す分量も多く、おそらく終始オタク早口だったろうに1時間以上かかってしまった。逐一丁寧に説明するような時間はなかったのでかなり飛ばし気味だったが、それで希釈された内容も少し元に戻ったかもしれない。ともかく、お付き合いいただいた皆さんには感謝しかない。内容に関するコメントで、知っていることばかりだろうと思っていたが思いがけず新しい知識を得られた、というものがあり、かなりありがたかった。

上でも述べたが、スライドは競プロer向けに作成したものだった。競プロで使うだろう入出力回りを丹念に説明している。というわけで、使用したスライドはその後、いろんな競プロerに見てもらえるようTwitterで公開した。ここにもリンクを貼っておこう。

勉強会1115.pdf - Google ドライブ

スライドの題名は題材そのまま「競プロでシェルスクリプトを使う」となったが、これを見て、シェルスクリプトで競プロの問題を解くのだと思った人が何名かいた。それでもよかったかもしれない。しかし結構泥臭い作業が必要だった気がするな、と思って、例えば文字列の末尾1文字取得をbashの変数展開でやるのは大変というツイートをしたら、よりシンプルなやり方を教えてもらえた。変数$aを使うとして、これまでは「文字列長を取得してそれ-1以降のsubstringを取る」という意味で${a:${#a}-1}を使っていた。二重に変数展開をしているのでシンタックスハイライトがかなり醜くなった記憶がある。ところがこれは${a: -1}でできる。自分で試してダメだったような、と思ってよく見ると、途中に空白がある。実はこの空白がない場合、別の変数展開の機能である代入なしデフォルト値と解釈されてしまっていたようだ。

少しインターンを進める。引き継いだコードをそのまま使っている箇所があるが、その部分の理解が浅いことを自覚したので、ライブラリについていろいろググっていた。期待していた機能がちゃんと存在したので、やりたいことは問題なくできそうでよかった。

その途中で気づいた事実をコードに反映してみて、ちょっと学習を回しつつ午前0時過ぎ就寝。

11/16(火)

午前7時半に目を覚まし、しばらくなろうを読んでいたようだ。午前10時過ぎにまたて、次に午後2時半に起床。昨日回していた学習の結果は、Lossの値こそよくないものの値の分布的にはかなり求めている状態に近いように見える。昨日の改善を採るか採らないか、ちょっと迷ってしまう。

午後3時からミーティング。これはヒアリング準備ということで、普段の定例会とも1on1とも違ったものだったから、ちょっとばかり緊張していた。自分が準備不足であるような気もしていたが、そもそも何を準備したものかわからないので、ほぼ無手で挑んだ。結果はまあよかったのではないだろうか。メンターさんともう一人が話しているのを聞く時間が多かったが、大まかな方向性は掴めたと思う。そもそも今日はその「大まかな」部分を決めるミーティングだったので、前提としての説明だったりあいまいな話だったりが多く、準備がなくとも何とかなったという面がある。別部署へのヒアリングを始める前に、しばらく相手方の業務を自分でもやってみるのがよいのではないかという話になって、実は結構楽しみ。

このミーティングは1時間で終了し、直後にいつもの1on1。先ほどの話を踏まえての、今後の動きのようなものを確認した。あとは関係ない話として、先ほどのミーティングではカメラをオンにしていたが、背景ぼかし機能がすごいですねということを言った。これも機械学習の結果だろうが、動画を処理できるほどのスピードというのは凄まじい。

午後6時前に家を出て、途中油そばを食べ、ゲーセンに行った。まず先週土曜日の続きとしてLv.13+をちゃんとAJ埋めした後、Lv.14に進んだ。こちらもできる限りAJ埋めするつもりだったが、曲数が多いのもあってこの日は中途半端なところで終わった。

閉店までプレイした後マックに寄ってポテトとコーラを注文。午前0時閉店とのことなのでちょっと焦っていたが、食べ終わってみるとまだ結構時間があった。帰宅してシャワーを浴び、しばらくチュウニズムネットを眺めてから布団に入る。なろうを読もうとしたが即座に寝落ちした。午前1時半だった。

11/17(水)

午前8時起床。少しなろうを読んでから起きる。今日は午前中からゲーセンに行くつもりだ。

と、その前にTCB42が開始していたので、解いた。ここ最近1時間ちょっとで全完できているので舐めてかかったら、ひどい目に遭い、合計で5時間くらいかかってしまった。午前中からゲーセンに行くどころか学食の昼の部にすら間に合わなかった。例のごとくこの日記が公開される頃には終了しているコンテストなので、各問題の感想を書いておこう。

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

1問目はともかく2問目からもう面倒だが、5問目までは問題なかった。まず6問目で1ペナ出した。誰も0を宣言していない状況下で0が出て全員0点、というケースはカバーしていたが、それ以外のところで0の処理を間違えていた箇所があった。この問題で0が登場するのは、単純に問題を面倒にしたかったんだろうとしか思えない。くだらん。7問目もよい。8問目は変数をミスって1ペナ。これは僕が悪いが、サンプルで落ちてくれなかったのが悲しいミスだった。9問目はよくある迷路探索、と思ったがMLEに悩まされた。MLE？と疑いながら高速化を繰り返していたが、ある時BFSでキューに入れる条件を間違えていることに気づいた。距離が同じになる場合もキューに入れてしまっていたのだ。結局この問題では3ペナも重ねてしまった。

10問目。面白いことは面白かったが、できれば解きたくなかった。問題文が難解だが、結局区間ごとにそこにある確率を求めて、あとは選んだ地点から離れるよう区間の端に寄せたときを考えればよい。制約から区間を処理するのはグラフを作ってBFSなり行えばできて、選ぶ地点としては、差の絶対値の和を考えれば区間の中央だけが候補になる。あとは累積和など使えば解ける！と思って提出すると、1ケースだけWAだった。考察ミスや実装ミスを探して、コードを単純化したり処理を変えたりしてみるも、このケースのWAは取れない。

1時間くらい考えていると、区間の幅がちょうど1のとき、期待値の計算を間違えていることに気づいた。通常\int_x^{x+1}|y-t|dy=\left|x+\frac 1 2-t\right|であるが、x\lt y\lt x+1のとき壊れる。そこで、ちゃんと期待値を計算するようにして投げなおすも、やはりWA。さらに30分かけてよくよく計算すると、この場合区間の中央が最適になるとは限らないことが分かった。立式すると二次関数になって、平方完成して最小値を求めるコードを出すもまだWA。立式に間違いがあって、二次関数の二次の係数にその区間に対応する確率（の分子）が出現するようだった。これまで出力する答えの分母は常に2だったので、なぜ\bmod{10^9+7}で答えさせるのか理解していなかったが、ここにきてP\lt 10^9+7の制約とともに理解した。この限られた場合だけ分母が一般の整数になってしまうのだ。コードを修正しているとオーバーフローが避けられなさそうだったので、有理数を使いたいことでもあるし、Rubyで書き直すことにした。さらに30分くらいでコーディングし、dfsの再帰が深くなりすぎて1ペナ出しつつ、ついにAC。3時間と10ペナかかってしまい、得られたスコアは最初に9/10通った時のものと全く同じだった。

午後3時からゲーセン。昨日イベントマップを（最後のスタチュウを残して）走り切ったので、今はNEW ep.Iを進めている。それで解禁した新曲を埋めつつ、Lv.14の残りを触っていた。Lv.13+で苦労させられた「XL TECHNO -More Dance Remix-」の紫譜面がLv.14にあって、それは譜面があまりに嫌らしいのでSSを出して放置したが、それ以外は鳥で埋めて、さらにAJを出せそうなものも軒並み出したと思う。

夜になったので夕食を探して歩き回った。何か定食が食べたい気持ちだったので記憶を頼りに定食屋を探したが、なく、そうこうしているうちにラーメンが食べたくなってきたので、結局つけ麺屋に入った。食後の腹ごなしに本屋に行って本を3冊買い、またゲーセンに戻る。いよいよLv.14+を触り始める。

とりあえず全部触ったので、銀ポゼが復活した。また、試しに「XL TECHNO -More Dance Remix-」を選曲してみたら、急に覚醒してAJが出てしまった。4回しかプレイしていないはず。多分もう二度と出ない。それにしても、縦連が何連打なのか数えたりしていないのだが、ずっと交互で叩いているだけで本当に全部通せるのだな。事実としては面白いが、譜面になると非常に嫌らしい。

今日も閉店までいて、日付が変わるしばらく前に帰宅。OPを確認すると98%台後半まで伸びていて安心した。

OVER POWERもプロフィールから確認できるようだ。思ったより低くてびっくりしたが、まだ新曲を埋めきっていないので、当然といえば当然だった。……よく考えたら、そもそもMASTERを解禁していないので、OPにも含まれていないのだろうか？そうだとしたら、自分のOPがもともと低かったということで、かなりショックだが。

週記（2021/11/08-2021/11/14） - kotatsugameの日記

しばらく椅子に座ってぼんやりしていたが、火曜日の講義にコメントをつけるという課題が水曜日で締め切りだったので、焦って出した。数分間に合っていないが、正直コメントだけなのでどうでもいいとは思っている。

ABC227の学生4位だったらしく、キーエンスからアマギフ1万円に関するメールが来ていた。5位か6位だろうと思っていたが、よくわからない。賞金メールといえば、ゲーセンにいる間にTCB41のメールが迷惑メールに入っているのを見つけてびっくりした。こちらは返信期限が11/12だったので、もう手遅れ。まあ1000円だし、いいかな……。

午後9時からABC227。 KEYENCE Programming Contest 2021 (AtCoder Beginner Contest 227) - AtCoder 全完10位。学生順位は5位か、6位か。よくわからない人が一人いて怪しい。

週記（2021/11/08-2021/11/14） - kotatsugameの日記

yukicoderで1問問題が公開されていたので解いた。手を付けるのが遅く、考え始めた時にはすでに「ZobristHash」というタグが見えていたので、解法は一瞬。このハッシュ方法の存在自体は知っていたが、使ったのは初めてだった。

No.1746 Sqrt Integer Segments - yukicoder

午前2時半就寝。

11/18(木)

午前10時前起床。うっかりハーメルンを読み返し始めてしまった。

午前11時半くらいに切り上げて学食に向かい、帰ってきてゼミに備える。今日は夕方から別のセミナーがあるとかで、ゼミが普段より30分前倒しになっていた。しかし午後0時半になっても始まらない。LINEでの会話を見るに、先生にメールを送っても返事がないようだ。午後0時45分になって、普段の定期ミーティングのZoomに入ることができた。しかしこれは普段通りの設定で、先生はいまだ音沙汰なし。しばらく4年生の進路についての話をしていたら、午後1時ちょっと前にようやく先生がZoomに入ってこられた。前倒しにしたことをすっかり忘れておられたらしい。ほぼ通常通りの時間から始まった。

発表を聞きつつメールを確認していたら、pixivのほうでメッセージが来ているのを見つけた。以前書いたpixiv小説がイベントの抽選に当たり、アマギフ1000円がもらえるらしい。そのような商品があることを知ってはいたのだが、まさか当選するとは。イベントの情報を見るに、本当に抽選しているだけなので、ただただ運がよかった。

またこのツイートが最後の一押しとなって、小説のPVが1000を突破した。しばらくPV数を確認していなかったが、じわじわ伸びてはいたようだ。

ゼミは何事もなく終了。僕も先週の残りの分を発表したが、スライドを作成した時の記憶が薄れていて、流れを把握できずちょっと大変だった。事前に見直しくらいしておくべきだった。今週の発表者の時間を圧迫してしまった結果、その人もまた週をまたいで次回発表することになった。

先週の対面ゼミがかなり良かったということで、今先生が教室を確保しようとしていて、成功すれば今後ずっと対面でゼミが行われるようになるらしい。移動が面倒なことだけが辛い。最後に、先週対面で集まって撮影したゼミの集合写真が共有された。写真屋に送って、卒業アルバムにも載せてもらうことになる。

ゼミが終わった後は布団に倒れこみ、朝の続きでハーメルンの読み返しを続けていた。「アイドルの世界に転生したようです。」の外伝の部分。おすすめのなろう小説まとめでも触れた。ここはオリ主たちがライブをやる完全オリジナルの章で、逆にそれ以外の章は、ちゃんと二次創作らしく元となった公式ストーリーがあるらしい（が、自分はアイマス関連に無知なのでよくわからない）。それが理由か、普段ライブのシーンはあまり描かれないのだが、そのぶんここで念入りに描かれていて満足感があった。何度読んでも面白い。

これ本当に好き。外伝『Days of Glory!!』はまるまるライブをやるんですけど、マジで面白い。それまでの数百話を振り返り、泣きながら読んだ。

おすすめのなろう小説まとめ - kotatsugameの日記

syosetu.org

「天才最弱魔物使いは帰還したい」の更新が来ていた。作者ツイッターを見ると、どうやら2巻の発売が決定していたらしい。しかも12月のはじめとかなり近い。多分この巻で前作「Tamer's Mythology」の終わりまでが描かれるだろう。そちらをちょっと読み返していたが、やはり唐突に終わったように感じられて消化不良という思いがあるので、ぜひぜひ3巻も出てほしい。いくらでも待つ。

先週日曜日のyukicoderのコンテストのupsolveをした。有向辺を張って強連結成分分解するというアイディアだけを知ったまま臨み、2問とも解けたが、方法は少しDM分解と異なった。一つ固定した最大マッチングに含まれる辺は、両方向に張るのではなく、含まれない辺と逆方向に張ることにする。解説にある一番上の資料に従えば、含まれる辺は任務からスパイに、含まれない辺はスパイから任務に張る。このもとである辺を含む閉路、あるいはマッチングに含まれない頂点からの到達可能性を知りたい。

特に後者も、適切に辺を追加すると強連結成分分解で解ける。具体的には、任務側ではマッチングに含まれる頂点から含まれない頂点へ、スパイ側ではその逆に、すべての組に辺を張ればよかった。これで「任務側でマッチングに含まれない頂点から含まれる頂点へ」「スパイ側でマッチングに含まれる頂点から含まれない頂点へ」の到達可能性がどちらも、今追加した辺を使った閉路の存在判定で解ける。辺を張るのは超頂点を追加すればよい。解いた後に解説を参考に調べて、DM分解も何となくの理解はしたつもりである。

Y.Y. さんの単発問題コンテスト 2 - yukicoder

AHC007の開催が発表された。株式会社THIRDがスポンサーにつく。これまで具体的な名前は出さなかったが、これを機会に明言しておこう。ここが僕が今インターンをしている会社だ。そういえば、火曜日のミーティングの時に自分でも業務を体験することになって楽しみということを書いたが、これには理由がある。以下のページに「お客様の現場に突入し、お客様と同じ仕事を経験し、現場に落ちている改善の変数を見つけ、管理ロイドに組み込む事を得意とする」という文言があって、そういうのが一番「開発」っぽいなと感じ、初めて目にした時から気に入っていたのだ。

チームメンバー – 株式会社THIRD

日付が変わったあたりからは溜めていた日記を書いていたが、眠くなったので途中で切り上げて布団に入った。試しになろうを開いてもほぼ読み進められず、午前3時就寝。

11/19(金)

午前11時前に目を覚ましたら、昼過ぎから予定されていたミーティングが来週火曜日に変更になっていた。CLISTを見てコンテストの予定がないことを確認し、メッセージに了解の返事をしておく。その後予定表を確認していたら祝日だということを知り、びっくりした。まあ問題ない。

その後二度寝しようとしたが失敗。昼過ぎになって起きだし、学食で昼食を摂ってからゲーセンに行くことにした。すでに全曲触ったのでやることもないかと思えたが、旧Lv.13の上位勢が軒並みLv.14+となったので、残っているLv.14を埋めればAJフィルまで付けられるのではないだろうかと考え、今日はAJが出せそうなものを出し、同時に未SSS+も減らしていた。

成果としてはLv.14の新規AJが新曲含め+9。未SSS+も残り4つになり、さらにLv.14+もいくつか伸びて、かなり満足のいく日になった。またFREEDOM DiVE↓が無理せず押せたり、Blackmagik Blazingの最後の高速トリルがガチ押しで追いついたりと、成長を感じる場面も多かった。最近上手い人の横からの手元動画を見たので、それっぽい脱力を意識してみたが、効果があったのだろうか。

途中食事のためガストに行ったが、ラーメン屋に慣らされた自分の金銭感覚ではやたら高く思えた。不用意に入るのは憚られる。これもあって閉店前に手持ちの現金が底を尽き、帰宅した。そういえば今日は部分月食だったらしい。ガストに行った前後に見る機会もあっただろうに、完全に失念していた。

今日のyukicoderのコンテストを少しだけupsolveした。ACDは自明、Bは実験。Eで詰まったので切り上げた。

yukicoder contest 323 - yukicoder

昨日の日記を書き進め、少しコードゴルフをして就寝。午前2時半だった。

11/20(土)

午後0時半起床。学食に行こうと思ったが、午後1時からyukicoderでコンテストがあるので止めにして、パックご飯を温めつつインスタント味噌汁を用意した。しかし食べる前にコンテストが始まってしまった。

yukicoder contest 324 - yukicoder

すさまじい難しさで、ABを何とか通した後CとDを読んで心を折られた。5時間コンテストだったが、実質1時間半くらいしか参加しなかった。実はCまでは客寄せ用問題のつもりだったらしく、完全についていけない。AはbitDPに見えるが、2行持つ必要があって実装が爆発。書いているうちに実はパターンは少ないのでは？となり、試しに最初少し決め打った後埋めてみると、4x4をいくつか横に並べたもののみ、それぞれに2通りの敷き詰め方があることに気づいた。これをもとにdpを書いてAC。

Bは最初頑張って立式しようとしたが合わず、文字の種類数を絞っての実験に切り替えた。立式の段階でNの偶奇が関係することはわかっていたので、それで分けて眺める。Nが奇数の場合はすぐ法則性がつかめたが、偶数の場合は全然わからなかった。文字の種類数2の場合はOEISにあったが、そこから演繹できない。種類数3は、そのままでは見つからないのだが、全体をN=2の場合の答えで割ったものが見つかった。一般項に3が何か所か表れていたのでそれっぽく書き換え式を整理すると、種類数2の場合の式と一致したので、これが正解であることを確信。出すとACだった。

上のツイートの最後の一文は結構過激な言葉を使っているが、コピペのパロディという文脈があって言いやすくなっている、という解釈を見た。確かに、文脈を知っている側からすれば強い言葉というよりはネタに走っているような印象を受け、一方これまでその言葉を使ってこなかったことから一線を越えた怒りが表現されているとも捉えられる。

ハーメルンを1作読んだ。設定がかなり良かったのだが、9話でエタっている。

syosetu.org

夕方は日記を書き進めていた。午後9時からABC228。

TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228) - AtCoder

なんとか全完して19位。学生順位なら10位に入っていたりしないだろうか。

Aから面倒。AWKで場合分けを連ねた。Bは適当にやる。Cは境界の周辺が微妙に怖い気がしたが、別に怖くなかった。Dは-1の区間を管理することも考えたが、-1のindexを全部setに入れても間に合う制約なのでそちらで解いた。

Eは答えがM^{K^N}であることがあまりに明らかすぎて、何を問うているのかしばらくわからなかった。これを\bmod{p=998244353}で答えればよいことを確認して、慌ててdcで出すと、WA。dcが微妙に信用できなくなったのでとりあえずC++で書き直すも、さすがにこれで答えは変わらないよな……となってもうちょっと考えた。フェルマーの小定理を使おうとしているが、a^{p-1}\equiv 1\bmod{p}はa\equiv 0\bmod{p}のとき成り立たなかったことに気づく。今制約はM\ge 1に見えるが、上限をよく見るとM=pなどがありうるようだ。さらにK^N\equiv 0\bmod{p-1}となったとき、M^0を計算してしまって困るらしい。K^N\gt 0であることが分かっているので、このような場合は答えを0としてしまってよさそう。これで出すとACして、さらにdcでも、計算した指数にp-1を足すことで正しく計算できることに気づき、通しておいた。

Fは二次元累積和をしたあと二次元区間minがしたい。二次元セグ木を貼ることも考えたが、定数倍がちょっと怖いので、スライド最小値2回で書くことにした。参照する配列を間違えていてしばらくサンプルが合わなかったりとコーディングはちょっと苦労したが、通る。

Gは非常に難しく、また面白かった。パッと見普通のdpかと思ったが、重複をどう省くかが問題のようだ。同じ数字を生成する移動たちが今いるマスの集合を管理して、これをどんどん分割することを考えたが、冷静になると管理する集合の個数が答えの通り数になるため容易に爆発する。埒が明かないので、移動の特徴を観察することにした。すると、2回の移動をまとめると、駒が今いる行だけで状態を表せることに気づいた。この考察を経てさっきの集合の話に戻ると、等しい集合を何個管理しているかを持つbitDPが可能なことに気づく。これで本当に重複が省けているのか半信半疑で書くとサンプルが合う。計算量もちょっと多めだが、手元でサンプル3がほぼ一瞬なのでまあ通りそう、と思って出すとAC。

Hはあっけなかった。とりあえずA_iをソートして重複を省いておき、どの区間の値をそろえるかをdpする。オンライン・オフライン変換など考えていたが、C_iの累積和など用いて冷静に立式するとCHTだった。この時点で残り20分弱だったので、イチから書くと間に合うか自信がない。ということでうしさんのライブラリから、直線の傾きが単調なときのCHTを窃盗してきた。いろいろなケースに対応していてかなり便利だった。ドキュメントを読んで適当に使ってみると見事にサンプルが合い、そのままACした。

Convex-Hull-Trick-Add-Monotone | Luzhiled’s Library

コードゴルフ。A問題は、sとt・xの間隔を、差を24で割ったあまりを取ることで求め、大小比較するRubyコードを見つけた。強そうなのでこれをdcで書いておいた。BはRubyやPerlも試してみたが、AWKが大幅に短くなった。Cは隙のないシンプルなRubyコードが提出されていて負けかと思ったが、Perlで縮めることに成功した。普通にsortすると辞書順なので比較関数を書かねばならなかったところ、bit反転しておけば264から引いたような値になるので桁数が揃い、辞書順比較と数値での比較が一致する。その状態でも数値の差は保たれるので、判定も正しく行えるという寸法。Dは負け。Eはコンテスト中のコードから、998244353-1=119\times 2^{23}+1-1を利用して定数の記述を縮めたコードが提出されていた。パースの関係で空白が入っていたため、それを頑張って取り除いたようなコードを書いたら、13秒差で勝った。残りはGがC++で最短になっているくらいで、手付かず。

火曜日に出ていたPythonの課題をこなした。講義スライドの内容はいよいよデータ分析が本格化してきたなあという感じで、気合を入れて課題提出用のノートブックを開いてみたら、今週もまたサンプルコードとしてほぼ答えそのままのコードが書いてあって拍子抜けした。弄るところもほとんどないので、ちょっとビジュアライズなど追加して終わり。

しばらくラノベを読んでから、午前4時半就寝。

11/21(日)

正午あたりしばらく起きていたが、1時間くらいでまた寝た。午後5時半起床。食事してから、昨日のABCがいくつか縮められていたので、コードゴルフしていた。

A問題は負け。t-xとs-xを比較してもよかったらしい。言われてみれば確かにそうで、sを先頭に持ってくる手間がなくなり-2B。C問題は、Perlで行の和をとるとき、空白を+に置換してevalするのがシンプルで短かったらしい。別のところで縮めて取り返した。Dは昨日からさらに更新されていて、そちらのコードからさらに-2Bできたが、ARCに出ている間にさらに縮めて取り返されていた。

昨日から読んでいたラノベを読了。「恋人全員を幸せにする話」。この作者の著作では「クラスの大嫌いな女子と結婚することになった。」を読んでいて、そちらの文章のテンポが結構面白かったため、こちらも購入した。ヒロインが極端なことを言って主人公が冷静に突っ込むという掛け合いはこちらでも健在で、やはり面白かった。しかしこの作者が描く登場人物が誰もかれも極端な思考・行動なのはちょっと気になる。

午後9時からARC129。ギリギリの4完で自尊心が粉々になった。

AtCoder Regular Contest 129 - AtCoder

Aは最上位bitだけが問題なので、それを全探索。Bはよく見ると累積max/minを計算すればよかった。ここまではシュッと通ってかなりいい感じだったのに、C問題で迷走してしまった。三角数で分割するのだろうなと思い、しかし7ばかり並べるとちょっとまずそうだと思ってしまい、142や356をずっと繰り返してみていた。判定関数を書いていろいろ試したが全然合わない。長い間適当に試していたが、ふと自分の書いた判定関数そのものに注目すると一瞬で分かった。「文字列のある位置から後ろを数値としてみたものを7で割ったあまり」を全部計算し、それぞれの重複度を見てカウントしていたが、その7で割ったあまりは7種類全部任意に作り出すことができる。つまり三角数7個以下で分割できればよくて、これは実際にやってみたらできた（多角数定理で、3個以下で分割できるらしい）。あまりをずらすための数の計算に手間取ったが何とか実装してAC。

Dも全然わからずかなり辛かった。適当に差を取ってみたりしてもいい性質がなさそうだったので、操作回数をa_iとしてA_i+2a_i-a_{i-1}-a_{i+1}=0の式を考えることにした。隣接する2項を決めると全部決まりそうだが、そうやって決めていった結果が合わない場合もあるらしい。たとえばa_0とa_1（0-indexedにした）を決め打ったとすれば、頑張って展開するとa_0=a_N=A_{N-1}+2A_{N-2}+\dots(N-1)A_1+Na_1-(N-1)a_0が得られる。ここで、すべてのa_iから同時に1引いても結果は変わらないので、a_0=0としてみる。するとA_{N-1}+2A_{N-2}+\dots(N-1)A_1は非正かつNで割り切れる必要があって、しかも次にa_1=0と決め打つときの更新も定数時間で行える。とりあえずこれらの条件を満たした場所を全探索してみるコードを投げ、当然のようにTLE。

次に、a_{N-1}の値をa_Nと同様に計算して、ちゃんと決めていった結果が合うことを確かめてから改めてa_i\ge 0をチェックするコードを投げた。TLEするケースは減った。最初に\sum A_i=0をチェックしてみても変わらず。やはりa_i\ge 0のチェックをしているのがまずいらしい。何か区間加算のセグメント木などで扱えないかと考えていたが、無理そう。残り時間がなくなってきたので、試しにa_iの最小値を全体に足しこんでみると、なんと通ってしまった。どうやらa_i\ge 0の条件を外しても解は定数の差を除いて一意らしい。

Dの解説は、操作回数の差を取っていてなるほどなあという感じ。そちらの差を見る問題は初めて見る気がする。言われてみればA_i+2a_i-a_{i-1}-a_{i+1}=A_i+(a_i-a_{i-1})-(a_{i+1}-a_i)で、よく見る係数列なのだから気づいてもよかったはずだ。

コンテスト後にしばらくAとBのコードゴルフをしていたが、どちらも負けていいところなし。失意のうちにCodeChef SnackDown 2021 Pre-Eliminationに出た。

https://www.codechef.com/SNCKPE21

PRDTPAINは、列の先頭・末尾と、そのできるだけ中間のものを選べばよい。尺取り法で書いた。DECSUBKは先頭から貪欲ができる。判定は、実際に選んだ際にLISのdp配列がどうなるかを計算し、残りの列は降順に並べておけばよい。初期化ミスで1WA。GOODRANKINGは面白かった。各人の勝利数を数えると、列の前半に来るか後半に来るかで完全に分かれる。分かれたそれぞれでは、誰が誰に勝つという関係が完全DAGにならなければならないので、順番は存在するなら一意に定まって、最後にくっつけて残りの部分をチェックすればよい。

コンテスト開始時は上の3問がその順に並んでいたのだが、いつの間にかSLIPPERSが大量に解かれて前のほうの問題になっていた。実際後ろから累積minをキーにするdpをすればよいだけ、だったが、境界条件を間違えて1WA。MEGAMU1はなかなか特徴的な問題文をしているが、結局包除原理ができればよさそう。タプルがspecialであるかどうかは、先頭から見ていって0を取り除いたときの最後の要素を持っておけばよいため、これをキーにしてdpした。キーの値が大きい代わりに非ゼロの部分が少ないため、vectorでvalueと一緒に持つことにした。一方valueはどれくらい大きくなるかわからないのだが、結局最後にゼロかどうかさえわかればよいため、3つくらいmodintを用意してHashを取ることにした。

GUESSROWが全然わからないため、MEGAMU2に移った。先ほど述べた遷移をより詳細に観察すると、結局vectorとしてありうるのは\{\}、\{(x,1)\}、\{(x,1),(x-1,-1)\}とその符号反転のみであることが分かった（実は先ほどのHashは必要なかったらしい）。特に\{\}の場合は以降何をしても変わらないため無視することにして、符号反転も無視して2M-1状態のdpを書いた。もともと結構複雑な遷移をしていたので、dpに直す際にかなり手間取ったが、何とか通った。結果は6完21位。

TCB42が終了して結果が出ていた。6位。全完は少ないようだったが、僕が10問目で得たスコアがカスすぎて9完に負けてしまっている。まあ賞金が得られたのでOK、次は賞金のメールが迷惑メールに振り分けられないことを願う。

ARC129-Aのdcコードが提出されていたので、粗探しをして-2Bした。そのあとは朝方まで日記を書いていた。