07/03(月)

午後4時半起床。すぐインターン先定例会に出席した。

進捗はほんの少し。先週は別部署の方とやり取りする必要があって、日記では特に触れなかったものの神経をすり減らしていた。今すぐ必要なわけではないがそのうち必要になる、ただし自分の進捗状況によって「そのうち」が平気で数か月前後してしまうようなものを頼むのは難しい。せっかく用意してもらったのに塩漬けにしてしまったら心苦しいから、自分が待つことを受け入れてこちらの準備が整ったらまた連絡することにした。

作ったデータセットのファイル名にハッシュ文字列を使っていたところ、元データがわからなくて困るという話が出た。正確には結構異なるシチュエーションだがどこまで説明して良いのかわからないのでこれで。データセットを作るまでが自分の仕事になっていて、使う側のことを全く考えていなかった。そもそもデータセットの個々のデータを人の手で確認するケースがあるとも思っていなかった。

その後の勉強会は今日こそ自分の発表。スライドに書いてないことを補足しようとしてしまうのは変わらないが、今回はまず書いてあることを書いてある順番で話すということに注意していた。それでもページ数が少ないため30分もかからず終了。

その割に質問が活発で嬉しかった。正直ソースコードに書いてあったコメントを読んだくらいの知識しかなく、組み込みシステムでは実際はどう動いているのかとか、暗号のアルゴリズムは何をどうしているのかとか細かい部分には答えられなかったのが残念。後者については勉強会の方針としてそういう話を完全に省くとしても自分ではちゃんと調べておくべきだったな、と反省。

解散後にスライドを公開した。

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

勉強会をしました。今日のテーマは「/dev/random」です。スライドを公開します。https://t.co/Hz4e4S9PwN
— こたつがめ (@kotatsugame_t) 2023年7月3日

それから週記を書いて日付が変わるギリギリで投稿。今週はUniversal Cup部分以外は完成している。本当はTwitterがもしサービス終了したらどうなるかみたいなことを書こうとしたが、文章がまとまる前にタイムアップ。今からわざわざ書き足すくらいなら今週の週記で書くだろう。

来週水曜日の昼からホスフィンと昼食会→家飲みを行うことになったので、それに向けてAmazonで酒類やボドゲの注文を行った。今回は昼から集まって飲むので早々に死んでしまうことがないようにしたい。いつも無理して飲んだという自覚がないまま急激に気分を悪くしてしまうので、飲み方で予防するしかない。常に手元にお茶を用意しておくことを心掛ける。

1時間半ほどかけて、今日の定例会で指摘されたファイル名の件について対処した。

新しいTweetDeckが使えるようになったらしい。開いてみると更新されていた。以前使っていたカラムのうち「Activity」「Mentions」は存在しないようだが、概ね満足できる。自分はTLをあまり見ないので実はホームの「おすすめ順」を愛用していて、これがTweetDeckでも表示できるようになったのは素直に嬉しいと思った。

布団に入って論文を少しだけ読んだところで寝落ち。午前4時くらいだったはず。

07/04(火)

午後3時半起床。新しいTweetDeckはそのうちTwitter Blueに加入しなければ使えなくなる予定だということを知った。ぬか喜び。

サークルに出席してバチャに参加した。数週間前からICPC練習のためAOJ-ICPCの問題でセットが組まれており、今日もそれだった。ICPC前最後のサークルである。

https://onlinejudge.u-aizu.ac.jp/services/room.html#puzzleknot20230704

セットの中ではGが未ACだっただろうか。最小全域木っぽい問題だからどうせ貪欲だろうと思って出したら通ってしまっただけで、正当性はわかっていない。何かのマトロイドとして解釈しようとしても自分ではうまくできなかった。

また感想戦においてEが自明という感じで流されたのには唖然としてしまった。自分がこの問題を初めて通したときは一部解説を見ていたような記憶がある。ただ恥ずかしいので黙っていた。

