03/21(月)

先週の週記は、せっかく観光してきたので奇跡の一本松の写真をサムネ画像に設定しておいた。スマホを縦にして撮ったものであり、はてなブログの記事管理ページから見るとちゃんと縦向きになっている。しかしツイートのカードでは横向きになってしまっていた。残念。

はてなブログに投稿しました #はてなブログ
週記（2022/03/14-2022/03/20） - kotatsugameの日記https://t.co/Qim1xKIynE
— こたつがめ (@kotatsugame_t) 2022年3月20日

ICPCの参加記と週記を続けざまに投稿した後、比較的すぐ布団に入った。午前9時就寝。

HUPC day3が始まる午後1時に目覚ましをかけてはいたものの、あまりの眠さに何もかも諦めて二度寝した。午後3時起床。

週記のうち以下の記述について、ホスフィンから「付属のスプーンがあるのではないか」との指摘があった。改めてパッケージを読み直すと、確かにそういう記述がある。粉を掘り返してみると見事に見つかった。これを使ってすりきり3杯を溶かして飲むと、ほのかな甘みが感じられて飲みやすくなった。粉っぽくもある。

水に溶かして恐る恐る飲んでみると、まったく味がしなくてびっくり。スプーン3杯と書いてあったが、使ったスプーンが小さかったのだろうか。
週記（2022/03/14-2022/03/20） - kotatsugameの日記

ABC244Cが取られていた。最初に $1$ を出力して、以降は ${\rm input}\oplus 1$ を出力しているらしい。ジャッジのハックかと思ったもののそんなこともなく、正当な解法である。つまり、 $\{1\dots 2N+1\}=\{1\}\cup\{2,3\}\cup\dots\cup\{2N,2N+1\}$ と分割して初手で $1$ を宣言しておくと、以降は ${\rm input}$ と対になっているものが存在してそれを常に出力できるということ。なるほど……。Perlだったのをdcに書き換えて取り返しておいた。

午後4時過ぎに家を出発し、一番町のあたりに向かう。今日はたいぺーとホスフィンと3人で飲む予定を立てていた。集合時刻が午後5時ちょっと前で、ゲーセンに寄るかかなり迷ったものの断念して早めに集合場所へ。2人は少し遅刻してきたので、結果的に僕も1クレくらい遊ぶ余裕はあった。まあこういうすれ違いが起こるのも、これまで僕が遅刻しまくってきた報いである。

ホスフィンが予約しておいてくれた焼き鳥屋で3時間ばかり飲み食いした。今日焼き鳥にしようとしたのは僕の希望だったので、それが叶ったのは嬉しい。美味しかったはず。人手が足りていないようで、店員が常に忙しそうだったのと、頼んだものが出てくるのが結構遅かったのは気になるが、一方僕らの方もあまり頼まなかったのに延々席に居座り続けていたのは申し訳なく思う。

食事 pic.twitter.com/KfBEtaUCpW
— こたつがめ (@kotatsugame_t) 2022年3月21日

帰り道、ドンキでお酒やおつまみを買い、僕の部屋に行って本格的に飲酒を始めた。

飲酒します pic.twitter.com/r0c74PkMOv
— こたつがめ (@kotatsugame_t) 2022年3月21日

アニメを見るのも途中で飽きるし、僕の部屋には他にすることもないため、結局毎回YouTubeやニコニコ動画でお互いにお薦めの動画を見せ合うことになってしまう。アニメに途中で飽きてしまうのはモニターが小さい（あるいは遠い）からだと思って、脚立を引っ張り出して頑張ってセッティングしてみた。かなり近づいていい感じになったと思う。ジョジョの奇妙な冒険の第1部を観た。

いい感じや pic.twitter.com/SHRT2hV0Yr
— こたつがめ (@kotatsugame_t) 2022年3月21日

途中一休みで適当なMADを挟みつつ、午前2時くらいまでかけて10話見終わった。めちゃくちゃ面白かった。ネットミームとして聞いたことのあるセリフやシーンがちょくちょく出てきたものの、話の流れとしてはもちろん自然なものに感じられて、ややオーバーな表現も画風にマッチしてより強くストーリーに引き込まれた。熱くてよい話だった。その直後から第1部の素材を使ったMADを見始めて余韻もクソもなくなったが、それはそれでつい先ほど見たシーンが出てきたのがわかるため笑えた。

今日家を出る前に縮めたABC244Cが再度取られているのを見つけた。今度は $2N+2-{\rm input}$ らしい。その解法も発見していたものの、dc力が足りず自力では縮められていなかった。完敗。

