遺物紹介

この記事は PUC 逆 Advent Calendar 2023 の 8 日目の記事として作成されました。

adventar.org

(逆ってなんだ……？)

前日の記事は養生さんの18ローラー記事です。

note.com

ボルテの埋めはほとんどやってないので、地力向上のためにもそろそろやった方がいいかな～
埋めてないせいでアリーナが弱かったり曲を全然知らなかったりするので、気運があればぼちぼちやりたいですね。

記事概要

null です。

今回は総集編ということで、これまでに作ってきた様々なツールを紹介しようと思います。

本当はもっとぶっ飛んだ記事書きたかったけどネタがないので仕方なし

音ゲー編

Score-Tolerance

分類	ユーザースクリプト/ブックマークレット
機能	譜面保管所で許容を表示する
作成年	2021
使用言語	JavaScript
GitHub	○

音ゲーのサポートツールを作った話 - メモ帳

ボルテのS許容やウニのSSS許容などが気になるときに使えるツールです。

ボルテ

ウニ

TamperMonkey版はPC限定ですがページが自動で書き換わるので便利です。
ブックマークレット版はスマホでも使えます。

実装は譜面保管所のHTML構造に完全に依存しているため、リニューアルされると動かなくなります。そのため現在は動きません。

……と書くつもりでしたが、時間があったので現在のページで動くように書き換えておきました。あとついでにオンゲキも追加しました。
よかったら使ってみてください。

オンゲキ

また動かなくなった場合でも一言くれれば直します(時間があれば)

chunifil

chunifil

分類	Web サイト
機能	CHUNITHM の埋めを支援する
作成年	2022
使用言語	HTML, CSS, JavaScript
GitHub	○

note.com

ウニの下埋めモチベを上げるために作りました。

理論値埋めをするにあたって「何から触ればいいかわからない」という状態に陥ってしまったので、課題曲を提示してくれるツールがあればいいと思い実装に踏み切りました。
実際これのおかげでかなり理論値が埋まりました。

そこそこ気合入れて作ったので、自分が今まで作った成果物の中では多分一番ちゃんとしてます。
chunirec は API が整備されているのでこういうのも割と簡単に作れます。便利ですね。

ちなみに当の本人は現在下埋めから逃げて4曲しか収録されてないチュウニズムをやっています。
全AJしたらやるかもですが、他の音ゲーもやりたいし音ゲー以外にもやりたいこと/やらないといけないことが大量にあるので、モチベーションが残ってたらやってもいいかなくらいの気持ちでいます。

PrskEx

分類	Web サイト
機能	プロセカのリザルトのEXスコア(後述)を計算する
作成年	2023
使用言語	HTML, CSS, JavaScript
GitHub	○

PrskEx

部内のIRでEXスコア制 (PERFECT×3 + GREAT×2 + GOOD) が採用されたため、リザルト提出の負担を減らすために作成しました。

がんばりポイントとして、画像から文字データを抽出する技術(OCR)を組み込んでいます。
OCR のライブラリは Tesseract.js を用いています。

ただそのまま画像を突っ込んでも謎の文字列しか得られないので、実際には

1. リザルトがある領域をざっくり切り取る
2. 画像をグレースケールに変換し、さらに白黒を反転させる
3. コントラストを特定の値に変換する
4. OCR を行い、英数字から成る文字列の列を抽出する
5. 数字以外を消し、4桁の整数が4つ得られたら成功。そうでなければ、ハイパーパラメータを変更して1.に戻る

という流れで抽出しています。
ハイパーパラメータはそれっぽいものを事前に手動で列挙しておき、それらを全て試してうまくいったものを採用するという実装になっています。

リザルト提供：R2様

GitHub Pages 上で公開する Web サイトは静的なものに限られるため、JavaScript のみで完結させるのが結構大変でした。
実際 Python で試作するのはそれほど手間ではありませんでしたが、JavaScript に移植するのに多くの時間を費やした記憶があります。

これもアプデの影響で動かなくなっていたので直しました。
新UIに対応させた後も何故か激唱Full(APPEND)だけ読み取れなくて唸っていたら、昔書いた「読み取った数値が4000以上なら認識ミスとする」(2本指音ゲーに4000ノーツ越え譜面があるわけないので)という処理が原因で爆笑しました

あと、今調べたら先行研究がありました。参考にしたかった…

qiita.com

逆紅白戦2023 スプレッドシート更新自動化

