2024-12-24

ICPC 2024 Asia Yokohama Regional 参加記

ICPC 2024 Asia Yokohama Regional にチーム Screenwalkers の一員として参加しました。練習や本番の様子を記しておきます。

練習

特筆すべき点はあまりないかも。自分が駒場に、双子が本郷に通っていることもあり対面で集まれない日もそこそこ多かった。ただでさえ東大の1年は授業で忙しいのに、11月には駒場祭があり、所属している大学合唱団での練習も増えていたので、競プロに注力しきれなかったのはちょっと心残り。

バチャのセットは大体 E869120 さんが選んでくれていた。UCup や海外の Regional を解くことが多かった。毎回というわけではないが、そこそこ良い成績を維持できていたと思う。

全員 JOI 育ちなので得意分野が被っているかと思いきや意外とそうでもない。大雑把に言うとグラフ(特に木)・データ構造が自分、幾何・構築・ad-hocが square さん、文字列・数え上げ・インタラクティブが E869120 さんという感じなのだが、全員オールラウンダー寄りなので明確に分類できない問題についても3人の能力の和集合をとると良い感じに対応できる。そのため、問題とのマッチングがうまくいった回は大体が成功に終わった。

国内予選

時系列がごちゃごちゃになっているが、7月の国内予選についても少しだけ言及しておく。

国内予選ははっきり言って最悪の結果だった。1位を取る気持ちで臨んだにもかかわらず得られた結果は1位と2完差の11位。敗因は色々あるが、

本番の環境が特殊だったにもかかわらず、前日までに諸々の確認を行うのを怠った。
国内予選ルールでの練習が少なかった。3時間という短いコンテストに合わせた戦略を準備しておくべきだった。
コンテスト数日前に E869120 さんに色々あってチーム全体としてメンタルが整っていなかった。

などだろうか。この失敗を踏まえて、8月頃からは練習が多くなった。

Taichung Regional

実は、Yokohama より前 (11月上旬) に台湾の台中市で開催された Regional にも参加していた。もちろん WF に参加できる可能性を高めるという意図もあったが、うちのチームは (国内予選での失敗もあり) 本番に弱いのではないかという不安があり、経験を積むという目的も大きかった。

運良く台湾の強豪 std_abs を抑え優勝することができたため、Yokohama で SPJ または HHIJKT が優勝しなければ WF 確定という非常に心強い状況になった。この成功でメンタル・本番力・チーム力すべての成長を実感でき、良い流れに乗って Yokohama に向かうことができた。

Yokohama Regional

本編

前日の夜はあまり眠れなかった。緊張のせいなのかもしれないが台湾ではしっかり眠れたんだよな……。とはいえ特に誰かが体調を崩すということもなく、会場にも時間通りに到着することができたので第一関門は突破した。

コンテストは 20 分ほど早めに始まった。これが ICPC Timer というやつですか？最初のフォーメーションとしては、自分が環境構築、E869120 さんが A 問題、square1001 さんが B 問題となっていた。B->A の順に一発 AC し 2 完時点では 1 位になった。流石の早解き力である。自分は C~L から問題文が短いものを読んでいたのだが、3 問目くらいに読んだ K が簡単であることに気づく。実装して提出したがWA、え〜〜〜〜〜〜〜。序盤でロスするとかなりもったいないので、目視デバッグより安全に AC を取るべくランダムテストを実装。この見切りとテストの実装速度は良かった。実行してみるとすぐ落ちるケースがみつかり、試してみるとなんと REP マクロの罠を踏んでいた。#define RREP(i, l, r) for (auto i = r - 1; i >= l; --i) と書いていたんですね。皆様なら何がヤバいかお分かりでしょう。こんな初歩的なミスでペナ 20分 + 10分程度失ったのはかなり痛いが、それでもSecond ACだったのは安心。この間にPenguin FeedersがE,Iを通していて速すぎだろと思ったが、双子が爆速でI->Eの順に通してくれて心強かった。その間に自分はG,Hを少し考えていた気がするが、読むだけ読んでスルーしていたCが通されていたのでIを通して帰ってきたE869120さんと少し考える。最短路木がそのまま答えになったら良いんですけどねえ、などと話していたらE869120さんが証明してくれた。AC。この間のどこかのタイミングでsquare1001さんがLを実装していた気がするが、どうやら嘘解法だったらしい。ABCEIKの6問とその他で難易度に崖があり、ここで前半戦終了という感じか。

幾何担当のsquare1001さんがFで賭けにでていたので残った二人でG,Hあたりを見る。Gを読んで、真ん中一列の矢印の個数の差で左右どっちか決まるから二分探索できるんじゃないかということをE860120さんに伝え解法を詰めてもらうが、今思い返すとこれは最初のアイデアの時点で嘘解法で、これをもとに考察・実装を任せてしまったのはかなり痛手。Fは通らず、Gも実装にかなり時間がかかり、詰まってしまった。そこで自分がAMATSUKAZEに解かれていたDに移ると解けたので実装することに。3人が別々の3問に取り掛かるというのはかなりリスクが大きい(特に、全員詰まると破滅)が、Dは一発で通ったので安心した。その後双子にはF,Gを頑張ってもらいつつ自分はHを考えたりJの双対を取ってみたりしていた気がする。このあたりでGが嘘解法だったことが分かったので考察しなおす。1列見るのではなく2列見た方がよいことに気づき再度E869120さんにアイデアを投げ、考察してもらう。Lがしばらく手つかずになっていたことを思い出し考察してみると、時間はかかったものの解けた気になったので希望を持つ。しばらくするとsquare1001さんがFを通し、自分のLも(1ペナの末だが)通ったので勢い付き、今度こそ正しい解法を詰めてくれていたE869120さんにGを実装してもらう。AC。この一時間でF,G,Lの3問を通すことができ、完数的にもペナ的にも優勝がかなり堅くなった。自分がLを通した後square1001さんとJを考えていたのだが、square1001さんが今回のコンテストで一番の天才をしてJの正しそうな解法を生やしてくれたので、自分が正当性を検証しつつGが通った直後から実装してもらうことになった。

最後の一時間。square1001さんはまずJの実数の場合を実装。自分とE869120さんでHを考え、これ絶対Y.Y.さんだろマトロイド交叉だろなどと話していた。マトロイド交叉ということは絶対マッチングに似た解法で解けるはずということになり、それっぽい増加路のようなものを見つけて改善する方針をE869120さんから提案された。自分はこういうE869120さんの勘のようなものを会得できていないので正当性は分からなかったが、残り時間も少ないのでJが通ったらこれを実装することになった。その間にsquare1001さんがJの実数の場合で正しい答えを出力することを確かめていたので、お祈りしながら有理数の場合を実装してもらった。2回提出してWAだったが、ランダムテストをかけたり印刷したコードを残りの二人で読むなどしてデバッグに全力をかける。なんと残り15分でACした。あまりに強すぎる。最後まで諦めずE869120さんがHを超絶熱烈実装していたが間に合うはずもなくコンテスト終了。凍結された順位表から分かる範囲でも、少なくとともWF進出は確定していた。しばらくチームでお互いを労っていた。

Yes/Noにより無事優勝が確定。最後JがYesだった時に会場が沸いたのが嬉しかった。

おわりに

Regional 2大会優勝を果たし WF 進出を決められて本当にうれしい。国内予選のときからかなり成長したと思う。チームとしてさらに改善できる点もあるし、自分としてももっと強くなれると思っているので、今後の練習も頑張ります。WF も見ててくださいね。

(宣伝) 直前すぎるのですが、今週末12/28に自分が所属している東京大学柏葉会合唱団(@HakuyoChoir)の定期演奏会があるので、興味があればお越しください。チケットはこちら

2023-09-10

IOI2023 参加記

はじめに

IOI2023 に関わった全ての方々へ感謝を申し上げます。自分にとって初めての完全オフラインの IOI であり、一生思い出に残る素晴らしい体験ができました。