その後も適当な動画を流し見つつ、ねるねるねるねを作ったりしていた。午前5時前に急激に気持ち悪くなり、洗面台でしばらくえずいた後布団に誘導されて、そこからぐっすりだった。

日記の最後に一番面白かったMADを一つ。ジョジョではない。

www.nicovideo.jp

03/22(火)

午前11時過ぎに起床。2人ともいなくてびっくりした。頭痛はないが気持ち悪さが残るため、水分を取ってまたすぐ寝た。

午後3時過ぎに再度起床。自分の記憶では、買ってきたお酒のうちカルーアミルクがボトルに半分くらい残っていたはず。見るとさらに半分になっていたので、僕が潰れた後も2人はしばらく飲んでいたらしい。聞いてみると、ホスフィンは早朝のうちに帰宅して、たいぺーはひと眠りした後朝になってから研究室に向かったそうだ。たいぺーが家を出るとき僕も少し反応を返したと聞いたが、一切記憶にない。部屋を出た直後に中に鍵束を忘れたことに気づいたたいぺーが再度インターフォンを鳴らしても反応がなかったらしいことから、本当に一瞬だけ意識が浮上していたのだろう。

いつも飲酒を始めるとすぐに腹を壊すのに、昨夜はそんなことはなかったため、調子が良いなと感じていた。一方潰れる直前の吐き気はしばらく感じたことのない強いもので、結局苦しむ羽目になるのかと絶望した。酒量をセーブすることを覚えなければならないのだろう。思えば昨夜はアニメに集中していて、スローペースで飲んでいたかもしれない。それで腹を壊すことがなかったのだろう。

微妙な気持ち悪さを抱えつつ部屋を掃除。せっかくモニターを一度取り外したので、接続するケーブルを取り換えて、以下の現象の解決を図った。真ん中のモニターと左端のモニターをPCに接続しているケーブルを交換することで、起動時に特別な操作をすることなく、無事真ん中の画面をキャプチャできるようになった。

これまで真ん中のメイン画面をキャプチャできていたのが、いつの間にか左端の画面をキャプチャするようになってしまっていた。調べたところ、regeditでモニタの設定をいったん削除し、改めて番号順にモニターを1枚ずつ増やしながら接続→再起動を繰り返すと正しく設定できるらしい。
週記（2021/09/13-2021/09/19） - kotatsugameの日記

午後5時からインターン先の定例会に出た。先週木曜日のコーディングの成果を発表。今日の勉強会はデザインの話で、フォント選定にも触れられていた。明朝体は縦棒の太さに比べて横棒を極端に細くすることで字を美しく見せている一方、細い字が読みにくいタイプの人には辛い。一方教科書体というフォントは縦横の太さをほぼ同じにしているのでそういう人にも配慮している、という話を聞いたことがあった。今日の発表ではさらに、ゴシック体などに比べてフォントの端を丸めることで、目に優しい印象を与えてもいるということを知った。実際にフォントを切り替えた様子を見せてもらって、確かにかなり印象が違うなと体感した。

上に書いたように、たいぺーが部屋に鍵束を忘れていったので、それを取りに来ることになっていた。聞いてみると研究室での用事がまだ終わっていないらしい。大変そう。しばらく人の日記を読みつつ待って、午後8時過ぎにやってきたたいぺーと家を出た。ラーメンを食べに行く。まだ気持ち悪さが残るのに替え玉をしてしまって後悔しつつ、何とか食べ切った。ラーメン屋を出たところで別れ、今日開店した新しいゲーセンに行くことにした。

「スーパーノバ仙台一番町」本日３月２２日１５時よりオープンしました！
一番町アーケードのサンシャインビル１階になります！
お店は年中無休！朝９時～夜２４時までになります！
ご来店をお待ちいたしております！#ゲームセンター #開店 #オープン pic.twitter.com/RrPuc5BfMq
— スーパーノバ仙台一番町 (@nova_ichibancho) 2022年3月22日

音ゲーは、太鼓の達人が1階にある以外は地下にまとめられていた。チュウニズムのゴールドモデルが4台に、あとはメジャーなものが2台ずつ。個人的にはチュウニズム4台というだけで感謝の念が強い。ただチュウニズムのように筐体に種類がある他の機種はあまり力を入れられていないようで、TLで「チュウニズム屋さんが増えただけ」と言われているのを見た。これも理解できる。コロナ禍でアーケード音ゲーが振るわない状況なのは論を俟たず、その中でもひとまず人気があるチュウニズム以外はどうせ集金力も高くないだろうという判断がなされている。そのような現状を見聞きすることは多いが、音ゲー全体の栄枯盛衰には興味がない。自分はチュウニズムさえプレイできれば満足で、そのサービスの進退が問われるのはアーケード音ゲーが全体として終焉を迎えた後だろうと思っているからだ。これ何か英語の熟語みたいだな……チュウニズムは最後にサービス終了するアーケード音ゲーです。

