nononの落書き帳

不定期に、でもずっと更新したい

ICPC2026 国内予選参加記 (Aobayama_BlueMountain, nonon 視点)

去年:

nononmath.hatenablog.com

〜模擬国内

チームは去年と変わらず. 今年は院試があってチーム練をする時間が取れないので下振れしない立ち回りをしようね〜と話していました.

模擬国内

チーム内で一番レートの高い私が全ての実装を担当することに. 普段通りの環境なのでデバッグとかがやりやすいです.

A はやるだけです. (0:02)

B は異なる 2 種類が作れたらいいので昇順ソートと降順ソートを見れば良いです. (0:03)

C は aqua さんから問題概要を聞いて考えます. 答えで二分探索ができるのでします. あとは累積和とかでいい感じにします. (0:07)

ripity が D で詰まってそうでしたが一旦任せて E を考えます. 返答が 1 だと何も分からないので返答ででかい値が欲しいです. 2 を作ることを考えると (0,1), (1,0) とかを聞けばようさそうな感じです. 細かいところを詰めるのが面倒だったので ripity に任せ, ripity から D をもらいます.

D はブロックではなく, 最終的な範囲を固定すると各ブロックについて置けるか置けないかが決まることが分かります. 実装ミスで 1 ペナをしましたが無事 AC します. (0:51 + 1)

E はripity が擬似コードを紙に書いてくれたのでそれを写経します. 怖いので手元でランダムをたくさん回してから提出しました. (1:15)

F は短い良い文字列を列挙してグッと睨むと括弧列が見えます. aqua さんと共有し, 見守られながら実装すると通ります. (1:49)

この間に ripity が G を解いてくれたらしいので実装します. 投げますが TLE です. 流石に二分探索+binary trieは重すぎたらしいです. 定数倍高速化とかを頑張りましたが結局通らず. コンテスト終了です.

最終的には全体 18 位, 学内 1 位でした. 東北大の 1 年生チームが 6 完していてすごいです. 普通に負けそうで怖いですね.

コンテストは納得いく出来ではなかったですが, 日本代表が勝ってくれたのでチャラになりませんか？なりませんね.

G は深夜に upsolve しました. 最後のパートは上の bit から決めれます. この方針自体は終了 30 秒前くらいに分かっていたのですが流石に実装する時間がなく...

TL を見ると半分全列挙を (4,4) ではなく (3,5) に変えると通ったというのを見ました. 我々もそれを試したので binary trie の実装が悪かったのかもしれません.

国内予選

昨年同様サークル内でのチームの取りまとめや会場の調整などをしていました. 去年より早めに準備を終え, 落ち着いてコンテスト開始を待つことが出来ました.

A 少し面倒ですがまぁやるだけです. (0:02)

B 貪欲に置けばよいです. (0:05)

C 苦手な見た目をしているので ripity に任せると通してくれます. (0:16)

D C を任せてる間に考察をしますが, 苦手な見た目になったので ripity と aqua さんに任せ, 私は E を考えます.

E ABC-like で助かります. ジェムの入ったものとそうでないもので分けます. ジェムの入ったものは 1 つ買えば残りも買えるので, ジェムの入ったものをコインで買う個数を全探索します. このとき, 最終的なジェムの個数は買い方によらないのでコインで買うものは貪欲に選んでよく, 入ってない方も同様です. 丁寧に実装すると通ります. (0:34)

この辺りで順位表を見て学内 1 位だったのでペナ差に気をつけた立ち回りをすれば良さそうだなぁという感じです.

D は大体解けていると主張されましたが, 細かいところを合わせるのが大変そうに見えたので愚直を書いておきました. 何回かランダムで落ちていたようで, 書いておいて良かったです. (0:53)

F 座圧して頑張ります. こういう実装への苦手意識が減ってるなぁと感じました(それにしては遅いですが...). 何はともあれ AC を得ます. (1:55)

H 気づいたら ripity が通してくれてました. (2:14)

G ぶつかる条件を考えるとある 1 つの行に限られることが分かります. よって, その行の各マスについてそのマスで初めてぶつかるような動かし方が分かればよく, これは 4 方向から DP をしておくことで求めることが出来ます. (解説に耳って書いてあったけどこっちの方が楽じゃないか?) (2:43)

最終的には 8 完ノーペナで全体 12 位, 学内 1 位でした. 無事 Yokohama に行けそうでひと安心です.

Standings

ノーペナは偉いですが全体的に実装に時間をかけ過ぎた感じです. ただ, 冒頭にも書いたように今年はチーム練ゼロ, 個人での練習も全員あまり出来ていなかったのでこれ以上を望むのは難しい気もします.

Yokohama はちゃんと練習を重ねて全力を出したいです, 頑張ります.

↓国内予選の日の最大の偉業

プチコンテスト解説

これの解説です.

解説というか自分用の解法メモ程度のクオリティですが...

I Love AB Problem

問題文

A, B からなる長さ $N$ の文字列 $X,Y$ が与えられます. あなたは, 以下の操作を $0$ 回以上好きな回数行えます.

  • $i \ne j$ かつ $X_i \ne Y_j$ なる $1$ 以上 $N$ 以下の整数 $i,j$ を選び, $X_j$ と $Y_i$ を入れ替える($X_i$ と $Y_j$ を入れ替えるのではないことに注意してください)

$X$ と $Y$ を一致させることが出来るか判定し, 可能な場合は必要な最小の操作回数を求めてください.

