Shirotsume の日記

嘘Greedyを生やすな

ラベルなし木の数え上げ

最終目標

整数 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人で大阪王将に行きました．店員がやたらフレンドリーで面白かったです．

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

AtCoderの公式生放送「あーだこーだー特別配信」を見た感想，そして興行としての競プロの可能性

なんか論文みたいなタイトルになっちゃったな　まあいいか

かなり雑書きなのでいろいろ勘弁してくれ

元動画リンク↓

www.youtube.com

AtCoder11周年記念ということで，THIRD株式会社, 株式会社ALGOARTIS, フューチャー株式会社のそれぞれから社員2人ずつが参加するヒューリスティックコンテストの生配信が行われた．しっかりした新作の問題でこの規模のコンテスト配信は初めてではないかと思われる．chokudaiさんは以前から競プロを観戦することについて言及しており，その理念の実現としては非常に素晴らしい放送であったと思う．ただ，同時にいくつか気になった部分があったので，良いところと改善すべきことを列挙していきたい．私はヒューリスティックコンテストについてはあまり詳しくないので，コンテストの結果や問題内容については言及をやめておく．

良かった点

  • 実況陣の喋りが面白かった．

kaedeさんが一般人枠してるけど普通に全然強いと思う．実況陣は強ければ強いほどいいので，今の構成は非常にいいと思った．初めてコンテストを知った人のためのアルゴリズム説明もちゃんとしていて，こういう気づかいはかなり大事だと思った．

全員が参加しない前提のコンテストなら，初めから実況陣が想定解や考えた解法を説明していくくらいの勢いでもいいかもしれない．

  • ルールが良かった．

30分から15分ごとに得点がつくシステムで，序盤から見どころが生まれてよい．速い実装は見栄えもよいので，魅せプがそのまま勝ちにつながるようなルールは良い．例えば今回はtakumiさんが爆速で焼きなましを実装して断トツの点数を取っていたのが印象的だった．レートや賞金がかかっているコンテストでは向かないルールだが，こういうエキシビション的なコンテストにはあったルールなのではないか．

  • PVがかっこいい

アルゴリズムがいっぱい出てくるところで unsigned main があって笑ってしまった　悪いことを教えるんじゃない

  • 参加者の顔がライブで見れる

てりーさんなどはリアクションが面白くて面白かった．参加者の真剣な顔はかっこいい．Webカメラがあると，それぞれの参加者が何を考えているかが伝わるので良いと思う．今回は全員会社代表ということで実現したのだと思うが，やっぱりあれば観戦していて面白くなるのでできるだけあったほうが良いと思った．

気になった点

  • 音質が微妙

本当にこれはmustで直さないといけないと思う．普段のあーだこーだーもそうだけど，かなり気になった．少なくともAtCoder社側は改善できると思うので，音質をよくしたほうが良い．どうやってよくなるかは知らない．

  • 画面レイアウト

今回は参加者が6人ということで，6人分の画面が一挙表示されていたわけだが，正直コードなどはなんも見えなかった．普段は画面キャプチャ映さずに顔カメラだけ映して，状況に応じてキャプチャをクローズアップ表示くらいのバランスで，順位表や提出状況，ビジュアライザなどを大きく表示するのが良いと思う．

  • 順位表がわかりにくい

多分これは改善するって言ってた？ペナ表記と点数が同じところに表示されるのはさすがにわかりにくい

  • ビジュアライザ表示

アルゴにはないヒュの面白要素としてビジュアライザがある．これをもうちょっとフル活用していくのはどうか．例えば，最高点が更新されたらその提出の実行結果のビジュアライザを実況側で再生してワイワイ言うみたいにすると，コードが読めなくても状況がわかるので良いと思った．

終わりに

非常に面白い放送でした．

Tenka1 Programmer Contest D 「Crossing」

解説などをみるとかなり非直感的な解法があったが，グラフで解釈するといい感じになることに気づいた．

atcoder.jp

問題文要約

整数 N が与えられる．1 以上 N 以下の整数の集合の組 (S_1, S_2, … S_k) （kは自由に決められる）であって，

  • 各iについて，iはk個の集合のうちちょうど2個に含まれる．
  • 任意の2つの集合について，共通要素はちょうど1つである．

条件を満たすものを構築せよ．

解法

集合を頂点，整数を辺に対応させると，以下の条件を満たすk頂点グラフを求める問題になる．

  • それぞれの辺は，ちょうど2個の頂点を結ぶ．
  • 任意の二つの頂点は辺で結ばれている．

これは完全グラフそのものである．よって，以下のように解ける．

  1. k頂点完全グラフの辺数がNとなるようなkを見つける．
  2. k頂点完全グラフの辺に1からNの番号を付ける．辺iの両端点をx, yとするとき，S_x, S_y に iを含める．

atcoder.jp

AtCoder 黄色になりました

こんにちは，Shirotsume です．黄色になれました．

いつものやつ↓

こうみると1問でレート1増えるというのは正しそうですね

誰？

現在は神戸大学M1です．中学高校は公立で，高校では吹奏楽で部活漬けの生活を送っていました．（塾も，中学生のころに夏季，冬期講習にいったことがあるだけです）

高校生の頃に友人から Shadowverse というゲームを教えられ，人生が狂いました（いいえ）．大学入学後は（学業や部活と並行して） Shadowverse をかなりやっていたのですが，圧倒的に自分にはシャドバのセンスがないことが判明し，競技的にやるのは限界かなーと思っていました．というわけで移住先のゲームとして競技プログラミングに出会い，初めてみたところそこそこ勝ててなにより楽しいので続けているというところです．*1

学習したこと

いろいろやりました．Library Checker をしたり，EDPC埋めをしました．典型90も埋めたかったのですが，どうしても分からない問題を放置しているのであと数問残っています．

