週記(2021/08/23-2021/08/29)

08/23(月)

先週の日曜日は、週記を投稿してから布団に入り、少し本を読んで寝た。午前6時半だった。

午後1時起床。ワクチンの予診票を印刷して記入し、家を出る。まず大学生協でゼリー飲料をミールカードの1日分限度額いっぱい、6パック買った。ゼリー飲料はもともと好きだが、こういう機会でもないと食事としてたくさん買い込むのはためらわれるので、ちょっとワクワクした。地下鉄に乗って駅前まで出て、丸亀製麺で昼食を済ませる。今日も仙台駅にあるアンパンマンの石像を写真に収めた。

ほぼ予約通りの時間に接種会場に到着。今日は1回目のときよりも人が少ない気がするが、タイミングの問題だろうか。問診で、1回目の副反応で腕の痛みがひどかったことを訴えたら、氷嚢で冷やすくらいしかないと言われた。これは冷えピタではいけないらしい。氷嚢と冷えピタで患部を冷やすメカニズムが異なるというのは、あまり意識したことがなかった。

特に問題なく接種完了、15分経過観察して接種会場を去る。薬局に寄って冷えピタと解熱剤を買う。解熱剤がどこに売っているのかわからなくてしばらくウロウロしていたが、レジに立っている人が薬剤師さんだったらしく、話しかけるとレジの後ろにある薬棚からいろいろ紹介してくださった。先週の週記ではカロナールがいいのかもと書いていたが、置いていないようだし、薬剤師さんのおすすめを買うべきだろうと思って、結局イブクイック頭痛薬というものを買った。

まだ駅前で買い物を続ける。まずLOFTに入って洗面所にかけるための手拭きタオルを購入。前にもここで買ったことがあって、その時は1枚700円くらいのタオルしか見つからなかったのだが、今日は2枚組で1000円のタオルを発見した。次に本屋に行ってラノベを購入し、いよいよ帰宅した。

腕が痛くなることを見越して、帰ってきてすぐにシャワーを浴びた。その後、CF #739 div.3を解いた。

Dashboard - Codeforces Round #739 (Div. 3) - Codeforces

Aはよい。Bは-1を出力する場合分けが面倒だが、サンプルを合わせれば通る。Cも面倒なだけ。Dは適当に259まで調べたら通ったが、ちょうどそこまで調べればよいということに理論的な裏付けがあるらしい。つまり、答えが18桁以下となることが示せるようだ。Eは難しいと思ったが、まず文字が消える順番がわかり、各文字の出現場所を見てsとしてあり得るprefixを調べたら一意的に定まるのでOK。Fはよくわからない。出現した数字を10bitで持つ桁dpで解こうとしたがTLEしてしまった。まずF1は、10bitのうち高々2bitしか立っていないものだけ考えればよい。F2も同じ感じで計算量が削減できて、K\ge 7の場合は桁dpせず実際にインクリメントして探すことにしたら、639msで通った。想定解はprefixを固定してなんやかんやするらしい。

午後9時になって、ゲノコン2021に出た。AtCoderのトップページからリンクを辿れないので、かなり不便。

Genocon2021 ー DNA Sequence Analysis Challenge - AtCoder

今日はA問題だけが公開された。問題を一読してy/ATGC/TACG/だと思い込み提出、WA。実は答えをreverseしなければならなかったらしい。sedでreverseは難しいので、bashを使う。その場合はsedを呼び出すよりtr ATGC TACGのほうが短くなる。10分間の提出制限を悶々として待ち、2回目の提出でACした。21B。

布団に入って本を1冊読了。「世にも美しき数学者たちの日常」で、院試の面接後に図書館で借り出したもの。面白くはあったが、数学科の院に進むことを決めた今読むと、いろいろ思うところがあって素直に楽しめなかった。あとは、数学が苦手な人間が数学の面白さを知る、みたいなことに興味を持てないのも大きい。

なんとなく熱っぽいが、体温を測ると36.4度だった。しかし寒気がひどい。タオルケットしかないので、それに無理やりくるまるようにして就寝。午前0時だった。

08/24(火)

夜中から朝方にかけて何度か寝たり起きたりを繰り返していた。記録を残してある。