$T$ 個のテストケースについて解いてください.

制約

  • $1 \leq T \leq 2 \times 10^5$
  • $1 \leq N$
  • $X,Y$ は A, B からなる長さ $N$ の文字列
  • $T,N$ は整数
  • $1$ つの入力ファイルに含まれる $N$ の総和は $10^6$ 以下

解説

$X_i =$ A, $Y_i =$ B なる $i$ の個数を $C_{AB}$, $X_i =$ B, $Y_i =$ A なる $i$ の個数を $C_{BA}$ とします.

操作によって $C_{AB},C_{BA}$ の偶奇は不変なので, $C_{AB},C_{BA}$ が共に偶数である必要があります. 逆にこのとき $X_i=X_j=$ A, $Y_i=Y_j=$ B なる $i,j$ を用いて操作すれば $C_{AB}$ を $2$ つ減らせます. $C_{BA}$ も同様です. よって, $(C_{AB}+C_{BA})/2$ 回で $X$ と $Y$ を一致させることができます.

All Pair Swap

配点 : $500$ 点

問題文

$(1,2,\dots, N)$ の順列 $P = (P_1, P_2,\dots,P_N)$ が与えられます.

以下の操作をちょうど $N (N - 1) / 2$ 回行うことで $P$ を昇順に並べ替えられるか判定し, 可能な場合はその操作列の一例を示してください.

  • $1\le x\lt y\le N$ を満たす整数組 $(x, y)$ を選び, $P_x$ と $P_y$ を swap する. ただし, ここで選んだ $(x, y)$ はこれ以降選ぶことができない.

$T$ 個のテストケースが与えられるので, それぞれについて答えを求めてください.

制約

  • $1 \leq T$
  • $2 \leq N$
  • $P$ は $(1,2,\dots,N)$ の順列
  • $1$ つの入力ファイルに含まれる $N^2$ の総和は $3 \times 10^5$ 以下
  • 入力は全て整数

解説

$(x,y)$ と $(y,x)$ を同一視します.

swap によって転倒数の偶奇が反転するので $P$ の転倒数 $\bmod 2$ と $N(N-1)/2 \bmod 2$ が一致する必要があります. 逆に, これを満たすときは必ずソートできます. 以下, 手順を示します.

$P_i \ne i$ なる $i$ が存在するとき

$P_j=i$ となるように $j$ を取り, $(i,1),(i,2),\dots,(i,j-1),(i,j+1),\dots,(i,N),(i,j)$ の順に操作を行えば $N$ が $1$ 小さい場合に帰着できます.

$P_i \ne i$ なる $i$ が存在しないとき

転倒数の条件から $N \bmod 4$ は $0$ または $1$ です. $N=0,1$ のときは可能な操作がないので $N \geq 4$ とします. このとき $(1,3),(2,4),(1,5),(2,5),(1,6),(2,6),\dots,(1,N),(2,N),(2,3),(1,4),(1,2)$ の順に操作をすれば $N$ が $2$ 小さいケースに帰着されます. 気持ちとしては, $1,2$ を $P_3,P_4$ に逃した後で $(1,k),(2,k)$ を消費し, 最後に引き戻しています.

Aobasan's Contest

問題文

あおばさんは競技プログラミングの問題を $N$ 問作りました. $i=1,2,\dots,N$ に対して $i$ 番目の問題のジャンルは $X_i$ で面白さは $Y_i$ です. あおばさんはこのうちのいくつかの問題を使って競技プログラミングのコンテストを開催することにしました.

様々なジャンルの問題が出題された方が面白いコンテストになると思っているあおばさんは, コンテスト全体の面白さを (ジャンルの種類数) $\times$ (各問題の面白さの総和) としました. 形式的には, コンテストに使う問題を $1 \leq i_1 < i_2 < \cdots < i_K \leq N$ として $$\lvert \lbrace X_{i_j} \mid j=1,2,\dots,M \rbrace \rvert \times \displaystyle\sum_{j=1}^{K}Y_{i_j}$$ がコンテスト全体の面白さです.

$K=1,2,\dots,N$ に対して次の問題を解いてください.

  • $N$ 問のうち $K$ 問を使って作れるコンテストは $\binom{N}{K}$ 通りありますが, それら全てに対するコンテスト全体の面白さの最大値を求めてください.

$T$ 個のテストケースについて解いてください.

制約

  • $1 \leq T$
  • $1 \leq N$
  • $1 \leq X_i \leq N$
  • $1 \leq Y_i \leq 10^6$
  • 入力は全て整数
  • $1$ つの入力ファイルに含まれる $N$ の総和は $3 \times 10^5$ 以下

解説

集合は多重集合とします. また, 適切に番号付けを行うことで, $1 \leq X_i \leq L$ かつ $j=1,2,\dots,L$ に対してある $i$ が存在して $X_i=j$ が成り立つとします.

$i=1,2,\dots,L$ に対して $M_x = \max \lbrace Y_i \mid X_i = x \rbrace$ とし, 列 $A,B$ を以下で定めます. 直感的にはジャンルごとの最大値を並べた列が $A$, それ以外を並べた列が $B$ です.

  • $A$ は $\lbrace M_x \rbrace_{x=1}^{L}$ を降順に並べた列
  • $B$ は $\lbrace Y_i \rbrace_{i=1}^{N} \setminus \lbrace M_x \rbrace_{x=1}^{L}$ を降順に並べた列