分類	スクリプト
機能	対戦相手の chunirec を監視し、スプレッドシートに反映する
作成年	2023
使用言語	Google App Script (JavaScript)
GitHub	○

CHUNITHM の部内チーム戦である逆紅白戦の際に作成したスクリプトです。

誰が選曲したかわからない楽曲群から1人1曲選んでそれを選んだ人と戦う、というのを自選他選ともに行うルールのため、誰が選んだのかを知るためにスコアの更新を確認する必要がありました。
そこで chunirec のスコアを監視してスプレッドシートに反映させることにしました。chunirec を更新していない人には使えませんでしたが、労力が減ったのでよかったと思います。またやりたいね

音ゲー以外編

千葉大生向けGPA計算ツール

分類	ブックマークレット
機能	学生ポータルで GPA を計算する
作成年	2021
使用言語	JavaScript
GitHub	○

千葉大生向けGPA計算ツール - メモ帳

学生ポータルがリニューアル直後で GPA の表示機能がなかった時に作りました。
現在は公式で GPA を計算してくれるので、完全に過去のものですね。

スプラトゥーン疑似ブキチ杯bot

分類	Discord Bot
機能	Discord のコマンドでブキのランセレを行う
作成年	2023
使用言語	JavaScript(, Google App Script)
GitHub	×

身内でスプラトゥーンをやるための discord サーバーであるクラブラ禁止鯖で動く bot です。

ブキがランダムに配布される「ブキチ杯」をプラべでやったら楽しかったので、勉強がてら作ってみました。

spoiler タグを使っているため他チームのブキは見えないようになっています。

クリック前

クリック後

現在は停止中。

おわりに

今までの成果物を列挙してみました。
他にも研究やらインターンやらで色々作ってますが、ここでは紹介できないので割愛。

Web 関連は授業では全くやらないので、基本的に独学で習得しました。
とはいっても何からやればいいかわからなかったので、月額制の学習サービスに1か月だけ登録して一通り勉強しました。
それからは既存のスクリプトやF12とにらめっこしつつ見様見真似で色々作っています。

何かを作るときや不慣れな言語でコーディングする際は、必ずと言っていいほど ChatGPT を使っています。
正直これを使いこなせるかどうかで作業効率に明確な差が出るように思います。
以下は使用例：

使用例1

使用例2

あとこんだけWeb開発しておいてなんですが、フロントエンドは大して好きじゃないです。
表示が思い通りにいかずくねくねしてる時間が虚無すぎるのと、JavaScript がカスなのが大きな理由です。できれば TypeScript を使いたかったんですが、GitHub Pages で使えないんですよね……

でも自分の作ったものの動く様がわかりやすいので、達成感はあると思います。

そろそろバックエンドとかも触ってみたいですね～

ICPC2023国内予選 参加記

今年もICPCの予選に参加したので、参加記を書きます。

チーム情報

チーム名：Type-C
所属：千葉大学
メンバー：stoq, hiryu, WiIIiam

自分 (stoq) は 4 回目の参加、他 2 人は初参加です。
hiryu くんは B2、WiIIiam くんは B1 で、来年以降も ICPC に出てくれる若い人が欲しかったので最終的にこのメンバーとなりました。

余談ですが、"WiIIiam" の I は大文字の i です。

作戦

自分が一番コーディングが速く ICPC の提出方式にも慣れているのと、チームメイト 2 人は考察が強いことを考慮した結果、自分がコーディングを全て担当しその間に 2 人に解法を考えてもらう作戦にしました。
特に hiryu くんは AGC の銅 diff 構築を本番で通すほど考察が強いので、自分の苦手な構築が出た場合は丸投げするつもりでいました。
結果として、この作戦が功を奏しました。

当日までの練習、リハーサル

過去の予選 1 年分 (2019) と模擬国内で練習しました。
過去問の方は D で詰まってしまい 3 完でしたが、模擬国内は調子が良く 5 完でした。

リハーサルでは研究室のプリンターのドライバをインストールするなどして準備を整えました。

本番

問題文：
icpc.iisf.or.jp

初動は簡単な環境構築をしたのち、自分が A、WiIIiam くんが B、hiryu くんが C を開きました。

A はシンプルな実装問題でしたが、ペナルティを絶対出せないので丁寧にチェックしてから提出しました。
緊張していましたが、無事 AC(5:57)。