まず午前3時半ごろに頭痛と喉の渇きで起床。脱水症状で苦しむ人が多いらしいので、意識的に水分をたくさん摂る。熱を測ると38.3度だった。腕や足が熱を持っていて、寒気という意味では多少マシになっていた。次に午前5時半ごろ、また喉の渇きで起床。38.5度だった。頭を少し動かすと頭痛がひどいので、ゼリー飲料を食べて頭痛薬を服用。さらに冷えピタを貼った。さらに午前7時半ごろにも起床。頭痛は収まったかと思ったが、やはり頭を動かすとかなり痛む。今になってようやく少しばかり汗が出てきた。38.5度。

それからしばらくはスマホを触っていた。ワクチン1回目の時は、どんな体勢でも左腕が痛くてたまらなかったものだが、今回はそこまで痛くない。やはり1回目接種の直後にしこたまチュウニズムをやったのがマズかったのだろう。しばらくpixivで小説を漁ったりYouTubeを見たりしたあと、昼前にまた寝て、午後3時に目を覚ました。37.3度。

しばらく布団でゴロゴロした後、いよいよ起きることにする。食欲は全くないが、頭痛薬を服用するために食事はしなければならない。ゼリー飲料でもよかったが、多少元気があるので生協の冷凍弁当を温めた。熱を測ると37.5度だったので、まだ微熱がある。

7セメスターに取った全学教育の成績が出ていた。定理証明支援系を実装して提出した論理学はAA、数理統計学はAだった。まあいい感じじゃないだろうか。結局GPAがいつ使われるのかわからないまま院に進もうとしている。AとかAAを気にする必要は、今はもうないように思われる。

先週金曜日のyukicoderの問題を少しだけ解いた。なかなか難しめの回だったようで、3問だけ。

No.1650 Moving Coins - yukicoder

操作回数はすぐわかるが、実際に構築するのがちょっと面倒。ほかのコインに邪魔されずに目的地までたどり着けるコインを優先的に動かし、それが動いたことによって新たに目的地にたどり着けるようになったコインを操作待機キューに入れるという、bfsみたいなことをして解いた。解説は右に動くコインと左に動くコインの操作範囲が被らないことを示していて、非常に頭が良い。

No.1651 Removing Cards - yukicoder

実験すると、最後に残るカードというのはある程度一定らしい。しかもそのようなカードの種類はそれほど多くなさそう。なので、うまいこと最後に残るカードだけを前計算して、クエリには二分探索で答えるという方針が立つ。前計算はちょっと難しい。カードを0-indexedにするとX_{i+1}-\left\lfloor\frac{X_{i+1}}K\right\rfloor=X_i+1なるX_{i+1}が計算できればよくて、僕はX_{i+1}=X_i+1とした後条件を満たすまでX_{i+1}\leftarrow X_i+1+\left\lfloor\frac{X_{i+1}}K\right\rfloorと更新し続けたが、解説のようにO(1)で求めることもできるようだ。

No.1653 Squarefree - yukicoder

ちょっとTLでヒントを見てしまったかもしれない。区間篩を使って\sqrt[3]{R}までの素数で割り算した後、残ったものが平方数かをチェックすれば十分。

午後9時になって、ゲノコン2021にB問題が追加された。

Genocon2021 ー DNA Sequence Analysis Challenge - AtCoder

今日の問題はいつものdp。復元がかなり面倒。この問題のFAが3分を切っているのはかなり驚きであったが、どうやら事前に予想して問題を解いておいたタイプのFAらしい。

夜になって熱が下がり、頭痛も収まったように思える。寝たり起きたりを繰り返していたので眠気もあるはずだが、ともかく思ったより元気なので、CF #740 div.1に出ることにした。

Dashboard - Codeforces Round #740 (Div. 1, based on VK Cup 2021 - Final (Engine)) - Codeforces

4完86位で2886→2844(-42)。コンテスト中はpredictorが動いていなかった(プロフィールページへのアクセスが禁止されていたことが原因らしい)ためわからなかったが、自分のレートが上振れしすぎていて、生半可な順位を取るとすぐ落ちてしまうような位置にいたらしい。

Aはよい。先手2通りとAliceが自分のサーブをどれだけキープできたかを全部試すことができる。これが場合の数を求めさせる問題であっても面倒なだけだったろう。Bはメモリが制限されていて、空間O(n)が許されないのか?と不安になったが、調べたら余裕だった。最初に貰うdpを書いたらO(n\sqrt n)でかなり時間がかかっていた。これを高速化するのかと途方に暮れそうになったが、配るdpのほうも試してみたらO(n\log n)になっていてびっくりした。後者のまとめ方のほうがより多くの要素をまとめられるようだ。