さらに, それらの累積和 $S(A), S(B)$ を

$$S(A)_0=S(B)_0=0,S(A)_i=\sum_{j=1}^{i}A_j,S(B)_i=\sum_{j=1}^{i}B_j$$

で定めます. これを用いて, 非負整数 $k,i$ に対して $f(k,i)=i(S(A)_i+S(B)_{k-i})$ とします. なお, 定義されていない添え字に対しては $-\infty$ が返るとします.

このとき, $K=k$ のときの答えは $\max\limits_{i=0,\dots,k}f(k,i)$ です.これは, $A,B$ のどちらについても prefix でないものを使っているときに, prefix の問題に置き換えても答えが悪化しないことから従います.

さらに, $\text{argmax}_i f(k,i)$ は $k$ について単調増加です(タイブレークは $i$ の大きい方を採用するとします).

証明

$l=\text{argmax}_i f(k,i),r=\text{argmax}_i f(k+1,i)$ とします. $l \leq r$ が示されれば良いです.

$l \gt r$ を仮定します. このとき

$$\begin{align} f(k+1, l) &= l(S(A)_l+S(B)_{k+1-l}) \\ &= l(S(A)_l+S(B)_{k-l}) + lB_{k+1-l} \\ &= f(k,l) + lB_{k+1-l} \\ &\geq f(k,r) + lB_{k+1-l} \\ &\geq f(k,r) + rB_{k+1-r} \\ &= r(S(A)_r+S(B)_{k-r})+rB_{k+1-r} \\ &= f(k+1,r) \end{align}$$

となり, これは $r=\text{argmax}_i f(k+1,i)$ に矛盾します. よって $l \leq r$ が示されました.

よって monotone minima などによって全ての $k$ に対する $\text{argmax}_i f(k,i)$ を列挙できるので本問題を $O(N \log N)$ で解くことができました.

ICPC2025国内予選参加記（Aobayama_BlueMountain，nonon 視点）

ICPC2025国内予選に参加したのでその参加記です．

去年:

nononmath.hatenablog.com

ripity 視点:

ripity.hatenablog.com

〜模擬国内

去年まで組んでた neko が今年は組めないとのことで同学年の aqua さんに声をかけてチームを組みました．ripity は去年と変わらずです．

週 1 でチーム練をしてました．個人では，ライブラリ整備と国内予選の過去問埋めをしてました．

また，今年は学内 2 位は堅いと思っていたので下振れを引かないようなムーブを心がけてました．

模擬国内

今年は他 2 人に序盤を任せて，自分は E 以降を担当することにしてました．

D:
ripity が「昔この問題作ったことあります」と言ってたのを聞いて本番でも引いてくれ〜と思ってました

E:
構文解析をして木を作ると，DFS しながら各葉の寄与が簡単に求まることが分かります．構文解析をやりたくないので実装を ripity 任せます． が，RE が返ってきます．私もコードを眺めますが何が落ちてるのか分からず...

そのまま 3 人でコードと睨めっこしたり，assert を山のように入れてランダムを回したりしますが全く落ちません．1 時間ほど経ったところで ripity が main で return true; をしてることに気づきます（これが手元で落ちないの困った...）．

F:
考察はしましたが実装キューから出ませんでした．

H:
時間がなかったのであまり考察できず，適当に思いついた良さそうなのを出しては落ちてました．

結局 5 完 36 位というなんとも言えない結果でした．途中の 1h 捨てても突破ラインは超えてそうだったので良かったねと言ってました．

あと，応援に来てくださった Dispersion さんから 6/9 問の原案だったことを聞き驚いてました．私も引退したら貢献したいよ〜〜

国内予選

開始直前までバタバタしてたので現実感のないままコンテストが始まりました．

D:
ripity が落ちたというので問題文を読み，2x2 を見ると良さそうと言ったら ripity が通してくれました

E:
貪欲で良さそうですが，怖かったので簡単な証明をしてから ripity に解法を伝え実装を任せました．これが結構ミスで，私が実装をするべきでした（なんとなくの実装方針が浮かんでいたので）．

F:
Bessie が右から探索すると誤読をしていました．aqua さんと話しているときに話が噛み合わずなんとか気付くことが出来て助かりました（ありがとう...）．誤読をしないと簡単に後ろから構築できるので E の実装で沼ってる ripity から PC を強奪して通します．

G:
考えておらず...

H:
考察はすぐ出来ましたが筋の悪い実装方針を引いてしまい間に合わず...

I:
何もわからず...

学内 2 位/全体 42 位でした．

コンテスト中もそれ以前も（この記事には書いてませんが）色々あって大変な国内予選でしたが，なんとか突破できてそうで一安心です．

最後に

模擬国内・国内予選を運営してくださった方々に感謝，毎年本当にありがとうございます！！

初の Yokohama 頑張るぞ！！

ACPC2025 参加記 & TUPC2024 開催記

ACPC2025 の参加記，兼 TUPC2024 の開催記です．

会津若松駅を庇い石にされてしまったあかべこ

去年の TUPC 開催記はこちらから:

nononmath.hatenablog.com

当日まで

今年の TUPC の開催を決めたのは去年の TUPC が終わった直後だったと思います．昨年とは異なり，自分がサー長になっていたので頑張らないとなぁとなりました．

スケージュールとしては昨年を参考に，国内予選が終わったくらいから本格的に動き出そうと思っていました．

