Shirotsume の日記

嘘Greedyを生やすな

FPS24題B - 整数の組

なんで気づかなかったんだシリーズ

問題文

整数 N が与えられます。次の条件を全て満たす非負整数の組 (a,b,c,d) の個数を 998244353 で割った余りを求めてください。

  • a+b+c+d=N
  • a は 0 または 1
  • b は 0 または 1 または 2
  • c は偶数
  • d は 3 の倍数

制約

  • 0≤N≤10 ^ 9
  • N は整数

解法

X = a + c , Y = b + d とおきます。この時、 a の制約より任意の 0 \leq X \leq N について、 a + c = X を満たす (a, c) の組がちょうどひとつ対応します（ X を 2 で割った商と余りを考えると明らか）。

Y についても同様に、 (b, d) の組が一対一対応します（ Y を 3 で割った商と余り）。

よって結局 0 \leq X, Y \leq N かつ X + Y = N を満たす (X, Y) を数えればよく、これは N + 1 通りです。

ICPC 2024 Asia Yokohama Regional 参加記

2024年12月22日~23日に開催されたICPC 2024 Asia Yokohama Regionalに神戸大学からShirotsume+fky_+tmb=Uriboysで参加しました。

事前情報

チーム名について

神戸大学のマスコットとして神大うりぼー*1がいるので、それにちなんでUriboが名前に入っています。そして、年初にあった某炎上サークルにあやかって（？）boysをsuffixに付けることに。かなり攻めた命名で、最初はそのままBadboys *2 にしようぜと言ったのですがさすがにチームメイトから反対されこの名前に（正解でしたね）

チームメンバー

Shirotsume

Highest: A 2051 H 1621

すみません　去年よりレートが下がっています　典型が得意　ARC Div2で太陽を生やすなど活動は多岐にわたる

fky_

Highest: A 1625 H 2368

実装&構築が強い。US配列をよく利用しているので、ICPC本番でもほとんどつっかからずにコードを書いていてすごいと思った。

tmb

Highest: A 1789 H 1762

期待の超新星 AHともに実力をめきめきと上げている　考察も強いので、アドホック系は考察をガンガン投げてもらうようにしていた

練習について

大学コンに参加したり、ABC後に感想会をやったりしました。ICPCに向けたというよりかは、競プロ全体の力を上げるという方向で今年はやってみました。これは全員集まって練習する時間を取るのが難しかったためなので、集まれるなら集まったほうが良いと思います。また、JAG夏合宿にチームで参加しました。コンテスト経験だけでなく、他大学の方々との交流によって全員のモチベ&実力向上に大変寄与したと思っています。JAGのみなさまありがとうございました。

TTPCなどチーム戦の各種コンテストにもいくつか参加しましたが、これはICPCルールに厳密に則るわけではなかったので、ICPCに向けた練習と言えば微妙かもしれません。

ライブラリについて

ライブラリを整備しました。といっても自力で作ったわけではなく、noimiさんが公開されていたSpeed Starのライブラリに使用例や簡単な説明をつけ、ダイクストラやDSUなどいくつか必要と思えるコードを追加したものを持ち込みました。もともとは全部自前で用意する予定でしたが、工数的に無理だったのでありがたく拝借しました。

リポジトリを貼っておきます。最後スペースが余ったので バグった原因集 - Motsu_xe 競プロのhogeやfuga を引用したり好きなシャドバカード発表ドラゴンを召喚したりしました *3（ICPC舐めてる？）これらも含めると30ページになりました（正味29ページ） github.com

ライブラリKPT

やってよかったこと:

  • 使い方説明を付けたこと。これをやる過程で自然に全コードを読んで使うことになるので、特に他人の物を拝借した場合は必須だと思いました。横浜はページ制限ないので付けて損しないし。

  • 写経検証用ハッシュを使えたこと。実際にコンテスト中にも検証して有効だったのでよかった。せっかく用意してくださった機能は使うべき。

問題だったこと:

  • 必要なライブラリの洗い出しが不十分だった？ とくに強いチームのライブラリを窃盗してくる場合、彼らには不要だが自分たちには必要なアルゴリズムがいくつかあります。例えば、ダイクストラはシンプルだが適当に書くと計算量が悪化する罠がいくつかあるので、よほど自信があるという場合でなければライブラリを置いておくべきでしょう。横浜にはページ制限ないし。

今後やってみたいこと:

  • ハッシュで写経検証できるのはよいが、全体があっているかしかわからないのが問題。例えば行ごとにハッシュを書いておけば、間違えた時に行で手動二分探索することで誤っている行を高速に発見できます。私たちのチームは前日にこれに気づいて、絶対に写経するであろうテンプレートに対しては適当な区切りごとにハッシュを手書きで付け加えました。実際にコンテスト中にこれが役立ったので、可能なら行ごとのハッシュを用意しておくべきだと思いました。

コンテスト時系列

ここからは時系列順にコンテストまでの流れを振り返ります。解いた問題についてかなりちゃんと書こうと思っているので、ネタバレ注意です。

Day -1 (12/19)

実はこの日から関東にいました。新宿マルイメンでやってたレイジングループ *4 のポップアップストアに行きました。 謎解きイベントがあったのですが荷物が多いし、横でめちゃくちゃライブやってて音が大きかったので謎解きはやらず、グッズをいくつか購入しました。

買ったもの: 回末李花子*5ぬいぐるみ、泰長 *6フィナンシェ、ケムコアドベンチャーパック本編 *7

本編買った時店員さんにマジ？みたいな反応されたけど気のせいかな？気のせいだな　りかこぬいはICPC本番にも持っていきました。

Day 0 (12/20)