Cは、偶数番目と奇数番目をそれぞれ独立にソートすることしかできないことがわかる。後ろから2番目の要素を正しいものにするとき、どうやっても最後尾の要素と一緒に動かしてくるしかないので、その2つの最初の位置関係2通りで場合分けしてみると、どちらもちょうど5手で達成可能なことがわかる。その操作を使って後ろから2つずつ決めていくとちょうど\frac{5(n-1)}2手で達成可能なので、想定解であることに確信を持った。毎回の操作で愚直にreverseしてよい制約なので実装も簡単。

Dは難しい。まず操作列の情報から、出来上がったソート済みの列の大小関係において\ge\gtがそれぞれどこに入るかを決められる。それがわかったら、対応して適当に値をいくらか引くことですべて\geに置き換えることができ、そのとき答えは重複組み合わせで計算できる。よって問題は最初のパート、操作列の情報を処理する部分だけになる。\gtの場所を管理することを考えると、「y-1以上の値をインクリメントする」「yを挿入する」ができればよい。この方針からbitsetなどを使って解くこともできるようだが、思いつかなかったため別の方法で解いた。

まず、新しく挿入する要素を、以前のインクリメントが適用されていた場合の数に置き換え、最後に一気にインクリメントする方法を考えた。しかしこれは置き換え先のちょうど良い値を確保できず失敗。次に、操作列を逆から見て、インクリメントされる先をありうるすべての値に対して管理することにした。こちらは、例えばy=3での更新を考えると、(0,1,2,3,4)\mapsto(0,1,2,3,4)だったのが(0,1,3,4,5)に置き換わり、次にy=1での更新を考えると(1,3,4,5,6)になる。つまり、列の途中を抜き去るような形で実現することができて、これは双方向連結リストで効率よく実装できる。どこを更新すればよいかは、消されていない数字を管理するBIT上の二分探索で判定できる。

実装はちょっとだけ面倒で、テストケースごとに初期化することを許されていないので、更新された部分だけ最後にロールバックする必要があった。

コンテスト後はラノベを読んでいた。途中でatgolferを確認したら、先週日曜日の技術室奥プロコンのA問題が縮められていた。どうやら数式を弄って場合分けするのではなくて答えをスタックに積んでRで持ってきたほうが短くなったらしい。そのコードには縮む余地が残っていたので、そこを縮めて取り返した。

CFのシステムテストを見届けてからベッドに移動し、それからもしばらくラノベを読み続けていた。残り100ページを切ったところで眠気に耐えられず就寝。午前6時だった。

08/25(水)

午後1時半ごろ起床。もうちょっと寝ようかどうしようかと2時間以上ゴロゴロしていたら眠気が消えてしまったので、ベッドから身を起こした。

昨日読んでいたラノベを読了。「辺境都市の育成者」4巻。カバー折り返しの著者コメントに「5巻出せたらいいなあ」と書いてあって、お前……打ち切られるのか?と焦ったが、後書きを読んだ感じでは普通に出そう。よかった。この作者の文章は読みづらいということを週記で何度も言及してきたわけだが、今巻でも読みづらさに新たな発見があった。とにかくセリフや描写の文章を最後まで書かないのだ。例えばそれは、視点人物の驚きを表現するためであったり、ここまで書けばわかるでしょう?という感じで省略したり。

……ということをここまで書いて、改めて本を確認したところ、別にそうでもないような気がする。体言止めが多い気もしたが、主に戦闘シーンだし疾走感の表現と解釈できるだろう。この独特の癖がある文章は、一体何に由来するんだろう。これまで文体に注目していたが、実は単純にセリフ回しが特徴的なだけかもしれない。どうであろうと、読みにくさをこらえて読むだけの面白さは十分ある。

「東方遺骸王」の更新が来ていた。最近は旧作1作目の東方靈異伝の話をやっていたのだが、一区切りついたらしい。東方古代スタートのオリ主ものは、原作が始まったら自機組に対応して動く必要が出てくるので、存分に無双できるのは原作前と、あとはクライマックスにありがちなオリジナル異変のみとなる。そういう意味では今作も例に漏れず、この章では主人公の雄(?)姿があまり見られなくてちょっと残念だった。

章題が「東方靈異伝」になっていた。ついに旧作突入らしい。感慨深い。