すると，なんとビックリ！会津大がオンサイトコンテストを開催するという告知が出たのです．

昨年の感覚から，地方でのオンサイトは人が集まりにくいのでは？という気持ちがあったので，3 月に東北で 2 つもオンサイトがあると人が来なくなりそうです． 一人で考えてもどうしようもないので，その日のサークルで相談をし，会津大に共同開催を持ちかけることにしました．

会津大が快く引き受けてくださり共同開催が決定しました．

また，8 月の頭には会津大の方に行き，日程決めや会場の下見などをしました．ところで，この会場の下見には仮の人さんと在来線でゆっくりと行ったのですが，この間の会話で生まれた問題が今年の D 問題です．

それ以降は，基本的に問題準備をしていました．問題についての詳しい話は day2 のところに書きます．

そして，1 月の中旬に UCup 部分の問題を決めました（簡単枠はもう少し後でした）．その後は赤の tester に走ってもらったり簡単枠を完成させたり部内 tester に走ってもらったりしました．

部内 tester が青 2 人で簡単枠 300 点だったので，部分点を増やすことにしました．この時増えたのが C の 1 つ目と O の部分点です．コンテスト中に結構解かれていたので追加して良かったです．

後は問題文のチェックとか諸々をしていたらあっという間に ACPC 前日になってました．

day 1

ACPC の前後に実家で予定があったので実家の横浜から向かいました．新幹線は自由席でしたが，かなり空いていて快適でした．

お昼過ぎに会津若松駅に到着，そんなにお腹が空いていなかったのでコンビニでおにぎりと菓子パンを買って会場に向かいました．到着するとかなりの人がいてびっくりしました．

立命館大学からは 10 人以上が来てると聞き，これにもまたびっくり．部としてのシステム等が自分たちよりちゃんとしてそうで見習いたいなぁと思いました．

day1 コンテスト（立命館大学セット）

この日は kotatsugame さん，olphe さんとチーム kotatsugame_marunage で出場，クジで決まったチームでしたがチームに赤コーダーがいて緊張です．

特に難易度等の情報がなかったので自分が A から，olphe さんが E から，kotatsugame さんが L から読むことになりました．

コンテストが始まり A を読むと解けそうです．B を読むと強いデータ構造で殴れそうです．C は 3 乗まではすぐ分かります．チームメイトの実装 queue が空になってから A の実装を始めます．書きながら kotatsugame さんに B と C を共有，両方できそうだと言われます．

A でバグらせたので B を書いてもらい，A が通ったら C を書いてもらい，あっという間に 6 完です．

その後は D を考えます．N が小さいので列を全て見ることができ，各列はいい感じに区間に分かれるので境界が分かれば良さそうです．あとは olphe さんに実装を丸投げして AC を取ってもらいました．

残り時間は J と K を反復横跳びしながら椅子を温めていました．

結局 9 完で全体 4 位，オンサイト 2 位でした．

day1 コンテスト後

解説終了後は懇親を探してウロウロします．すると，駅前に集まると良いという情報が手に入ったので駅前に行きます．集まった人数が多かったのでいくつかのグループに分割することに，自分は kotatsugame さん，m_99 さん，んをさんと「桜莉紙」という居酒屋に行きました．

izakayaorigamiaizu.wixsite.com

店の雰囲気もよく，ご飯も美味しくて最高でした．特にソースカツ丼が美味しく，day2 以降もたくさん食べてました．

ご飯を食べたり，お話をしたり，kotatsugame さんの ABC を見守ったりしながら 23 時すぎまで店にいました．帰り道で kotatsugame さんが歩きながら div2 に出ていました．

自分はホテルについてそのままベッドに突き刺さっていました．

day2

この日は東北大セットです．自分は writer なのでドキドキとワクワクが半々くらいの気持ちで会場に向かいます．すると，用意された admin ルームのなんと広いことか．快適な順位表観戦が保証されていてワクワクです．

昨年まで司会をしていた milkcoffee さんがいないので自分が司会を引き受けることにしました．特に大きなトラブルなく進行できたのではないでしょうか（そもそも話すことが少ないので，それはそう）．

以降ネタバレ注意です．

問題の感想

writer/tester をした問題だけ書きます．

A - Inversion PQ and QP

tester とユーザー解説の執筆をしました．いきなりですがこのセットで一番好きな問題です．パズルっぽい構築に見えて，ゴリゴリの数学問なのがめちゃくちゃ好きです．

仮の人さんから問題概要を聞いた直前の週の群論の授業で共役類についてやっていたので驚きでした（実は去年の 012 Grid も問題を聞く直前に LGV 公式について勉強していたので，それも含めてびっくり）．群論パートの後の考察も実装もかなり大変だと思います． 実験をすると実は swap と 3-point-rotate しか使わなくて良さそうという部分をエスパー＆最大化が貪欲でできることが分かればあとは頑張るとなんとかなります．最後の復元も簡単じゃないと思います．自分は授業ノートとにらめっこしながら書きました．

仮の人さんがエスパーパート頑張って証明していたので（すごい）それの査読をしました．

本番は riano_ さんが解いていてびっくり（0AC になりそうだと思っていたので）．すごいですね...

D - Swap Counter