音ゲーの成果は、新曲を埋めただけ。1曲、初見で理論値を出すことに成功した。譜面動画を1回だけ見た記憶はあるが誤差だろう。MASTERで初見理論値は初めてなのでかなり嬉しい。

ヴァンパイア　初見理論値！ pic.twitter.com/q3AcsP9rBa
— こたつがめ (@kotatsugame_t) 2022年3月22日

腹を壊してトイレに駆け込んだら、トイレットペーパーが切れていて青ざめた。ポケットティッシュを持っていたため難を逃れた。

「クーネル・エンゲイザー」という曲を気に入ったので、しばらく詰めていた。結構すぐ1落ちは出たのに以降ウンともスンとも言わず断念。

助けて〜〜〜〜〜〜〜〜〜〜〜！！！ pic.twitter.com/lpFv4H8Fs8
— こたつがめ (@kotatsugame_t) 2022年3月22日

午後12時の閉店まで適当な譜面を触って帰宅。セガ仙台より閉店が遅いのはありがたいところ。ただ開店当日なのに音ゲーコーナーはガラガラで、大丈夫かという気持ちになった。平日深夜はさすがにしょうがないのか？

帰宅して少し日記を書きつつYouTubeを見ていた。今日チュウニズムでプレイして気に入った「クーネル・エンゲイザー」の本家PVを探して見てみると、楽しげな曲調に反して歌詞が重苦しく、ひっくり返った。

www.youtube.com

本を1冊読んだ。「かくりよの宿飯」12巻。これまで特典などで出ていた短編をまとめたもので、ストーリー完結前の話が多く懐かしい気分になった。大旦那様が現世に来る話もいくつかあったので以下のようなシーンがまた見られることを期待したが、主人公とイチャイチャするだけだったのでちょっとばかり拍子抜け。天神屋の社員旅行はまた別の外伝という形でそのうち出版されるらしいので、そちらも楽しみに待ちたい。

主人公と大旦那様が現世で一緒に買い物をしているとき、大学の同級生と遭遇して、大旦那様がキャーキャー言われる……というのは非常に僕好みの1シーンだろうが、回想という形でサッと流されてしまった。
週記（2021/09/13-2021/09/19） - kotatsugameの日記

またしばらくYouTubeを見ていた。百万年後でも情報を伝達できるような、核廃棄物の最終処分場を示すのにふさわしい標識についての話。非常に面白かった。現代文明からの情報の伝達が途切れた後の世界というのは、想像するのは非常に楽しい。非常に長い時間の経過を感じさせるような話が好みだからである。

www.youtube.com

布団に入り、午前7時くらいに寝落ちした。

03/23(水)

午後3時ちょっと前に一瞬起床。メールで注文していたラノベが生協に届いたことを知るも、もう閉店時間に間に合わないので諦め、またすぐ寝た。次に午後6時半に起床。

しばらく布団に横たわったままネットサーフィンをしていた。午後8時過ぎに起き上がって、シャワーを浴びたり食事したりした。一念発起して3回目のワクチンを予約する。週末は絶対に副反応を残したくない。4月に入ってからだと大学院がどうなるのか全然わからないので、来週月曜日を選択した。インターン先の定例会は、熱が出ていたら最悪休むことになる。

izrytさんがYouTubeで見たということでツイートしていた問題が流れてきた。 $x,y,z\gt 0$ として、以下の連立方程式を解く。

$\displaystyle \begin{cases} x^2+xy+y^2=49\\ y^2+yz+z^2=144\\ z^2+zx+x^2=169 \end{cases}$

適当に2式選んで引くことで、 $(x-y)(x+y+z)=25$ のような式が3つ作れるのが天才パート。Y.Y.さんのリプライを見て感心していた。ここから一度 $x-y:y-z:z-x$ のような比に持ち込んでしまうと計算が苦しかった。一方 $x+y+z=k$ と置くことでも解けて、こちらのほうがストレートだがいずれにしても値の大きな計算を必要とし、答え $(x,y,z)=\frac 1{\sqrt{13}}(17,12,36)$ が出る。