週記(2021/05/17-2021/-5/23) - kotatsugameの日記

東方遺骸王 - ハーメルン

GCJ Tシャツが届いた。間違えてSサイズを注文してしまっていたが、着てみると案外Mサイズより体に合っていた。やはりアメリカとのサイズ感の違いは大きい。これまでずっとコンテストTシャツはMサイズを注文していたが、そんな中で同じくらい体にフィットしていたものがあったのも確かで、この違いはどういうことだろう?と確かめてみたら、TCO RegionalのTシャツだったから、日本サイズのMだったということか。

GCJ Tシャツのサイズ表記はSM、MD、LGなどと書いてあって何のことかよくわからなかったため、胸囲と身長の対応など調べてSMにしておいたが、どうやらこれらはSMall、MeDium、LarGeの意味らしい。これまでは確かMサイズを注文していたので、間違えてしまったか?

週記(2021/05/24-2021/05/30) - kotatsugameの日記

学食に行って夕食を食べ、図書館で本を返却して帰宅。山の上で借りた本を下で返せるとは便利なものだ。本当はこの本は暇つぶしにちょっと借りただけで、返却してから下山するつもりだったのが、下でも返せるということを聞いてそのまま読み通すことを決意した、という背景があった。

今日もゲノコン2021。今日はC問題のマラソンが公開された。

Genocon2021 ー DNA Sequence Analysis Challenge - AtCoder

largeで正の点数を取るのが非常に難しかった。今のところようやく100点くらい取れて、もう限界。方針としては、まずすべての文字列を部分文字列として含むような文字列を作り、適当に文字を削除しつつ一致する文字数が最大になるようにうまいことあてはめてみている。1回の計算にかなり時間がかかるので全然試行回数が稼げず、最初のほうは一気に100文字くらい削除したりしつつ山登り法で頑張っている。一度に削除する文字数を増やしたことが、largeで正の点数を取れるようになった改善点だった。

マインスイーパを久しぶりにプレイしてみたが、トラックボールマウスだと難しい。細かい制御が簡単になるかと思っていたのだが、今のところ(慣れていないだけか)全然そんなことはないし、大きな移動はどうやっても難しくて散々。ボールに指を突き立てるのがよいとアドバイスをいただいたがこれもなかなかうまくいかない。

トラックボールの掃除ということも指摘されて、調べてみたら、実は掃除だけならドライバなど持ち出す必要はなく、ボールを裏から押し込むだけで取り外せたらしい!取り外してみると信じられないくらいのゴミが溜まっていて、取り除くと格段にボール操作がスムーズになったが、逆に転がりすぎてまた操作精度が悪くなってしまった気もする。まあ練習あるのみだろう。今はもうそこまでマインスイーパに対するモチベがなくなってしまったが……。

ラソン問題に対する別の方針を思いついたので試してみたが、全然ダメだった。各文字のインデックスを管理して適当に±1する焼き鈍し、文字列の表現では'-'を適当に挿入したり移動させたりして焼き鈍す方針だったが、文字が左右に散らばりすぎてしまった。

日記を書いた後、ふと大学生協で本を注文しようと思い立った。買っていない新刊はそれほどなく、今日は6冊注文した。週明けに届くだろう。

布団に入り、ラノベを読み始めた。適当なところで切り上げて寝るつもりだったが、週末は夜よりむしろ昼間にコンテストが集中しているようなので、このあたりで生活リズムを1周させておこうという気持ちになって、とりあえずそのままラノベを読み切った。

「英国カノジョは“らぶゆー”じゃなくてスキと言いたい」。あまり面白くなかった。最近似たような話が多すぎて設定に既視感があるとか、ヒロインの好意が1巻時点ですでに駄々洩れになっているとかは大きな問題ではなく、主人公の初恋相手が悪女で、かなり不穏な動きをしていたことが受け入れられなかったのが一番の原因。主人公は初恋相手をまだ好いていて、逆に手玉に取られておもちゃ扱いされそうになっているという展開で、1巻からする話ではないだろうと思ってしまった。

そのあと別のラノベに手を付けたが、眠気に耐え兼ね午前2時就寝。

08/26(木)

消えた。

08/27(金)

08/26 午後10時半くらいに目を覚ます。CFで謎のテストラウンドが生えていたので出ようかと思ったが、眠気が勝った。