感想戦終了後、今週末に迫ったICPCに関してしばらく雑談してから解散。学食で食事して帰宅し、少し休んでまた外出した。今度はゲーセンに行く。

まず2時間ちょっとniconicoフォルダの譜面に天地創造のクリアランプを付けていた。SUN PLUSからデンジャースキルを使ってのクリア状況がランプに表示されるようになったため、天地創造という最もハイリスクなスキルを使って簡単な譜面をプレイしていくことのインセンティブが存在する。しかし譜面が多くて切りがないし、niconicoフォルダの全譜面を天地創造でクリアできるかというと全然そんなこともないので、結局何にもならないんだよなあという気持ちは拭い難い。理論値はいくつか出た。

理論値 pic.twitter.com/yhZ5ZCFZkW
— こたつがめ (@kotatsugame_t) 2023年7月4日

あとは閉店までずっとLv.15の「To：Be Continued」をプレイしていた。終盤の運指についてYouTubeで見たのでお試し。なかなかいい感じに仕上がって噛み合い待ちになったくらいで閉店時間が来てしまった。残念。18連奏したうち最後の数プレイは本当に一か所上手くいっていればという感じ（しかもその一か所は毎回異なる）が続いていたので完全に波が来ていたのだが……。

退店前にトイレに寄って何気なく鏡を見たら、薄茶色のTシャツに首元の汗がめちゃくちゃ目立っていて赤面した。音ゲーをする際は薄い色のTシャツは避けるべきらしい。暗い色の服ばっかり着ているのオタク仕草だよな～と思って6月頭に明るい色のTシャツをいくつか買ったのだが、完全に裏目に出てしまった。

立ち食いそばを食べて帰宅。シャワーを浴びて日記を書き、午前5時過ぎ就寝。

07/05(水)

午前11時半くらいに目を覚ました後、4時間ほど布団で論文を読んでいたらしい。二度寝して今度は午後6時起床。少しハーメルンを読んだあとまた論文に戻る。

$\prod\sum$ を各因数から項を一つ取った積の和と見ることで $\sum\prod$ に書き換えていた。いかにも競プロチックな式変形で感動。自分はこれを積の和典型の一種だと思っているが、その典型はcombinationに書き換える部分のほうがインパクトが大きいだろうから用語の使い方としては微妙かもしれない。

日付が変わったくらいで布団から脱出。夕方先生からメールが届いていたようだ。今週金曜日のセミナーでは修論の研究計画について発表することになっていて、これに関してどのような資料を作ってきてほしいかが書かれていた。一応どんなことを調べたいかという方針は考えてはいるのだが、要求されているほどの具体性がなくて苦しい。前々からこの日に発表するということは決まっていたものの、期限があるからと言って決められるようなら苦労はしないわけで……。とりあえず進捗報告としてさっきまで読んでいた論文のことを書いて返信しておいた。

マラソンのほうのトヨタコンのためのホテルを調べた。参加登録フォームに交通費・宿泊費申請のための欄があるから、これを決めないと参加意思を表明できない。今回の会場「ベルサール渋谷ファースト」のある渋谷駅東側はちょうどホテルの空白地帯らしかったが、いろいろ探して何とか「そこそこ近く」「朝食付き」で「宿泊費を出してもらえるくらいの価格」のホテルを見つけ、予約した。かなり迷っていたのでフォームを送信したころには午前5時になっていた。

今日はもう閉店。布団に転がってしばらくハーメルンを読み、午前7時半就寝。

07/06(木)

午後1時前に起床し1on1に臨んだ。月曜日の定例会の話とその後の対応について説明し、残り時間で次のタスクを確認して合計ピッタリ1時間で終わった。

セミナー発表のための準備をするべきだが、やる気がびっくりするほど出ないのでatgolferの改修を行うことにした。4月の半ばくらいにDDoS対策で提出一覧を見るのにログインが必要になり、それ以来ずっと動いていない。Issueだけ立ててあったところについ最近ログイン方法に関するコメントを頂いたので、もうそろそろ対応しておきたかった。