B 問題はあみだくじの問題で、WiIIiamくんに問題の解釈が合っているか確認しつつ実装。これも簡単な全探索の問題で、落ち着いてAC(16:29)。

C は構築の問題で、大昔の Div 1 で似た問題を見たことある気もしましたが思い出せず、hiryu くんに丸投げしました。
(後で調べたら見つけたものの、言うほど似ていなかった。Problem - B - Codeforces)

D を先に見ると、なんとなくいけそうな感じがしたので並行してこちらを考えます。
答えが最大になるのは かつ が全て 'o' のときですが、これは の 7 個で達成可能です。
よって 6 個以下の場合を全探索し、各場合についてナップサックDPをすれば解けそうです。
6 個以下の場合を DFS で実際に数えてみると 14 万程度だったため、この方針で書き進めます。

ナップサック DP パートは bitset を使うと速くなるな～と思いつつ使わなかったので実行に 2,3 分かかりましたが、提出すると無事 AC(50:47)。

D を解いている間に hiryu くんが C を閃いたようなので、解法を聞いて実装。左上から順に 1,2,... としたとき、奇数全て→偶数全て と並べると条件を満たすようです。
実装ではアサーションを合わせて書いたので実行が終わるなら AC が出る、と考えていました。無事実行が終わったので提出。

しかしここでトラブルが発生。
ファイルを提出した直後、WA でも AC でもなく「サーバーに接続できません」のような画面が出てしまいました。
そこでリロードボタンを押すと、Wrong Answer の画面が。解法に誤りがあると思い肩を落としましたが、Top 画面に戻ると何故か No.2 のデータセットが用意されていました。
どうやら変なタイミングでリロードしたせいで 2 回同じファイルを提出した扱いになってしまったようです。
動揺しつつも No.2, No.3 のデータセットで提出すると AC(1:09:52)。

この後コーチを通じて審判団にペナルティを取り消せないか聞きましたが、サーバー自体は正常だったようでダメでした。
(まあ結果的にはこのペナルティがあってもなくても順位は変わらなかったので、セーフ)

気を取り直して E に取り掛かります。
E は先に見ていた hiryu くんから、 を見て 個改ざんしたときの最後のペアの辞書順最大、とする DP で解けそうと言われ、実際それでいけそうだったのですぐに取り掛かりました。
はじめに x と y を swap することで通常の辞書順序にしておきます。

DP の遷移は、全てちゃんと書こうとすると細かい場合分けが必要になります。
しかし実際には、 から配る遷移について、

• 改ざん後(改ざんしない場合も含む)の としてあり得るのは の 3 通りのみ
• 改ざん後(改ざんしない場合も含む)の としてあり得るのは の 4 通りのみ

しかありません。そこでこれらの12通りの候補を全部調べて条件を満たすものだけ遷移する、という実装方針を取りました。
これはかなり定数倍が悪いですが、ICPC は手元実行のため、実装の軽さを優先しました。実行は 4,5 分かかりましたが、実装・デバッグにかかったであろう時間を考えれば十分プラスだと思います。提出して、AC(1:50:34)。

F は幾何でしたが、なんと WiIIiam くんが解けたかもしれないとのことで、hiryu くんも正しそうと言っており、解法を聞きました。
(strictな)凸包を取った後、凸包に含まれる全ての点 と前後 2 方向について、多角形での[次/前]の頂点を 、凸包での[次/前]の頂点を としたときに、 が直線 上にあることが必要十分、とのことです。

2人に都度質問して自分が解法を理解できているか確認しつつ、全力で幾何ライブラリを写経して実装。
デバッグを繰り返してサンプルが合ったので提出すると、なんと一発でAC(2:36:03)。
もし自分だけなら間違いなく思いついていなかったので、チームの強さを思い知りました。

ここら辺で順位表を見てすげ～と言って踊っていました。

G は期待値の問題で、式変形をこねくり回していると終了 3 分前にそれっぽい DP が降ってきましたが、時間切れ。

H は見ていません。

結果

301 チーム中 6 位で予選通過しました！

まさかここまでの高順位を取れると思ってはいなかったので、ただただ驚いています。

感想

チーム戦かつ手元実行という、ICPC ならではの環境をうまく活用して勝つことができたと思います。
実装担当であるため緊張していましたが、同じようなバグに嵌り続けることなく素早く実装できてホッとしました。
(余談ですが、次のようなテンプレがデバッグでかなり役に立ちました。普段から愛用しています)