某があったのでそれに行きました。その後の飲み会に参加しましたが、アルコールは一切摂取しませんでした。夜11時30分くらいまで東京都にいて、そこから横浜のアパホテルまで移動して、着いたのが12時半くらいでした。飲み会などは楽しかったのですが、かなり疲れたからかBAD入っていて友達LINEグループに「電話しよ…」って言ったりしていました。*8

Day 1 (12/21)

アパ11時チェックアウトだと思ったら10時で焦る。ほかのメンバーは今日新幹線で来るのでそれまで待機。GIGO中華街に行ってチュウニズムをやり条件が緩和されていたメッちゅう殴打*9のアンロックチャレンジを解禁したり、レートを16に戻したりしていました。

tmbとfky_がついたので合流。一旦ホテルに荷物を預け、お昼は中華街の適当な中華屋に入り、餃子とか点心をいくつか頼んで分け合った。餃子が革命的においしかったです。

午後会場に行きチェックインをしました。ライブラリ印刷をお願いしていたtmbがイーブイのぬいぐるみを持っていたが、ライブラリを持っていなくて笑った。

リハーサルについては、問題を一通りガチで解いた後、一通りジャッジステータスを試したり印刷クエリを投げたりしていた。ShirotsumeだけPythonを使う可能性があったので、Pythonについても一通り通すまでの予行演習をしておいた。

自己紹介についてはほかのメンバーに喋る担当を押し付けられたので自分が話すことに。英語が崩壊していたが誰も気にせんやろ。