github.com

2時間くらい格闘してコードの取得部分が完成。苦労したのはアクセスのリトライ部分で、例えばABC001の提出一覧ページは非常に重く頻繁にステータスコード500を返してくるから、時間を空けて何度かリトライしそれでもダメだった場合はエラーを吐くのではなく適切にスキップしなければならない。このあたりを慎重に書いていたら時間がかかった。

その間にAmazonで注文したボドゲが届いた。今回はBlade Rondo第3弾に加え、ホスフィンの提案で同じくDomina Gamesから二人協力プレイのできるものを買った。やはりイラスト含め雰囲気が良い……見ているだけでワクワクしてくる。

ムフフ pic.twitter.com/5HS26xTt9N
— こたつがめ (@kotatsugame_t) 2023年7月6日

いざ実行！と思ったら今度はツイート部分がうまくいかない。ここは以前新APIに対応したはず……と思ってTwitterの開発者ポータルを見に行くとbotがsuspendされていた。よくわからないが一回削除して作り直すといいらしい。そのようにしたらツイートできるようになった。

コードは全部完成したのでbotが動いているサーバーにデプロイしに行った。実行はcronで定期的に行っているので、スクリプトだけ入れ替えてしばらく待ってみる。しかし1時間ほど経過しても一向にツイートされない。不審に思いロックが取得されていないのを確認してコマンドラインから起動してみると、なんとImportErrorで落ちていた！新しく追加したdotenvがインストールされていないらしい。

さらに、pipでdotenvを入れようとするとエラーを吐いてしまった。実はサーバーの管理者アカウントのパスワードを忘れたためこれ以上の対応ができない。アップデートも溜まっていたことだし、せっかくだから全部投げ捨ててOSのインストールからやり直してみることにした。

再度セットアップしてpipで入れるところまで進めたが、また同じエラーを吐く。調べてみると必要なモジュールがdotenvではなくpython-dotenvだったことに気づいた。さっきうまくいかなかったのもこれが理由らしい。赤面しながら入れて、今度はcronではなく手元でちゃんと実行。ようやく完全に動作し、ツイートも行われ始めた。

しばらく見守っていたらツイート時にエラーが発生した。Too Many Requestsらしい。botのツイート数上限が月1500件というのは聞いていたが、実はこれは1日50件のことだったようだ。しょうがないので、更新を消化しきるまでしばらくは1日1回手動で実行することにした。今日はとりあえず終わりである。エラー時の終了処理が正しく行われているのを見れたのはよかった。

しばらくatgolferのツイートを見つつコードゴルフをし、午後11時半からCF #882 div.2に出た。

Dashboard - Codeforces Round 882 (Div. 2) - Codeforces

Aは1か所区切るごとに $|a_i-a_{i+1}|$ を一つ答えから取り除けると思えるので、値が大きいものから $k-1$ 個以外の和が答え。

Bは最小値が明らかに $(l,r)=(1,n)$ の場合である。 $f(1,n)$ が0でないならそれ以上分割できない。0の場合はbitwise ANDが0の区間に分割するのがvalidで、貪欲に分割を行うとグループ数を最大化できる。うっかり $f(1,n)$ が0でない場合も同じことをやってしまい1WA。

Cは $a$ の任意の区間XORを列に追加することができて、それ以外はできない。値域が2⁸なのでそれぞれについて達成可能か $O(n)$ かけてチェックした。振り返りをしている最中に解説のような証明を思いついたが、コンテスト中はほとんどエスパーだった。WAが出て冷や汗を流したもののチェックにミスがあって、解法の破綻ではなかったためセーフ。修正して出したら通った。