#define dbg(x) cerr << #x <<  ":" << x << endl;

また、チームメイトの考察力にもとても驚かされました。
3 人いれば同じ問題を様々な視点から考えることができるので、それらをすり合わせて解法に辿り着くのが面白いです。
昔と比べるとコミュニケーション力が(主にゼミのおかげで)上がっていたので、齟齬なく意思疎通ができたのもいい点だったと思います。

アジア地区もこの調子で頑張ります！

統計検定2級 感想など

合格しました

試験概要

• 出題範囲は大学1,2年レベルの統計学
• 90分で35問程度
• 100点満点/60点以上で合格
• 全て選択問題
• PCで受験する。ただし自宅受験はできず、近所のパソコン教室などに申し込む
• 問題は、プールされている問題の中からランダムに出題される(そのため問題は秘密)

結果

82/100 で受かりました。
85点くらいから優秀者表彰があるとの噂なので惜しくも届かず。

テキスト、資料

bellcurve.jp

↑のページの基礎編が大体ちょうど統計検定2級の範囲なので、とりあえずこれを一通り見とけば大丈夫です。

演習は院試対策で買っていた『大学１・２年生のためのすぐわかる統計学』を使いました。amazon

過去問は公式サイトで公開されています。これらはペーパーテスト時代のものなので参考程度に。

過去問題｜統計検定：Japan Statistical Society Certificate

過去問に挑戦｜統計検定：Japan Statistical Society Certificate

ちなみに1個目の2021年6月のは歴代最難らしいのでこれが解けたら受かります。

公式の問題集も買いましたが、おそらく全て直近の過去問からの抜粋なので買わなくてもいいです

小賢しいテク

選択問題なので適当やっても解けます。時短大事

例：

• 正規分布とは書いていないが、答えが分布に依存しなさそうなら勝手に正規分布を仮定してよい
• I, II, III の正誤を判定する問題で、明らかに I ならば II が成り立つので選択肢が減る
• 一般常識から帰無仮説が成り立つわけないとわかる

ただ、確信を持てない場合は真面目に解きましょう

あと、計算した答えが 12.73 だったけど選択肢に12.8しかない、みたいな場合は大体間違ってるので選ばず解き直した方がいいです。

罠ポイント

• 適当に近くのパソコン教室に申し込んだら騒音がひどくて大変だった。途中で耳栓を貸してもらったが、あまり変わらなかった。
• 計算用紙と筆記用具は会場側が用意するが、シャーペンではなくマジック+透明のクリアファイルみたいなやつだった。

感想

範囲は広いので勉強しないと難しいですが、逆にちゃんと勉強していれば簡単な問題が多いのでそれほど合格難易度は高くないと思います。手頃な資格が欲しい人にオススメ。

気が向いたら準1級も取ります

ABC272 F - Two Strings 筋肉解法

パワー

問題概要

問題リンク：

atcoder.jp

要約：

• 長さ の文字列 が与えられる
• を 回 rotate した文字列を と書く
• 組 であって、 (辞書順序) を満たすものの個数を求めよ

解法

想定解法は Suffix Array ですが、ローリングハッシュのみでも解けます。

流れとしては、

• を辞書順で昇順ソート
• に対し、 を満たす最小の を二分探索で求め(存在しないなら )、解に を加える

となります。

もちろん を実際に作ってしまうとそれだけで MLE になります。

これは を長さ 2 倍にしたもののハッシュの累積和を取っておき、その左端の index を と見なせばよいです（実装参照）。

ローリングハッシュを用いた文字列の辞書順比較

ローリングハッシュと二分探索を組み合わせると、2つの文字列があったときに、それらの部分文字列の common prefix の最長を高速に求めることができます。
これにより、2 つの文字列の部分文字列の比較が高速に行えます。

さらにこれを比較関数とすることで、部分文字列のソートを 2個で行えます。

（↓同様の手法で解くことができる問題。というよりこれの tester 解を見てこの記事を書いています）

yukicoder.me

同様に、 に対して を満たす最小の を求めるパートも 2個で行えます。

実装

ローリングハッシュはライブラリにしておくといざという時に役立ちます。

提出：
atcoder.jp

なんか 2000ms って書いてますね。見なかったことにしてください

定数倍高速化すればもう少しマシにはなると思います。
(ちなみに mod1000000007 でやったら衝突しました。それはそう)

まとめ