月曜日の残りのカルーアミルクと牛乳を消費しつつ、ノクターンノベルズから1作読了。「エッチできるＶＲＭＭＯで性奴隷にした美少女たちがリアルでも知り合いだった件」。物語としての評価は別として、良かった。

https://novel18.syosetu.com/n8146gy/

カルーアミルクはほんの少ししか残っていないように見えたのに、薄めに作って飲んでいたら牛乳を1L空けてしまった。腹を壊しまくってしばらくトイレに出たり入ったりしつつ、コードゴルフをしていた。いわゆる牛ゲーを解いていて、networkxではあえなくTLEしたため、現在の最短コードを見て同じ方針を取った。ACLのmincostflowを持ち出し、流量1のフローを流すもの。

朝方からはハーメルンを漁っていた。「RTA」で検索してよさそうなものを1作見つけ、読み進めた。

昼前に、大学生協に行ってラノベを受け取ってくることにした。うっかりヘルメットを忘れたまま原付にまたがるも、エンジン音の聞こえ方の違いからなんとか気付くことができた。大学の前の道路が工事で道幅が狭くなっており、えらく渋滞していた。交差点の前で信号待ちをしていたら、交通整理の方から押して歩いたほうが早いと言われるくらいだった。ラノベを受け取り、ついでに昼食のパンを買って帰宅。

と、日記を書いていて初めて気づいた。そういえば今日はお酒を飲んでいたのではなかったか。気づかないくらい体内のアルコールが抜けていたと考えたい一方、一度はヘルメットを忘れて家を出たことなど、ちょっと危うい感じがする。お酒を飲み終わったのが午前4時で、原付に乗ったのが午前11時半なので、適当に調べて出てきた目安である7時間は何とか経過している。しかし問題は体内に保有しているアルコールの分量であって、実際にどうだったのかはもうわからない。正直このことを日記に書くのも迷ったが、気づいてしまったものは仕方ない。

帰宅してからまたハーメルンを読み続け、午後2時くらいに寝落ちした。

03/24(木)

午後5時半起床。

今朝コードゴルフした問題が縮んでいるのを見つけた。そのときの最短コードに引きずられて、pairを受け取るのにstd::tieを使っていたが、普通に構造化束縛でよい。別のところで1B縮めて何とか取り返した。

午後6時からミーティング。先週書いていたコードは、2月末にデプロイしたものの機能拡張である。なので、現在デプロイされているものを使ってみた感触がどんなものか聞くのと、新しいものに置き換えたいのですがどうですかと確認するための時間。相変わらず機能が評価されていてうれしい。置き換えたものについても使った感触をフィードバックしていただけることになったので、話し合いで判明した改善案を実装して再度デプロイするのが直近のタスクになった。

先週金曜日のミーティングを受けて、ひとまず今できている部分を使ってみようという話になっていたのだ。
週記（2022/02/21-2022/02/27） - kotatsugameの日記

結構気を張っていたので、終了したとたん疲れが出た。いろいろやるべきことは残っているし、実装にもとっとと手を付けたいところだが、睡眠不足を理由にすぐ布団に戻ってしまった。しばらくハーメルンを読んで、午後9時半ごろ寝落ち。真夜中からCF combinedがあったことは、一応知ってはいた。しかしやる気がない。

午前1時半起床。CodeChefからメールが届いていて、以前僕にかかったコピペ疑惑が間違いだったこと、ペナルティが解除されたことが知らされた。一安心。

僕のコードがACLに由来すること、またACLがコンテスト前に利用可能だったライブラリであることを証明すればよい。英作文してメールを送った。
週記（2022/03/07-2022/03/13） - kotatsugameの日記

またハーメルンを読み続け、午前4時前に1作読了。「万魔殿の主〜胡散臭いトレーナーとウマ娘たちは日本を驚かせたい」。面白かった。やはり天才トレーナー視点は面白い。担当するウマ娘をポンポン増やしているのも、たぶん現実的ではないのだろうが見ていて楽しい。他のハーメルンで主人公陣営だったウマ娘をこちらでは外側からの視点で見たり、その逆を行うことで、それぞれのウマ娘の原作における性質らしきものがなんとなくわかってきた気がする。原作を知らないなりの楽しみ方である。

syosetu.org

別のハーメルンを少し漁って、午前5時くらいに布団から出た。食事してシャワーを浴び、洗濯機を回した。一人暮らしを始めてから使っている柔軟剤は、いつの間にかリニューアルされてしまったのに店頭では詰め替え用しか見当たらなかったので、仕方なく現在使っているボトルを洗って詰め替えることにした。