Dは $t(s)$ に現れる $s$ のインデックスを先頭に近いものから列挙し、順に1にしていくのが最適。列挙はsetを使うなどして行える。 $s$ に存在する1の個数 $c$ を数えておくと、列挙したもののうち先頭 $c$ 個を1にすることになるので、その区間にある0の個数が操作回数となる。BITにでも乗せておけば更新・取得ができる。列挙したものが $c$ 個未満だった場合余っている部分はどうでもよいことに気づかず1WA。

Eは大変。クエリの答えとしてどんな値が返ってくるのか調べてみたらかなりバラバラなことに気づいた。特に $a_i=a_j=a_k$ だったら値が確定し、そこから $(i,j,\ast)$ を聞いていくことで他の要素も特定できそう。 $n\ge 9$ の場合そのような三つ組が必ず存在するので、先頭9個の組み合わせを全部聞いて見つければよい。 $n\le 8$ の場合はそもそも全探索が可能。

ただ、 $a_i=a_j=a_k=1$ の場合は他の要素を特定しきれない。この場合は $(i,j,\ast)$ によって1かそうでないかがわかるので、2以上の要素だけ残して再度解きなおすことで特定できる。結局2以上で同じ要素のペアが見つかればよいので、自分は $(i,\ast,\ast)$ を使って4個の組み合わせを全探索した。2以上の要素が4個見つかった瞬間にこちらの計算を始めないとクエリ回数が $2n$ ぐらいになってしまう点に注意。一敗。

Fは実験のときに書いた表がたまたま答えへの近道だった。まず $n$ 項を1行に書き、それ以降は行を変えつつ左端を開けて $n-1$ 項ずつ書いていく。すると $a_1\dots a_n$ が寄与する項がそれぞれ表で三角形のような領域に広がっていることが分かった。ここから、あるいは単に実験結果から、 $a$ に現れる値は $a_1\dots a_n$ を円環状に並べた時のある区間のbitwise ORとなることがわかる。

区間の一方の端点を固定し、もう一方の端点を動かす。値が変化するのは高々30回であり、区間は狭いほうが対応するインデックスが小さいので、セグ木上で二分探索することで調べるべき区間を全列挙できる。これはつまり $a$ に現れるすべての数が列挙できているということであり、それぞれに対応するインデックスが計算できればクエリに答えられるようになる。

さっきの表を見ると、対応するインデックスが区間の右端と同じ列に存在するということがわかった。また何行目に存在するかは区間の幅と一致するらしい。正確には区間の右端が $a_1$ の場合は注意しなければならないが、とにかく単純な算数でインデックスが求まるようだ。

円環の2周目に突入する部分でミスして3WAを重ねたが、序盤のジャッジキュー詰まりで延長された15分の間に気づいて修正できた。何とかACして全完、11位。今回のコンテストは問題もなかなか難しかったし、自分のミスも多くて非常に大変だった。

www.youtube.com

ようやくセミナー準備に取り掛かり、しばらく研究計画をでっち上げるために調べ物をしていたが、もう全然ダメ。気を抜いてハーメルンを開き日間ランキングから「有効射程距離25バ身」を読んだ。まだ4話しかないものの幼年期が1話で終わっているのですでに本編に突入しており満足感がある。設定もいい感じだった。

syosetu.org

研究計画についてはもはやどうしようもないため、昨日読んだ論文について資料を作ってお茶を濁すことにした。午前8時くらいにひとまず完成。1時間ほどハーメルンを読んで寝た。

07/07(金)

午後3時起床。

今日はICPC国内予選の日である。大学に向かいサークルから出場するメンバーとしばらく話した。午後4時開始だと思っていたのでかなり急いでいたが、実際には半からだったので思ったより話す時間が取れて良かった。アイコンを貼るくらいだったらもちろんいくらでもやってもらって構わない。

pic.twitter.com/1j8gTQoBqa
— とりゐ(競プロ) (@torii_kyopro) 2023年7月7日

