Shirotsume の日記

嘘Greedyを生やすな

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

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

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