ゴミ出しをして、午前7時くらいに布団に戻った。明日、というか今日は卒業式なので昼前に起きる必要がある。午前8時までハーメルンを読んでから寝た。

03/25(金)

午前11時、執念の起床。

眠い目を擦りつつ、先日両親に実家から持ってきてもらったスーツを着用した。ネクタイをうまく結べず、鏡の前でモジモジしているうちに時間がヤバくなってきた。それなりの結び目で妥協して、急いで家を出た。

先週木曜日の日記でも書いたように、地震の影響で卒業式の会場が変更された。定員がずいぶん少なくなってしまったようで、溢れた人はサテライト会場などと言って、講義棟の教室から遠隔で参加することになっていた。東北大学の大学院に進む人はできるだけサテライト会場から参加しろとのお達しが出ていたので、僕も最初からそちらに向かった。午前11時40分まで集合と言われていたところ微妙に遅れてしまったが、特に問題ないようだった。普段講義を受けていた教室にスーツなり着物なりで集まって卒業式に参加するのはどこかシュールである。席を詰めて座らせられたので、感染症対策も大丈夫かと心配になった。

これが4年間の集大成か…… pic.twitter.com/CjnOYd3RVa
— こたつがめ (@kotatsugame_t) 2022年3月25日

式は正午開始。途中で地震があった以外は特筆すべきこともなく進んでいった。その間はハーメルンを読んでいて、1作読了。「幻想郷の接触」。文章がカス。設定は面白かった。

syosetu.org

30分くらいで終了。寝坊したたいぺーから連絡が来ていて、写真だけ一緒に撮ろうぜとのことだったので合流した。会場のどこかに「学位記授与式」みたいな看板がないものかと探していたのだが、聞いてみると感染症対策で設置していないらしい。施設の名前が書いてあるところの前で撮った。その後たいぺーは友人と遭遇し、僕も数学科で集まっているようだったのでそちらに向かうことにして別れた。

数学科は十数人集まっていた。すでに一度集合写真を撮ったらしいが、また集まってきたので再度撮影することになった。撮影場所が空くのを待つ間、久しぶりに会う人々といろいろ話をしていた。チラッと聞いてみると、大学院に合格した後すぐ担当教員にメールを出している人が多く、かなり焦った。また、4年ゼミで一緒に何度かスカルをプレイしていたうちの1人が、実際にスカルを購入したという話を聞いてびっくりした。

解散し、今日も生協でラノベを受け取って帰宅。スーツ姿を見てか、生協の店員さんにも卒業をお祝いされて嬉しくなった。

スーツ姿の自撮りをツイートした。入学式の日にほぼ同じ構図で自撮りした写真がスマホに残っていて、日付でツイートを検索してみると見つかったので、それへのリプライとしてみた。こういうところにも4年間の流れが感じられて感慨深い。

押忍 pic.twitter.com/oAIrIy73tI
— こたつがめ (@kotatsugame_t) 2022年3月25日

しばらくYouTubeを見てから午後3時半に布団に入り、寝た。

午後8時半起床。PayPalでCodeChefの賞金が受け取れるようになったとのメールが来ていた。

PayPalにCodeChefから賞金が贈られてきた。ただ、この送金のリスクが高いとされていて、すぐに受け取れるわけではないようだ。
週記（2022/03/14-2022/03/20） - kotatsugameの日記

布団でハーメルンの更新を漁ったり、新しい作品を読み始めたりした後、午後11時くらいに布団から出た。ラノベについて、3月の初めに注文した分で受け取っていないのは残り2冊だけとなったため、また新刊を予約する。4月分をいろいろ探して、とりあえず19冊予約した。タイトルからは似たような設定の話に見えるのに、一方はタイトルを見て即座に購入を決め、他方はあらすじを確認して取り止めたりと、思い返すに買う基準がバラバラであった。

日付が変わってからまた布団に戻り、ハーメルンを読んでいた。午前2時過ぎに寝落ち。

03/26(土)

午前5時起床。2時間ほどハーメルンを読んでまた寝た。次に午後1時半、目覚ましで起床。眠気をこらえつつハーメルンを読んで、午後3時前に布団から出た。AHC009。ちょうど大学生でも大学院生でもない微妙な時期で、所属をなんと書くか迷った。結局大学生にした。

Monoxer Programming Contest 2022（AtCoder Heuristic Contest 009） - AtCoder