午後5時からセミナー開始。まず1時間ほど自分の発表をした。結局昨日用意した論文についての資料は使わず、一昨日具体性がないと書いていた方針について喋ったところ、やっぱり具体性がないという指摘を受けた。次は同級生の番だが当然ながら詳しいことは書かない。先生と話している時間が長かったので、その間に自分は先生が持っていた教科書をパラパラ読んでいた。

午後7時半くらいには解散。ちょうどICPCも終了した頃合いなので、参加場所となっていた教室に行って1時間ほど話した。

問題も見せてもらった。Dは個数が少ないので何でもできるだろう。ただし実装には苦労しそうだった。Eは今見ているペアの2数を状態と思うdpを考えた。2次元のテーブルをin-placeに更新していくとデータ構造で $\log$ つけつつ解けるのではないかと考えたが詰め切れていない。Fは少し考えた後すぐ解説を見たらちょうど考えていたことが書いてあってびっくり。しかしこういう形では解けたとは言えない。

打ち上げは辞退して帰宅し、午後9時20分からyukicoder 396に出た。

yukicoder contest 396 (Asakatsu Presents 2) - yukicoder

Aはよい。Bは問題文が長いが書いてあることを実装すれば通る。Cは思考停止してdp。Dは $a_2$ と $a_3$ を固定すると $a_1$ 、 $a_4$ となれる値が決まるのでカウントすればよい。EはbitDP。

Fは丸太の端点の間を直線で移動するような経路のみ考えるとしてよい。端点のペアを全列挙し、経路上にほかの丸太がないかチェックして辺を張ったグラフでワーシャルフロイドをする。チェックの際、経路とある丸太が端点を共有している場合にその丸太と交差しているとは判定しないように注意。

Gはbitごとに分解して考えると木dpで解ける。Hは選んだカードのみを辿りつつ表裏を決めるdpで部分列をインデックスで区別する場合が解ける。ここから普通の部分列dpと同様にカードを貪欲に選ぼうとするのは、単に遷移の範囲を特定の区間に絞ることになるため、区間和を取得しながら遷移していくことで元の問題も解ける。最初の提出はBITで $\log$ を付けたが問題なくAC。後から累積和に書き直しておいた。

最速で全完し優勝した。実は今日はwriter陣にコンテストの様子の撮影を頼まれていたのだが、思いがけずかなり良い成績を動画に残せて自分も嬉しい。次のコンテストが始まる前に急いで投稿した。

www.youtube.com

午後11時半からCF #883 div.3に出た。

Dashboard - Codeforces Round 883 (Div. 3) - Codeforces

Aは $a\gt b$ なるロープを切ればよい。Bは単なる実装。Cは直感的に $t$ の昇順に解くのが最適で、証明もまあできる。これで完数とペナルティを計算し比較する。Dは一つ下の三角形と共通部分の面積を求めて引いていく。求めるのには相似比を使った。

Eは $1+k+k^2+\dots+k^c=n$ なる $k,c\ge 2$ を求める問題。最初からE2の制約で解いた。 $c=2,3,4,5$ については二分探索で求め、 $c\ge 6$ のケースは $k\le 1000$ なので全探索した。

Fは実装がダルいだけの問題。mimicが変化するまで待ち、物体のタイプの頻度配列を見ることで、変化後のmimicのタイプが特定できる。そのタイミングで他のタイプの物体を取り除き、また変化するまで待つことで一意に決められる。Gは症状 $2^n$ 通りを頂点とし、薬で $m\times 2^n$ 本の辺を張ってdijkstraすればよい。

全完9位。

www.youtube.com

数時間ほどぼんやりとTLを眺めていた。

COSS2023というセミナーに参加するためお盆前に京都に行くが、混むから新幹線は早めに確保しておいたほうがいいと指摘された。同じく東北大から参加するsotanishyさんに一緒に行きませんかと声を掛け、了承を頂けたものの、これからしばらくは切符を買うタイミングがないらしい。広義明日の午前11時なら大丈夫とのことだったので、その時間に仙台駅で待ち合わせることにして慌てて就寝した。午前6時前だった。