終了後はご飯。昼夜中華はどうなんだということで、適当な洋食屋？に入って、ステーキ載せピラフ(1780円）を食べました。実質中華でしたがめちゃうまかったです。

ホテルにチェックインしたあと、ABCに参加するまでの準備。Shirotsumeはずっと「ABC全完してから優雅に風呂入るわｗｗｗ」とか言っていたが実際はABC前真っ先に風呂に入る。熱い掌返し。また、コンセントが少なく争いが発生するかと思いきや全員のPC電源コードがめちゃくちゃ長いことが判明し事なきを得たり、fky_ & Shirotsume が思ったことをそのまま喋り続けるモードに入ったりとかなり騒がしいチームになった。

ABCは5完。終わっている。Fに固執してWAが出ていたが、GはFPS知ってればやるだけだったのでこっちに行くべき。判断が遅い。

tmb も5完だったので、じきに実力は抜かされるだろうなあという思いをさらに強めることになりました。

ABC終了後は素早く就寝。消灯後はイヤホンでオモコロウォッチを聞いたりしてました。

Day 2 (12/22)

Day 2 は7時に起床。Shirotsumeだけ早く起きて近くのコンビニにコーヒーを買いに行きました。

突然ラブライブの話になり、怒涛の μ's メドレーが始まる。

全員が準備完了後、朝はすき家に行くことに。去年も行ったので神戸大ICPCの伝統にしてほしいね。

牛丼（並）を完食後会場に向かいました。少しお腹が痛いのでトイレに行ってからチェックイン。

当初の予定から前倒しでコンテストがすぐにスタート。まず取り決め通り、fky がA問題を解くことに。当初の立ち回りルールでは、A, Bをfky_が解くことにしていた。ただし、どちらかにおいてShirotsumeがPythonで解いたほうが早いと判断した場合強権を発動して交代すると話していた。

Aはぱっと見で極大な区間を埋めていくしかなさそうで、計算量はなんでも許されるのでfky にお任せすることに。無事AC(0:20)。

Bについては、答えとpopcountを持ちながら1桁目を決めていくメモ化再帰が高速と判断。解法を説明するのが面倒かつたぶんPythonのlru_cacheが高速なので強権発動。ShirotsumeがPythonで実装し無事AC(0:36)。

しばらく色んな問題を読んであーでもないこーでもないと言っていたが、fky がEを簡単と主張。自分はまだあまり問題設定がわかっていないが任せることに。その間もずっとほかの問題を考えていた。fkyがすぐにEをAC(1:01)。

fkyがEを実装する間、Cから順番に問題を読んでいた。Cは全域木についての問題は超簡単か超難関のどちらかと思っているので、うちの実力なら一旦順位情報を待ってもよさそうと判断。tmbがHがワンチャンありそうというも、こちらも問題文の読解が難しく、一旦他を見ようと判断。

Iが典型の見た目をしていたのでこちらに移動。まず、選ぶ値の片方を固定した場合、gcdとしてありうるのはその値の約数に限られる。よって、gcdの値 gと、選ぶ値の片方xを固定したとき、もう一方の値は、gcd(x, y) = gを満たすyであってxから最も近いものになる。これは、Aの要素を試し割で約数列挙しながら、約数ごとのindexを持って走査すればペアを全部列挙できる。このあたりでセグ木の匂いがしたので、tmbに写経の構えをしてもらう。上記の考察より、問題は次の形に落ちる。

  • O(N \sqrt{max(A)}) 個の重み付き区間 (l, r, g) がある。各クエリについて、区間 (L, R) に含まれる区間の最大値を求めよ。

これは、クエリを L の降順にソートすると、セグ木の1点更新区間maxで解くことができる。これをC++で自力で実装するよりかは、解法を説明してtmbに書いてもらったほうが良いと判断し、解いてもらう。1ペナをもらうも、デバッグ出力やコード睨みつけなどのテクニックを駆使し、なんとかAC(2:20+1)。

tmbにIを書いてもらっている間、Cが解かれていることに気づき、再度考えてみる。主客転倒をすると、コストは各頂点について頂点1からの距離×重みとなり、これは各頂点に対して最短経路で辿った時の距離が下界となる。そして、最短経路木をとることで実際にこれが達成できるので、ダイクストラをやるだけで解ける。ダイクストラのライブラリを持ち込んでいたので自力で書いてもいいが、tmbがダイクストラをソラで書けると言っていて、罠については自分なら大丈夫だろう（慢心）ということで空で書いてもらうことに。解法をざっくり言ったがあまり納得いっていないようだったので、とりあえずダイクストラを書いてください。そして各頂点についてPと掛け算してください。ほらサンプル合うでしょう？とマジシャン的な言いくるめ術を行い提出。無事ACを得る(2:44)。

Kが可能枠に見えたので向かう。タイブレークがやばそうだが、各iについて最適なjを選ぶという方針になると、i, j が重複するケースは考えなくてよいことがわかる。よって、あらかじめbit集合ごとに最適な相手を前計算することでiごとの最適ペアがわかり、それらを比較できれば良いことになる。実行時間に不安があったのでC++でShirotsumeが実装。ゼータ変換は書きなれているので特に苦労することなくできたが、文字列の取得でセグフォを食らいひっくり返っていた。チームメイトに相談しつつ解決。無事ACを得る。(3:39)

一旦実装キューが空になる。ShirotsumeはDかLが行けると思っていたが、fkyがGの解法がわかったと主張。しかし、聞いてみるとかなり方法が際どく、なおかつインタラクティブを時間内に実装できる自信もお互いなかったのでDの考察に。しかし、Dのサンプルを手で試したりしても全く分からず、最後1時間何の成果も得られず終わってしまった。

今思えば、Dに執着しすぎだった。順位表情報からはD <<< G, Lだったが、実際の難易度としてはそうではなかったと思う。なので、Lをもう少し考えるか、ワンチャンに賭けてGの実装をやってもらうかすればよかった。

コンテスト終了後は部屋を移動しYesNoに。自分たちのチームは解凍なしだったので、少し寂しい気持ちになったが、全体の盛り上がりは楽しかった。

写真を撮ってから、懇親会に行きました。お話してくださった方々ありがとうございます。個人的に驚いたのが、後ろに気配を感じて振り返ったらchokudaiさんがいたことでした。ここが戦場なら死んでた。 *10

主に実力が少し～けっこう上の人々を中心に話しかけに行ったりしていました。*11ごはん全体的においしかったですが、エビは凍っていました。

他の2人は就活世代なので企業ブースに行っていたが、自分はあまり行かなかった（すみません）。

19時ごろ荷物をまとめて撤収。すぐに新横浜までバスで移動し、お土産を買って新幹線で帰った。帰りの新幹線でtmbとICPCのyoutube配信を見たりしていた。名古屋あたりで寝て、2人に新大阪に着いたときに起こされた。本当にその間の記憶がなくて、ワープしたかと思った。

日付が変わる前に無事帰宅。

感想

6完で全体26位という結果でした。残りの問題について、今の私たちの実力では時間内に通すのは厳しいというのが率直な感想でした。しかし、去年に比べると順位は上がっていますし、tmbやfky_もモチベが高まっている感じがするので、神戸大は来年もっと上まで行けるんじゃないかなという気がしています。

FORCIAさんのゆるふわコンでsquare1001さんに神戸大も出ろやと言われたのがきっかけで昨年からICPCのチームを組んだのですが、今思うと本当に組んでよかったなと思います。私は今年でラストですが、残り2人については来年以降も誰かメンバーを捕まえて出てくれたらなぁと思っています。

競技プログラミングに興味があるという本学の学生も何人かいて、話をしたり観測したりするので、あわよくば2チーム以上参加する未来もあるんじゃないかと期待しています。今後も引き続き頑張ってください。

社会人になって以降の競プロ生活については未知数ですが、元気とモチベが続く限りAtCoderには出続けようと思っています。また、行事としてのICPCにも強い魅力があると思っているので、できればJAGに入ってお手伝いをしたいと考えています。

コンテストのスタッフ、審判団の皆様。JAGの皆様。コーチを引き受けてくださったY先生 *12 や、予選や練習の場所を提供してくださった研究室の皆様、本当にありがとうございました！！

*1:かわいい。が現物は全く可愛くない上に怖いので注意。本学は夜になるとイノシシの親子のお散歩姿を見ることができます。https://www.kobe-u.ac.jp/ja/about/public-relations/uribo/

*2:学生の不適切な行為についてのお詫び | 国立大学法人 神戸大学 (Kobe University)

*3:リーシェナ: アミュレットが強くて好き バルバロス: 打点でかくて好き。エンハ使うか使わないかの択も深くなって好き。エレノア: 能力が好き。ウィッチで早投げしたくなるデザイン、良い エイラの祈祷: リメイク版を一生擦ってた。清浄の領域: こちらも回復するとバフする奴。

*4:「人狼」をモチーフにした和風ホラーアドベンチャー。姉妹作（実は姉側)のデスマッチラブコメ！とのセットパッケージがSwitchで最近出た

*5:「レイジングループ」のキャラクター。蜘蛛を守護獣とする回末家の長者。かわいい。

*6:「レイジングループ」のキャラクター。織部家の長男。頭が良くてやがる。

*7:大ヒット人狼アドベンチャー「レイジングループ」 その姉妹作である「デスマッチラブコメ！」が 1本になって登場!!

*8:結局風呂入ってるとかで電話できんかった

*9:STEAKA feat. 山田じぇみ子の楽曲。譜面定数はMASTER 14.1。このときはLIFEが150まで緩くなっていた

*10:AC, そのまさかだよ

*11:これは主観だし、話しかけなかったとしても実力下に見てるとかじゃ全然ないです。強い人には喋りに行きにくいので、目標として積極的にいこうってノリです

*12:Y.Y.さんではない。Shirotsume/fkyの指導教員。fkyは金曜締め切りの原稿提出を金曜の朝に投げつけていてやばかった

CHUNITHM 虹色(16.00)になりました

広義色変記事

今年の3月くらいに本格的にやり始めて，ようやく到達できたという感じです．とりあえず一区切りとして，ゲーセンに通うペースは少し減らそうと思います（自制）