次に目を覚ましたのは、午前2時くらいだった。スマホでTLを眺めていたら眠気が消え失せたので、午前5時くらいになって布団から身を起こし、パソコンの前に座って開いていた問題の考察をした。

Submission #25355266 - CODE FESTIVAL 2016 qual A

ちょっと前に橙diffを何問か解いたとき、一緒に考察も大体終わっていて、しかし実装する前に飽きてしまったらしく、未ACのままだった。当時の考察を思い出して解こうとしたが、実装している最中に全然詰め切れていなかったことに気づき、そこからさらに数日空いた。

2×2マスの条件は、マス目の縦横の差を見て一致していることと言い換えられる。すでに値がわかっているマスから、その差分に関する条件を取り出すと、矛盾していないなら適当に0埋めすることで全体のマスについての縦横の差が復元できて、差を累積的に足していって縦が最小になり、かつ横でも最小になるマスの値が非負かをチェックすればよいと考えていた。しかし実際にやってみると、復元できるのはある種の連結成分ごとに限られて、いくつかの連結成分が成立していても全体で成立しているとは言えないかもしれない。適当に手で試してみてよさそうだと感じ、提出すると、ACできた。

解説では、差を取った後適当に戻して、マス(i,j)の値がx_i+y_jとなるようなx,yを考察していた。これだと、値がわかっているマスから復元した情報を元に、ストレートにマスの最小値が非負であることを確かめられそうだ。

数学基礎論の単位が出ていた。AAだった。レポートを頑張った甲斐があった。4年ゼミは通年の講義として扱われるので、火曜日に出た2講義と合わせて今セメスターの成績が確定したことになった。しかし3つしか講義を取らなくてよいとは!2、3年生のときの頑張りがあって今、4年生でこんなに楽ができている。

またマインスイーパをしばらくプレイしていた。ボールに指を突き立てるとよいというアドバイスは、ボールを強く押さえながら操作するのが良いということだと考えているが、なかなかうまくいかない。細かい移動でもすぐ積み重なってボールから指がずれていってしまう。頻繁に指を置きなおすのもタイムに影響がありそうだ。ということでこのアドバイスはうまくいかず、今のところは諦めてポインタの移動速度を1段階下げることで対処している。

何度かプレイしていたらそこそこ良い記録が出たので、動画をキャプチャしてTwitterに上げた。中級で21.69秒。

昼過ぎ、外出する。学食で昼食を食べてゲームセンターに向かった。道中は信じられないくらい暑くて大変だった。いつもゲーセンに着くころにはマスクがしっとりしていて、そのままプレイしてさらに汗をかくものだから、かなり不快感がある。替えのマスクを用意しておくのも手だろう。

今日の成果は12の理論値が1譜面、13のAJが4譜面。おねがいダーリンの譜面が追加されたとき、当時実力が同じくらいだったFFがポンと理論値を出していたのを覚えていたのでプレイしてみたが、かなり精度を取りやすかった。といっても10回ちょっとプレイしている。途中FASTが少し出るようになったので判定を前にずらしてみたところ、なぜかさらにFASTが出るようになってびっくりした。結局この譜面は±0.0でプレイするのが一番らしい。

たいぺーと合流して夕食に向かおうとしていたら、インターン先から電話がかかってきた。ゲーセンの中だったので、折り返し電話しますと言って静かな場所を探したが、周りも繁華街でどうしようもなく、結局壁に向かって耳を塞ぎながら通話する羽目になった。何とか聞き取れたので安心。

夕食はガスト。魚介類は意識しないと全然食べないので、今日はネギトロ丼を注文した。帰りに本屋に寄ったが、水曜日に大学生協で新刊を注文してしまったので店頭では買えず、歯がゆい思いをした。

帰宅してyukicoder 311に参加した。

yukicoder contest 311 - yukicoder

ABDEFの5完。Gはともかく、Cが全然わからない。solvedが100を超えていて精神にダメージ。

Aはよい。Bは\frac{B(B+1)}2-\frac{A(A-1)}2=\frac{(B+A)(B-A+1)}2と式変形して、B-A+1の値で適当に場合分けする。するとB\le A+1であることがわかるので、適当に素数を前計算したあと全探索でよい。次にCを開いたが、わからなかったので、BのHard VersionであるFに移った。こちらは制約が1010くらいになっている。素数を列挙するのは不可能だが、知りたいのは個数だけであり、Library Checkerの素数カウントの制約が1011なので、そこからライブラリを盗んでくれば通る。

