新春TCB 2021 羽根つき　解説

初めて TechFUL に参加してみたんですが、1 位でスイッチ lite がもらえることになったみたいで嬉し～なのいみです。

 

割と簡単(青 diff くらい？)めの問題が多かった印象ですが、この「羽根つき」の問題だけ少し難しめに感じました。解説の計算量は O(N ^ {2} 2 ^ N) らしいですが、O(N 2 ^ N) で解けたので簡単に解法を紹介しようと思います。

問題

N 戦先取の羽根つきを A, B の二人で行う。 A_i 対 B_i になったら B の勝ち、というルールが M 個提案されている。 A が勝つような試合の通り数が奇数になるようなルールの選び方を 998244353 で割った余りを求めよ。 N \le 17 問題リンク

解法

斜めに bit dp をしながら見ていきます。 dp _ {i, b} = (i 試合後に A が j ( \in b ) 勝しているような通り数が奇数となるルールの選び方の通り数) とします。

dp _ i から dp _ {i + 1} を追加ルールを一切追加しないものとして求めた後に追加ルールを適用することを考えます。

この場合の DP は簡単に求まります(A が勝つか負けるかで場合分け)。 ただし、A が N 勝している、というケースは場合分けする必要があることに注意してください。

追加ルールについて処理をします。 dp _ {i, b} についてルールを追加することは、 b のルールに対応する勝敗の組み合わせが奇数ならば偶数にすること (bit が立っていれば 0 にすること) に対応します。

b において、ルールに対応する勝敗の組み合わせが奇数の(bit が立っている)個数を s 個、偶数の個数を t 個とします。 ルール 2 ^ {s + t} 通りをそれぞれ選んで加算することは、 2 ^ s 通りの部分集合について 2 ^ t をそれぞれ加算することに対応します。

  • 例えば、6 戦目に関して、(2,4) (3,3) (5,1) というルールが存在するとします。 b = {0,2,4,5} という集合に対して 8 通りのルールを加算することは、 {0,2,4,5}, {0,4,5}, {0,2,4}, {0,4} という 4 通りの集合に 2 ずつ加算することに対応します。というのも、(3,3) のように、元々対応する勝敗になる組み合わせが偶数の場合はルールを追加するかどうかは影響しないので、単に 2 を掛ければいいことがわかります。 (2,4) (5,1) のように、対応する勝敗が奇数の場合はルールを選ぶことでその組み合わせを偶数 (0) に変えることができます。これは各 bit について独立に行えるので、ありうるすべての部分集合が列挙されます。

また、これは各 b について先に 2 ^ t を掛け算した後に、ルールが存在するような bit についてのみ高速ゼータ変換を適用することで高速に求まります。

    for(int a = 0; a < n; a++) {
        if(rule[a][i - a] exists) {
            for(b in B) {
                if(b & 1 << a) dp[b ^ 1 << a] += dp[b];
            }
        }
    }

ただし、B はありうる b の集合です。

正方形のグリッドを斜めに見ているので、考える必要のある長さは 1, 2 , 3 , \cdots , N, N-1 , \cdots, 1 となっているため、全体での計算量は O(1 * 2 ^ 1 + \cdots + N * 2 ^ N + (N - 1) * 2 ^ {N-1} + \cdots + 1 * 2 ^ 1) = O(N * 2 ^ N) となります。