ベ枠画像

誰？

普段は競技プログラミングとかシャドバとかやっています．音ゲー経験としては，中学～高校と太鼓の達人を遊んでいて，毎回八段～九段になっていました．主にハウス勢で，マイバチは持っていましたがほとんど使っていません．部活が忙しかったことや，近くに良い感じのゲーセンがなかったことを理由に継続して通うという感じではなかったです．あと，同時期にmaimaiをちょっとやっていました．

CHUNITHMとの出会い

高校時代に先にイロドリミドリを知っていました．最寄りゲーセンにウニがなかったので，イロドリミドリは謎のボイスドラマと曲PVが供給されるコンテンツとして楽しんでいました．お姉ちゃんが卒業するやしないやというらへんです．大学に入ってもウニはやらず，大学の部活の同期や後輩へのLINEに送信相手の担当楽器と合わせたキャラのスタンプを送る遊びをしていました（例えば，ベースの人に箱部なるのスタンプを送るなど）

ところで，イロドリ譜面難易度の割にやばいの多くないですか？特に最近のどこにもいかないとかラビットランドとか癖が強すぎる

なんか去年の夏位に撮った謎のスクショがありました（東京に行ったときに秋葉原のゲーセンかどこかでやった記憶がある）．

本格的に遊び始めたのは，研のメンバーと大阪のゲーセンに行ったのがきっかけです．そこからは週に何回かのペースで通っていました．

精進について

基本的には譜面画像や動画で予習をして，何譜面か用意した状態でゲーセンに行くという感じでした．初見が苦手かつ，癖譜面が得意（これは太鼓のころから感じでいた自分の傾向です）なので，このスタイルがあっていると思っています．1日は大体5~7クレくらいで，10クレ以上やることはほとんどありませんでした．これは，それ以上やっても自己べ更新ができないという傾向があったからです．

競プロTLはチュウニズムに詳しい人がたくさんいるので，おすすめ譜面を投げてもらったりそれをガン無視したりしながら楽しく遊んでいました．物理好きさんありがとう…

プレイするときは同じ曲を3回以上連続でやらないようにしています．これは単なる気分でそうしています．同じ曲を詰めたいときは，間に別の曲を挟んでいます．

設定は壁4 HS8.5です．壁がないと視線が上になって横にずれたところを押してしまいがちなので，壁を付けて意図的に視線を下に寄せています．

ベスト枠について

ベ枠平均についてはそんなに尖っていないと思いますが，下限が小さめなのは課題という感じです．下から順番に，他の人のベ枠に入っていない曲や語りたい曲を抜き出してコメントを書きます．

Aleph-0 (EXP) 13.7 1,008,037 (SSS)

序盤のホールドはやや難しいですが，後半はわしゃるだけで通ります．これが14だった時代うらやましいです

The wheel to the right 14.4 1,003,550 (SS)

1日1回は絶対やっていました（MEGA曲好きなので）全部難所で大変なんですが，何回もやってると割とできるようになってくるので楽しいです

とあちゃんのおもちゃ箱 14.8 999,919 (S+)

現状ベ枠唯一のS+以下です．2回目くらいでこれが出て得意か？と思ったのですが以降スライドが抜けまくる症状に悩まされ終わりました．バグ？

中盤のドンカマみたいなポリリズム好き

評価されなくていいですがプラレでも単曲16とかポンと出る人は出そうなので触る価値はあるんじゃないですか（適当）

がんばれ！蜘蛛子さんのテーマ 14.3 1,005,132(SS+)

14フォルダの先頭で存在感を放つ曲．燃えてもエンジョイ亜種という感じで，盛れる人はこれでも盛れるのかもしれない

燃えてもエンジョイは序盤のフリック交じりのタップが普通に難しくてしんどい

チューリングの跡 (EXP) 14.0 1,007,003 (SS+)

新曲．全体的に配置が変な感じなのでMISSが出やすくて困っていた．あとスライドが抜けまくる

MASはまだ触ってないです．

玩具狂奏曲 -終焉- (EXP)13.9 1,007,772 (SSS)

ベ枠唯一の13.9．技術的に難しいところはあまりないので，押し方を覚えるのと16分を片手で叩く覚悟を決めておけば行けます．エアーが楽しい．

MASはまだ触ってないです．

グラウンドスライダー協奏曲第一番「風唄」(EXP) 14.0 1,007,756 (SSS)

指押し譜面ですが，指押しというよりかは如何に横にずれずに正確に押すかのゲームでした．ある配置が来た後，そのミラーが来ると見せかけて後者は全体的に横に寄っていたりするので，それに気を付けるとうまくいきました（1サビ?の16分トリルとか）．ラストは後ろで鳴ってる金管？に合わせます　活きる吹奏楽経験

MASはまだ触ってないです．

Joe Fight 14.3 1,006,513(SS+)

新曲．耳が気持ちいいので実質ASMR

一番の難所は小粒

TECHNOPOLIS 2085 14.5 1,006,542 (SS+)

敷譜面好き！！これは抑えてる手をできるだけ下に寄せることを意識するともう片方が動かしやすくなって楽になりました．

ピロピロの指押しや縦連など敷以外に難しポイントが結構あるので，難しい

Brightness 14.2 1,009,015 (SSS+)

敷譜面好き2！！こういうレインボーンをスライドと誤認させるやつ，音ゲー的にギルティだと思うんですが許されてるんですね（グルコスとかだと演出で偽ノーツってあるし，今回はプレイヤーの動き誘導ということでいいのか？）縦連が混じる乱打はシンセ研に鍛えられているので個人的にはあまり難しく感じなかったです．これが高難度で一番安定したので，リセ枠の詰め兼鳥プラ狙いで虹レ突入時はこれを2連奏しました．