07/08(土)

午前10時に起床し仙台駅に向かった。sotanishyさんと合流して切符を購入。行きは買えたが帰りはギリギリ一か月以上先なので買えなかった。まあ後泊のあるなしでそもそも帰る日が異なるため、ここは一緒に買わなくてもよい。セーフ。

少し時間があるらしいので一緒に食事を摂った。休日家から出ない生活を送っていたので知らなかったが、昼間ということもあって人混みがすごい。駅地下のレストラン街はどこも行列ができていたので諦め、ウロウロしていたところいい感じのお茶漬け屋を発見した。

食事 pic.twitter.com/Ql6cEDtcMB
— こたつがめ (@kotatsugame_t) 2023年7月8日

食後にアンパンマン像を撮った。撮っている自分も撮られていたらしい。スマホを構えたりポーズを取ったりする際無意識に常に膝を曲げてしまいへっぴり腰になるのは何とかしたいなあと思っている。

仙台駅を庇い石にされてしまったアンパンマン pic.twitter.com/7fN07MjiU3
— こたつがめ (@kotatsugame_t) 2023年7月8日

仙台駅を庇い石にされてしまったアンパンマンを撮るこたつがめさん pic.twitter.com/kSX3PH0N3i
— sotanishy (@sotasingularity) 2023年7月8日

解散してゲーセンへ。今日はひたすらLv.15の日だった。「To：Be Continued」のSSS+と「Invisible Frenzy」のSSSを出した。前者はLv.15では初のSSS+である。

To：Be Continued SSS+ pic.twitter.com/AI16xiSBB3
— こたつがめ (@kotatsugame_t) 2023年7月8日

火曜日の時点では噛み合い待ちになっていたはずなのに今日改めてプレイすると中盤も終盤もできなくなっていて大変だった。感覚を取り戻すのに30回くらいかかって、それまで毎回手元を撮影していたらスマホの充電がなくなってしまった。それからさらに10回プレイしてSSS+が出た。動画を撮れなかったのは残念だが、すべてが理想的に噛み合ったのでスコア的には大満足である。

運指は基本的に8分全押しである。そんなに速くないので、焦らずに少し遅らせるのを丁寧に行うべし。譜面を確認するとノーツの重なりがほとんどなくてかなりの部分をこれで解決できてしまうのには驚いた。具体的には69小節、81-82小節、105-16小節である。

他の部分についても書いておく。15小節のフリックは端まで擦ることを意識。このため最後のスライド始点は右手で取るべきだった。74小節は餡蜜しているわけではないがこれも全押し。その後は右手でジグザグに擦りながら左手で他のノーツを押していく。

85小節は前半は頑張って押し、後半は2鍵ずつ餡蜜して交互で取った。103-104小節は結局よくわからないまま通した。押せないし擦り運指も定着していなかったため運ゲーの域を出ていない。

105小節以降は譜面をほとんど見ず覚えた運指に全てを賭けた。まず裏拍から入って11回8分全押し、次に蟹地帯のような手の動きを5回、最後に餡蜜で両手トリル。ここも運ゲーであった。

残っていた手元のうち中盤までがそこそこ上手かったものと終盤が上手かったものをツイートした。中盤はここから運指を全押しベースに変えたが、終盤はだいたいこのままである。

To：Be Continued 手元
（前半と後半は別の回です） pic.twitter.com/Zngs5PFYxD
— こたつがめ (@kotatsugame_t) 2023年7月8日

Invisible Frenzy SSS pic.twitter.com/nrVitmNeoM
— こたつがめ (@kotatsugame_t) 2023年7月8日