とりあえず1B解を提出してから考察。できるだけまっすぐ進むような経路を作って、それぞれの直線で何回か余計に操作することで予定通りに進む確率を高めるとよいのではないかと考えて少し実装していたが、まっすぐ進むような経路は必ず通路のつきあたりまで行かなくてはならないし、操作回数も平均的に長くなってしまうので、普通に山登りなどをしたほうが強いのかも知れないと考え、面倒になってシャワーを浴びたり日記を書いたりしていた。

コンテスト終了時刻である午後7時の20分前になってから、さすがに0点のままはまずいと思って適当な貪欲の実装を開始。毎回どの位置にどれくらいの確率でいるかを計算しておいて、4方向それぞれ進んだ時にゴールまでの距離の変化がどのくらいかの期待値を求め、最も小さくなる方向を出力し続けるというもの。これで2528180402点が出て、ゴールまでの距離の変化 $-1,0,+1$ に対する重みを適当に変えてさらに2回提出し、最終的に2555201986点になった。

401位で1834→1836(+2)。できるだけまっすぐ進むような経路を作るのは、それなりに良い方針だったらしい。通路のつきあたりまで進むような移動でゴールにたどり着けない場合も、できるだけ近寄ってからフラフラ移動することを考えれば、疑似的にスタートとゴールの位置を近づけるという意味で十分効果があるようだ。あとは案の定山登りした人も多そうだった。実装していないのに適当な考察だけで案の定とか言っちゃダメか。

その後も日記を書き続け、午後9時からABC245に出た。

AtCoder Beginner Contest 245 - AtCoder

Aで1WA。 $A\lt C$ とすべきところを $A\le C$ にしていた。コードゴルフは少し面倒そうに見えたのですぐ先に進む。Bは適当にRubyで、その先からはC++で書いた。Cは先頭から見て、直前を $A$ 、 $B$ 由来の数にできるかのフラグをそれぞれ持つ。Dは端から1つずつ決めていく。うっかり $A_0$ を使って $B_0$ から決め始めてしまい、1WA。これだとゼロ除算が発生しうる。 $A_N$ を使って $B_M$ から決め始めるのが正解。Eは縦の長さでソートして、使える横幅をmultisetで持ち、貪欲に消費していく。FはSCCして、サイズ2以上の強連結成分にたどり着ける頂点の数を数える。

Gで2WA。まず想定解と同じdijkstraを書くも、queueに入っている余計な要素を無視する部分で、関係ないところのコストと比較してしまいTLE。次に、「その頂点と同じ国・違う国」で分けてコストを持つという大嘘を書きWA。ここでようやく先ほどのミスに気付いてACした。Exは解けず、前半のコードゴルフをしている間にコンテスト終了。7完25位。

コードゴルフ。Aはコンテスト中にdc 32Bを書き、コンテスト後に1B縮めて満足していたら朝方さらに1B縮められた。無理やり引き算してvで正負を判定していたところを、普通の大小比較に書き直すという更新。なぜ気づけなかったのか。BはRaku。Cは、 $A$ 、 $B$ が使えるかのフラグを持つ代わりに使える要素を直接保持すればわかりやすい。これをPerlで実装。DはOctaveの多項式除算が通らず、Pythonとnumpyを使うコードが提出されていて万事休すかと思ったが、自力でループを回すと短くなった。Perlで縮め、AWKで書き直すとさらに短くなった。EはCrystalなら線形時間のinsert・eraseが間に合う。位置は二分探索する必要がある。FはPerl。これも単純なミスで取られてしまいかなりショック。

真夜中から午前6時までずっと日記を書いていた。週の初めからずっと溜めてしまっていた。

今日の部分まで追いついたところで布団に入り、ラノベを1冊読了。「異世界でチート能力を手にした俺は、現実世界をも無双する」10巻。1巻で主人公がとんとん拍子にチート能力を手に入れられた理由付けがなされた。主人公はこの巻で過去に飛ばされたのだが、そこでチート能力を主人公に受け継いだ賢者と会って契約を交わしていたということらしい。そういう時間軸をぐるぐる回るような展開が思いもよらないところで出てきたので、大変驚いた。ただ、このラノベの作者はあとがきで行き当たりばったりで書いていると何度も述べているから、これも伏線回収でもなんでもなく、そういう話にできるからそうしてみたという感じなのだろうか。それはそれですごいことである。過去編なんて9巻まで影も形もなかったと記憶しているので、余計に驚きが増したのかもしれない。