きゅうりバーにダイブ 14.4 1,007,375 (SS+)

初プレイヤバかったんですが，危険予知する術を身に着けアタックをかなり減らすことに成功しました（アタ出るときは予兆として赤とか出がち）．純粋に押し方を覚えないと難しいところが結構あると思います．安定して好スコアがとれるものでもないので，鳥出せと言われるときついです．

最後に

色んな人から虹レからが本番やぞとか17からが本番やぞなどのハラスメント（）を受けています．しかしいったん一区切りということで，プレイペースは減らします．いつかはAJしまくったり15なども触れるようになりたいので継続はしていきたいなと思っています．

CF #956 E. I Love Balls

↓問題リンク

codeforces.com

問題概要

N 個のボールがある．それぞれには点数 v_i が与えられている．また，番号 1 から k のボールはSpecialである．

Alice と Bob が次の行動を繰り返す．

  • ボールを等確率でランダムに 1 つ選び，それを取り除く．取り除いたボールに書かれた点数を得る．ボールがSpecialなら次も自分の手番で，そうでないならもう一人に手番を回す．

それぞれの点数の期待値を求めよ．

解き方

ゼロサムゲームなので，Aliceのが求まれば合計から引くことでBobのがわかる．よってAliceを求める．

ランダムに1つ選ぶのではなく，事前にシャッフルしてから前から順番に取るとしてもよい．よって，ボールの並べ方 N! 通りに対する総和を求めてから N! で割ればよいことになる．

主客転倒をする．ボールの並べ方を固定した時，ボール i の点数はどちらが得ることになるか？

Specialでないボールが当たるたび交代するので，ボール i を Alice が得る必要十分条件は，ボール i より前にあるボールのうち，Special でないものの個数が偶数個という条件になる．

よって，それぞれのボールについて，すべての並べ方のうち，Specialでないものが前に偶数個並ぶものの個数を求められれば良いことになる．ここで，この個数は対象となるボール i 自体が Special であるかのみに依存するので，それぞれの場合を考えればよい．そして，これらは前に並ぶ Special でないボールの個数を固定すると簡単な二項係数の数え上げになるので，それぞれ O(N) で計算できる．

あとは，各ボールが Special かどうか考えて，それぞれの係数をかければよい．計算量は全体で O(N) ．

ラベルなし木の数え上げ

最終目標

整数 N が与えられるので、 N 頂点の木の個数 mod 998244353 を数えよ。ただし頂点は互いに区別されないとする（同型な木の個数を数える）

↓これです

oeis.org

この問題は ABC230Hの解説で発展問題として提示されています。この記事ではABC230Hの理解は前提としませんが、解説を事前に読んでおくとわかりやすいかもしれません。

Editorial - AtCoder Beginner Contest 230

ラベル付きの場合

もしかして：Prüfer Sequence, ケイリーの公式

この記事では説明しないので、↑でググってみるといいかも

根付き木の場合

整数 N が与えられるので、 N 頂点の根付き木の個数 mod 998244353 を数えよ。ただし頂点は互いに区別されないとする（同型な根付き木の個数を数える）

oeis.org

ラベルなし根付き木と多重集合の対応関係

めちゃくちゃ唐突ですが、ラベルなし根付き木と各要素が多重集合である多重集合との一対一対応が取れるので、それを考えます。

頂点数1の根付き木（根だけです）を空の多重集合 \{ \} と対応付けます。 一般の根付き木に対しては次の要領で再帰的に多重集合を対応付けます：

根である頂点の（直接の）子それぞれについて、子の部分木に対応する多重集合を S_1, S_2, \dots, S_k とする。このとき、この根付き木と対応する多重集合は \{S_1, S_2, S_3, \dots, S_k \} とする。

というわけで、多重集合の多重集合とラベルなし根付き木の対応関係を作れました。ラベルなし根付き木なので、子の順序などは考えません。

これは言い換えると、根付き木とは、「根付き木の多重集合に根を加えた構造」という再帰的な性質を持つといえます。

根付き木の集合を特徴づける

FPS（形式的べき級数）をやります。頑張って頭をFPSにしてもう一回ここに来てください。FPSになりましたか？

FPS は、何らかの組合せ的構造をもつオブジェクトを数えるときによく使われます。ここで、「オブジェクトを並べた列」や「オブジェクトの多重集合」も、うまくやれば数えることができます。

例題：6面さいころを5回振る。振って出た目を順に並べてできる長さ5、総和 i の数列の個数を A_i とする。 A の母関数を求めよ。

答え： (x + x ^ 2 + x ^ 3 + x ^ 4 + x ^ 5 + x ^ 6) ^ 5

もうちょっと一般的にいうと、母関数が F(x) であるものを K 個並べてできる列の母関数は \{ F (x) \} ^ K になります。

このテクニックを使えば、母関数がわかっているとき、それを並べてできる列の母関数もわかるということになります。やったね！

さて、根付き木の話に戻ります。頂点数 i のラベルなし根付き木の個数を A_i とします。 A の母関数 \displaystyle F(x) = \sum _ {i=0} ^ {\infty} A_i x ^ i を求めたいです。

ここで、前提知識として次を使います：

母関数が F(x) であるオブジェクトからなる多重集合の母関数は \displaystyle \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )

いきなりゴツイ式が出てびっくりさせたかもしれませんが、このまま突き進みます。

根付き木は、「根付き木の多重集合に、根を加えた構造」としてみなすことができます。よって、 F(x) は次の関係式を満たします。

\displaystyle F(x) = x \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )

手前の x が根を表し、後ろの部分が根付き木の多重集合を表します。あとはこの F(x) の先頭 N 項を求められれば良いです。

両辺を微分してみます。積の微分公式を思い出すと、

\displaystyle F'(x) = \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right ) + x \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )' \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )

となります。両辺に x をかけると、

