02/26(月)
午後3時過ぎ起床。半からインターン先定例会に出席した。
先週は修論修正を口実に稼働していないので、今週はタスクを進めますと宣言しておいた。勉強会はAHC030の話。ベイズ推定による特定方法はビジュアライズすると魔法のような挙動をしているが、この理論が聞けて良かった。最上位層はそこからさらに焼きなましで配置パターンを探索していたらしい。奥が深すぎる。
解散後はずっと先週の週記を書いていた。日曜日の時点である程度書いてあったので、午後10時くらいにはUniversal Cupを残して完成。そこが穴あきなのは毎週のことだからもう投稿してしまおうかとも思ったが、気合いを入れて埋めることにした。結局コンテスト後にD問題を通した部分が書ききれず、日付が変わってから追記した。
グダグダしながら食事したりシャワーを浴びたりゴミを出したりした。もうちょっとテキパキ行動したかった。ただ無為に時間をかけたおかげでゴミ出しが日の出少し前のタイミングになり、夜明けの空気を楽しむことができた。
セミナー発表の準備でしばらく論文を読みながら資料を作っていた。午前8時就寝。
02/27(火)
午後3時起床。昨日の続きに少し取り組んで眠気を覚ましてからゲーセンにでも行こうと思ったのだが、線形代数に手こずっているうちに3時間経過してしまった。これ以上遅くならないうちにと外出。
夕食は油そば。普段の行動範囲から微妙に外れたところにあってこれまで行ったことのなかった店に入ってみた。よく行く一二三よりタレの量が多く、その分薄めになっている。麺の量は大盛り・320gを選択。かなり空腹だったので難なく食べきれたが、そうでない場合は厳しいくらいのサイズ感だった。今後のために記録。
— こたつがめ (@kotatsugame_t) 2024年2月27日
ゲーセンに行く途中にあるたいやき屋がさくらみこさんとコラボしていたので、商品を買うわけではないが写真を1枚。いつも歩く道にいきなり巨大なイラストパネルが現れるので目に付く。第二弾とあるように昨年も見かけた記憶があったので、当時のツイートを探しリプライに繋げておいた。
第二弾 pic.twitter.com/dy9vo7VI8z
— こたつがめ (@kotatsugame_t) 2024年2月27日
ゲーセンには午後7時から午後10時半くらいまでいて20クレプレイ。今日も未プレイの譜面を埋めていた。「ASH」は「My First Phone」の再来と聞いて身構えていたが、そんなに難しくはなかった。似ているのは前半だけで、後半はまた違ったトリッキーさ。新要素である高さの違うエアーが乱れ飛んでいた。譜面が見にくいだけで手をぶんぶん振り回していれば何とかなる。それにしても4落ちはかなり上手くいった。
ASH AJ！ pic.twitter.com/gs7MmqQUcF
— こたつがめ (@kotatsugame_t) 2024年2月27日
帰りにトイレで手を洗おうと思ったら、いつの間にか午後9時以降使用不可となっていた。びっくり。GiGO仙台も確か午後9時半だったか、ともかく夜になるとトイレを使えなくしてしまう。結構不便。
ドンキに寄ったら安くバナナが売っていたので20本ほど買った。皮の色がくすんでいる気もしたが、食べてみるとなかなか甘い。ドンキが熟した頃合いを見計らって売るわけがないと見くびっているため、店で売れ残っているうちに食べごろになったのではと考えている。まあ自分にとってはいい買い物だった。
毎日バナナ健康生活 pic.twitter.com/ZjWzsFcNPr
— こたつがめ (@kotatsugame_t) 2024年2月27日
午後11時帰宅。半からCF #929 div.3に出た。
Dashboard - Codeforces Round 929 (Div. 3) - Codeforces
Aは絶対値の総和。Bは場合分け。Cはを全探索。Dは最初
に注目して考えていたが、その議論は最小値に対して一般化できる。最小値が一つなら可能、二つ以上のときも最小値の倍数でない数があれば可能。それ以外は不可能であることも示せる。Eはパフォーマンスの増分が負になるセクションを含むトラックを探し、その周辺で実際に計算してみる。
Fは岩を動かす代わりに自分が下に1マスずれるものと思う。岩に対する相対位置が同じならできるだけ早く到着すべきなので、BFSが正当となる。上への移動はその場に留まる遷移となるため、右端に到達してゴールと重なるのを待つときだけ行う。ここで、岩だけ動かしているのでゴールマスは下に1マスずつずれていくのだが、岩と一緒に上にずれると勘違いしてかなり手間取ってしまった。
Gはサンプルが最初から8パターンしかないと言っているので全部チェックする方針が立つ。手で試していたらそれらのパターンを特定できた。という制約がそれらのパターン以外を排除するのに十分大きいと信じて提出。
全完7位。Gはを全探索して8パターン見つけるのが安全だろうか。手での実験だと、自分は左上マスから適当に埋めていたが、十分に広いグリッドの中央から始めて
に3マス同じ形があったとき矛盾することを確かめるのが良いらしい。
その後はずっとカクヨムを読んでいたが、寒くて布団に移動したところそのまま寝落ちした。午前8時前。
02/28(水)
午後3時から3時間ほどカクヨムを読んでいたらしいが、本格的な起床は午後8時。
昨日からは最近追えていなかった作品を最新話までと、同じ作者の新作を読んでいた。後者の「神ゲーに転生したけど人生はクソゲーだった」も起きて少しで読了。この作者が描く主人公の態度が好み。何事に対してもどこか適当な感じで、しかし圧倒的に強い。
布団から脱出し、セミナー準備を開始。興が乗って翌日までずっと続けていた。今読んでいる論文はself-containedなのにたった7ページ。その分行間は自分が経験したことのない広さだが、本当に重要な式はちゃんと書いてあるし、間違いもほとんどない。読んでいてワクワクするようなものである。
午後1時過ぎに学食で昼食を摂り、ラノベを受け取ってきた。セミナー準備の今できているところまで先生に送り、午後3時就寝。
02/29(木)
午後11時起床。今日は4年（正確には4年強）に一度のうるう日だが生活リズムの関係からもう終わりかけ。半からCF #930 div.1に出た。
Dashboard - Codeforces Round 930 (Div. 1) - Codeforces
書く：CF
朝までセミナー準備を続けていた。これまで用意した分で内容の量としては十分だろうが、論文自体はまだ読み切れていない。昨日送ったメールに対する先生の返信では最初に全体の流れを聞きたいと書いてあったので、それに答えられるようにしていた。
午前7時過ぎにシャワーを浴びて布団へ。明日のセミナーは正午開始。しかし寝る前になぜか2時間近くスマホを眺めてしまった。
03/01(金)
午前11時半起床。本当は30分前に起きるつもりだった。セミナー開始まで時間がなく、地下鉄で登校すると間に合わないだろう。外がよく晴れていたので久しぶりに原付で山登りすることにした。路面が濡れていたのでスピードは控えめだったが、山道を走りながら昨年以来の景色を眺めているうち2月＝冬を越えて3月＝春がやってきたことが実感され、清々しい気持ちになった。
余裕を持って教室に到着。予定通り正午から2時間ほどセミナーを行った。全体の流れについてはおそらくそれなりの感じで喋ることができたものと思うが、今週頑張って準備してきた細かい内容についてはほとんど触れられなかった。ただせっかく準備したので、これから数週間かけてじっくり話していく予定。
午後4時から論理学セミナーに参加するよう言われていた。それまでの時間は今日そこで話す先生が来て詳しいことを語ってくれるはずだったらしいのだが、トラブルで来られなくなったとのこと。それで空いた時間は図書室から借りていた本を返しに行ったり先生と話したりしていた。
時間が来たので建物を移動してセミナーへ。この内容は……ほとんど何もわからなかった。専門でないものを英語で発表されると聞き取るのすらおぼつかない。さらに板書の文字も汚かったため手も足も出ず。ただ、つい先日の日本数学会東北支部会で聞いた発表とほんの少し重なっていたところがあったようで、奇遇だなと思った。
学食で食事して午後7時に帰宅。学位記授与式のため実家に置いてあったスーツ一式を送ってもらったのだが、荷物の底にチョコとうなぎパイが入っていた。この年になっても貰えるというのはありがたいものだ。
母からバレンタインのチョコが届いた pic.twitter.com/Nm98Ee8oNq
— こたつがめ (@kotatsugame_t) 2024年3月1日
2月の読書記録をツイート。先月もなろうにすべてを捧げてしまった。おそらく今月もそうなるだろう……。
2月の集計
— こたつがめ (@kotatsugame_t) 2024年3月1日
買った：30冊
読んだ：3冊
積読：+27冊
積読（累積）：+63冊
しばらく日記を書き、午後9時20分からyukicoder 419に出た。
yukicoder contest 419 - yukicoder
Aは二つの軸に分けた後どうすればいいのか分からない。大きな値から貪欲に使って半々に分割しようとしてみたところWAだったので、何か条件を考えることにした。奇数のほうは奇数個あると無理、偶数個あるとできる。偶数のほうは2で割ると連番になるから、その総和が偶数なら必ず可能。これで通った。
Bはよりスライムの移動が交差するならマージしてしまったほうが得であるため、dpで解ける。
Cは下の行から順に答えを求めていった。各マスについて、同じ行で障害物に阻まれず移動できる区間を尺取り法で求め、それに応じてセグ木に値を乗せておき、二分探索でボタンを押す回数を求める。セグ木上の二分探索が使えなさそうだったので毎回かけたが、400msとかなり速い。
Dは微妙に制約が小さかったのでを出したら6600msで通った。prefixとsuffixのXORをカウントすることにして、調べる位置をずらしながら差分更新していく。テストケースが多いのでいつTLEするかとハラハラドキドキしながら見守っていた。
この後はずっとEを考えていたが本当に何もわからない。途中で寝そうになったのでシャワーを浴びて眠気を覚まし、午後11時半からのCF #931 div.2へと逃亡した。
Dashboard - Codeforces Round 931 (Div. 2) - Codeforces
Aは式をぐっと睨むと最大値二つと最小値二つの差の2倍だとわかる。Bは適当なところまでdpして残りは15円連打でよさそう。真面目に見積もろうとしてよく分からなくなったため、105までdpしておいた。Cは左上・右上・左下を聞くことでmineの乗る線分が3本得られ、その2交点のどちらかには必ず存在する。正確には1本に退化するケースもあるが同じ。
D1は立っていなかったbitを立てるのに、そのさらに上に「1→1」と「1→0」の2パターンのbitを用意しておく必要がある。もともとならよし、そうでないなら「0→1」のbitのうち一番上を探し、その上に2パターン用意できるかチェックする。「1→1→0」と「1→0→0」を使い2手かけて遷移させるケースもあることに注意。
D2は問題も解き方もD1と似ているとはあまり思わなかった。実験するとのpopcountが偶数なら先手勝ち、奇数なら後手勝ちだと分かる。ところがそこから自分の手を実装するのに大苦戦。popcountを等分しても奇数になるとは限らないことを忘れ、63回より多く操作できないことを忘れ……。全部サンプル1で落ちたのでペナルティにならなかったのだけは助かった。最上位bitとそれ以外を分けるのが正解。
Eは後半個を3個ずつ組にして操作し、LCM二つのGCDで元の数が得られるようにするのだろうと思ったが、肝心の組を作る戦略がわからず。D2までで27位。
日記を書いて午前6時就寝。
03/02(土)
ICPCプレーオフのミラーに出るため午前11時少し前に起床。ところが30分延期されてしまった。二度寝すると寝坊しそうだったので日記を書いて待った。
ソロ参加でコピペなし。結果的には検索もしなかった。HCJGEFKをこの順で解いて33位。
Aを読んでしばらく唸っていたが、難易度順ではなかったらしい。しばらくしてHが解かれ始め、そこからは自分もsolved数の順に取り組んでいった。
Hは人数が少ないほうをどこかに移動させる。ただしすべてのテーブルで人数が少ないほうが同じメニューだった場合はそのために一つテーブルを確保する必要がある。さらに全員が同じメニューを頼んだ場合はその処理を行ってはならない。なんだか2段階のコーナーケースがある感じだった。
Cは生成される数列の階差を観察した。それ自体特徴的な形をしているが、解法に繋がったのは階差がであるのと直後の数の下
bitだけが0になっているのが同値だという事実。つまり階差が最小値を取るところを探せば、上のほうのbitは他で変化しないため、そこの数が
1...10...0のような形になるのが最小とわかる。あとは実際に復元してチェックした。は別処理。
Jは行きを最短経路としても損しない。帰りに寄る辺を全探索した。Gはを固定し、各問題に対し同じ文字を回答した人をリストアップしても間に合う。鳩ノ巣原理からここで
個より多く見ることになった場合その時点で答えが確定する。
Eは順列を壊す。順列である行と列のうち多いほうの数が答え。基本的にはインクリメントでずらし、ダメだった場合1マスだけ追加でもう一回インクリメントすれば、よりうまくいく。
Fは難しい。約数を全探索し、
を入れる場所をずらしながらグループのスキルレベルをセグ木に乗せようとした。これは
であり間に合わないようだ。何とか
を落とそうと考えた結果、左右からの累積を求めることにした。挿入箇所がどんどんずれていくだけなので、右か左の値はずれる度に一つずつ修正していける。もう片方は
回に1回
で修正すればよい。
Kはまずが確定する。次いで
の祖先とそれがLCAとなる
の個数を持ち、二分探索することでLCAが決まる。最後に
だが、これはオイラーツアーにおける高々二つの区間のうちから選ぶことになる。rangefreqで個数カウントすることで二分探索が可能。
三つだがエイヤと書いたら通った。二分探索付きBITとrangefreqの写経も含め26分でかなり順調だった。
次にLに取り組んだ。後ろのほうから次元を求めればよいかと思ったものの通らず。立て続けに4WAくらいしたところで午後2時になったため一旦DDCC予選に移った。このために焦っていてよく考えずに提出してしまった。まあ結局ここのペナは何も関係なかったのだが。
ディスカバリーチャンネルコードコンテスト2024 | Discovery Japan ディスカバリージャパン
こちらはあまり言うことがない。1問目はやるだけ、2問目は多少面倒なパース、3問目はちょっとした幾何、4問目は少し捻ろうとした感じのナップザック。26分弱で全完した。3問目でライブラリの写経ではなくコピペを行えばもう少し速くできたかなと思う。ネットに公開済みのコードをそのまま使うのが少し怖かった。
後からTLを見ていた感じ、入力を受け取るところで苦労した人が多かったようだ。自分はトップページの注意書きを熟読していたためソースコードに直接コピペできることを知っていた。D問題は文字列と数値が同時に出現して少し面倒そうだったが、適切な構造体を定義しておくとそのまま使えることに気づいた。ここは少し気持ちがよかった。
ICPCミラーに戻ってLとの格闘を続けたが全然わからない。なんとそのまま2時間椅子を温め続けて終わった。Fはとして素因数だけ見ればよかったらしい。
Lに向き合っているうち眠気が耐え難くなってきていたので、午後5時から午後8時半まで仮眠。起きて午後9時からABC343に出た。
AtCoder Beginner Contest 343 - AtCoder
Aを見てちょっとギョッとした。を出力。Bは
なる
を順に改行区切りで出力してもジャッジがよしなにしてくれる、と思ったらWAが出てしまった。今回はちゃんと空白で区切る必要があったらしい。まあ理解はできる。Cは106まで全探索。Dはmapで頻度配列を持ち、0になった要素を逐一消す。
Eは大変。立方体たちをギチギチに詰めてもよいので、にどう配置するかという問題になる。ここで立方体を一つ中央に固定しても良いことに気づいた。すると全探索ができるようになる。体積については包除原理で求まる。
Fはセグ木に乗る。Gは文字列たちに包含関係がないよう前処理をすると、直前に置いた文字列とどれだけ重ねられるかという話になる。前計算しておいてbitDP。前処理も前計算もZ-algorithmでできる。
1ペナ全完、3位。Bのつまらないミスさえなければ……。普段はそういうところも丁寧にやっているのだが、今回ばかりはB問題でわざわざ手間暇かけるのが馬鹿らしくなってしまった。Eで立方体を固定する位置が中央ではなく角だとWAになるらしい。どのようにずらしても角に立方体を寄せられない位置関係が存在するようだ。正直何も考えていなかったので運がよかった。
コードゴルフはABCD。Aはdcでとしてみた。テストケースハックで5B。しかし
でも同じく5Bが出る上、Nibblesにはさらに
という4B解もあった。Bは
`?_1で一発。各行ごとに1のインデックスを全部探してくれる。こうなるとで1行目を読み飛ばさなくて良くなっているのがありがたい。CはNibbles、DはAWK。
少し日記を書いた後、TUPCのテスター作業をした。午前10時くらいに一段落ついてなろうへ。今週はほとんど読み進めていなかったが、このタイミングでついに以前読んだことのある最前線に到達した。
午前11時就寝。
03/03(日)
午後8時半起床。しばらくなろうを読んでから布団を脱出し、UTPCへの参加登録をした。いずれUniversal Cupに収録されるらしいからrisujirohさんと現地でチームを組む。たまにはこういうのもいいだろう。Nyaanさんは残念ながら来られないらしいのでオンラインで。
PCを眺めていたがまた眠くなってきた。布団に戻って午前1時前には就寝。本当は今日、インターンの作業を進めたかったのだが……。
今週はなろうを2608話まで読み進めた。実はちょっと興味が離れたタイミングがあって、その時ちょうど面白い論文を読み始めたためそちらに掛かり切りになっていた。
そういえば、先週も今週も火曜日・水曜日あたりに布団の上で一日を終える日がないよう意識して行動できていた。しかしその反動か知らないが代わりに日曜日が消えてしまっている。たまたま2週連続コンテストがなかったこともあるだろう。平日は気合いで耐え、土日はコンテストに没頭することで何とか週七日きちんと活動したいところだ。