午前8時半就寝。

03/27(日)

目覚ましのスヌーズを繰り返し、午後0時50分ごろ起床。10分後からUTPC2021に参加した。

UTPC 2021 - AtCoder

Aは面倒。最初、長さ4の連続部分文字列を全部試して、"UTPC"と一致しない文字数の最小値を出力しようとしていた。ただ提出の直前に、部分文字列内でswapすることで操作回数を少なくできることに気づいた。swapで2文字一気に揃えられるケースにも対処して提出。しかしWAだった。swapで2文字一気に揃えられるのは長さ2のループだと思うことができて、長さ3や4まで考えられる。かなり面倒。再帰関数で操作を全列挙し、ようやくACできた。

順位表を見るとM問題にACが出ていた。優先度付きキューを使い、その時々で最も当たりである確率が高い鍵を試すようなコードを書いたらサンプルが合って、そのまま通った。あまり深く考えていない。この時点で一瞬1位になっていた気がする。ほかに解かれている問題がないので、しばらくB問題に取り組んでいた。値でソートして、swapできるものを区間とみなし、その区間の重なり方でswapの影響を分類できることまで考察したが、その先に進めず、適当に2ペナ付けて諦めた。

C問題が解かれているので見る。とりあえず符号が同じ数は絶対値が大きなほうからペアにしていってよいだろう。残りを適当に決めるとサンプルで落ちた。残りのうち $k$ 個取ると決め打ったとき、絶対値の小さいほうから $1$ 番目と $k$ 番目、 $2$ 番目と $k-1$ 番目……のようにペアにしていくのがよさそう。いったん愚直に書いて部分点を取りつつ正しいことを確認。さて高速化するぞと気合いを入れたが、ちょっと冷静になると畳み込みで書けることに気づいたので、満点もすぐに取れた。

次はG問題。行と列に分割してそれぞれ解ける。最大値の位置から左右にマージしていくのがよいと考えるも、貪欲に操作するとサンプルで落ちてしまったため、いったん区間dpで部分点を取っておいた。しばらく考察していると、貪欲に操作していたのが悪い気がしてきた。目先の得点を捨ててでも遠くにあるより大きな数とマージさせたい気持ちになる。実装としては、区間dpで分割を全探索していたところを、左端・右端で分割するパターンだけ試すようにした。これで通った。実は考察が不正確で、最大値の位置が複数ある場合などどこからスタートするか決められなくて壊れてしまうのだが、書いたコードは正しい。実装方針を選ぶときの運がよかった。

Eが結構解かれているのに全然わからない。I問題に進む。今どのカードを食べたかと最後に食べたカードを持つ $O(M2^M)$ 状態のdpが考えられて、最後に食べたカードが $i$ の状態から次にカード $j$ を食べる遷移のときは、「カード $k$ がカード $i$ とカード $j$ の間にある山の数」をまだ食べていないカード $k$ すべてに対して求められればよい。 $O(NM^3)$ の前計算をしておけば、毎回 $k$ を決める $O(M)$ のループでコストが求まる。これを実装して部分点。

コスト計算のループが一番内側で、 $O(M^3 2^M)$ かかっているので、ここを高速化したい。 $2^M$ 状態それぞれで、まだ食べていないカード $k$ に応じていろいろ値の和をとる必要がある。このとき、直前の集合との差分だけ更新すればよいのではないかと考えた。このアイディアを実装するとジャッジで6sec強だったが、配列アクセスが飛び飛びだったのに気づいて次元を入れ替え、#pragma GCC optimize("Ofast")すると爆速になった。4.5secで通った。

しばらくコードゴルフした後、ようやくEと向き合う。 $K=1$ の時は明らか。 $K=2,3$ の時は、あらかじめ符号を決め打った状態で累積maxを取っておくと無理やり求められる。これで $K\ge 4$ としてよく、このとき四方向それぞれ最も遠い頂点を必ず選ぶことができる。 $c$ の値で降順ソートし、順に点集合に入れていく。点集合のサイズが $K$ を超えた場合は、 $X$ 、 $Y$ の最大最小が変化しないような点であって最も $c$ が小さいものが存在するので、代わりにそれを削除する。ただこの計算だとサンプルから合わない。点集合のサイズが $K$ を超えた場合に削除すべき点より $c$ が小さい点は高々4個なので、それらを代わりに削除してみるのも毎回試すと通った。日記を書いているときに気付いたが、 $K=3$ の場合で1点がほかの2点からなる長方形から完全に含まれる場合を考慮し損ねていた。