writer をしました．これは上にも書いた通り会津大学に行く途中の電車内で生まれた問題です．最初に考えたのは（辞書順最小とは限らない）構築でしたが，少し考えると次の 3 つが全て解けそうだとなりました（実際解けます）．

  • $ B $ が与えられるので $f(P) = B$ なる $ P $ を構築せよ
  • $ P $ が与えられるので $ f(P) $ を求めよ
  • $ B $ が与えられるので $f(P) = B$ なる $ P $ を数え上げよ

後日，丁寧に解説を書くと辞書順最小ができたので，問題セットとの兼ね合いでそれを出題することにしました．上手く書くと python 解が 20 行を切ってびっくり（https://atcoder.jp/contests/tupc2024/submissions/62430681）．

本番では全然解かれませんでしたがそんなに難しくないので是非 upsolve してみて下さい．

F - Another Long Sequence Inversion

writer をしました．原案は次のものでした．

$L \oplus X, (L + 1) \oplus X, \dots, R \oplus X$ のうち $ M $ の倍数はいくつですか（$R, X, M \lt 2^{60}$）

これだと XOR 区間の分割の知識すぎると言われたので転倒数に変更，さらにとりゐさんからクソデカ制約でも二進数出力でも解けると指摘を受けて今の形になりました． 解法自体は典型（らしい）ですが実装をちゃんと詰めるのが結構大変に感じました．

コンテスト中の提出が 0 で悲しいです．全然不可能じゃないので是非解いて下さい．

I - Small Steps

tester をしました．自分が原案を見たときは $K = 1$ のとき（ただの木についての問題）でした． ただ，直径 like なパスの隣接する葉の個数の階乗積で書けるのを出題したいなぁと提案，仮の人さんが考えた今の出題形式によってガッツリした数え上げになりました．場合分けが多くて大変な問題なのでマルチテスト＆部分点なしを提案しました．

これもコンテスト中の提出が 0 でしたがめちゃくちゃ面白いので是非解いて下さい．

L - Square Connection

writer をしました．最初は構築なし（長さのみ出力）だったのですが仮の人さんに一瞬で（構築込みで）解かれたので構築込みで出題しました．

また，原案段階では「無限グラフ上の最短経路を求めよ」という形だったのですが，ジャッジの都合で入ってしまう $u \leq 4 \times 10^{18}$ という制約を上手く問題文に入れるのが大変だったので今の形に変更しました．

M - Divide Digit String

tester をしました．$K = 1$ かどうかで全く違う問題になる＆どちらも非自明・それなりに大変な実装になっていてすごいなぁと思いました．こういう問題を作れるようになりたいですね．

順位表では想定以上に解かれていて，人々は強いなぁとなっていました．

day2 コンテスト後

この日はかっつさん，m_99 さん，sotanishy さん，とりゐさん，仮の人さん，E49869826 さん，ripity に自分を合わせた 8 人で「権兵衛」という居酒屋に行きました．

www.instagram.com

人生で初めて馬刺しを食べましたが，創造以上の美味しさで最高でした．その横についていた辛子味噌も最高の味です．また，この人数なのでみんなでいろんな日本酒を注文して飲み比べることが出来ました．個人的には「写楽」と「一生青春」が美味しかったです．

後は「にしんの山椒漬け」がとても日本酒に合い，最高でした．

店を出た時間が 21 時を過ぎていたので，ARC を諦め夜の観光に行くことにしました．sota さん，仮の人さんと鶴ヶ城の方まで歩きました．

day3

最終日です．名残惜しい気持ちになりながらホテルをチェックアウトし，会場に向かいます．お昼ご飯を食べる時間がなさそうなのでコンビニでおにぎりと菓子パンを買って向かいました．

day3 コンテスト（会津大学セット）

この日は kotatsugame さん，かっつさんとチーム kotatsugame_arigatou で出場，この日もクジで決まったチームでしたが再びチームに赤コーダーがいて緊張です．

この日は A, B が簡単であることが公開されていたのでかっつさんが A を，自分が B をやることにします．B を読むと制約がすごく小さいのでやれば良いです．が，カスの実装ミスで無限分溶かした上に 2 ペナをつけてしまい大反省です．

なんとか通した後は C を読みます．max の寄与を少なくしたいので端に置くと，問題が小さくなるので同じことを繰り返せば良いです．同じ値の部分に気をつけながら実装し，AC．その直後に kotatsugame さんが N の FA を取り順位表を破壊していました．

このあと少しすると順位表情報が無くなったので kotatsugame さんと相談しながら色々と考えます．赤コーダーの考察速度が早過ぎて置いていかれまくり...

結局開始 2 時間と少しで I, K を除いた 12 完になり，残りも考察は終えている感じになっていました．K は kotatsugame さんが受け持っていたのでかっつさんに「I の実装どうしますか？」と聞くと「実装バトルでしょ」と言われたのでバトルスタート．途中からは K を通した kotatsugame さんも合流し 3 人でバトルすることに．

1 番最初にサンプルがあったのは kotatsugame さんでしたが提出すると WA．続いてかっつさんも提出しますが WA に．最後にサンプルを合わせた私が提出すると，なんと AC．大逆転勝利でした．

コンテスト終了まで 1 時間ほど時間があったので学食でお昼ご飯を食べました．

結局他に全完は出ず，優勝することが出来ました．

day3 コンテスト後

m_99 さん，仮の人さんが会津駅前でお土産を買うというので付いて行きました．途中で ripity も合流し 4 人で駅前へ．その途中に「かついち」というとんかつ屋さんで再びソースカツ丼を食べました．

tabelog.com

お土産は駅ナカのお店へ．