こっちは3回で出た。27-29小節と35-38小節は全押し。めちゃくちゃ速いので、あまり手を広げないようにしたり、腕の力を抜いたり腰を落としたりしてとにかくリズムキープに注力した。127-132小節は右手で連打しつつ左手を上げ下げ。左手は偶数回目だけ押せばいいらしいが、譜面をろくに見ていないので初音ミクの消失ラストみたいに1回エアーを取って3回押すのを繰り返していた。無駄に疲れていたらしい……。最後のトリルは人間には追い付けない。ここで1ミス出してしまった。

午後5時帰宅。睡眠時間が足りず疲れ果てておりシャワーを浴びたらすぐ仮眠に入った。目覚ましを何度もかけていたがなかなか起きられず大変。午後8時半に何とか起きて撮影準備を整え、ABC309に参加した。

Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309) - AtCoder

Aは一読してダルすぎ！と叫びそうになったが、よく見ると左右に隣接しているかのみ判定すればよいらしい。これなら簡単である。Bは今度こそダルい。チマチマチマチマずらしていくしかない。

Cは $a$ の昇順にソートして、飲む薬の量を減らしていきながら $K$ 以下になるタイミングを見計らう。Dは重み付きで最短路を作る問題を見たことがある。ただこのレベルなら既出だろうとそうでなかろうと大して変わらない。やるだけ。Eもやるだけ。

Fはまず箱を回転させていると思って $h\le w\le d$ となるようにソートできる。こうすると以降回転を考えなくてよくなる。箱を $h$ の昇順に見ることにすると $(w,d)$ に関する問題になって、これは $w'\in[1,w)$ に対する $d'$ の最小値が求められれば解ける。 $w$ を座圧してセグ木のインデックスにすればよい。

Gは $|P_i-i|\lt X$ なら値のうち周囲 $2(X-1)+1$ 個の使用状況を持つdpで解ける。実際は条件が逆だが、条件に違反すると決めたインデックスの個数を持ってdpし、包除原理を行えば対応できる。

Exには70分ちょっと残したが解けなかった。鏡像法だろうなというのはすぐ分かったのに、そこから先に進めず。7完22位。

コンテスト終了直後にExの解説を読んで、自分が鏡像法を正しく扱えていなかったということに気づいた。鏡写しで負の始点を置いた後、さらに向こうにまた鏡写しで正の始点を置き、以下同様に無限に続けなければならない。ここを自分は負・正・負の三つだけで十分だと勘違いしていた。

この差は $M+3\le N$ くらいになると答えに関係し始めるから、サンプル2まででは気づけない。実はコンテスト中かなり長い時間をかけてサンプル3を計算しており、それが合わなかったのだが、大きすぎる数だからどこかで壊れているのだろうとあまり気にしていなかった。壊れているのは自分の頭だったのである。愕然としつつupsolveした。

コードゴルフはA、C、E。Aはdcで、テストケースハックしたら $B\le A+(A\bmod 3)$ で通った。CとEはPerlで適当に。

www.youtube.com

朝までTLを見たり日記を書いたりした後、布団に転がって2時間ほどハーメルンを読んで寝た。午前8時就寝。

07/09(日)

午後7時起床。日記を書いて時間を過ごし、午後9時からARC164に出た。

AtCoder Regular Contest 164 - AtCoder

Aは「ちょうど」 $K$ 個というのを見逃し、 $K$ 個以下だと勘違いして1WA。実況のため声に出して問題文を読んでいるのに何たる体たらくか。本当にガックシ来てしまった。

改めて考えなおし、すべて $m=0$ の状態から増やしていくことにした。増分 $3^m-3^0$ は必ず偶数だから、 $N-K$ も偶数である必要がある。もしそうなら、 $(N-K)/2$ を $1,4,13,\dots,a_j,3a_j+1,\dots$ という額面のコイン $K$ 枚以下で支払えるかという問題に書き換えることができる。貪欲法で最適解が求まる条件が成立するので、それで実際に計算してみればよい。

qiita.com