また、Twitter (現 X) などを通して日本選手団へのたくさんの応援コメントを拝見しました。皆様の応援が力になり、よい結果を出すことができました。ありがとうございます。

以下の内容は IOI2023 の問題に関するネタバレを含みますのでご了承ください。

8/27

羽田空港での壮行会 & 出発。SET で遊んだり、競技規則を確認したりした。飛行機が 11 時間 + 2 時間とかなり長く、きつかった。

8/28

ハンガリーに到着。飛行機で眠れず、7 時間の時差があったのでずっと眠かった。去年のインドネシア大会ではホテルの食事が美味しいとは言えず衛生的にも心配だったが、今年のホテルの食事はかなり美味しかった。今年はインスタント食品ばかり食べなくともなんとかなりそうだと思い安心した。

8/29

プラクティス & 開会式。前日に 4 問目の解法を他の選手と話し合っていたので、1,2 問目をさっと解いた後に実装してみたが、1 時間かけてもバグが取れなかった。後になってプラクティスの順位表が公開されていると知り、2 時間で全完している選手が複数人いることに驚いた。

プラクティス 4 問目は次のような問題。

頂点に非負整数の重み S_1, ..., S_N が、辺に非負整数の重み W_1, ..., W_{N-1} がついた木が与えられる。
整数 i をちょうど S_i 回含み、先頭と末尾が 1 である整数列 P_1, ..., P_K に対し、P のスコアを i = 1, ..., K-1 に対する頂点 P_i, P_{i+1} の距離の総和と定義する。
「S_i を x に変更する」というクエリが Q 回与えられるので、各クエリに対し、それを処理した直後の P のスコアとしてありうる最大値を求めよ。

実装激重 Nlog² N しか生えなかった。

帰り道に、木の頂点に重みがついていて重みの一点更新がある場合の重心の求め方を韓国選手に教えてもらった。オイラーツアー順に重みを並べたときに累積和が総和の半分を初めて超える位置を求めて、その頂点の祖先を見ればよいらしい。言われてみればという感じだが自分は見たことがなかった。

8/30

競技 1 日目。

A を早速誤読し嘘貪欲に 20 分使ってしまった。勘違いに気づき正しそうな 83 点解法を実装するも全く点が得られない。ヤバいと思いつつ C に移るがこちらも嘘解法しか生えず、105 分経過時点でほぼ 0 点だった。未実装のものも含めて全く正しい解法が思い浮かんでいないので流石に焦った。しかし B を見ると 15 分程度で 70 点の解法が見えた。少しバグらせたが 140 分経過時点で 70 点を取ることができ安心した。その後 C に戻り、落ち着いて判定条件を考えるとようやく正しい多項式時間の解法を思いついた。190 分経過時点で 70 点まで伸ばした。やっと A に集中できる状態になったので最初の 1 時間に書いたコードを見直すと、なんと簡単な場合分けを忘れていることに気づき、一瞬で 83 点まで伸びた。
残り 90 分、何か一つでも満点を取りたい状況。保険として C の 77.5 点を整理しておいてから、満点まで小課題が 2 つ残っている B を考える。償却でクエリが 2N 回になっていそうな解法を思いついたが、筋が悪く場合分けが多くなってしまい、1 時間かけても点数を伸ばせなかった。残り 30 分は C の 77.5 点を通すのと、A の満点を考えるのに使った。

悪くない順位だったが、1 問も満点が取れなかったことや、A の 83 点を木 DP ではなく満点のもとになる解法で取っていたにも拘らず満点がとれなかったことが悔しかった。

夜はメキシコの選手とビリヤードをした。一人かなり上手い人がいて凄かった。

8/31

エクスカーション 1 日目。

ハンガリーののどかな風景を楽しめた一日だった。しかし日本選手の 1 人が風邪で休むことになったので少し心配だった。

この日が卒業文集に載せる文章の期限だったので、日本時間の 23:59 ギリギリ (ハンガリーの 16:59) に完成させて提出した。

ふと思い出して IOI2018 のテーマソングである Euphoria を聴いていた。IA が実行委員をやってテーマソングをじんさんが手がけているのはかなり凄いことだと思う。曲はもちろん、歌詞もすごく好き。ボカロでは IA が一番好きなので、いつかの JOI 本選でもらった IA のクリアファイルは使わず家に置いてある。

IA / Euphoria (じん) (PARTY A GO-GO WORLD TOUR FINAL) 【LIVE MUSIC VIDEO】 - YouTube

9/1

競技 2 日目。

今までで一番緊張した。JOI 本選/春のようにいい成績を取らないと次へ進めないということはないが、自分は 2 度 IOI で金メダルを獲っている。誰かに「今年も金メダル期待しているよ」と明確に言われたわけでもないし、どんな結果でも周りの人は讃えてくれるのだろうが、やはりプレッシャーは重い。

最後の競技が始まった。A を読むとかなり部分点が多く、少なくとも M=2 や N<=200 は取らなければならない見た目をしている。しかし開始 80 分後までに思いついた貪欲が全て嘘解法だった。N <= 10 の愚直解を書いてランダムケースで答えを比較するも全く反例が見つからない。絶望して B に移る。愚直の 39 点を取り、しばらく満点を考えるが、A は多項式にすら落ちておらず、考察・実装ともに時間のかかりそうな C は手付かずという状況や、このままでは銀メダルになってしまうという焦りでパニックになってしまった。結局 65 点で妥協して、なぜか手付かずの C ではなく A に戻ってしまった。

残念ながら嘘解法が直ることはなく、結局小さい自明部分点を回収して 9 点→ 23 点にするだけで 1 時間使ってしまった。この時点で 23-65-0 で 100 点にすら届いておらず、問題文がかなり長く特殊な見た目をしている C が未だ手付かずという状況だったので、本気で絶望してしまった。応援してくれた人や惜しくも IOI に来れなかった人たちに脳内で謝ったり、呆然としてマスコットを眺めていたりした。先に B の満点を考えるか C に手をつけるか迷ったが、満点に突撃するのは流石にリスクが大きいと考えようやく C に手をつけた。DFS を上手くやる方法を思いついたので実装して 34 点を取ってから、54 点がすぐに見えたつもりになって実装するも一向に通らない。ランダムケースを 1000 ケース試しても落ちず困惑し、残り 15 分程度になってハッとして A の残っている自明部分点に取り掛かった。結局 31-65-34 で、銀メダルに落ちたと確信して文字通り頭を抱えた。

なお C で 54 点が通らなかったのは、答えは常に合うが特殊なケースで操作回数が指数オーダーになるからだった。ランダムケースで落ちなかったことで気づくべきだった。

自分の弱さが出た日だった。これまで何度も 5 時間コンテストをやってきたし、春合宿や IOI2021 で大逆転も経験しメンタルは強くなったと思っていたのに、最後の最後にプレッシャーに負けて普段通りの考察力が発揮できず戦略ミスもしてしまった。今までの経験が自分の精神力に対する過信を生み、かえって足枷となってしまったような気がする。本来ならまず B に取り掛かるべきで (この日だけなぜか最初に全ての問題文に目を通すということをしなかった)、C を手付かずで放っておくべきではない。後になって考えると当たり前のことができていなかった。これからは (当分の間大きな大会はないが) この経験を忘れず自分の弱さに向き合っていかなければならないと思った。

しかし幸運なことに、なんと 21 位で金メダル圏内で耐えていた。絶対に銀メダルだと思っていたのでかなり安心した。さらに日本選手全員が金メダル圏内にいて 2 人が一桁順位を取っていた。2 年連続で全員金メダルなので、JOI 春合宿のレベルは相当高いのではないかと思う。

9/2

エクスカーション 2 日目。

午前はセゲド動物園へ行った。ミーアキャットが可愛かった。

午後は公園のようなところへ行って海外の選手たちと一緒にバレーボールをした。全くサーブが入らなかったし手首が内出血を起こしたが、体を動かすことができて楽しかった。

夜は懇親会やディスコみたいなイベントがあったが、体力的にきつかったので夕食だけ食べて早めに帰った。一緒に帰った日本選手に触らせてもらったゲームがかなり面白かった。