Dは素因数分解して適当に二項係数の計算をする。Eは(A-0E)^m=Oと見て、院試のことを思い出して固有値0だの広義固有空間だの考えそうになったが、サイズの制約105を見て冷静になった。非零要素のことを列から行への辺だと思うと、行列の積はパスの集まりと見ることができる。これでグラフの問題に落ちたので、あとはそこから最長パスを探せばよい。トポロジカルソートしながら計算できた。

Cの希望が見えないのでGを考えていたが、急激に眠たくなってしまった。コンテスト中だがさすがに耐えられない。午後11時前、ベッドに倒れ込むように就寝。

08/28(土)

何度か目を覚ましたり寝たりしていた。朝方目を覚ますということに慣れておらず、かなり現実感が希薄。結局午前11時くらいに起床した。しばらくコードゴルフをして、学食に行った。帰ってきてから午後2時までは、FHC Qualの問題を読んでいた。実装は後回しにして、午後2時から日本橋ハーフマラソン 2021に参加した。

RECRUIT 日本橋ハーフマラソン 2021 - AtCoder

まずAに1Bの解を提出してFAとshortestを取り、続いてBのゴルフをした。ちゃんと40x40マスに並べて出力しなければならないようで、Vimが最短となった。改めてマラソンに取り掛かる。

まずAにとりあえずの解を出した。\frac K 2以上で最小のものを\frac K 2未満で最大のものに足して1回オーバーフローを起こす。起こせないなら\frac K 2以上の要素を未満のほうに回して同じことをする。これを一通り行った後、\frac K 2以上の要素をそれぞれオーバーフローさせて、余った操作回数では適当に2倍してみたりする。これで86216点だったが、周りと比べてかなり低いので、見切りをつけてBに移った。

Bは、性能が高い椅子だけを抜き出してパワーを1増やす焼きなましをした。40個抜き出すと156656点だったが、全体のちょうど半分、800個の椅子を抜き出すと191210点と急激に伸びた。実はこの時、過去のAHCで目にした解法を真似して椅子のパワーを0に戻す更新もたまに行っていたが、後に無駄であったことが分かった。実際、椅子のパワーを0に戻す更新の確率を引き下げた提出は194644点と少し伸びていた。

そのあとしばらくパラメータを変えて投げ続けていたが、全然変わらない。と、ふと、焼きなましの更新処理に間違いがあることに気づいた。今見ている椅子の動作音の範囲にほかの椅子が入っていたらその椅子のパワーは0にしなければならないが、ほかの椅子の動作音の範囲に今見ている椅子が入った場合は、その椅子のパワーを下げるにしても0にする必要はない。ここを直したら一気に209130点と1桁順位に入った。さらに、出力する直前に空いているマスがあった場合はそこの椅子を動作させることにしたら、209413点になった。

これまでTL目いっぱい焼きなましをしていたが、時間を短くしてもスコアにはほとんど影響がないようだ。なので、同じ焼きなましを15回行い、最良の解を出力するようにした。これで211058点となり、B問題の最終結果となった。

ここまででコンテスト時間は残り40分くらいであった。A問題でまともな点数を取れれば景品がもらえる可能性があるので、改めて挑戦してみる。値の大きいほうから順に相方を探して小さくしてみたが、全然スコアが出ない。ビジュアライザを見ると謎の挙動をしている。コードを読み直してみると、大量のバグが見つかった。不等号の向きが違うので値を大きくしてしまっていたり、更新前の値をそのまま参照しているため意図しない足し算をしたり。ここを直すとそれなりにまともなスコアが出た。相方を探す処理のループを増やし、そちらでは自分を2倍して試してみるという処理を追加して115146点。残り時間がほとんどないが、自分を4倍する処理も無理やり書ききってギリギリで提出したら、122478点になった。

終結果はA問題267位、B問題8位で積の順位は37位。景品は上位40名までは必ずもらえるので、何とか滑りこめたようだ。

コンテスト後に少しTLを眺めていたが、A問題は\frac K 2で分けるのは良くて、そのあと一旦0Kに少しずつ寄せてから、改めて0に寄せるのが良いらしい。そうでなくても、みんなある程度アルゴリズムで押していて、試行回数がどうのという問題ではなかったようだ。B問題は、動作させる椅子の集合を決めると設定すべきパワーがわかるので、動作させる椅子の集合を焼きなますと良かったようだ。これは非常に面白い。できるだけシンプルで根本的なものを焼きなますのが一般に良いのだろうか。