www.livit.jregroup.ne.jp

にしんの山椒漬け，辛子味噌，日本酒（山廃純米　末廣）を買いました．

最後に

信じられないくらい楽しい 3 日間でした．欲を言えばもっとたくさんの人にオンサイトに来てもらいたかったですが...

今まで話したことない方と話したり，夜遅くまでお酒を飲んだり，観光に行ったりと今まで自分が行ったことのあるオンサイトではなかった経験がたくさんできてよかったです．来年もやりたい〜

準備期間からお世話になった会津大学・立命館大学の皆さん，オンサイトに来てくださった皆さん，コンテストに参加してくださった皆さん，本当にありがとうございました！！

ARC190 B - L Partition を解く

問題: atcoder.jp

解説やユーザー解説と考察過程が違ったので簡単にメモ書きを残しておきます．

$f_k(n,r,c)$ を $n \times n$ のマス目の分割であって，マス $(r,c)$ がレベル $k$ の L 型に含まれるようなものの個数とします（範囲外の部分は $0$ としておきます）．$k \lt n$ のときはレベル $n$ の L 型の置き方を場合分けすることで

$$f_k(n,a,b) = f_k(n-1,a,b)+f_k(n-1,a-1,b)+f_k(n-1,a,b-1)+f_k(n-1,a-1,b-1)$$

が成り立ちます．これを配る DP の遷移のように表現すると

$$f_k(n+1,r,c) += f_k(n,r,c)$$ $$f_k(n+1,r+1,c) += f_k(n,r,c)$$ $$f_k(n+1,r,c+1) += f_k(n,r,c)$$ $$f_k(n+1,r+1,c+1) += f_k(n,r,c)$$

となります．また，base-case の $f_k(k,r,c)$ は次のようになります．ただし $C_k = \lbrace (1,1),(1,k),(k,1),(k,k) \rbrace$ です．

$$ f_k(k,r,c) = \begin{cases} 1 & (k=1) \\ 3\cdot 4^{k-2} & (k > 1 \land (r,c) \in C_k) \\ 2\cdot 4^{k-2} & (k > 1 \land (r \in \lbrace 1,k \rbrace \lor c \in \lbrace 1,k \rbrace) \land (r,c) \notin C_k) \\ 0 & (otherwise) \end{cases} $$

さらに，遷移が線形なので $g(n,r,c) = f_{1}(n + 1, r + 1, c + 1)$ として $$\begin{align} f_k(n,r,c) &= \displaystyle\sum_{1 \leq i,j \leq k}g(n - k, r-i,c-j)f_k(k,i,j) \\ &= \displaystyle\sum_{(i,j) \in C_k}g(n - k, r - i, c - j) \cdot 3\cdot 4^{k - 2} \\ &+ \displaystyle\sum_{i=2}^{k - 1}g(n - k, r - i, c - 1) \cdot 2\cdot 4^{k - 2} \\ &+ \displaystyle\sum_{i=2}^{k - 1}g(n - k, r - i, c - k) \cdot 2\cdot 4^{k - 2} \\ &+ \displaystyle\sum_{j=2}^{k - 1}g(n - k, r - 1, c - j) \cdot 2\cdot 4^{k - 2} \\ &+ \displaystyle\sum_{j=2}^{k - 1}g(n - k, r - k, c - j) \cdot 2\cdot 4^{k - 2} \end{align}$$

が成り立ちます（各 base-case がマス $(r,c)$ に与える寄与に注目しています）．よって $g(n,r,c)$ がある程度閉じた式になって欲しさがあります．

結論から述べると $g(n,r,c)=\displaystyle\binom{n}{r}\binom{n}{c}$ です（これは実験により容易にエスパーできますし，私もコンテスト中はそうしました）．証明は

$$\begin{align} & \displaystyle\binom{n}{r}\binom{n}{c}+\binom{n}{r+1}\binom{n}{c}+\binom{n}{r}\binom{n}{c+1}+\binom{n}{r+1}\binom{n}{c+1} \\ &= \displaystyle\left(\binom{n}{r} + \binom{n}{r+1}\right)\left(\binom{n}{c} + \binom{n}{c+1}\right) \\ &= \displaystyle\binom{n+1}{r+1}\binom{n+1}{c+1} \end{align}$$

から帰納法が回ります． これを先ほどの式に代入して整理すると

$$\begin{align} f_k(n,r,c) &= \displaystyle\sum_{(i,j) \in C_k}f_1(n - k,r - i,c - j) \cdot 3\cdot 4^{k - 2} \\ &+ 2 \cdot 4^{k - 2} \displaystyle\binom{n -k}{c - 1}\sum_{i=2}^{k - 1}\binom{n - k}{r - i} \\ &+ 2 \cdot 4^{k - 2} \displaystyle\binom{n -k}{c - k}\sum_{i=2}^{k - 1}\binom{n - k}{r - i} \\ &+ 2 \cdot 4^{k - 2} \displaystyle\binom{n -k}{r - 1}\sum_{j=2}^{k - 1}\binom{n - k}{c - j} \\ &+ 2 \cdot 4^{k - 2} \displaystyle\binom{n -k}{r - k}\sum_{j=2}^{k - 1}\binom{n - k}{c - j} \end{align}$$

を得ます．結局 $\displaystyle\sum_{i=2}^{k - 1}\binom{n-k}{a-i}$ が $k=2,3,\dots,N$ に対して列挙できれば良く，これは $A_{k} = \displaystyle\sum_{i=2}^{k - 1}\binom{n-k}{a-i}$ とおけば