9/3

閉会式。

ニュージーランドの10歳の子が銅メダルを受け取ったときの歓声が一番大きかった。10歳でメダル獲るって相当凄いし、なんとあと7回もチャンスがあるらしい。

IOI2024 の予告映像も流れた。来年はエジプトのアレクサンドリアで開催されるらしい。2025 はボリビア、2026 はウズベキスタンという噂も耳にした。ハンガリーは予想以上に環境が良かったので来年以降どうなるかな。

9/4

日本へ向けて出発。ブダペストを観光…するはずだったが、日本選手の一人がリュックを紛失するという事態に。結局見つからず、予備のメダルを受け取ったらしい。

ブダペストは綺麗な街だった。ドナウ川は思っていたより汚かったけど…

そして、この日に 18 歳になった。誕生日に金メダルもらいたいね、という話を事前に家族としていたので、実現できてよかった。中高を競プロとともに過ごして、競プロを通して大人になったような感覚がある。

9/5

日本到着。日本の米と肉を求めてたどり着いた先はなんと焼肉屋だった。久しぶりの日本食だったので白米だけで既に美味しかった。

さいごに

IOI2023 で金メダルを獲得しました。IOI2021, IOI2022 に引き続き 3 度目の金メダルとなり、安堵と達成感でいっぱいです。

競技の内容や 21 位という順位に関しては悔しさが残る部分もありますが、ここで競技プログラミングを辞めるのは嫌だと思える結果でもありました。この悔しさは、今後も競技プログラミングに取り組むためのモチベーションに変えていこうと思います。今回見つかった自分の弱さをしっかりと見つめ、より強い選手を目指して今後も努力します。

情報オリンピックは僕にとっての青春で、そこには様々な感情と思い出があります。情報オリンピックがなければ今の自分はないだろうし、全てが今後の人生を形作っていく経験だと思います。情報オリンピックへの最大の感謝をもって、筆をおくことにします。

2023-03-22

JOI 春合宿 2023 参加記

JOI 2022/2023 春季トレーニング (IOI 2023 日本代表選抜) に参加した。

問題に関するネタバレを含むのでご注意ください

Day 0

本選の表彰式と交流会、プラクティスがあった。交流会では色んな人が話しかけてくれて嬉しかった。

ホテルに着いてからは Library Checker の問題を解いてソラ実装の練習をした。

Day 1

競技一日目。実は過去の春合宿の Day 1 はことごとく失敗しているので、今年こそはと思って競技に臨む。

currencies は読んですぐに解けた。部分問題が当日の ABC に出していた原案そのものだったので驚いた。festival2 は難易度高の数え上げ、passport は解けそうで解けない最適化だった。passoport の自明部分点を回収し、festival2 を取れるところまで伸ばした。6 乗くらいの DP をなんとか 3 乗まで落とした。

結果 100+51+54 = 205 で 2 位となり、悪くない順位。初めて良いスタートを切ることができた。

festival2 は前から見るより後ろから見た方が解きやすいらしい。どうせ対称だろ (実際は違う) と思って捨ててしまったのが良くなかった。満点がオンライン畳み込みなのはやりすぎでしょう

passport の解説を聞いてこれは解けるようにならねばと思った。1,2,...N に行ける⇔1,N に行けるの言い換え、思いつけないなあ

Day 2

競技二日目。

まず解けそうな見た目をした council に手をつける。なかなか上手にゼータ変換に落とし込めず、かなり手こずってしまったが、なんとか満点を取った。mizuyokan2 は明らかに難しい見た目をしているので飛ばす。初 Communication 課題の conveyor を見ると、なんと最後の小課題が 75 点。25 か 100 かという問題なので、これは解かなければヤバいと思って考える。かなり時間がかかったが 3 時間かけて満点を取ることができた。残りの時間で mizuyokan2 の自明部分点を回収した。

結果 100+100+28 = 228 となり、Day2 単独では 1 位タイ。予想通り conveyor でかなり差がついていた。5 位とそれなりに差はあったものの、過去に自分は 100 点差をひっくり返して代表になったことがあるので全く安心できない。

解説: mizuyokan の谷ではなく山に注目するパートが人間的ではないと思った。これが区間スケジューリングになるのは凄い

Day 3

競技三日目。

cookies が簡単な問題設定なので手をつけるが、10 分くらい考えてこれはヤバい問題かもしれないと思って離れ、chorus に手をつけた。言い換えにかなり苦労したが、コスト関数が簡潔に表せる最短経路問題になり、どうせ Monge DP だろと踏んで WQS Binary Search を実装。O(N² log N) が通って 61 点になったことを確認すると、遷移の高速化を考える。この時点でほぼ満点を確信していた。時間はかかったものの CHT + スライド最小値で O(N) で計算できるとわかったので実装し、満点を取った。次に tourism を見ると一瞬で Mo が降ってくる。O(Nsqrt(Q)logN) くらいなので明らかにヤバいが、TLが4秒なのでワンチャンに賭けて実装する。当然満点は得られない。その後、Mo をジグザグにしたり分割のサイズを変えたりすると TLE するケースが減っていった。思い切って std::set を BIT に置き換えたり連結リストで集合を管理したりすると、TLE がわずか 2,3 ケースになった。入出力高速化や std::vector を生配列に置き換えてなんとか 3.9 秒くらいで AC。残り一時間程度だったので cookies は部分点を回収して終わった。

Day3 単独では 1 位だった。正直 tourism が通ったのは完全に運だと思う。

解説: tourism の解法が賢かった。一度 Mo を思いついたら離れられない…

Day 4

最後の競技。5 位とかなり差があったので「〇〇点とれば代表確定」などと考えていたが、これが立ち回りの足枷になってしまうんじゃないかと色々悩んだ。

travel が自明だったので 30 分もかからず 100 点を取る。その後 40 分程度 battle を考えると 54 点を取ることができた。なんと開始 70 分で代表が確定してしまった！

とはいえ、どうせなら総合一位を取りたいのでさらに点数を伸ばすため guard を考える。問題を理解する時点でかなり難しく手こずる。思い切って大胆予想を実装することを何回か繰り返してパスグラフの場合を解いた。木はパスの延長で解けたので一般グラフの Q=0 の場合を考える。「どうせ使う辺は木、なんならMSTとかじゃないと解けないだろ」と考えてコスト関数を min(S[i], S[j]) と max(S[i], S[j]) と S[i]+S[j] の三通り実装して提出してみると、S[i]+S[j] が通って 50 点。ラッキー。その後 bitDP を実装して 8 点追加。

残り 1 時間は battle と guard の嘘解法に使ってしまい、合計 54+100+58 = 212 点。

なんとか逃げ切って総合 1 位！

解説: battle は思った通り E8 問だった。割り当て求めるのに焼きなましをするのがそれっぽい

結果

Σ870 1 位、IOI 2023 代表決定！！

感想

踏んできた場数が多いので、立ち回りにはかなり安定感があったと思う。特に、どの日についても最初に実装したのがその日で最も多く解かれた問題だったのが、難易度を見抜く力がついた証拠だと思う。

代表になれたのがとても嬉しい。最後の IOI も悔いのない結果を残せるよう頑張りたい。

2023-01-16

日記 1/4–1/15

あけましておめでとうございます。去年 12 月初めから更新が止まっていた日記を再開します。
過去に「12/15 くらいから再開する予定」と書いたのは見なかったことに。

1/4

競プロ

ARC137 - E. Bakery (800) に突撃。LP で書いてみたり双対を取ってみたりしたが、うまくいかず断念して解説を開いた。フロー以外で解けないだろうとは思ったが、どうしても「流量が 0 または R-L」みたいな変な形になってしまっていた。imos 法に思いを馳せるべきだったのか…
MCF への理解が浅いため、どんな設定なら解きやすくて、逆にどんな設定なら解けないのかといったことが判断できず、考察中によからぬ方向へ行って沼ってしまったときに抜け出せない。経験値ゲーなのか？