Bは辿る経路をサイクルとなるように取れる。するとそのサイクルは長さが奇数で、最初にちょうど1辺だけ端点の色が同じになっている。この存在性を判定するには、 $c_a\ne c_b$ なる辺 $(a,b)$ でグラフを作り、 $c_a=c_b$ なる辺 $(a,b)$ の端点同士が連結かをチェックすればよい。

CはAliceが表 $\le$ 裏なるカードを裏返した瞬間Bobがすかさずそれを取るという行動が強そう。カードが1枚減っただけで状況はほとんど変わらず、またBobは損をしていない。よってAliceは表 $\gt$ 裏なるカードしか操作したくないはず。もし $A\gt B$ なるカードが偶数枚あるなら、AliceとBobが半分ずつ裏返したり取ったりした後、残りのカードがすべて表 $\le$ 裏の状態になる。よってBobは一切損するタイミングがないので、答えは $\sum\max(A_i,B_i)$ となる。

$A\gt B$ なるカードが奇数枚ある場合、Bobは一度だけ損しなければならない。損とはカードを小さい数字の面で取ることであり、これによって先ほどの解から $|A-B|$ だけ得点が減少する。つまりBobは可能なら $|A-B|$ が最小になるカードで損をしたいのだが、実はこれは常に可能である。以上で解けた。

Dはボールが消滅しても他のボールに対する $F$ の値は変化しない。つまり移動の向きが変わらないから、互いに打ち消しあって消滅したボールのペアについて、そのインデックスの差の絶対値が二つのボールの合計移動距離に一致する。

まず初期状態の $F$ を考えてみた。自分より左にある電荷の和を変数に置けば、右にある電荷の和もそれで表せて、 $F$ の正負が1変数の条件で書ける。この変数の値は結局 $\pm 1$ の累積和であるから、その値でジグザグのグラフを書き、各ボールが左右どちらに行くかを重ねた。するとほとんど括弧列のマッチになることが発覚。正の部分では+と-が、負の部分では-と+がこの順でマッチする。

インデックスの差を求めるには、ボールのペアのうち先にあるほうに負号をつけてインデックスを足し合わせればよい。だから今のインデックスの寄与が累積和の値によって定まる。例えば+を置くときは、直前の累積和が非負ならインデックスを引き、負なら足せばよい。これでインデックスと累積和の値を持つ $O(N^2)$ のdpが書ける。

Eは結構面白かった。勝手に0-indexedの半開区間とする。セグ木がどのようにクエリに答えているかというと、与えられた区間をノードが対応している区間のdisjointな和に分解しているのだ。深さ $d$ にあるノードは $[0,N)$ を $2^d$ 個に分割した区間を担当するから、これらで $Q$ 個のクエリすべてに答えられれば深さ $d+1$ 以降は調査されない。

クエリ $[L,R)$ の（ $0$ と $N$ 以外の）端点を全部集め、重複を取り除いたものの個数を $n$ とする。この $n$ 個を $2^d$ 個に分割された区間の境目 $2^d-1$ 個で覆うということで、 $n\le 2^d-1$ を満たす最小の $d$ が求めるものとなる。

あとは $c$ について。深さ $d$ の区間はあまり調査されたくないから、できるだけ深さ $d-1$ の区間で対応しておきたい。そこで、あらかじめ $2^{d-1}$ 個の区間を用意しておき、そこから $n+1-2^{d-1}$ 個選んで分割することで $n+1$ 個の区間を作ってクエリの端点を全部カバーする、と考えた。

つまりクエリの端点たちから分割位置を $n+1-2^{d-1}$ 個「隣り合わないように」選べばよい。分割位置 $x$ を選ぶと、 $L=x$ または $R=x$ なるクエリのみが分割後の二つのノードを調査しに来るから、ある分割位置を選んだ時のコストというのが計算できる。この総和が $c$ であり、あとは $O(N^2)$ のdpで解ける。