$$\begin{align} A_{k} &= \displaystyle\sum_{i=2}^{k - 1}\binom{n - k}{a - i} \\ &= \displaystyle\sum_{i=2}^{k - 1}\left(\binom{n - k - 1}{a - i}+\binom{n - k - 1}{a - i - 1}\right) \\ &= \left(A_{k+1} - \binom{n - k - 1}{a - 2}\right) + \left(A_{k+1} - \binom{n - k - 1}{a - k}\right) \end{align}$$

なので $A_{k+1}$ から $A_{k}$ が $O(1)$ で計算できます．以上を適切に実装すれば $O(N + Q)$ で解くことができます．

実装例 ($O(N+Q\log N)$): https://atcoder.jp/contests/arc190/submissions/61684007

入黄記事

AtCoder黄色になりました！！！

自己紹介等は過去の色変記事を読んでもらうことにして，この記事では青から黄色までの間にやったことを書いていきます．

過去の色変記事はこちら:

精進の記録

Achievement

AtCoder Pie Charts - ABC

AtCoder Pie Charts - ARC

AtCoder Pie Charts - AGC

Difficulty Pies

Climbing

青→黄の間にやったこと

  • TUPC の writer
    初めて競プロの作問をしました．テストケース作成や問題文 / 解説の執筆など，色々なことを学びました．ぜひ upsolve してください！

  • ICPC・UCup 等のチーム戦
    去年はゆるりと参加した ICPC でしたが今年はちゃんと精進して出ました．落ちました．来年は Yokohama，あわよくばその先に行きたいですね．

  • ライブラリ整備
    ICPC 用で始めたものですが，楽しくなって自分用のやつも盆栽しています．

  • 学業
    無事，全学教育の単位を取り終え，授業が専門科目のみになりました．数学しかやらなくていい日々，最高すぎるぜ！

精進について

他の方の色変記事を眺めているとみなさん精進の方法について書いていらっしゃるのでそれに倣って私も書きます． と言いつつ特別なことをしているわけではありません．AtCoder Problems から未 AC の問題を適当に選んで解くということを繰り返しています．
あとは過去に解いた問題も解き直してます．そもそも解法を覚えていなかったり，別の解法で解いたり，とできることは多いです．同じ解法でも，前よりもいい実装ができると嬉しくなります．

競プロ以外の話

せっかくなので話したいことを話します．

キーボードとかマウスとか

この lofree というメーカーの製品が好きなので結構愛用しています．他にもリストレストやデスクマットも lofree のものを使っています．

生活

最近美味しいチャーシューの作り方をマスターしました．家で食べるラーメンがめちゃくちゃ美味しいです．

家で作ったラーメン

あと，最近二十歳になりお酒が飲めるようになりました．飲みにいきましょう．誘ってください．

読書

最近読んでよかった本の紹介です．ラノベもそうでないのもあります．

今後やりたいこと

  • AtCoder 橙
    むしろここからが本番だと思っているので頑張ります
  • こどふぉ
    最近健康的な生活習慣になってしまい出れてないので頑張ります
  • UCup・ICPC
    これが一番力になる気がしているので力を入れていきたいです
  • 作問
    TUPC 以外にもゆきことかで作問したいですね，全然アイディアはありませんが

これからも頑張ります！！

JAG 夏合宿 2024 参加記

JAG 夏合宿 2024 に参加したのでその参加記を書く．覚えてない部分はなんとなくで書いてるのでたまに間違ってるかも．

チームメンバーは国内予選と同じ．

nononmath.hatenablog.com

コンテスト以外のお話

Day 0

準備をした．来年以降のために持っていったもの，持っていけばよかったものなどを書いておく

持っていたもの：

  • 服・下着など
  • パジャマ
  • バスタオル
  • ハンドタオル
  • ハンカチ
  • ポケットティッシュ
  • 歯ブラシ
  • パソコン
  • スマホ
  • 充電器
  • 電源タップ
  • ライブラリを印刷した紙
  • 考察用紙
  • 筆記用具
  • 英和辞典
  • 財布
  • パスモ
  • 家の鍵
  • イヤホン
  • エコバッグ

持っていけばよかったもの：

  • サンダル or スリッパ
  • ぬいぐるみ
  • クリアファイル
  • アイコンの写真付きの名札

持って行ったのに使わなかったものはポケットティッシュくらい．でもこれは時と場合によるのであって損はなさそう（英和辞典は開かなかったけど精神的に助かっていた）．

Day 1

代々木のマックで月見バーガーを食べてから会場に向かった．12 時すぎに着き，13 時から 3 時間のコンテストをした．
コンテスト終了後は食事や解説などの後に部屋に行った．部屋に着いてすぐに，ABC の時間も近かったのでお風呂に行ったが，去年と同じ道で迷ってしまった．

来年用メモ： C 棟の番号の若い方に進んだ先の出口から出て，右に曲がるとすぐに風呂に着く

ABC では，隣にいた anmichi さんが 8 位でびっくり．強い...
ABC の終了後は upsolve を未来の自分に任せて談話室でボドゲなどをした．消灯直前に部屋に戻り，0 時過ぎに就寝．

Day 2

7 時ごろに起床．ベッドが固く，腰と肩が痛かった．朝ご飯を食べ，支度をすると 9 時前だったのでコンテスト会場に行き 5 時間を走った．コンテスト後は少し部屋でダラダラしてから懇親会へ．