とりあえず、

よくある「sink, source, 中間ノード」という形だけで表せると思い込んではいけない
辺のコストが区分線形凸関数でなくなってしまったら、別の条件設定を考えてみた方がよい
「s-t パスに流す」ではなく、最小費用循環流なども含めた b-flow の形を考えてみるべき

といったところだろうか。

＜解法＞

以下の最小費用循環流の答えを -1 倍したものが元の問題の答え。

頂点 $0, \dots, N$
$i \rightarrow i-1$ に容量 $A_i$ 、コスト $-D$ の辺
$i \rightarrow i-1$ に容量 $M-A_i$ 、コスト $0$ の辺
$L_j - 1 \rightarrow R_j$ に容量 $1$ 、コスト $C_j$ の辺

$i \rightarrow i-1$ の辺にめいいっぱい流しておいてから調整すると考えると負辺が消える。

数オリ

もうすぐ予選なので、2015 年の予選の過去問を解いた。若干記憶に残っていたのもあり、一時間ちょっとで 9 問目まで解けた。明日 10 問目を考えてみよう

その他

チェンソーマン二部、ナユタちゃん（おそらく）が秀才なの解釈一致で助かる

1/5

競プロ

数理最適化のお勉強

今までいい加減だった LP への理解を深めたくなった。梅谷俊治教授の「しっかり学ぶ数理最適化」を読んでいく。理解が甘かったところを以下にまとめる。