今日はこの後何もコンテストがない。電車で街に出て碧黴さんと食事した。土曜日の夜、この時間に出歩くのはなかなか新鮮な気持ち。赤達成のお祝いに日本酒を下さるという話を前からしていて、ついにそれを受け取った。

帰り道で別れた。ゲーセンに行こうとしたが、お腹がいっぱいなのでしばらくブックオフで休んでいこう、と久しぶりに入店した。棚を見ていると、文庫本でシリーズ11冊全部そろっているものを発見し、思わず買ってしまった。重い荷物を抱えてブックオフを出て、ゲーセンに向かった。今日は特に成果なし、素手だったのでスライダーが滑らなくて大変だった。2時間くらいプレイして帰宅。

atgolferに流れてきた更新ですごいものがあった。2数のbitwise andとしてありうる最大値を求めるのは上位桁から決めていけばよかったが、これは区間の左端を0、右端を2^{31}にした二分探索で実現できる。挙動を思い浮かべれば確かにという感じだが、これに気付くのはすさまじいとしか言いようがない。

Submission #25382467 - 技術室奥プログラミングコンテスト#6 Day1

Facebook Hacker Cup - 2021 - Qualification Round

今朝読んでいたFHC Qualの問題を実装する。提出しようとしたら、今年から入力ファイルがパスワード付きzipで渡されるようになったらしく、かなり困惑。自分のパソコンに7-zipが入っていたので事なきを得たが、エクスプローラーでできないことを要求されるとびっくりしてしまう。取り合えずaABcを解いた。このことは順位表からわかる情報だが、問題の内容に関する言及が許されていたかどうか記憶にないし、この日記が公開される時点でまだコンテストは終わっていないので、特に何も書けない。

Cを考えていたらうっかり意識を飛ばしてしまったので、素直に布団に入って就寝。午前1時だった。

08/29(日)

午前7時半起床。かなりまともな生活リズムになってしまい、夜中のコンテストに不安がある。なのでもう少し寝ておこうと布団でゴロゴロしていたが、全然眠れなかった。YouTubeを見たりなろうを読んだりしていた。

昼前になって起きだして、食事したりコードゴルフしたりした後、午後1時から技術室奥プログラミングコンテスト#6 Day2に出た。

技術室奥プログラミングコンテスト#6 Day2 - AtCoder

ABCDFHjKの4300点で11位。

Aはかなり迷走して、小さなケースを実験してようやく気付いた。挿入dpのようなことを考えれば自明。4分ちょっとかけて出したdc 15Bは、コンテスト後に見たところ、何とか最短を取れていた。Bは文字列の先頭に'A'をつけて、隣接する文字が異なるかどうかを管理することにした。適当に操作を言い換えると、前から貪欲に揃えるのが楽に書ける。Cは実験して規則性に気付いた。コードゴルフ的には、N=4のときの解としてサンプルにある[2,3,2,1]ではなく[3,1,3,1]を使うと、繰り返しになるのでちょっと短く書ける。Dは01を繰り返してYesが返ってくる文字列を作成し、後ろから削っていく。N=1のときに空文字列をクエリとして投げてしまい、WAを何回か食らった。

Eが解けなかったのでFに移る。FはD_1との偶奇の違いを見て、もし異なっていた場合はそれ同士でうまいこと構成しておく。最後に辺が規定量に達するまで重み最大の辺を追加する処理が面倒だった。1点、D_1=0のときに奇数長のパスを求められるとうまく構築できないケースがあって、それにも引っかかった。

次にKがたくさん解かれていたのでそちらに移った。二項係数をバラしてみると、前の答えに何をかければよいかがわかる。具体的には\prod(A_i+x)x^Mで割った形をしている。割り算のほうは適当に計算することにして分子を考えると、多項式を計算して多点評価すれば求める値が得られる。1次式の積を高速に計算する方法がわからず、logでも取ってみようかといろいろ調べていると、分割統治法で計算すればよいという言及を見つけたので、セグメント木に乗せてall_prodした。多点評価はうしさんのライブラリを盗んできたが、多項式が0と等しくなってしまった場合に配列外参照をしてしまうバグがあってREとなり、大変だった。適当に試したケースが当たらなかったらバグの原因は一生わからなかっただろう。