定数倍高速化を入れて君だけの最強ローリングハッシュを作ろう！

ICPC 2022 Asia Yokohama Regional 参加記

2022/12/27,28 に開催された ICPC 2022 Asia Yokohama Regional に参加してきました。

Day1

1日目は開会式→リハーサル→チーム紹介の流れでした。

開会式

registraion を済ませてしばらくすると開会式が始まりました。やっぱりオンサイトだと盛り上がりが感じられていいですね。

つもいよろずさんのオープニング映像がめちゃかっこよかったです。

リハーサル

エディタやUS配列キーボードに慣れながら、練習用の問題 4 問を解きました。

エディタは導入が楽と聞いていた CLion を使いました（VSCodium とも迷いましたが、あっちは拡張機能が使えず不便らしい）。
実際補完やコード整形も問題なく使えたので、おすすめです。

CLion は使用する前に activate する必要がありますが、これは手順を記した紙が配布されるので、それに沿って行います。
さらに自分のチームは自動補完(Editor -> General -> Code Completion)や型、パラメータのヒント(Editor -> Inlay Hints) を切っていました。補完は Crtl+Space で出てくるので切っていいと思います。

コードの置き場所は、まず CLion で ICPC という名前のプロジェクトを作り、そこに A.cpp などのファイルを置く感じでやりました。team01/CLionProject/ICPC/A.cpp みたいな感じ。
また、コンパイルや実行は CLion を介して行わず、全てターミナルから行いました。ターミナルを使う際はコピペのショートカットを Ctrl+C, Ctrl+V に変更していました。ただしこれをやると Ctrl+C で実行を停止することができなくなります。

ICPC ではコードを印刷することができ、これを利用してPCを使わずデバッグすることができます。が、結果的に本番では使わなかった。
print.sh というシェルスクリプトが用意されており、ターミナルで $ print.sh (ファイル名) を実行すると、印刷されたコードをスタッフが届けてくれます。便利！

環境（物理）については、暖房が効いているので結構暖かかったです。ただ T シャツ 1 枚だと寒いので、T シャツの下に長袖を着ている人が多かったです。（Tシャツが見えないといけないので、上には着れない。羽織るのはいいらしい）

コンテスト中はおやつが大量に用意されているので、お腹が空くことはありません。

チーム紹介

ユニークなチームが多くて、すごい（すごい）
実在しないと思っていた人が実在していて驚きました。

終了後

のいみさん達と麻婆豆腐を食べに行きました。てかのいみさん2年前会った時と比べてチャラくなってた。草

横浜と言えば pic.twitter.com/0m9IZ8OsAq

— stoq (@stoq_) 2022年12月27日

Day2

前日は不眠が発動したため全然寝れませんでしたが、がんばって起きました。朝早いのはキツい。

本番

問題リンク(ミラーコンテスト)：
onlinejudge.u-aizu.ac.jp

前半のペナルティを極力抑えたかったので、私がA、はにゅさんがB、ころも君が環境構築とC以降の和訳を担当しました。

Aは単純な実装問題で、早解きは得意なので素早く実装しました。構築問題なので丁寧にテストした後提出、そのまま AC(0:15) 。

次にはにゅさんがインタラクティブのBを実装。1ペナしたものの、程なくして AC(0:24) 。

その後他の問題の要約をころも君から聞きながら、解けそうな問題を探します。
が、ここからが苦しく、解けそうな問題が見つかりません。

順位表をずっと見ていたものの、上位陣もかなり苦戦しているらしく、しばらく全然動きがありませんでした。
D,F,G あたりが通されていたため、それらを考察しました。

しばらくしてはにゅさんが G を解けたそうなので実装をお願いしつつ、D,E,F を考察します。
この辺でモニターが映らなくなるトラブルがあり、コンテスト時間が3分伸びました。
その後はにゅさんのサンプルが合い、提出すると G が AC(2:33)。チーム戦の心強さを感じました。

D は考察した結果コインの移動と回転を数パターンだけ試せばよいとわかり、頑張って実装しました。
回転による座標変換が面倒でしたが、気合で実装すると AC(3:45) 。
回転は移動前の盤面を回転させましたが、終わった後で移動後のターゲットパターンを回転させると楽と聞いて目から鱗でした。