そもそも LP (線形計画問題）とは、線形な目的関数の値を最大化・最小化する問題であって、制約条件が全て線形の等式（不等式）で与えられるものを指す。LP は全て以下の標準形に書き換えられる。

maximize $\boldsymbol{c}^\top \boldsymbol{x}$
subject to
- $A \boldsymbol{x} \leq \boldsymbol{b}$
- $\boldsymbol{x} \geq 0$

最小化問題、非負制約がない変数、不等号の向きが逆、不等号じゃなくて等号…などの場合も全て上の形に帰着できる。ついでに $|\boldsymbol{a}^\top \boldsymbol{x}| \leq b$ みたいな条件も OK。ただしこれは不等号の向きが逆だと OR の条件になってしまうので無理。

subject to 以下の条件を満たす点 (ベクトル) の集合は凸多面体になる。凸多面体とは、集合 $S \subset \mathbb{R}^d$ であって、任意の $\boldsymbol{x}, \boldsymbol{y} \in S, 0 \leq t \leq 1$ に対して $(1 - t)\boldsymbol{x} + t\boldsymbol{y} \in S$ となるものである。

x, b がそれぞれ n, m 次元のとき、合計 n+m 個の条件 (平面) が存在するが、最適な値を与える点の少なくとも一つはこれらの平面のうち n 個が交わる点である。平面を通るというのは不等号に対して等号を成り立たせることと同じである。スラック変数を導入すると n+m 変数、n+m 個の非負条件、m 個の等号条件に置き換わる。n 個の平面が交わる点というのは、n 個の変数を 0 にすることと同じである。残りの m 個の変数 (0 でないとは限らない) を基底変数と呼ぶ。

単体法では目的関数の値が増加するように、0 にする変数を 1 つずつ入れ替えることを繰り返している。0 である基底変数が存在する解を退化している (degenerate) と呼ぶ (フローで聞いたことがあるような) 。

実行可能解が自明でない場合も、制約の違反量を人工変数として導入し、この違反量を最小化する (つまり、0 にする) というステップを踏んで解を見つけることができる。

主問題、双対問題は (解なし, 解なし), (非有界, 解なし), (解なし, 非有界), (有界, 有界) のいずれかである。最後の場合、最適値は一致し (強双対定理)、これは単体法を経由して証明することができる。

$\boldsymbol{x}^\top (A^\top\boldsymbol{y} - \boldsymbol{c}) = 0 \land \boldsymbol{y}^\top (\boldsymbol{b} - A \boldsymbol{x}) = 0$ を相補性条件 (complementary slackness condition) という。

ARC151 - E. Keep Being Substring (700)

本質ケースがサンプルにない。X のどの要素も Y に含まれないとき、どうせ X の要素は消すことになるので、一つだけ残して全て消してしまった方が自由度が上がってよい。結局 X と Y から一つずつ要素 a, b を選んで a を b に一致させるための最小の操作回数を求めればよい。

数オリ

'15 予選 10 番、解説を見てしまった…これもうちょっと考えたら解けたな
N_1 = 10x + y と N_2 = x + 4y を足し引きして mod M での関係を導く

その他

はてなブログの数式めちゃくちゃ書きにくいな…そもそもこれが最初に Zenn を使うことにした理由だった

1/6

競プロ

JOI2022sc - Ants and Sugar

本番最高点が 6 点だっただけあって難しい

この問題に限らず、最大二部マッチングは (max-flow min-cut 定理より) 片側の頂点集合を L として、 $S \subset L$ に対する $|L| - |S| + |\mathrm{out}(S)|$ の最小値である。これは今までも暗黙のうちに使ったことがあるはずだが、改めて一般化しておくと今後も使えそう。

区間種類数クエリも似たような考え方を使うが、「区間に一個以上」といった形の条件を各々の要素の寄与と隣接する 2 つの要素の寄与に分解することでセグ木に乗せられる。非常に賢い

1/7

競プロ

CF Round 841 (Div. 2) バチャ

14 分残しで全完できたが、これは 1 時間で全完するべきセットだった。

A: a+b <= ab+1 なので一つを残して全て 1 にする
B: 対角線上を通っていく。帰納法で証明できる (i + j = 2n となるマス (i, j) では (n, n) までジグザグで行ったときが最大)
C: 平方数を列挙 & 累積 XOR で数える
D: 二分探索 + 二次元累積和
E: k が大きいものから貪欲に使ってよい
F: 多項式補間

部分和問題 O(NW)

全ての重みが W 以下の部分和問題の O(NW) アルゴリズムを履修した。参考

順番に重みを加えていって、初めて目標の値 S を超えた位置を b とする。もし和を S にできるなら、この状態から b 以降の要素をいくつか追加し、b 以前の要素をいくつか削除することで実現できる。さらに、この追加・削除は重みの和と S の差が W 未満である状態を保ったまま行うことができる。

dp[i][j][k] を、「b,b+1, ..., i について追加するかどうか決め、b-1, b-2, ..., i+1, i について削除するかどうか決めたとき、和を k にできるか」と定義する。このままだと O(N² W) だが、dp'[i][k] を「dp[i][j][k] = True となる j の最大値」と定義することで O(NW) に落とすことができる。

数オリ

'16 予選を解いた。10 番面白かった

1/8

競プロ

CGR 24 バチャ

悪くなさそう？G1 解きたかったな

A: ギャグ、(1, n) を出力
B: g = gcd(a_1, ..., a_n) とすると、最大値以下の g の倍数が全て作れる
C: 二部グラフになるので、値でソートして split する位置を決め打つ。ただし全ての値が同じ場合は floor(n/2) が答えになることに注意
D: 対称なので、最後に a に追加されるのは 1 であるとしてよい。1 を取り除いた直後に n/2+1 以上離れた 2 点が現れるので、この 2 点の距離と a に追加する個数を決め打つ
E: k <= a_1, k > a_1 + b_1 の場合は簡単。そうでない場合、k-b_1 <= x <= a_1 となる x が少なくとも一つすでに塗られていなければならない。ここで、k-b_1 が塗られているとしてよい。この考え方を繰り返し用いると、結局「k <= a_i + b_i となる i を選んで k から b_i を引くことを繰り返して、まだ選んでいない i に対して k <= a_i が成り立つようにする」という問題になる。k <= a_i を成り立たせる i を決め打つことにすると、j ≠ i となる j を a_j+b_j の昇順に並べ、現在 a_j+b_j 以下なら b_j 引くことを繰り返すことになる。この処理は、うまくやると遅延セグ木を用いて全ての i について同時に行うことができる。
F: 頂点 1 を含む部分木を徐々に確定させていくと考える。現在確定した頂点集合を S とする (最初 S = {1})。S に含まれない u であって、f(1, u) が最大になるものを取ると、u は S のどれかの頂点に接続している。そして、その頂点とは、S に含まれる v であって f(u, v) が最大になるものである。f(u, u), f(u, v), f(v, v) を用いると uv 間の辺の重みがわかる。
G1 (upsolve): 2 で割って切り捨てた値が等しいものどうしに辺を張ると、次数が 0 なのは 1 と、n が奇数のときは n の最大 2 個である。query(l, r, 2) を用いると区間に完全に含まれる辺の個数がわかる。query(0, m, 2) と query(m, N, 2) を用いると次数 0 のものが左右に何個ずつあるかがわかるので、1 が存在する区間を二分探索できる。左右に 1 個ずつある場合、どちらが 1 でどちらが n かを知るために、長さが 2 以上の区間に対して query(l, r, N) を投げればよい。二分探索の両端が [l, r) のときに、query(l, m) と query(m, r) ではなく query(0, m) と query(m, N) に注目するのはレアな気がする。

1/9

数オリ

JMO 予選。やばいミスがなければ通ったはず。9 番は似たようなのを見たことがあって、ARC なら 600 点くらいで出そう？

作問

去年「今年は ARC を開きたいな」というツイートをしていたらしい。この人原案作りすらしてないですよ
とりあえず設定を一問生やした。さあ何日続くだろうか

1/10

作問

二日目

アプリ開発

訳あって Flutter の勉強をすることになった。とりあえず環境構築をしたので、Dart の公式ドキュメントを読んでいく。
このためだけに Xcode インストールするの嫌なんだが (異様に容量がデカく、動作も遅いため)

1/13

二日飛んだのは気にしない

作問

三日目（？）

競プロ

ARC099 - F. Eating Symbols Hard (1200)

https://atcoder.jp/contests/arc099/tasks/arc099_d

A を多項式の係数だと思うことにし、ローリングハッシュの要領で一致判定を行う。

先頭 i 文字を処理した時のハッシュを H_i, P の値を P_i とおき、base を x とおく。
[i, j) を処理した結果が [0, N) を処理することは $\frac{H_j - H_i}{x^{P_i}} = H_N$ すなわち $H_j = H_N \times x^{P_i} + H_i$ と言い換えられるので、i を固定して j の個数を数えることができる。

一致判定だけでも愚直で $\Theta(N)$ かかるんだから、ましてそれの数え上げなんてハッシュ使わな到底無理やろ！という発想。
衝突確率を雑に見積もると mod 2⁶¹ でも危ない気がするが、大丈夫だった。

atcoder.jp

その他

久しぶりに Yunomi さんの曲を聴いていたら、いい曲に出会った

枕元にゴースト (feat. nicamoq) - YouTube

1/14

競プロ

Codeforces Round 842 (Div. 2) バチャ

E までは自明だったので省略

i→j を一気に行く場合と一つずつ行く場合を比較すると、a_i, ..., a_j の最小値を m として、m(j - i) >= n ならば一つずつ行ったほうがよい。
m = a_k となる i < k < j となる k が存在するなら i→j→k と行った方がよい。

B = sqrt(n) とおくと、m >= B となる場合は O(B) で調べ尽くせる。m < B となる場合を、a_i = m となるか a_j = m となるかでさらに場合分けする。

a_i = m のとき : monotonous stack で B 未満の要素を管理しておけば O(B) で調べられる。
a_j = m のとき : まず monotonous stack を更新する (a_k >= a_j となる k を取り出す) 。最後に取り出されたのが k であるとする。a_k = a_j なら、k とそれ以前の場所は調べる必要がないので k+1 から j の間を調べる。a_k > a_j なら、stack に残った末尾の要素を k' として、k'+1 から j の間を調べる。一見 Θ(N²) になってしまいそうだが、各 i が調べられるたびに、「i より右で i に最も近い B 未満の要素の値」が真に減少するので、それぞれ最大 O(B) 回調べられることになり、償却 O(NB) になっている。

ARC 153

4 完 & 久しぶりの赤 prf。C で凡ミスしたのと D で実装に手間取ったのは良くなかったが、考察スピードは戻ってきている気がする。

1/15

競プロ

Educational Codeforces Round 14 バチャ

E: ceil(a_i/k) <= ceil(b_i/k) が成り立つかを判定する。ある k が条件を満たすか調べるとき、ceil(b/k) の値を固定して (n とおく)、 b_i <= nk となる全ての i に対して a_i <= nk かどうかを調べればよい。各 k に対しありうるすべての n を試しても O(N log N) である。

F: 順列が一つの場合は、i→p_i に辺を張ったグラフを考えると、「ソートされる⇔全てのサイクルについて、そのサイクル内で一度も選ばれなかった頂点は高々 1 つ」が成り立つことがわかる。一度も選ばれない頂点の個数を最大化することを考えると、次のような最大二部マッチングに帰着できる : 左側に 1 つ目のグラフのサイクルに対応する頂点を並べ、右側に 2 つ目のグラフのサイクルに対応する頂点を並べる。各 u について、u が一つ目のグラフで属するサイクルと二つ目のグラフで属するサイクルに対応する 2 頂点を結ぶ。

作問

過去の ARC の問題を眺めながら設定をいくつか生やすとやりやすいことに気づいた。盗作みたいにはならないよう気をつけたい

2022-12-18

日記 11/16–11/30

11/16

競プロ

AHC をずっとやっていたが、全くスコアが上がらず。残念

11/17

競プロ

AHC 進捗ダメです

解いたもの↓

https://atcoder.jp/contests/abc277/submissions/36546383

行に対する操作 / 列に対する操作は順番を入れ替えても同じ。行 / 列それぞれについて昇順にできるか解けばよい

行は簡単。上の行の max <= 下の行の min が成り立たなければならず、これは適当にソートしてそれが条件を満たすか確かめればよい

列は、「ある列が別の列の左側でなければならない」を辺として表した有向グラフが DAG かどうか判定すればよい。グラフの構築は各行ごとに行う。中間ノードを導入してやると、辺の本数が二乗から落とせる

群論

競プロのやる気が出なかったので久しぶりに本を手に取った $xH$ が左剰余類なの混乱するな…

11/18

競プロ

今日も今日とてライブラリの設計を考えていた最近、std::size_t を使うかどうかで悩んでいる

メリット

美的感覚に合う
C++ STL に合わせられる
0 以上の整数であることを型で明示できる

デメリット

普段使いするには面倒
符号付き整数と混ぜて使うと注意を要する
環境によっては int よりメモリを食う

どうしようか…

ところで、C++20 の機能を調べていたら欲しくなったので、AtCoder に導入されるとうれしい

11/19

機械学習

二年前くらいにかってそのまま置いてあった「Kaggleで勝つデータ分析の技術」を唐突に読み始めたなんで Python を使わなければいけないんだろう

競プロ

今週は ABC278 の tester をしていた。D, E の原案で、ADEG の tester をした

ジャッジ側がコンテスタント側より難しい。 $g_i \oplus g_j = x$ となる $(i, j)$ のうち $i + j$ が最大となるものを各 $x$ について管理する、という方針でできる

11/20

競プロ

ARC152 に参加、あまりにひどい結果に… 言い訳したくなるレベルだが、本気で出てこれなので逃げてはいけない

昔なら「今日は調子が悪かった」「問題との相性が悪かった」と逃げていたところだが、自分よりワンランク上の赤コーダーがこのような失敗をするのは想像できないので、ちゃんと実力不足を認めるべきだなあ、と思う

最後の JOI 春合宿や IOI でこのようなことが起こらないようにするためにも、ちゃんと練習しよう

upsolve↓

どの 2 点から出発しても、必ず 2 回出会う。出会う地点を X, Y とおく X から Y に行くまでに 2 人が歩く距離を a, b とおくと、

X で出発してから Y で出会うまでに片方が |a - b| 待つ
X で出会うまでと Y で出会った後で、2 人が歩く距離は 2L - a, 2L - b なので、合計 |a - b| 待つ

よって 2L + 2|a - b| が下界となる。これは、2 人が X から出発することで達成できる |a-b| の最小値を求めればよい

反省点 :

1 回目、2 回目の出会うタイミングの間に注目するのは考察ノートに書いていたので、詰めるべきだった
自明な下界が実は達成可能という方向の考察をすべきだった
同じ場所から出発するとしてよいという大胆予想を試すべきだった

https://atcoder.jp/contests/arc152/submissions/36694047

2 要素のときは、差を d、小さい方を m として、 $d + (m \bmod d)$ が答え要素が増えた場合、m を最小値、d を最大値と最小値の差として考える。d は不変なので、d を中心にして考察すると良さそうだという気持ちになる要素が増えても $d + (m \bmod d)$ は達成できるので、 $m \bmod d$ を最小化する問題になる

s に関して flip すると $m \bmod d$ は $2(s - m) \bmod d$ 増えるさらに、2 要素の差は不変なので、元々 s であった値による flip ではどう頑張っても $\pm 2(s-m) \bmod m$ しか動かせない

これらを踏まえると、 $d, 2(A_1 - m), \dots, 2(A_N - m)$ の gcd を g として、 $m \bmod g$ が下界となるそして、これは実際に達成できるこれについては、 $\pm 2(s-m) \bmod m$ 動かす操作を要素が負になることなく何度でも行えることを示せばよく、最大値による flip を好きに挟むことにより可能である

反省点 :

不変量として「全体の gcd」しか思いつかず、(4, 7, 10) のようなケースの扱い方がわからなかった
実際に操作をすると、差分は「2 要素の差の 2 倍」となり、単なる差の gcd よりも若干厳しくなるので、そこに注目するべきだった
d を中心として考えたり、2 要素の差が不変であることに注目したりするのは典型なので、一度冷静に考え直すべきだった

https://atcoder.jp/contests/arc152/submissions/36691068

11/21

競プロ

N が偶数なら作れない N が奇数なら実は作れる (明らかに、辺は $\frac{N-1}{2}$ 本)

2K > N なら、K を N-K で置き換えた場合を解いて、頂点番号を reverse ( $u \leftarrow N - u - 1$ ) すればよい

2K < N なら、 $q = \left\lfloor \frac{N}{2K} \right\rfloor$ として、

$(0, 1), (1, 2), \dots, (K-1, K)$
$(2K, 2K+1), \dots, (3K-1, 3K)$
$\vdots$
$(2(q-1)K, 2(q-1)K + 1), \dots, ((2q-1)K-1, (2q-1)K)$

を追加したのち、 $r = \frac{N - 2Kq - 1}{2}$ として、

$(2qK + 1, (2q-1)K + r+1), \dots, (2qK + r, (2q-1)K + 2r)$

を追加するとうまくいく。気持ちとしては、

N = 2K + 1 なら簡単
N > 2K + 1 の場合でも、最初の方は同じ方法で埋めて最後をうまく調整すればできないか？

となる。

https://atcoder.jp/contests/arc152/submissions/36703299

組合せゲーム理論

Subtraction Game の解析手が有限なら periodic で、手が無限でも禁じ手が有限なら arithmetic periodic になるらしい

射影幾何

perspectivity と projectivity の定義とその性質について projectivity による群 PJ(l) の導入など

11/22

競プロ

最初は全て左側に沿わせた経路を作り、その経路を "ひも" だとおもって上下に引っ張ったときにできる経路を求めればよい

上から順にひもを伸ばしていく。現在のひもの経路を $P_1, \dots, P_n$ として、末尾の3点を p, q, r とする p, q, r をこの順に結ぶひもを引っ張るときに q からひもが離れるとする。引っ張った結果、区間の右側に引っかかる場合があるが、引っかかる点は $O((\log N)^2)$ くらいで求められる。引っかかる点を s として、 $P_1, \dots, P_{n-3}, p, s$ を結ぶひもを (再帰的に) 引っ張る。そして、s, r を結ぶ線分が引っかかるかどうか判定し、引っ掛からなくなるまで同様の処理を続ける。

https://atcoder.jp/contests/arc001/submissions/36722593

11/23

競プロ

DAG であることが問題文に明確に書かれていない気がする…制約には $f \lt t$ であると明記されているが

dp[u][h] を「頂点 u で戦闘後 HP が h のときにゴールするのにかかる時間の期待値の最小値」と定義し、ゴール側から順番に計算する。ここで、「スタート地点に戻る」という選択肢が現れるが、問題の答え (スタート地点からゴールにかかる時間の期待値の最小値) x を決め打ちすると計算できる。最後に dp[1][H] >= x かどうかを判定する。この判定方法が正しいか気になるところだが、遷移式をじっと睨むと、傾きが 1 以下の直線の min をとった形になっており、x - dp[1][H] が単調増加になっていることが確認できる (はず)

https://atcoder.jp/contests/arc016/submissions/36728723

グリッドを 45 度回転して考える。加算クエリは愚直に処理し、全ての x+y, x-y について、そこに足された値を持っておく

最大値クエリが難しい。ここで、直角三角形型のクエリが、辺の長さに対する線形時間で簡単に処理できることに着目する (x+y を増加させると、使える x-y の集合は増える一方で減らないので、chmax していけばよい) 。長方形を正方形に分割し、さらに二つの直角三角形に分割することで、O(N) で処理できる。

https://atcoder.jp/contests/arc047/submissions/36732773

11/24

競プロ

値の重複は取り除いてよいので、集合として考える。また、0 は取り除いておく。

まずは簡単なケース。

$\mathrm{empty}$ なら Win
${1}$ なら Lose
${2}$ なら Lose
$n \geq 3$ のとき、 ${n}$ なら Win ( $n-1$ で割る)

次に、複数の種類の値がある場合を考える。とりあえず 2 で割ってみると、

2 以上の要素があり、かつ奇数が存在するなら Win

がわかる。3 で割ってみると、

割った結果が ${}, {1}, {2}$ になるなら簡単だが、 ${1, 2}$ になる場合はすぐにはわからない。

4 で割ってみると、奇数が存在する場合はすでに解決しているので、

${2}$ になるなら Win

ということが新たにわかる。ここまでで、全て 4 の倍数の場合以外は解決した。

全て 4 の倍数のとき
3 で割ると ${1, 2}$ になるとき

が分からないので、実験コードを書いて上の両方の条件を満たすケースを入れてみると、

${4, 8}$ は Lose
${8, 16}$ は Win で、先手は一手目で 12 で割らなくてはならない

ということがわかる。ここで、3 で割るのではなく 12 で割るというのがヒントになる。全て 4 の倍数で、3 で割ると ${1, 2}$ となるとき、12 以上の要素が存在するならば、

12 で割ることで ${4, 8}$ になるので Win

とわかる。これにより、全て 12 の倍数の場合以外は解決した。

ここで一旦立ち止まって制約を眺める。 $a_i \leq 200$ なので、全て 12 の倍数であるような集合は高々 $2^{16}$ 通りしかない。これは愚直にメモ化再帰しても間に合う。よって、全て 12 の倍数のときは bitDP で別に処理すればよく、そうでない場合は、 ${1}, {2}, {4, 8}$ を除いて Win である。

https://atcoder.jp/contests/arc134/submissions/36759552

11/25

競プロ

部内で JOI 対策バチャがあった。後ろから解いていたら、Cake (難易度 12) を解いただけで 80 分使ってしまったまぁ、ちゃんと解けたので OK

その他

ちょっとだけ Pandas の勉強をした。メソッドの仕様などをいちいち検索するのが面倒

11/26

機械学習

(機械学習というよりはデータサイエンスだけど) Kaggle 本を少し読み進めた。評価関数だけでこんなにあるのか…という感じ多分実践しないと身につかないけど、なかなかコンペのためのまとまった時間を取れず、どうしようか

競プロ

久しぶりに CF のバチャをやった。

0 を +1, 1 を -1 で置き換える。累積和を y_i として、S に入れられるのは y_l = y_r を満たす区間である。

「-1 される全ての箇所がいずれかの区間に含まれる」という条件を達成するには、次のようにする。

n = 0, 1, 2, 3, ... に対し、初めて y_i = n となる位置を f_n とおく
[f_k, f_{k+1}-1] を S に追加する

ある場所を flip することで、集合 {f_n} は高々 2 要素しか出入りしないので、変化する区間は高々 4 つである。よって 4N 回の出し入れで解ける。 f_n を見つけるためには区間加算の遅延セグ木で二分探索をする。

https://codeforces.com/contest/1758/submission/182595283

11/27

競プロ

$[x^{M - N}] (1-x)^{-2N} \prod_{n=1}^{\infty}(1-x^n)$ が答え。

$M-N \leq N$ という制約があるおかげで五角数定理が使える。次数 M-N 以下の項は $O(\sqrt{N})$ 個しかないので、それぞれに対し $(1-x)^{-2N}$ の対応する項の係数をかけて足し合わせる。

二項係数の計算には Lucas の定理を用いる。

https://atcoder.jp/contests/abc279/submissions/36849042

五角数定理関連、面白そうな話が多いので読みたい。

↓分割数を $O(N \log N)$ で

https://suu-0313.hatenablog.com/entry/2022/06/15/160626

11/28

競プロ

Codeforces Round #829 (Div. 1) バチャ

0 がない場合は簡単。N が偶数でなければならず、逆に偶数の時は、前から 2 個ずつグループ分けし、グループの 2 数が異なるならそれらをさらに一つずつに分割すればよい。

0 がある場合は、1,-1 が連続する連続部分列に分け、それぞれに対し↑のように分ける。すると各グループの総和は -1,0,1 のいずれかになるので、0 を含める / 含めないによって調節して上手く総和を 0 にする。

もともとの総和が偶数の時は必ず構成でき、そうでないときは絶対にできないのでこれで OK

各 $1 \leq n \leq x$ について $n!$ が足される回数を数える。このとき、 $n!$ が $n+1$ 回足されたら $(n+1)!$ が一回足されたとみなす。

すると、n < x ならば $n!$ が足された回数は 0 回でなければならない。1 回以上のものがあるなら、最小のものを k とおくと、 $(k+1)!$ で割った余りが 0 にならず不適。

終了条件を考える。0 の個数を Z として、先頭 Z 項がすべて 0 になっていればよい。

先頭 Z 項に 1 が k 個あるとすると、操作によって k は変化しないか 1 減るかのどちらかである。1 減る操作は $k^2$ 通りあるので、期待値 $\frac{N(N-1)}{2k^2}$ 回で 1 減る。あとはこれを各 k について足す。

それぞれのベッドはたかだか 1 回しか動かないとして良い (未証明。こうじゃなきゃ解けないだろの気持ち) 。ベッドではなく空きマスが動くと考え、グラフを作り、それぞれのマスについてそのマスを空きマスにするための最小コストをダイクストラ法で求める。市松模様に分けると、隣接する 2 マスを空けるとき、2 つのマスを空けるための操作は干渉しないことがわかるので、OK

11/29 以降

多忙につき休止。12 月中旬に再開するつもり大量に Scrap を作成するのが気持ち悪くなってきたので、一つにまとめるか悩んでいるそれに Zenn の Scrap を日記に使うという方法自体おかしい気がするんだよな

2022-12-18

日記 11/1–11/15

11/1

おやすみ

11/2

競プロ

ARC150 のバチャをやった。D は簡単だったが、C で関節点列挙などを考えてしまい手こずった。

B が A の部分列かどうか判定するためには、B の要素を前から見て、初めて A で現れる場所を貪欲に取っていく、という方法をとる。

逆に、「なるべく B が部分列として完成しないようにする」ためには、「最小で B の何番目の要素までにとどめられるか？」というのを計算すればよく、これは 01BFS で計算できる。

11/3

競プロ

PCK 本選の練習として、TeraPad (本番環境のエディタ) + cygwin g++ で 2018 年度の過去問を解いた。
なんとかペナを出さずに解けたが、シンタックスハイライトがない白黒の環境だとかなりストレスが溜まる…
あと Manhattan MST が出てきたのは驚いた。

11/4

競プロ

明日は PCK 本選。ライブラリの確認と、一応知っておくべきと思ったものを勉強した
実は多項式の除算を初めて学んだ。reverse して inv をかけるだけでいいのか

多項式補間のアルゴリズムを今まで「適当にセグ木っぽくやればいけるでしょ」と思っていたが、よくよく考えてみるとそんなに簡単じゃなかった

11/5

競プロ

PCK 本選。割と達成感のある結果だったと思う

その他

ABC276 の Writer をしていた

11/6

競プロ

パソコン甲子園本選、優勝！！！

11/7

組合せゲーム理論

hot/cold/tepid なゲームの復習と、cooling による解析と temperature を求める練習
hot なゲームは解析が難しい (PSPACE 完全) ので、完全にお気持ち解析

11/8

競プロ

暖色埋め

https://atcoder.jp/contests/abc276/submissions/36324137

$\displaystyle [x^M] (1-x)^{-2}\left(\frac{x+x^2}{1-x^3}\right)^{N-1}$ が答え

これを $(1-x)^{-2} (1-x^3)^{1-N}$ と $(x+x^2)^{N-1}$ に分ける
前者は、sparse な形式的冪級数の pow を微分で漸化式を導出して計算する方法を用いて $(1-x^3)^{1-N}$ を求め、2 回累積和をとる
後者はただの二項定理

https://atcoder.jp/contests/abc275/submissions/36324465

$f(X)$ は、 $a^\top x \leq X, b^\top x \leq X$ を満たす成分が非負整数のベクトル $x$ に対する $c^\top x$ の最大値
$\displaystyle \frac{f(X)}{X}$ について調べたいので、 $x$ の各成分を $X$ で割りたい気持ちになる

そこで、 $a^\top y \leq 1, b^\top y \leq 1$ 満たす成分が非負実数のベクトル $y$ に対する $c^\top y$ の最大値を考える
成分が非負有理数のベクトル $y$ であって最大値 $M$ を達成するものが存在する。成分の分母の LCM を $L$ とすると、 $y$ の $L$ 倍は成分が非負整数であり、もとのナップサックの解になる

$X = nL$ に対して $\displaystyle \frac{f(X)}{X} = M$ であり、 $nL \lt X \lt (n+1)L$ のとき

$M \geq \frac{f(X)}{X} \geq \frac{f(nL)}{(n + 1)L} = \frac{n}{n+1} \times M$

ゆえに $n \to \infty$ で $\displaystyle \frac{f(X)}{X} \to M$

$M$ を求められればよい。前述の LP の双対をとると、 $sa + tb \geq c$ を満たす非負実数 $s, t$ に対する $s+t$ の最小値、となる。 $K = s+t$ を固定して二分探索をすると簡単で、 $sa_i + (K-s) b_i \geq c_i$ が全ての $i$ に対し成り立つような $s$ の集合 (区間) が空でないか判定すればよい。

https://atcoder.jp/contests/abc255/submissions/36326840

座圧 + 遅延セグ木

11/9

競プロ

https://atcoder.jp/contests/abc261/submissions/36341690

「dp[l][r][c] := c を T[l..r) に一致させる最小コスト」を頑張って計算
置換する文字列の長さが 1 かそうでないかで処理を変える

https://atcoder.jp/contests/abc255/submissions/36345250

X_i の小さい順に Grundy 数を頑張って計算する

n の Grundy 数を g(n) と表す。g(n) = k となる n が 2 個以上あるような k は多くないので、このような k と対応する n の値を全て管理する。すると mex の計算に必要な情報が集まる

11/10

競プロ

https://atcoder.jp/contests/abc254/submissions/36365523

上下移動は必ず |Y_i - W_i| のコストがかかる。水平移動を最小化する問題

dp[i][k] を i 階から 2^k 回エレベーターを使ってたどり着ける最上階として、ダブリングを行う

Y_i < W_i ならば、スタート地点を含むエレベーターでなるべく登っておき、ゴールを含むエレベーターでなるべく降りておいてから処理する

X_i = Z_i または Y_i = W_i の場合に注意

11/11

競プロ

https://atcoder.jp/contests/abc262/submissions/36383071

S, X は常に単調増加であり、最終的に S は空になるとしてよい

S に追加する集合を固定し、前から順に a_1, ..., a_n とおく。a_i を S から取り除くのは、

a_i 以降ではじめて a_i より大きい数を S に追加する直前
a_n を追加した後

のいずれかである。前者の場合に X が単調増加でなくなってしまうのは、a_i を X 追加するより前に a_i より大きい数を X に追加してしまった場合であり、これが起こるのは a_i < a_j < a_k を満たす整数 j < k < i が存在する場合のみである。よって、このような 3 整数が存在しないように a_1, ..., a_n を最大個数選ぶ問題となる

「A_l, ..., A_r のうち d 以上 u 以下のもののみを選ぶときの最大個数」を dp[l][r][d][u] とおき、これをメモ化再帰によって計算していく

l = r は自明で、l < r のとき

A_l を選ばないなら dp[l + 1][r][d][u]
A_l を選ぶなら、dp[l][x][d][A_l] + dp[x + 1][r][A_l][u] を全ての x について試す

とすればよい

11/12

競プロ

cerr デバッグライブラリを整備した。今日だけで結構 C++ に詳しくなったかもしれないな… とりあえず

「引数それぞれに対してある処理をする」のようなマクロは書けない
マクロに MACRO(std::vector<int>{1, 2}) みたいなのを投げるとカンマのせいで壊れる。MACRO((std::vector<int>{1, 2})) にすると直る

というのは知らなかった。

Detection Idiom を使って型 T に対し std::ostream.operator<<(const T&) が定義されているか調べようとしたときに、modint のコンストラクタを explicit にしていないせいで std::vector<modint> が modint に変換可能と判断され、std::vector<modint> に対し operator<< が定義されていると誤って判定されるという罠を踏んだ

書いたもの↓

https://github.com/KodamaD/kod-library/blob/main/src/misc/debug.cpp

+α 今日の ABC の G を解いた

https://atcoder.jp/contests/abc277/submissions/36403640

ある移動方法について、頂点に書かれた 01 の列を b_1, ..., b_n と並べると、

b_i = b_j = 0, b_k = 1
i < k, j < k

を満たす i, j, k の組の個数がスコアになる

これを i < j < k を満たす組と i = j < k を満たす組に分類する。それぞれ DP で「 i, j, k のうち何個目まで決め終えたか？」を持って計算

11/13

競プロ

ライブラリについて

ラクするためのユーティリティだけ整備して、難しいデータ構造やアルゴリズムは他の人が準備したものを使えばよいのでは？と思った。多岐にわたるライブラリを自己製で最速・最良の状態で用意しておくのは非効率的な気がするとはいえ、どこまで自分で用意するかの境界を決めるのが難しい。平衡二分木とかになると流石に要らないと思うけど、畳み込みや FPS は (ACL に convolution があるとはいえ) 持っておきたい

解いたもの

https://atcoder.jp/contests/abc277/submissions/36465459

NM 変数の two-sat 各 $X_i$ について M 個の bool 変数 $b_{i, 1}, \dots, b_{i, M}$ を用意し、 $b_{i, k} = 0$ ならば $b_{i, k+1} = 0$ が成り立つように条件を課す。すると $b_{i, 1}, \dots, b_{i, M}$ は $1,\dots,1, 0, \dots, 0$ のように並び、 $b_{i, j} = 1$ であるものの個数を $X_i$ として定めると、 $X_i \lt k \Leftrightarrow b_{i, k} = 0$ と言い換えられる。これを用いると各条件は $O(M)$ 個の clause で書ける

5h

PTZ Summer 2022 Mirror Day 2 をやった。前回よりは活躍できた

C に「 $A_i \neq P_i$ であるような順列 $P$ を構成せよ」という問題があって、自分は綺麗な解法が思いつかなかったが、想定解が面白かった。

$A_i$ が全て同じ値なら構成不可能。そうでない場合は必ず構成できる。

先頭 $N-1$ 項は、すでに決めた整数が $1, \dots, N$ の円環上で常に区間をなすように決めていく。すると、つねにちょうど $2$ 通りの選択肢があるのでかならず条件を満たすように決められる。 $P_N$ は一通りしかないので条件を満たさない可能性があるが、その場合 $(A_N = P_N)$ は $A_i \neq A_N$ となる $i$ をとると(仮定より必ずとれる)、 $P_N = A_N \neq A_i, P_i \neq P_N = A_N$ より $P_i$ と $P_N$ を swap すればよい。

11/14

射影幾何

調和点列の定義と、いくつかの性質の証明

競プロ

AHC016 をやり始めた

11/15

競プロ

AHC016 をやった昼に提出したら 150 位くらいで、夜に改善して 95 位にした折角だしメモとっておいて参加記出そうかな

2022-12-18

日記 10/16–10/31

10/16

射影幾何

講義のための予習
Projective Plane の双対について

群論

準同型・同型、剰余群の復習

競プロ

ARC151 に参加
悔しいことに黄 diff が解けず。対象とする桁が異なる操作を入れ替えられることに気づかなかった
もっと練習して実力を取り戻そう

10/17

競プロ

ARC151-D を upsolve した
これ解けなかったのかなり悔しいな…

射影幾何

数研で講義担当

組合せゲーム理論

LS / RS の性質の復習、証明と Number Avoidance などの証明
難しい…

10/18

競プロ

自作 CLI に若干の不便さを感じていたので、機能を追加した
やっぱり Rust は書きやすいし clap が便利すぎる

10/19

競プロ

今週末 PG Battle があるので、ABC の過去問で練習

10/20

組合せゲーム理論

来週担当なので少しだけ予習。章末問題をちょっとだけ見ていたが、あまり面白いのがなかった

競プロ

昨日と同じく ABC の過去問を何問か

10/21

競プロ

黄、橙 diff を少し
ARC-E でまだ解けていない Random IS を考えてみたが、解けず
赤 diff はどれくらい時間を費やしたあとに解説を見るべきかかなり迷う

10/22

競プロ

PG Battle に参加
かつおぶし全完できてうれしい
チームメイトも頑張ってくれた

組合せゲーム理論

7 章を流し読み。今までとは打って変わって、順序を全く気にしない不偏ゲームの世界
ところで Grundy's game というのが出てきたのだが、簡単なルールなのに Grundy 数の公式が見つかっていないのは意外

その他

今週は ABC274 の tester をしていた
Nim Product を使って Rolling Hash みたいなことをする問題が出たのだが、結局 Nim Product 自体はあまり理解できないまま通してしまったので、また時間のあるときに勉強しよう

10/23

組合せゲーム理論

だらだらと講義資料作成をしていたらなんか一日が終わってた（？）

10/24

組合せゲーム理論

講義担当。毎回、準備した資料にどこかしら穴が見つかるのなんとかしたい

その他

数学研究部の追い出し会に参加した。追い出す側が今年で最後だということに驚き

10/25

競プロ

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_f
https://atcoder.jp/contests/jsc2019-qual/submissions/35959281

「総和が R 以下」から「総和が L-1 以下」を引けば答えが求められる。以降では L に関する条件を無視する。

大きい方から M, M + 1 番目が異なるものを数えることにする。M 番目の値 k を固定して全て調べる。

「大きい方から M 個は k 以上、それ以外は k 未満」から「大きい方から M 個は k+1 以上、それ以外は k 未満」を引いた値が知りたい。それぞれ $(1-x^k)^{N-M} (\frac{1}{1 - x})^{N+1}$ の $x^{R-kM}$ の係数と $x^{R -(k+1)M}$ の係数が分かればよい。