懇親会では，お寿司とか焼きそばとかローストビーフとかを食べた．色んな人と喋ろうと思っていたのに momoyuu さんと話していたら楽しくて気づいたら解散時間に...

そのあとはボドゲをした．Ito では「強そうな効果音」というお題がかなり脳死になれて楽しかった．この日も消灯直前に部屋に戻り，0 時過ぎに就寝．

Day 3

特に書くことがない... Day 2 と同じように過ぎて行った．解散後はチームメイトと食事に行った．

コンテストのお話

Day 1

EHIJK の 5 完で 18 位．かなり良くない立ち回りをしてしまった気がする．

自分は後ろから読む担当だったのでまず K 問題を読んだ（L 問題に気づかなかった）．同じ設定で単調減少列になるという結論を見たことがあったのでそのまま実装．狭義ではなく広義で実装してしまい 1 ペナするが 23 分で AC．
解き終わるとチームの考察メモに「A：区間最頻値クエリ」とあったので Mo で解けませんか？と提案．ripity に書いてもらったが更新に log がつくので TL 1.2sec では厳しく TLE してしまう．この辺りでようやく順位表を確認すると I が簡単らしいので neko に解いてもらう．40 分で AC．
その後は ripity が A の定数倍高速化を頑張っていたが TLE が取れない．その合間に J と H を解いた．J では二次元累積和をバグらせたので neko に直してもらい 104 分で AC，H ではオーバーフローを起こしてしまった（K で書いたセグ木をコピペしたのだが，K は max 取得だったので int で実装してあり一部修正を忘れてしまった）．愚直を走らせてようやく気づき 116 分で AC．気づいたら E も通っていた（125 分）．残り時間は A と B を頑張っていたが結局どちらも通せず．

簡単枠に取り組むのが遅かったり，バグらせたときのムーブが下手だったなぁという感想．

Day 2

ABFGN の 5 完で 14 位．Day 1 より問題文が読みやすかった．

昨日に引き続き後ろから読んだ．前から読んでいた ripity が A が解けると言っていたのでそのまま実装を任せる．7 分で AC．少しすると，G に AC が出ているので取り組む．こういうので嘘貪欲をしてペナをする経験を何回かしているので ripity と 2 人で正当性を示しながら考察した．
まず，$ 1 $ の棒を使おうと思うと，$(1,1,1),(1,2,2),(1,3,3)$ のどれかになる．さらに，$(1,2,2),(1,3,3)$ は合計で高々 $ 2 $ つあればいい．これは $ 1 $ がなければ $ 2 $ と $ 3 $ を同一視していいことから従う．よって $ 1 $ を正三角形→二等辺三角形の順で貪欲に取ってから，残った $2,3$ の和を $ 3 $ で割って足せばいい．この $\frac{M}{2}$ より大きい部分をまとめられるという考察で原案の長さ $ 8 $ まででも解けるという話を聞いた（$ M $ は長さの最大値）．
次に，F を考えた．木のパス更新クエリに見えるので HLD を書こうと思うが，冷静になると更新されるのが高々 $ 2 $ 点なので前計算をしておけばクエリあたり $O(1)$ になる．結構びっくりな結論だと思っていたが imos 法を一点でやってると思えばかなり自然だった．71 分で AC．この辺りで順位表を確認すると，BKFN あたりが解かれていた（気がする）．自分は N を担当した．
N は素数に注目した in-place な DP で長さの最大化は達成できる．数え上げは各素数ごとに，その時点で最大化を達成しているときに最後に見た index を持っておけば高速に更新ができる．109 分で AC．この時点で 4 位とかだった．
ここから先は苦しかった．自分は K を考えていたが最後まで解けず．neko が B を解けていたので実装を任せたが大炎上していたらしい．ripity が手伝い 277 分で AC．

序盤はかなり理想的な動きができたが，後半の中難易度で一気に落ちた．これは単純に個々の自力不足．

Day 3

ABDGI の 5 完で 18 位．苦しい...

AB が簡単枠だと言われていたので A を ripity が，B を自分が担当．A は難なく 9 分で AC．B も解けた気になったので実装するが WA．なぜか壁を超えた後の処理を sum ではなく max でやっていた．結局最後はランダムを書いてミスに気づいた．116 分で AC．その間にチームメイトが I と D をそれぞれ 38 分，64 分で AC してくれていた．感謝...
そのあとは ripity と G を考えていた．1 文字ずつ伸ばしていくときに，No が返ってくるのは端についたときと違う文字を付け加えたとき．端につくのは前と後ろで 1 回ずつなので基本的には違う文字を貼り付けて信じて進むような方針でいい．23 回 No を受け取ったら 1 文字ずつ引き返す感じで実装した（ripity が）．クエリの文字数上限などで 3 ペナしながら 178 分で AC．
その後は F とか K を頑張っていたが結局どちらも通せず．

B のミスが大きく 5 完最下位になってしまった．

最後に

3 日間を通して，チームとしても個人としても実力不足を感じる部分が多々あった．もっと精進して来年はもっとセットを楽しめるようになりたい．

コンテスト以外では，初めて話す人も多くてとても楽しい 3 日間だった（コンテストが楽しくなかったという主張ではないです．コンテストも面白い問題が多くて楽しかったです）．

運営の皆さん，参加者の皆さん，本当にありがとうございました！！