OpenCup後に解説などを読んだ感想。Iはかなり頭が良い。食べる順番 $\{p_i\}$ を決め打ったとき、カードの山の上から下まで見るのを何度も繰り返して正しい順番で食べていると考えられる。結局全部食べてしまうのだから、毎回必ず一番上から一番下まで見ていると考えてよい。この時、操作1の回数はカードを見たのに食べなかった回数であり、山の一番上に戻ったときにまだ食べていないカードの数を求めるとその和となる。山の一番上に戻るのが $1\le i\le M$ 番目のカードを食べるときだとすると、その時まだ食べていないカードは $M-i+1$ 枚で、そのような $i$ は「カードの山において $p_i$ の位置が $p_{i-1}$ より上にある」という条件を満たす。あとはdpのためにコストを $(p_{i-1},p_i)$ ごとに分解すればよい。

Eは最大・最小の条件を緩めても報酬が大きくならないことを利用するらしい。考えもしなかった。あとはコードゴルフ。MはPythonのheapqを使わずとも毎回線形時間で最大値を求めてよい。Aはとりあえず多始点の幅優先探索を書いておいた。

Eが通ったのが午後5時2分。午後5時からOpenCupだったので、急いでそちらの問題を読み始めた。久しぶりのOpenCupである。

チームメイトの二人がUTPCに吸い込まれていたので、開始から1時間は一人でやっていた。まずBが解かれ始める。読むとやるだけだったので通す。次に解かれていたCは全然わからないので、こちらも少しsolvedが出てきたEに移った。dpを考えると遷移の計算に時間がかかりそうに見えたが、遷移先をずらしながらコストを更新していくと全体では十分高速になることに気づく。こちらもすぐACできた。

そのままCを考えていた。数列 $\{A_0,A_1,\dots,A_{2^N-1}\}$ が与えられるので、 $A_i+A_j\lt A_{i\;{\rm AND}\;j}+A_{i\;{\rm OR}\;j}$ なる $(i,j)$ があれば出力せよという問題。他の2人が戻ってきて考察が進み始める。 $i-(i\;{\rm AND}\;j)=(i\;{\rm OR}\;j)-j$ であるという気づきがあって、この差 $d$ を全探索したい。 $d\subseteq i\subseteq i'=(i\;{\rm OR}\;j)$ について $A_i-A_{i-d}\lt A_{i'}-A_{i'-d}$ であればよい。ここで式をよく見ると、 $d$ としては2べきのもののみ考えればよいことがわかる。2べきで見つからなかった場合、 $d=d_1+d_2+\dots$ と2べきの和に展開できて、 $A_i-A_{i-d}=(A_i-A_{i-d_1})+(A_{i-d_1}-A_{i-d_1-d_2})+\dots\ge(A_{i'}-A_{i'-d_1})+(A_{i'-d_1}-A_{i'-d_1-d_2})+\dots=A_{i'}-A_{i'-d}$ という式変形から必ず条件を満たさないことが確認できるからだ。感動しつつ実装に立候補して書いた。 $i\subseteq i'$ という条件を見逃して1WA。

残り3時間はL問題と格闘していた。燃やす埋めるっぽいのに、どうやってもペナルティをうまく定義できず、惜しそうな気配を感じつつも一歩も進まなかった。念入りに椅子を温めている間にA問題が通っていてすごい。結局4完と完数ではかなり少ないものの、崖が大きかったので全体で24位だった。BECがたくさん解かれて、Aは40チーム、Lは25チーム、残りのsolvedは1桁。12問5時間でこれってマジ？

Aの解法はすごい。多重集合 $U$ と $V$ があって、すべての $(u_x,u_y)\in U$ と $(v_x,v_y)\in V$ の組み合わせに対して $\max(u_x+v_x,u_y+v_y)$ を計算したものの最小値を答えるのを、 $U$ と $V$ を更新しつつ行う問題。 $u_x+v_x\le u_y+v_y$ と決めて、 $u_x-u_y\le v_y-v_x$ と式変形する。 $u_x-u_y$ や $v_y-v_x$ をインデックスとして、 $u_y$ と $v_y$ をそれぞれ保持する。大小関係を意味している左右の位置関係を崩さないように気を付けつつ $U$ 由来の数と $V$ 由来の数の和を取って、それらの最小値を求める。これはセグ木に乗る。 $u_x+v_x\ge u_y+v_y$ も同様に行える。見た目に反してかなりスマートな解法だし、コードを見る限り実装も簡潔で感動した。