\displaystyle xF'(x) = x \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right ) + x \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )' {\times} x \exp \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )

\displaystyle xF'(x) = F(x) + x \left ( \sum _ {k > 0} ^ {\infty} \frac{F(x ^ k)}{k} \right )' {\times} F(x)

\displaystyle xF'(x) = F(x) \left \{ 1 + x \left ( \sum _ {k > 0} ^ {\infty} F ' (x ^ k ) \right ) \right \}

ここで、 F(x) = \sum _ {i = 0} ^ {\infty}f_i x ^ i 、 G(x) = 1 + x \left ( \sum _ {k > 0} ^ {\infty} F ' (x ^ k ) \right ) = \sum _ {i = 0} ^ {\infty}g_i x ^ i とおきます。

このとき、 x F ' (x) = \sum _ {i = 0} ^ {\infty} i f_i x ^ i であることから、

\displaystyle n f_n = \sum_{i = 0} ^ {n - 1} f_i g _ { n - 1 - i }

が成り立つことがわかります。 g_i の値については、 k を全通り試して i 番目までの寄与を求めれば、いわゆる調和級数のやつでできます。

よって、 f_1 = 1 から順番に f, g を漸化式に従って求めればよいので、 f, g の N 項めまでを分割統治FFTやオンライン畳み込みを用いることによって O(N \log ^ 2 N) で求めることができます。

実際に実装しましょう。オンライン畳み込みはkiriさんからお借りしたコードを使用します。

↓kiriさんによるオンライン畳み込みの記事

qiita.com

実際に実装したものが下のリンク先のコードとなります。Nを標準入力で与えるとN以下についての結果を出力します。実際にN = 20 などで試してみると、A000081と一致する結果が得られます。（それより大きくなるとmod998244353をとっているので一致しなくなります）

wandbox.org

ということで、 N 頂点のラベルなし根付き木の個数を数えることができました。

根なし木の場合

ラベルなし根なし木の母関数 U(x) とラベルなし根付き木の母関数 F(x) について、

\displaystyle U(x) = 1 + F(x) - \frac { \{ F(x) \} ^ 2 - F(x ^ 2)} {2}

という関係が成り立ちます。

これを証明するために、根なし木の重心を定義しましょう。頂点数 N の木の重心とは、以下の条件を満たす頂点です。

重心 v を根としたとき、 v のどの子の部分木のサイズも \displaystyle \frac{N} {2} 以下である。

ここでは証明しませんが、木の重心について以下の事実が成り立ちます。

木の重心の個数は 1 個または 2 個。木の重心が 2 個存在するとき、それらは隣接している。

N の偶奇で場合分けをします。また、以下では頂点数 i の根付き木の個数を f _ i とおきます。

N が奇数の場合

根付き木をとったとき、その根が（根なし木における）重心と ならない 場合を考えましょう。これは、根の（直接の）子の部分木であって、サイズが \frac{N} {2} より大きいものが存在することと同値です。

よって、根が重心とならない木は、 i + j = n, i > j なる i, j をとってきて、頂点数 j の根付き木の根に頂点数 i の根付き木を付けたものとして構成できます。よって、根が唯一の重心となる n 頂点の木の個数は、

\displaystyle f _ n - \sum _ { i + j = n, i > j \geq 0 } f _ i f _ j

= \displaystyle f _ n - \frac {1} {2} \sum _ { i + j = n } f _ i f _ j

として求めることができます。また、 n が奇数のとき、重心は必ず 1 個です。よって、根なし木の個数もこれと等しくなることがわかります。

N が偶数の場合

奇数の場合と同様に、根が唯一の重心となる n 頂点の木の個数は \displaystyle f _ n - \sum _ { i + j = n, i > j \geq 0 } f _ i f _ j です。頂点数が偶数の場合、これに加えて、重心が 2 つある木の個数を追加で数えます。

頂点数が n で重心が 2 つある木は、頂点数 \frac { n } {2} の根付き木を 2 つ取ってきて、それらの根同士をつないで作ることができます。よって、この個数は

\displaystyle \frac { f _ {n/2} ( f _ {n/2} + 1) } {2}

として計算することができます。

よって、根なし木の個数は

\displaystyle f _ n - \sum _ { i + j = n, i > j \geq 0 } f _ i f _ j - \frac { f ^ 2 _ {n/2} } {2} + \frac { f _ {n/2} } {2}

\displaystyle = f _ n - \frac{1} {2} \sum _ { i + j = n} f _ i f _ j + \frac { f _ {n/2} } {2}

として計算できます。

根なし木　実装

以上の偶数の場合、奇数の場合を合わせて、FPSで書き直すと上記の式

\displaystyle U(x) = 1 + F(x) - \frac { \{ F(x) \} ^ 2 - F(x ^ 2)} {2}

が得られます。

\{ F(x) \} ^ 2 の部分は畳み込みで計算できるので、 F(x) から U(x) を O( N \log N) で求めることができます。

よって、ラベルなし根なし木の個数を数えることができました。

実際にコードを書いたものが以下です。

wandbox.org

OEISによると、根付き木の時は 0 頂点で答えが 0 だったのに、根なし木のほうは答えが 1 になるようです。直感的には両方 1 が自然そうなのですが、根付き木は根を選ぶ方法の個数になるので 0 なんでしょうか？よくわからないです

あとがき

Bullion を解いたついでに一回やったことがあるのですが、完全に忘却しておりつらかったです。

ICPC 2023 Asia Yokohama Regional 参加記

早めに書かなかった結果、忘れた…

Shirotsume + MasKoaTS + fky = Uribo であったのが、MasKoaが体調不良により欠席することになったため Shirotsume + fky の 2 人チームでの参戦となった。

Day -1

Yokohama に向けて、特別な練習はほとんどしなかった。過去問セットもほとんど触れていない。Shirotsume が就活や学会発表準備など諸々で忙しかったということが主な理由。

一応 US 配列を触ったり仮想環境をいじってみる練習会は開催した。研究室のサーバーで好き勝手仮想マシンを立てられるので助かった。

Day 0 (11/24)

yukicoder の writer をやった

yukicoder.me

前日を狙うというよりかは空いているところに入れたら後で前日であることに気づいたという感じ。

懇親会などでも話のタネになってよかった

Day 1 (11/25)

朝は 7 時半くらいに起きて移動。割とぎりぎりの起床で終わったかと思った。朝 9:45 新大阪発の新幹線で移動。少し遅れていたが問題なし。

昼食は駅弁を買って車内で食べることに。私はひっぱりだこ飯を食べた。 fky は普通の幕の内みたいなやつを食べていた。

all.awajiya.co.jp

到着はほぼ時間通りで 12 時くらいに着。時間つぶそうかと思ったが、意外と新横浜から会場まで時間がかかる（40分くらい）ことに気づいたのでそのまま直行することに。

会場では俺たちは2人で出場するという旨を告げ入場。

リハーサル

とりあえず事前の取り決め通り最初はテンプレ（といっても bits や 575 など基本的なものだけ）を書いておく。

あとは適当に通す感じでやった。Bは fky 、それ以外は私が解いた。

A: はい

C: 頑張ってごちゃごちゃやれば通る。Pythonならオーバーフローをあまり気にしなくてよいので楽

D: 昔 ABC-Dでやられた記憶のある問題。最小を固定することでペアの全列挙が高速にできるやつ

あまり苦労せず完答できたので、残りの時間はWA,TLE,REなどのジャッジがどうなるか試したり、書いたプログラムを印刷してもらったりしていた。

B 問題についても時間があったので見ておいた。fkyは謎の方法で通していたが、1文字ずつ確定させるのが楽という話をし、実際にそれで通しておいた。

自己紹介

何も考えていないので適当にやった。MasKoaが休みなので2人だという話をした。自己紹介文もそうだけどまじめすぎたかもしれない（AAや作問を載せているチームを見ながら）

夜

夜はfky_と適当な中華屋に入ってチャーハンと小籠包を食べた。

ホテルはアパホテルだった。割高だったが、風呂がデカかったりファミマが中に2個あったりして面白かった。

この日はABCがあり、fky は出ないそうなので部屋の机を使って出た。青に落ちていたので戻したかったが、結果は-3だった（泣き）。ABC中に fky がデカい声で歌っていてカスがよ…って思った（言った）。

カウンター攻撃

Day 2 (11/25)

朝は普通に起きて準備をした。忘れたら死ぬ3点セット（ICPCシャツ、名札、学生証）を指差喚呼してから出発。

朝は fky_ とすき家で牛丼を食べた。朝定食も検討したが精をつけるという意味で牛丼にした。

時間通りに集合し、待機していた。

コンテスト本番

とりあえず序盤は fky に marunage ということで、A は見なかった。fky が A を通しているのを見つつ、Bを適当に読みながらわからんなぁと言っていた。

B は長さ C だけみればいいのでは？と言ってみるもののサンプル1で落ちていることに気づく。しばらく考えてみると累積和でえいえいやれば解けることに気づいたので書いた。通った。

B を通した後は、その時点でのAC数が多かった K を眺めていた。とりあえず 200 くらいの幅で当てていけば円内部を特定できるな～、そこからにぶたんすればいいな～など考えていたが確実に解ける感じではなかったのでかなりつらい気持ちになっていた。とりあえずコードを書いてみて出しても通らず、いったんほかの問題にすることに。

fky_に引き続きKを考えてもらいながらほかの問題に目を通す。Dがやるだけだったのでやる。とWAだった。aaaaaaaaaaが10(a)ではなく2(5(a)) だったので（このミス全人類やってない？）それを直してAC。

ほかの人は文字列アルゴリズムを組み合わせていそうだが、こちらは f(S) = （S を圧縮した結果の文字列）で再帰的に圧縮結果を求めることにした。無限ループを踏まないように気を付けて実装するとこちらの方が楽だと思う。

この辺時系列覚えていないが、Dを AC したあと fky_ が F の問題文を和訳してくれて、かなりフワフワした考察をして解くとサンプルがあったので投げると通った。

まだ K が通せていないが、自分の感覚的にこれが通せる未来が見えなかった（後から考えると、円の位置を特定する方法がわからなかったので結局通すのは無理だったと思う）ので、Kからは撤退することを提案。fky_ が引き続きやりたそうだったので、交代して問題を眺めることに。

可能性がありそうなのは E, G, H で、その中で一番可能っぽいのは G だった。指数関数的に個数が減っていくやつで状態数が抑えられる奴だろう、じゃあ再帰で高速にできるだろうと思って Python で提出するも、通らず。 fky に交代してC++へ写経をしてもらう。ここ自分でやろうか迷ったが、指も疲れていたのでまあ後退してよかったかな？

直したものを提出したもTLEだったが、最大ケースで 7秒くらいと、うまくやれば高速化できそうな気がしている。ここで、std::mapをstd::unordered_mapに変えると通った。

一通り unordered_map の講釈をしたのち、Kに戻る。しかし、手掛かりはつかめず5完で終了した。

残りの時間は E の O(N3 2N) を書いて落とされたり、K を考察しながらお弁当を食べたりしていた。

コンテスト終了後

解説などがあった。Hはまだ手が付きそうな感じで、こちらを見ておくべきだったかもしれない。

Yes/No は対象問題が1つしかなかったがYesされるのはうれしいのでよかった。

終了後の懇親会では、企業ブースを中心に回っていた。KLab の担当者さんになんでお一人なんですか？などのバッドコミュニケーションをしていた。

あとは目についたFFerに絡みに行っていた。本当すみません。鶏のトマト煮みたいなやつうますぎ

帰りの新幹線ではビールとつまみで盛り上がっていた。fky_ は寝ていた。

日付が変わる前に帰宅。いい時代になりました

Day3~

日常が始まる。いただいたメロンパンやミスドなどを食べつつ、大学のもろもろに向けた準備などをする。

感想

運営陣、スポンサーのみなさま、このような機会をいただけたのは本当にうれしいです。3人で出られればなおよかったのですが…

早生まれなので来年もこのメンバーのまま出られる予定です。ぜひ出たいですが、もしも野生のerが追加で生えてきたらコーチとして行くつもりです。出てこい！神戸er！

ICPC2023 国内予選　参加記

国内予選の目標．上から難易度順のつもり．

こういうのは早めに書かないと忘れるので．

↓問題文

icpc.iisf.or.jp

↓順位表

icpcsec.firebaseapp.com

神戸大学からShirotsume + MaskoaTS + fky_ = Uriboというチームで出場し，37位で予選通過しました．

練習，立ち回りについて

対面でのチーム戦は全員初めてだったので，チーム戦に特有のコミュニケーションや立ち回りなどの練習を中心として行い，並行してABC後に勉強会を開いていました．

コンテスト序盤の立ち回りは固定化して，まずShirotsumeが問題を印刷してフォルダを作り，MasKoaにバトンタッチをしてA問題を解いてもらう，fky_が印刷された紙を回収するというところまで事前に決めていました．ここらへんであたふたすると後に響くので，ガチガチに決めておいたのは正解だと思います．

Shirotsumeは3人の中で最も学年が上かつレートが高いので，進んでリーダー的立ち回りをしていました．「あと何分で解けそう？」とか，「今思いついている解法はある？」のような声掛けをしていました．泥沼化すると声が減ってしまうので，その時に鼓舞するような声掛けも心掛けていました．また，誤読や嘘解法で時間とペナを浪費するというミスが練習中に起こったことから，B問題以降は問題の概要と思いついた解法を3人で共有するということをルールとして定めておきました．これらについては，結果的に部屋が盛り上がって全員のやる気が増してよかったのではないかなと思います．今後のチーム戦でもやっていこうと思っています．

問題毎の話

最初は，序盤の割り当てを決めていたのですが，あんまり今回は機能していなかったようです．結局全員で読むことになるので，そっちの方がいいかも？

A

先述のとおり，AはMasKoaにやってもらうと決めていました．特に苦労なくサクッと通してくれました．

B

えー戦犯です．

まず問題文読んで「え，AtCoderのPVとかぶってるやんｗｗｗ」みたいなことをしゃべっていました．最初に問題文を読んで，Shirotsumeが上からと下からでたどっていって，隣り合うところで線を引けばよいという解法を思いついたので実装しました．

そして提出すると，

Wrong Answer

そ，そんな…

正直どこでバグってるのか分からなくて，かなりパニックになっていました．そこでfky_が「全部のところに線引いてみてシミュレーションすればええやん」という天才アドバイスをくれたので落ち着きを取り戻すことに成功しました．線を引くというのは配列xの任意箇所に要素を挿入するのと一緒なので，実装もこちらの方が簡単そうです．計算量はちゃんと考えてなくて心配でしたが，実行してみると普通に速く終わったのでOK．ということで提出すると…

Wrong Answer

そ，そんな…

今度こそ頭が真っ白になりましたが，OKの場合の分岐をミスっていただけと気づいて，修正するとAC．

C

私がBの底なし沼にハマっているときに並行して残り二人が考えてくれていました．fky_が方針を思いついたので実装することに．バグらせたりして大変そうでしたが，ジャッジを書いてチェックしながら丁寧に実装することでAC．さすがH黄色．私は進捗を管理したりD問題を書きたくてうずうずしたりしているだけで，Cはほとんどノータッチです．

D

fky_がCの実装をしているときに読んでいました．制約が小さいので多少ごり押しが通りそうということを考えて，1, 2, 4, 8…n - x みたいな集合でansの上界が小さいよね！ということを思いつき，実際にそれが構築可能なことをざっくり証明して，MasKoaに説明して確認してもらっていました．じゃあ答えはdfsとかで全探索で良いよね，計算量は額面ヤバいけど適切に枝刈りすれば定数倍軽くなるよね，ということを確認して，実装すると…

Wrong Answer

そ，そんな…

このミスの原因は，26 = 64なので上界は6や！というShirotsumeのカス過ぎる勘違いによるものでした．修正するとAC．

C, Dを通して順位表を見ると22位になっていて，一通り喜びました．観戦してくれていた後輩によると，この直前は順位が100位とかで結構やばかったとのこと．

E

眺めていて，LISっぽいよね～という話をしていました．実際yだけ見ると広義単調増加になっている必要があって，そうじゃないところは書き替えないといけないみたいなことを考える．ただ，これは筋が悪そうで一回離れた解法を考えようということになり，

dp[i][x][y] = i項目まで見て末尾がx, yである場合

というdpを高速化できないかということをうなりながら考えていたが，結局思いつかずコンテストが終了．

コンテスト終了後

最終順位は37位で予選通過は確実なので，祝勝ムードでした．ずっと観戦してくれていたコーチ兼監督員の先生にEの解法を即説明され，Fも見た目ほど難しくないという話をしていただいた．先生はアルゴリズムが専門ですが，競プロをそれほどしているわけではなく，今回も黙って観戦しているだけでしたが，そこまで考察できているのは本当にすごいと思いました．

終わった後，選手3人で大阪王将に行きました．店員がやたらフレンドリーで面白かったです．

アジア大会に向けて練習を重ね，私たちのベストを尽くして大学競プロ界に神戸ありというところを見せていきたいと思います．