残りは E,F を考察しました。
E は の DP は簡単に思いつくものの、セグ木で高速化しようにもそのままでは更新範囲が区間にならないので唸っていました。
F は明らかに天才必要十分条件ゲーで、符号を適切に割り振ると総和が0になる +α なんだろうな～と思いつつも、具体的な条件はわかりませんでした。終わる直前には「ある程度符号の割り振り方が多いならYes」みたいな嘘を書いていました。

そしてそのままコンテストが終了……

問題解説

解けなかった問題の解説を聞いて天才か～？とか言っていました。
Fは案の定天才ゲーで、順位表マジックがなければここまで通されていないんじゃないかと思います。

順位発表、Yes/No

チーム CUPC は4完で43チーム中21位でした。できればもう1問通したかったですが、まあ悪くはない順位なので満足です。

そういえば結果ツイートしてなかった。ABDGで21位、AとDを担当しました
一昨年の順位は抜けなかったけど、半分より上なのでそれなりに満足 pic.twitter.com/htseUpxdEm

— stoq (@stoq_) 2022年12月28日

上位チームの Yes/No はとても盛り上がりました。tonosama が一度 Time Manipulators に抜かれた後、I問題のYesで抜き返して優勝したのが熱かったです。

終了後

他のチームの選手たちやスポンサーの方々と交流しました。

その後は知り合いと遊んだのち、nok0 さん tatyam さん regi さんとご飯を食べました。

🔥🥩🔥 pic.twitter.com/0Awa2CnHYj

— stoq (@stoq_) 2022年12月28日

競プロの人たちと直接会って何かする機会は滅多にないので、新鮮な気持ちで楽しめました。

感想

初めてのオンサイトだったのでいい経験になりました。
強い方々と交流して刺激をもらったので、2023年はもっと Rated に出ようと思います。

はにゅさんが卒業してしまうため 2023 は出場するかどうかわかりませんが、出ることになったらまたよろしくお願いします。

-

Kőnig の定理と最大流最小カット定理

最近組み合わせ最適化を勉強中なので、考えたことをメモ

任意の二部グラフ について、次の Kőnig の定理が成り立ちます。

König の定理 の最大マッチングと の最小点被覆は同じサイズを持つ。

この定理の証明はマッチングに関する増加路(augmenting path)を用いたものが有名ですが、より強い定理である最大流最小カット定理の系としても示せます。

説明のため、 の例として次のグラフを考えます。

まずは から次のような有向グラフ を作ります。

つまり は に頂点 を追加し、向きと辺容量 をつけたものです。
競プロではマッチングをフローで求める際によく出てきますね。

の最大マッチング＝ の最大流

これは馴染み深いと思います。

のマッチングと のフローには一対一の対応が作れます。

具体的には、 のマッチングにその辺と に繋がる辺のみを使うフローを対応させればよいです。
マッチングでは各頂点は高々一つの辺にしか含まれないので、 の作り方からこのような対応は可能です。

さらにこの対応では、マッチングのサイズとフローの流量が等しいです。
これはフローの流量がフローで使われた中央の辺の本数に等しいことからわかります。

の最小点被覆＝ の最小カット

二方向に分けて示します。

の最小点被覆 の最小カット

の点被覆 を任意に取ります。

● が の点

において、 の点と のいずれかを端点とする辺の集合を とします。

そして、 から の辺以外を辿って到達可能な頂点の集合を 、到達不可能な頂点の集合を とします。

縦線が引かれているのが の辺

明らかに は の頂点集合を二分割します。

加えて、 が成り立ちます。もし から への の辺を使わないパス があったと仮定すると、 となり、 が の点被覆であることに矛盾するからです。

よって は カットとなっています。

さらにこのカットのコストは 以下です。これは から への辺が全て に入っていることからわかります。

以上より任意の点被覆 について、コスト 以下のカットを作ることができました。

(2022/11/01 追記：SSRS さんとだれさんに指摘を頂き修正しました。ありがとうございます！)

の最小点被覆 の最小カット

逆に今度は カット を任意に取ります。

カット

において、 または と繋がっている辺の でない方の端点の集合を とします。

● が の点

の から誘導されるグラフ を考えます。

に の点のうち出次数 以上のものを全て追加した集合 は点被覆になります。

さらに、

• のサイズは の左右の辺の本数に等しい
• と のサイズの差分は の中央の辺の本数以下
• の辺（に対応する の辺）は全て に入っている（カットなので）

ことから、 のサイズは のコスト以下であるとわかります。

まとめ

最大流最小カット定理から、