昔のコドフォ div1 を評価する(div1 #200 ~ #299)

div1 バチャの記録を付けます。ネタバレはなるべく無いようにします。 評価は主観ですがなるべく客観性のあるようにします。 url は standings を見てしまわないように my submission へのリンクを貼っておきます。

★★★★☆ : 星4 として使います。

div1 #299

★★★☆☆

E が「やっほー！木クエリだよ！」って感じでやる気をなくすけど C まではまあまあ。 D はなんかすごそうなんだけど実はこれを書いた時点ではまだ理解できていないため何とも言えません……(やらなきゃね…)

Status - Codeforces Round #299 (Div. 1) - Codeforces

div1 #296

★★☆☆☆

E はすごい、他はなんか何百回目？みたいな問題だらけ。 まあ典型の練習をしたいならアリかも。D とかは知らない人も結構いそう。 Status - Codeforces Round #296 (Div. 1) - Codeforces

div1 #295

★★★★☆

すごい、このセットすごいよ。B はカスなんだけどそれが許せるくらい後ろがすごい。 まあ問題と解法がすごいだけで書くのは嫌な気持ちになります。

Status - Codeforces Round #295 (Div. 1) - Codeforces

div1 #292

★★★☆☆

ふつーのセット、D は勉強になりそう。

Status - Codeforces Round #292 (Div. 1) - Codeforces

div1 #290

★★★★★

かなり面白い、ちょっと弱めの (令和) ARC みたいなセット。 E の想定解は学びにもなる気がする。A~C も結構面白い

Status - Codeforces Round #290 (Div. 1) - Codeforces

div1 #286

★★★★★

全体的に面白い問題が多い、重要なテクもあるが難易度がかなり高いため、コドフォで言うとレートが 2300 くらいを超えてから挑戦するのをおすすめしたいです。 https://codeforces.com/contest/506/my

div1 #285

★★☆☆☆

ABC はいい感じなんだけど DE がカス。定数倍と戦いながら実装したい方にはおすすめです。

Status - Codeforces Round #285 (Div. 1) - Codeforces

div1 #284

★★☆☆☆

微妙、面白くはない。特に教育的でもない。実装の練習にどうぞ。

Status - Codeforces Round #284 (Div. 1) - Codeforces

div1 #283

★★★☆☆

A~C は何とも言えないけど DE は面白いセット。結構ムズイ

Status - Codeforces Round #283 (Div. 1) - Codeforces

div1 #282

★★★★☆

めちゃくちゃ面白い問題、があるわけではないが教育的なセット。かなりやるべきだと思う。 Status - Codeforces Round #282 (Div. 1) - Codeforces

div1 #278

★★★☆☆

特になし。。 Status - Codeforces Round #278 (Div. 1) - Codeforces

div1 #276

★★☆☆☆

150min セットです。C は好きなんだけどそれ以外が無過ぎて…… 150min 掛けてやる価値はあんまりなさそう Status - Codeforces Round #276 (Div. 1) - Codeforces

div1 #275

★★★☆☆

練！習！って感じのセット、ただ難易度は高めです。

https://codeforces.com/contest/482/my:titile

div1 #274

★☆☆☆☆

色々と文句が多いセットですが、まずは人に伝える文章を練習してほしい。

https://codeforces.com/contest/480/my:titile

div1 #272

★★★☆☆

わりとありきたりの昔のコドフォ！って感じのセット

Status - Codeforces Round #272 (Div. 1) - Codeforces

CF Round#641 F1 Slime and Sequences (Easy Version)

問題ページ

問題概要

  • 「良い数列」とは次の条件を満たす正の整数列のことである。
    • 任意の k > 1, k \in (a_i) に対して、 ( k-1 , k ) を部分列に含む。

正整数 N が与えられるので、
各 1 \le k \le N に対して、次の問題を解いてください。

  • すべての長さ N の 「良い数列」に k は何回登場するか。

制約

  • N\le 5000

考察

まず、良い数列がどのような性質を持っているかを考えよう。
長さ n の良い数列の集合を s_n で書く。
(a_i) \in s_n を一つ fix する。
A = \max (a_i) とすると、 \{a_i\} = \{1, \cdots A \} であることはすぐにわかる。

ところで、サンプルに注目すると、 |s_n| は 1,2,6, \cdots となっていることがわかる。
ここで、 |s_n| = n! と仮定して、 s_n を構成してみる。

次のように良い数列を帰納的に構成する操作を考える。

  • 長さ n 良い数列がある。次の要素を挿入する場所を全部の隙間 n+1 箇所の中から選び、 挿入後も良い数列であるような数のうち、最大のものを挿入する。

例えば、今、
(2,3,3,1,2) という数列の 2 と 3 の間に要素を挿入するとする。
左に 3 は存在しないため、挿入できる最大の要素は 3 である。そのため、挿入後の数列は
(2,3,3,3,1,2) のようになる。
長さ n の数列には挿入個所の候補が n+1 箇所あるため、 このような操作の列で長さ n の数列を作るとき、 n! 通りの操作列が存在する。
ところで、新しく挿入する要素が現在の数列の \max か \max + 1 であることから、異なる操作列からは異なる数列が生成される。
なぜなら、相異なる数列に要素を一つ挿入して等しい数列になるとすると、より右側に挿入している要素の最大性に矛盾するからである。

f:id:no_imi:20200513220458p:plain

(二つが等しいなら、下の図では a ではなく a+1 が挿入できるはずである。)

逆は簡単で、良い数列を固定したとき、操作列は一意に復元できる。
例えば、
(4,2,3,4,1,1,2) という良い数列があった時、挿入された順番は
(7,4,5,6,2,1,3) である。(より小さい数字が先、同じ数字の中では右から左の順に追加されている。)

これにより、 長さ n の順列と 長さ n の良い数列の間に全単射を見出すことができた。

解法

  • 観察
    • 良い数列 (a_i) に対応する順列を (p_i) と置く。 i \lt j , p _ j = p _ i + 1 の時、 a_j = a_i + 1 となっている。 つまり、直前より右に挿入したときに限り、要素の値が増える、ということである。

d _ {i,j} を 長さ i の良い数列で 最大の要素が j 以上なものの数、と定義する。

上の観察により、 + 1 されるような組を j-1 個固定すればよいことがわかる。
このような組を辺で結ぶと、全体が i-j+1 個の連結成分に分けられる。
連結成分内での順番は一意 (左から順) なため、 i-j+1 個の連結成分の順番を定めてあげれば、元の順列、数列が復元できます。
f:id:no_imi:20200513224240p:plain
上は i = 6, j = 4 の例です。(inkscape で描くのが面倒になったんで手書きにしました、ごめん())

さて、このように分ける方法は何通りあるでしょうか？
区別のつく i 個のボールを 区別のつく i-j+1 個の箱に、一つ以上ずつ分ける場合の数に等しく、これは
\begin{equation} \sum_{k = 1}^{k=i-j+1} (-1)^{i-j+1-k} \dbinom{i-j+1}{k} \times k^{i} = S(i,i-j+1) \times (i-j+1)! \end{equation}

に等しいことが知られています。( S は第二種スターリング数)

これと、包除原理を適用して、すべての良い数列の中で t の登場する回数を求めてみます。
t が数列の i 番目に登場する場合の数は

  • (長さ i の数列で最大の要素が t なものの数) \times (i+1)\cdots N
    となります。 これは d _ {i,j} 達を包除してあげることで求めることができます。

式は以下のようになります。

\begin{align} ans_t &= \sum _ {i=1} ^ {N} \left(\sum _ {j=t} ^ {i} (-1) ^ {j-t} \dbinom{j-1}{t-1} (i-j+1)! S(i,i-j+1) \right)\times \frac{n!}{i!} \\
&= \frac{n!}{(t-1)!} \sum _ {i=1} ^ {N} \sum _ {j=t} ^ {i} (-1)^{j-t} \frac{(j-1)! \, (i-j+1)! S(i,i-j+1)}{(j-t)! \, i!} \\
&= \frac{n!}{(t-1)!} \sum _ {j=t} ^ {N} \frac{(-1) ^ {j-t} \, (j-1)!}{(j-t)!} \sum _ {i=j} ^ {i=n} \frac{(i-j+1)! \, S(i,i-j+1)}{i!} \\ \end{align}

スターリング数は O\left( N ^ 2 ) \right) で列挙することができます。 よって、 各 t に対して答えを O\left( N ^ 2 \right) で求めることが出来ました。
ところで最後の式の二つ目の Σ の中には t が現れていないので、前計算することで高速化が出来ます。
よって、全体での計算量が O\left(N ^ 2 \right) となり、この問題を解くことが出来ました。