次にJ。500点は一瞬だが800点は全然わからない。多分速いんじゃないかと思って書いたコードは普通にTLEを食らってしまったので、部分点のまま放置。順位表を見る感じ解けそうな問題が全然ないが、気力を奮い立たせて問題を読んでいると、Hが解けた。操作をまとめると、隣接しない駒を選んでひっくり返したと見ることができて、値の最大化も含めてセグメント木に乗る。

コードゴルフはCをRubyで、DをPerlで。DのN=1のケースで空文字列をクエリにしない場合分けが難しい。

多点評価のハックケースをLibrary CheckerのGitHubにissueとして上げておいた。

github.com

またしばらくFHC Qual Cを考えていたが、結局解けずじまい。諦めることにした。

午後9時からABC216に出た。

AtCoder Beginner Contest 216 - AtCoder

7完。Eで詰まってペナが大変なことになったほか、Hが何一つわからなくてかなり衝撃的。

Aからやや面倒。最初どう実装したものか迷って、とりあえずsedで出した。BはRaku。CからC++。DはBFSっぽく操作可能なボールを管理する。Eは二分探索して落ち続けていたが、原因は、ちょうどボーダーとなるような値も使いながら計算していたからだった。ボーダーとなる値は最後にあまりとして使わなければならない。コンテスト時は結局stackを使い、値が大きいものから順にまとめて操作するように書き直した。FはAをソートして\maxとなるインデックスを固定すると、残りは部分和問題になる。Gはrでソートして大きいほうにできる限り詰めつつ構築したいが、これはsetで使っていないインデックスを管理すれば可能。

Gは牛ゲーらしい。なるほどという感じ。Hは解説を読んでいないが、LGV公式を使うらしい。それがわかっていてもまだACまでは遠い。

コードゴルフ。Aはdcになった。BはVimらしい。Cもdcだが、文字列を出力する代わりに12進数で適切な数字を出力するというのはなるほどなあ、という感じ。Dはakouryyさんのコードがとても上手くて唸らされた。各列を直接持っておいて、先頭要素を取りだしてみて1回目の出現だったら残りの列を保管、2回目だったら保管しておいた列と一緒に次に調べる列のqueueにpushする。縮む余地を発見したので縮めた。

Submission #25454127 - AtCoder Beginner Contest 216

EはRubyのコードをVimで書くやつ。似たようなコード片が何度か出てくるので、変なところで入力を中断して、直前に挿入モードで入力した文字列を再度入力するコマンドを多用すると短いらしい。FはとりあえずRuby

今朝早く起きてしまったので眠気がちょっと怖いが、CF combinedに出た。

Dashboard - Deltix Round, Summer 2021 (open for everyone, rated, Div. 1 + Div. 2) - Codeforces

6完97位、2844→2823(-21)。Fにかなり時間をかけてしまった。

Aはよい。Bはどちらかのパリティの要素だけ抜き出して前から順に並べ、元の位置との距離の和を計算する。Cはかなり迷走したが、括弧を±1と読み替えて累積和を計算したとき、谷として複数回出る値「だけ」をstackで管理するとそれなりに簡単に書けた。そこだけが何回も答えにカウントされる可能性があって、それ以外は累積和の変化を見るだけでわかる。Dは3要素のbitwise and/or 6通りを書き並べてみると、元の要素3つが一意的に定まることがわかる。これを配列の先頭3要素で行い、あとはそれとほかの要素のbitwise and/orをそれぞれ計算することで、すべての値を復元することができる。

Eは数列aのみに対する操作に言い換えると、±1で均せばよいとわかる。これまた括弧列を思い出すようなチェックを行えばよい。具体的には、累積和が区間の左端と右端で一致していることと、累積和の区間minが左端の値未満になっていないこと。操作回数の最少は、括弧列でいえば最もネストした括弧の数、累積和においては区間maxから左端の値を引いたものであった。Fは「ある部分集合が強連結成分となる」ようなdpを考えて除原理。3^Nのループ内部で、固定した強連結成分とそれ以外の頂点の間の辺を向き付けて係数を計算するところがO(N^2)かかるが、必要なインデックスだけ先に抜き出しておいたら1secを切った。

今日は合計で10時間近くコンテストに出ていたらしい。夜中、眠気に耐えつつ日記を書いていた。来週からいよいよインターンだ。日記に書いてよいことと書いてはいけないことをしっかり区別するようにしたい。