の最大マッチング＝ の最大流＝ の最小カット＝ の最小点被覆

となり、無事 Kőnig の定理が示せました。

ICPC2022国内予選 参加記

今年もICPCに出場したので参加記を書きます。

チーム名はCUPC、メンバーは昨年と同じで はにゅ(@hanyu_ipf), stoq(@stoq_), ころも(@uytvcc) の3名です。昨年は惜しくも予選敗退という結果に終わったのと、はにゅさんは今年が最後のため、今年は特に集中しました。

問題：
icpc.iisf.or.jp

～前日

自分が院試*1を控えてるのとはにゅさんが忙しいのもあって、チームで集まって練習したのは模擬国内だけでした。前日は申し訳程度に ABC と AOJ-ICPC を解きました。

開始前

ご飯を食べたりレッドブルを買ったり胃腸薬を飲んだりして整えていました。

ころもくんは大学の授業の関係で途中から参加するとのことだったので、最初は自分がA、はにゅさんがBを担当することになりました。

コンテスト本番

事前に打ち合わせしたように、まず自分がA、はにゅさんがBを開きました。

Aは素直な実装問題で、素早く実装しつつ絶対にペナを出さないよう何回も見直しました。緊張しながらsubmitするとAC。(4:19)
かなり速いと思っていたのですが、他のチームはもっと速くてびっくり。

ほどなくしてはにゅさんがBをAC。(28:54)
Bは本番中チラ見しただけでしたが、後から見返すとかなり重い実装問題だった（実際苦しそうだった）のでノーペナで通してくれてとても助かりました。

続いてCを開くものの、解法がすぐには思いつかなかったので少し焦ります。

二乗和なので、直感的には練習日を連続させ休息日を分断するのが最適に見えます。しかし直接的に最適解の構造が求まるのかどうかが不明瞭でした。そもそも なので、直接求めるのではなく何かしらを全探索するのかなぁなどと考えていました。

そこでひとまず実験することにしました（ここえらい）。

すると最適解では

• 休息日は、いくつかの練習日によってほぼ均等な長さに分断されている

• 練習日は、一箇所だけ連続していて、残りの個所は単独で存在している

ことが判明。これにより練習日の連続している部分の長さを全探索する解法が可能となり、バグらせつつもなんとか実装しました。

しかし提出すると Wrong Answer の文字が。実験する前に の場合のみ途中まで書いていたのをそのまま残していたのですが、そこが嘘解法でした。該当箇所を全部消してもサンプルはあったのでそのまま提出すると AC。(43:16 +1)
折角愚直解を書いていたのだから、きちんとストレステストをすべきだったと反省しました。

その後Dを2人で考察します。

手元で例を書きだし、ひとまずは条件を満たす分断が存在するかだけを考えることにしました。手元での実験の過程をそのままプログラムとして実装可能に見えたので、書き起こしてみることに。

実装方針としては、

• の要素を前から順に見ていき、実際に を分断しながらシミュレートする。列の先頭要素は std::set で管理する。
• もし が先頭要素の集合に含まれていなければ の直前で を分断し、 を先頭要素の集合に入れる。
• その後、もし が先頭要素の集合の中で最小でない場合、どうやっても の順にはならないので即終了する。最小の場合はそれを集合から削除し、 における1つ次の要素を集合に入れる（存在し、かつ未使用の場合）。

となります。これにより「絶対に分断されないといけない箇所」がわかります。もし「絶対に分断されないといけない箇所」の個数が 以上の場合は の順にできないので、これもまた即終了します。

問題は残りの箇所で、「分断してもしなくてもいい箇所」「分断してはいけない箇所」があります。

の直前を分断しても順番が変わらないための必要十分条件を考察します。
まず必要条件として、 において より左に より大きい要素があってはいけません。何故なら が において より左にあるならば、本来 が取り出されるタイミングで が取り出されてしまうからです。

そこからしばらく考察すると、先程の必要条件は実は十分条件でもあるのでは？と思い始めました。
実際、これは十分条件になっています。 の左の要素が全て 未満ならば分断しようがしまいが の取り出されるタイミングは変わらないので、全体の取り出される順番は変動しません。（コンテスト中は非自明だと思っていましたが、今見るとそうでもないかも）

さらに「分断してもしなくてもいい箇所」の選び方は独立に決めることができます。これは分断によって全体の取り出される順番が変わらないので、結局分断していないのと同じとみなせるからです。この性質が重要で、これにより単純な二項係数で解を求めることができます。