実装方針

ここまで来たらどう書いてもかわんないって

ソースコード

vector<vmint> StirlingTable(int n){
    vector<vmint> res(n+1,vmint(n+1));
    res[0][0] = 1;
    rep2(i,1,n)rep2(j,1,i){
        res[i][j] = res[i-1][j-1] + res[i-1][j] * j;
    }
    return res ;
}

mint sgn(int x){ return (x&1 ? -1:1);}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);cout<<fixed<<setprecision(15);
    calc();
    int n = in();
    auto S = StirlingTable(n);
    vmint T(n+1);
    // 二項目を前計算
    rep2(j,1,n){
        rep2(i,j,n){
            T[j] += prd[i-j+1] * S[i][i-j+1] * invprd[i];
        }
    }
    // 各 t について答えを求める
    rep2(t,1,n){
        mint ans = 0;
        rep2(j,t,n){
            ans += sgn(j-t) * prd[j-1] * invprd[j-t] * T[j];
        }
        cout << ans * prd[n] * invprd[t-1] << " ";
    }

                
}

提出リンク

所感

コンテスト時間が6時間くらいあったら解けたかもね

競プロで出てもおかしくない！数オリの構築系問題　その3

そのいくつまで続くかはわかりませんが、いい感じの問題を見つけたら暇を見つけて書いていこうと思います！

趣旨

  • 各国の数オリで出た問題で競技プログラミングの問題にもなりそうな問題を集めて紹介
  • 原案はそのまま、場合によっては原文が証明問題のものも使用していい感じの問題文に改変して紹介 といった感じで行こうと思います。

例としては、「○○に対して□□を満たす△△が必ず存在することを示せ」という問題があったとしたら、「○○が与えられるので、□□を満たすような△△を出力せよ」に変える、って感じです。

今回の問題はだま氏(@dama_math)から教えてもらいました。 国際数学オリンピック(IMO)からです。
IMOと聞くと難しそうに聞こえるかもしれませんが、1986年の3番級なので、今に比べるとかなり簡単だと思います。

問題概要