これまではかなり知識を中心をしたインプットを行ってきました．解説もガンガン開くようにしています．分からなくて負け，というのはできるだけ避けるようにしたいと思っているので，知識の漏れはなくすように心がけています．あと，「アルゴリズムに問題を合わせに行く」という思考が大事そうなことに最近気が付きました．燃やす埋めるとかが分かりやすいのですが，こういう形式に持っていくと解けるという一般形を知っておいて，問題を一般形に変換できないか？という方向から考察するとうまくいきやすいという感じです．

考察の弱さ（というか，忍耐の弱さかもしれないです）が課題点だと思っているので，これからはそれを伸ばす方向に頑張っていきたいと思います．

作問，テスター

水色くらいから，yukicoder で作問をしたり，テスターをしたりしています．最近は Library Checker の作問作業もしています．半分は界隈へ貢献したいという思いから，もう半分は単に自己顕示欲のためにやっています．

競技プログラミングの練習という面から，作問はかなりよい練習になると思います．ABC-Exに自分の作問したのとほぼ同じ問題が出て，サクッと撃破することができました．

atcoder.jp

yukicoder.me

問題から先に考えた問題は，自分の知らない解法が出てくる可能性が高いので，特に良いと思います．

心構え，考え方

私の強みの一つは，ゲームの普遍的な捉え方だと思っています．シャドバをがんばっていたころにさまざまな記事を読んでいたのですが，そこで勉強した思考の部分を競プロに応用しているということが多いです．

私が読んで有用だった記事を列挙しておきます．

krone-sv.hatenablog.com

krone-sv.hatenablog.com

app.famitsu.com

nxjpn.com

wikiwiki.jp

強い人はたいがいメンタルも強いので，鍛えておくことはおすすめします．特に，コンテスト中にティルトしない*2というだけでもかなり強くなれると思います．

順位表やレート予測なども一長一短です．これが原因でモチベ上がるという人もいれば，むやみに焦ってしまうような人もいるでしょう．これらをできるだけ見ないようにしてコンテストに出てみると，新たな発見があるかもしれません．私はいろいろ考えた結果つけておくことにしています．

あと，「こだわりを捨てる」ということはかなり重要だと思っています．これは自戒でもあるのですが．言語，書き方，アルゴリズムについて，「なぜこれを使っているのか？」を常に考えるようにすると良いと思います．あんまり意味ないなーと思った自分ルールは積極的に捨てることをお勧めします．例えば，○○パフォ取らないとヤバいみたいな思考や，Cまで○○分で解けないとヤバいなど．それ本当にヤバいですか？最終パフォーマンスはchokudaiのボタン押しによって決定され，それ以外は全てまやかしです．

オンサイト

ゆるふわオンサイトとトヨタコン（イベントのみ）に参加しました．これはかなりモチベーションアップにつながりました．twitterでみる人たちが実在するんだなと思うと，一緒に頑張っていこうと思えました．会った人たちに作問面白かったよなどと言われたのも，かなりうれしくてにこにこしてしまいました．

このような機会があるのも，競技プログラミングを大事にしてくれる人や企業がたくさんあるからだと思っているので，感謝を忘れずにこれからも頑張りたいと思っています．

これからやること

AtCoder 黄色に到達すると，ABCがUnratedになります．これにより，Rated帯で解く問題数が4分の1くらいになるので，競プロがかなり別ゲーになるのではないかと考えられます．私はARCがやや苦手なのですが，なぜ苦手なのかに対して自分なりにひとつ仮説があって，これからはそれを検証するために時間を使ってみようかなと考えています．*3

具体的にやることとしては，ARC-D埋め，AGC-Cまで埋め，典型90埋めをやっていきたいと考えています．ばちゃやyukicoderにも，出れるタイミングなら積極的に出ていきます．

まだまだ上っていけると信じているので，やれることはやっていきたいと思っています．

質問コーナー

一部マージしたり本編に統合したりした質問があります．

好きな問題を教えて

問題のシンプルさと解法のエレガントさを考えると，Small Multiple が一番好きですね．

atcoder.jp

印象に残っている問題

断然 Happy Birthday! 2 ですね．茶色のころに見たのですが解法見てめちゃくちゃびっくりした記憶があります．

atcoder.jp

競プロに役立つ趣味

前述のとおり，シャドウバースは役に立ちます．音楽は，基礎ポイントの上昇くらいは役に立ってるのではないでしょうか．何より趣味は楽しむのが一番なので，あんまり役立つとか考えなくてもいいんじゃないかとは思います．

勉強したアルゴリズム

Library Checker を埋めつつ，ACLの勉強などをしていました．ACLの機能については，ひととおり勉強しておくと良いと思います．

あとは，アルゴ式などでDFSなどのテクニック（サイクル検出など）の勉強をやりなおしたのですが，これはかなり効きました．そういうのがスラスラ書けるようになって，ABC序盤の安定感がかなり増したと思います．

入黄までのモチベ

やはりオンサイトでいろんな人と交流できたことですね．橙コーダーや赤コーダーもちゃんと人間の形してるんだなって思いました．

好きな自作問

これです．

yukicoder.me

数えたいものがすり替わる感覚がかなり好きですね．実装はかなり単純なので，見た人全員解いてください．☆4は過剰かなと思っていたのですが，バケモンが☆3を提案していてバケモンはバケモンだなと思いました．

終わりに

入黄達成，やった～

*1:シャドバは今も全然続けています．レートなどはやっておらず，ランクマ毎期グラマスを目標に頑張っています．またやる気が出ればレートやるかもしれません．今期デッキない助けて～

*2:このティルトって誤用？

*3:正しいことが検証されれば公開しますし，そうでなければなかったことにします．