以上を実装するとサンプルが合い盛り上がりました。実装では一箇所サボって になっていましたが実行は爆速で終わりました。はにゅさんの助言もあってとりあえず出してみることに。

するとなんと一発で AC。(1:23:28)
研究やら院試対策やらのおかげで正当性の証明に耐性がついていたのでよかったです。

本番中のコード（本質部分のみ、あまり綺麗ではない）

void solve() {
  int n, k;
  cin >> n >> k;
  if (n == 0) exit(0);
  vector<int> p(n), q(n);
  cin >> p >> q;
  p--, q--;
  vector<int> pos(n);
  rep(i, n) pos[p[i]] = i;
  vector<bool> used(n);
  vector<bool> cut(n);
  cut[0] = true;
  set<int> tops;
  tops.insert(p[0]);
  for (auto qi : q) {
    int i = pos[qi];
    if (not tops.count(qi)) {
      cut[i] = true;
      tops.insert(qi);
    }
    if (*tops.begin() != qi) {
      cout << 0 << "\n";
      return;
    }
    tops.erase(qi);
    used[i] = true;
    if (i + 1 < n and not used[i + 1]) {
      tops.insert(p[i + 1]);
    }
  }
  int div = accumulate(all(cut), 0);
  if (div > k) {
    cout << 0 << "\n";
    return;
  }
  int can = 0;
  vector<int> q_pos(n);
  rep(i, n) q_pos[q[i]] = i;
  rep(i, n) {
    if (cut[i]) continue;
    bool valid = true;
    int j = q_pos[p[i]];
    rep(jj, j) {
      if (q[jj] > q[j]) {
        valid = false;
        break;
      }
    }
    if (valid) can++;
  }
  mint ans = 0;
  rep(i, min(k - div + 1, can + 1)) { ans += bc.C(can, i); }
  cout << ans << "\n";
}

int main() {
  while (1) solve();
  // solve();
}

千葉大学からは例年通り1チームしか出ていなかったのでこの時点で予選通過がほぼ確定し、肩の荷が下りました。

ここら辺でころもくんとも合流し、3人でE, Fを考察します。

Eは問題文を流し読みすると「像には美しい像と恐ろしい像の二種類があり、」の文字列が見えたので「これ2-SATでは？」などと発言しましたがちゃんと読むと全然違いました。ごめん。しかもはじめ和が か でないかと誤読しており、サンプルを見てようやく気付きました。ごめん。

誤読に気付いた後は、行・列の少なくとも一方が の交点を全部決めた後、どちらも の交点で辻褄を合わせる、という方針を考えましたが、反例を発見し断念。括弧列との対応も考えましたが、特に何もありませんでした。

ヒューリスティックが得意な人なら焼きなましで通せそうだなぁという会話もしていました（マラソン詳しくないので実際どうなのかはわかりません）。

Fは構文解析の問題ですがBNF自体はとても簡素なもので、アルゴパートが本質のように見えました。
ころもくんが前から貪欲に解く解法を提示してくれましたが、はにゅさんが反例を発見し頓挫。制約、問題設定的に貪欲ではなさそうという結論になりました。

せめて3乗でも思い付けたらマシンぶん回しで解けるのに、などと考えていました。

コンテスト終了後に解説を見てなるほどなぁとなりました。構文解析において構文が木構造になっているのはよく知られていますが、構文木を陽に持って木DPする問題は見たことがなかったので盲点でした。構文木くらいは思い付きたかった。

G,H はほとんど読んでいません。Hに謎の図があったのだけ記憶に残ってます。

そうこうしているうちにコンテストが終了。
3h コンですが、体感時間は一瞬です。

結果

ABCDの4完28位でアジア地区予選に進出しました！

奇しくも一昨年にチームharaharaとして出場したときと同じ順位です。

去年はほとんど自分のせいで落ちてしまい負い目を感じていました。今年はその雪辱を果たす形でしっかり解くべき問題を解けたので達成感があります。
今年も快く組んでくれたチームメイトの2人とコーチに感謝です。

さらに例年通りなら1問以上正答したチームのうち上位10%に対し表彰状が与えられるはずで、今回そのようなチームは283チームあるのでギリギリ表彰の対象に入っています。それも嬉しいです。

12月の横浜大会がとても楽しみです。オンサイトがいいな…

*1:助けて