平面上に N 個の点がある。i 個目の点の座標は (x _ i,y _ i) である。
この時、以下の条件を満たすように点を白または黒で塗り分けることは可能か。

  • 座標軸のどちらかに平行な任意の直線上の白色の点と黒色の点の数の数の差が一個以下

可能な場合は構成し、不可能な場合は-1を出力せよ。

制約

  • \(N \le 10 ^ 5\) , 整数
  • \(x _ i , y _ i \le 10 ^ 9\) , 整数

現問題url (IMO 1986 問題6)

AGC換算で 800～900 くらいだと思います(個人の感想)

ヒント1 結論から言うとどんな場合でも可能です

ヒント2 グラフです。

ヒント3 頂点が直線、与えられた点が辺のグラフを考えてみてください。

解答 結論を言うと、常に可能です。以下それを示し、構成します。
与えられた点集合のうち一つでも通るような座標軸に平行な直線を頂点とするグラフを考えます。
(x _ i , y _ i) に対し、 x = x _ i ~~ y = y _ i の二直線の(グラフにおける)頂点を結ぶ辺をグラフに追加します。 このようなグラフにおいて、問題文の条件を言い換えてみます。すると、次のようになります。

  • 無向グラフが与えられる。辺を向き付けることで任意の頂点において入次数と出次数の差が1以下になるようにできるか。

ところで、任意の無向グラフは端点が両方奇数次の頂点であるようなパス (その上、端点は重複しない) とループに分解できることが知られています。これは辺の数に対する帰納法で簡単に示せます。
これらのパスとループを全て同じ方向に向きつけると条件を満たすことは簡単にわかります。

実装としては、

  • 奇数次の頂点が残っている限り、その頂点から奇数次の頂点に到達するまで辺を取り除きながらdfsする。
  • 上の操作後は偶数次の頂点のみ残っているので、適当な頂点からdfsすることでループに分解できる。

のようにすればよいと思います。

所感 グリッドとかでも行、列を頂点、点を辺にすると見通しがよくなる問題めっちゃあるね、、、必ず一回は試すようにしたいです。

競プロで出てもおかしくない！数オリの構築系問題　その2

その2です。今回は難しめです！

その1

趣旨

  • 各国の数オリで出た問題で競技プログラミングの問題にもなりそうな問題を集めて紹介
  • 原案はそのまま、場合によっては原文が証明問題のものも使用していい感じの問題文に改変して紹介 といった感じで行こうと思います。

例としては、「○○に対して□□を満たす△△が必ず存在することを示せ」という問題があったとしたら、「○○が与えられるので、□□を満たすような△△を出力せよ」に変える、って感じです。

今回の問題はフランスからです。

問題概要

p を3以上の素数とする。

正の整数列 \( a _ 1 \cdots a _ p \) であって、以下の条件を満たすものを一つ出力せよ。

  • \( a _ i \le 2p ^ 2 \)

  • \( a _ i + a _ j  \, \, \, (i < j) \) は全て相異なる。

制約

\(p \le 10 ^ 5 \)

現問題url (France Team Selection Test Day2 p3)

AGC換算で 1000~1300 くらいだと思います(個人の感想)

 

 

 

ヒント1 大体 \(2p \) ずつになりそうな、、、？
ヒント2 \(a _ i = 2pi+ f(i) \) の形で表せます。

 

 

 

 

解答

 

 

 

\(a _ i = 2pi+ (i ^ 2 \% p) \) が条件を満たします。以下それを示す。

\(a _ i \) 相異なること、 \( 2p ^ 2 \)以下であることは明らかなので、二つ目の条件についてします。

\( a _ x + a _ y = a _ v + a _ w \) ならば  

\( \{ x , y \} = \{v,w\} \) であることを示します。

\( 2p ( x + y - v - w) = (x ^ 2 \%p) + (y ^ 2 \% p)-(v ^ 2 \%p)- (w ^ 2 \% p) \)  

右辺の絶対値は \(2p\) 未満なので、   

\(x + y = v + w \)  

\(x ^ 2 + y ^ 2 = v ^ 2 + w ^ 2 ~~ (mod p) \)  

が分かります。前者を二乗して後者を引くと

\( 2 xy = 2vw~~ (mod p) \)  

\( (2,p) = 1 \) より

xy = vw ~~(mod p)   

よって、 \( \{x,y\} ,\{v,w\} \) はともに \( \mathbb{F} _ p \) 上の多項式
\(f(x) = x ^ 2 - (x + y) +xy \) の解集合なので一致します。

 

 

 

所感 三番級なので流石に難しいですね。
おそらく \(2pi + f(i) \) の形に書けばよいというのをなんとなくで当てた後に詰めれれば順当に解けそうです。
しかも素数でわざわざ 3以上ならまあ大体 mod p で見るだろうしね...
あともうちょっとセンスのいいタイトル募集してます！