Processing math: 8%

目次

AtCoder Regular Contest 116 A,B,C,D,E,F問題メモ

AtCoder Regular Contest 116

Dのイージーミスの原因究明までにWA出しまくったのがもったいなかった。。。

A - Odd vs Even

A - Odd vs Even

問題

解法

素因数分解したときの2の個数で判定できる。

素因数のうち、2以外(奇数だけ)を組み合わせて作られる約数は全て奇数。

そこに2が1個あったら、それぞれにかけることで、同数の偶数の約数が作られる。

N =       3^2 * 5  →  1  3  5  9 15  45
N = 2   * 3^2 * 5  →  2  6 10 18 30  90 (上記に加えて)
N = 2^2 * 3^2 * 5  →  4 12 20 36 60 180 (上記にさらに加えて)

2が2個あったら、奇数の2倍の偶数の約数が作られる。この時点で奇数は逆転不可能。

よって、N が奇数なら'Odd'、2の倍数で4の倍数でないなら'Same'、4の倍数なら'Even'となる。

Python3

B - Products of Min-Max

B - Products of Min-Max

問題

解法

この問題における部分列は、連続していなくてもいい点に注意。そのため、最初に A をソートして考えて問題ない。

最小値,最大値を固定し、これらが \min(B),\max(B) になるような B が何個あるか考える。

 max=   2  3  5  6  8  9

min=2   1  1  2  4  8 16
min=3      1  1  2  4  8
min=5         1  1  2  4
min=6            1  1  2
min=8               1  1
min=9                  1

例えば \min=2,\max=6 の時、間の 3,5 が入るか入らないかで 2^2=4 通りの B があり、答えに寄与するのは 2 \times 6 \times 4=48 となる。

最小値を中心にまとめると、\min=2 のとき、2 \cdot 1 + 3 \cdot 1 + 5 \cdot 2 + ... + 9 \cdot 16 だけ寄与する。

表を見ると、minが1つ大きい値になるたびに、各値とのペアの数は概ね \dfrac{1}{2} ずつになっていく。

なので、最初に \min=2 の時の係数 C を上記の通り求めると、 次の \min=3 の時の係数は、C'=\dfrac{C - 2 + 3}{2} で求められる。

さらに次の \min=5 の時の係数は C''=\dfrac{C'-3+5}{2} ……と、逐次的に O(1) で求められる。

Python3

C - Multiple Sequences

C - Multiple Sequences

問題

解法

A_N の値を 1~M まで全探索する。

A_N=k と固定した時、k の素因数分解がたとえば 360=2^3 \ 3^2 \ 5 とかだったとすると、

となるので、そのような数列の個数は重複組み合わせを使って {}_NH_3 \times {}_NH_2 \times {}_NH_1 と数えられる。

便宜的に A_0=1 とすると、○倍とする箇所の候補は N 箇所というのがわかる。

  A0  A1  A2  A3  ...   AN
   1   ?   ?   ?       360
    ↑  ↑  ↑  ↑   ↑    ←N箇所

計算量は、素数を事前計算しておけば

で計算できる。素因数の個数は最大でもそんなに大きくならないし、ほとんどは1~3個程度なのでまぁ定数と見てよく(乱暴)、O(M \log{M}) 程度となる。

Python3

D - I Wanna Win The Game

D - I Wanna Win The Game

問題

解法

なんかC問題と似てる。解き方もまぁ似てるような気がする。

まず例外処理として、N=1 の時、XORを0にできず不可能なので除く。

総XOR=0の制約から、各bitについて、そこを'1'とする項は偶数個とならなければいけない。

なので、上位bitから、そのbitを'1'にする項の個数を「偶数」「個数が N を超えない」「より上位のbitの結果と併せて、総和が M を超えない」範囲で遷移するDPを作る。

初期値は DP[0][M]=1 となる。

N = 5   M = 20 = 10100(2)

bit    DPの内容
       10100:  1    初期状態

 1000  10100:  1    
         100: 10    残り10100からbit'1000'を2個立てると残り100,
                    立て方の場合の数は二項係数で 1 x 5C2通り
  
  100  10100:  1
         100: 15    残り10100からbitを4個, 個数  1 x 5C4 を加算
        1100: 10    残り10100からbitを2個, 個数  1 x 5C2

   10  10100:  1
         100: 65    残り 1100からbitを4個, 個数 10 x 5C4 加算
        1100: 15    残り10100からbitを4個, 個数  1 x 5C4 加算
       10000: 10    残り10100からbitを2個, 個数  1 x 5C2
        1000:100    残り 1100からbitを2個, 個数 10 x 5C2
           0:150    残り  100からbitを2個, 個数 15 x 5C2

このように、残り j からbit bk 個立てた時、DP[i][j-bk]+=DP[i-1][j] \times {}_NC_k で遷移できる。

最終的に、DP[Mのbit長][0] が答え。

計算量は、DPにおける i の状態数が O(\log{M})j の状態数が O(M)、さらに各 DP[i][j] につき何個のbitを立てるかで O(N)。あわせて O(NM\log{M}) となる。

もう少し細かく見ると、j の状態数はdictなどで持つと i が進む毎に1,2,4,8,…と2倍ずつになっていくので、(i,j) の組の状態数がまとめて O(M) となり、全体で O(NM) となる。

Python3

E - Spread of Information

E - Spread of Information

問題

解法

答えを決め打つ二分探索。

国王から時刻0に情報を伝えられる都市を、初期都市と呼ぶことにする。

時間 m を決め打って、m 以内に全都市に行き渡らせるのが可能かどうかは、木DPをおこなうことで判定できる。

適当に根を1つ決め、根付き木としておく。

2つは表裏一体なので、例えば前者を正、後者を負でもっておけばよい。

保留中の頂点とは、「まだ部分木内には自身をカバーできる初期都市が無いが、祖先に初期都市を置けばカバーが間に合う頂点」とする。 基本的に、保留中の頂点をカバーできなくなる前ギリギリで初期都市を置いていくことになる。

わかりやすいように1本道グラフを考えると、葉は DP[v]=1 となり、親をたどる毎に 2,3,4,... と増える。 m になったらその次は初期都市とする。初期都市は DP[v]=-m となる。

m=2
   根
   ○--●--○--○--○--○--●--○--○    ●:初期都市
DP -1  -2   2   1   0  -1  -2   2   1

複数の子を持つ場合、その統合は少し考える必要がある。

v の子頂点の中で DP の正の最大値 a と負の最小値 b を得る。

a+1 < -b のとき

    ⓥ:-2
  /|\     bの初期都市によって、他の子孫の保留中の頂点はすべてカバーできる
 -3  2  1
 |   |       DP[v] = b+1 となる
...  1
a = m のとき

    ⓥ:-3  m=3
  /|\     vを初期都市とする必要がある
 -2  3  1    
 |   |       DP[v] = -m となる
... ...
それ以外

    ⓥ:3     bの初期都市ではaの保留中の頂点に届かないため、
  /|\     aの方の制約を優先する必要がある
 -2  2  1    
 |   |       DP[v] = a+1 となる
...  1

全頂点のDPを埋めたとき、DP[根] が正なら、初期都市をもう1つ置く必要がある。(たとえば根頂点に置けば問題なくカバーできる)

これが m を決めたときの最小ギリギリの初期都市の置き方となり、K を超えないかどうかで判定できる。

1回の判定に O(N)、全体で O(N \log{N}) で求められる。

Python3

F - Deque Game

F - Deque Game

問題

解法

ゲーム問題。

数列が1個のとき

数列が1個しかなく、長さが短い場合から考える。
ただしAが先手とは限らず、どちらから始める場合も考える。

長さ1のとき

操作の余地がない。その1項が答え。

長さ2のとき

先に操作した方が好きなのを残せる。

長さ3のとき

この辺からちょっとややこしくなって、

Aから手を着ける場合
         A手番後  B手番後
1 2 3  →  2 3  →  2
1 3 2  →  3 2  →  2
2 1 3  →  1 3  →  1

Bから手を着ける場合
         B手番後  A手番後
1 2 3  →  1 2  →  2
1 3 2  →  1 3  →  3
2 1 3  →  2 1  →  2

このように、先に手を着けた側が一番残したくないもの (Aにとっては最小値、Bにとっては最大値)が中央にある場合のみ、 それが残ってしまう。

その他の場合は、中央値が残る。

長さ4のとき

左端と右端のどちらを取り除いた方がよいかは、3個のときに帰着して両方調べれば確定する。
先手が得する方を選ぶ。

長さ5以上の奇数のとき

先手だった方が、残り3個になったときにも先手となる。

真ん中3つの要素が重要となる。結論から言うと、真ん中の3つから始めたときと結果は同じになる。

      v v v
... 9 3 5 7 9 ...

Aが先手の時、ちょっと欲張れば9とかに手が届きそうに見えるが、 BはAと逆方向をとり続けることで真ん中を3,5,7の状態に保ち続けることができ、9にはできない。

またBにとっては、ひょっとしたら3,5,7を中央に保つより、 中央をずらすことで残す値をもっと小さくできるかも知れない。 しかし、その場合はAが阻止できる。

          v v v
1 1 ... 1 3 5 7 1 ... 1 1

Bとしては1を残すべく、中央をずらしたいところである。
Aがたとえば左を取り、Bも同じ側を取ると、中央が5,7,1にずれる。
しかし、そしたらAは次からは右しか取らないことで、これ以上、中央がずれるのを阻止できる。

このようにずらして中央が 5 7 ? となった際にこの3数から残される値は、?の値によらず5以上となる。

もしAが右を取ったら、ずらされた中央 ? 3 5 から残される値は3以上なので、 Aとしては左を取るのが正解となり、このようにAが選ぶ以上、 Bも、最初の真ん中3つから残される値より小さい値を残すのは不可能となる。

AもBも、真ん中3つよりよい値を残したくても相手が阻止でき、その時に残る値は真ん中3つのみの時に残る値と一致する。

真ん中3数の大小関係の並びは複数あるが、調べれば、どのパターンもそうなる。

長さ6以上の偶数のとき

奇数個の場合 O(1) で残る値が特定できるとわかったので、 偶数個の場合、先手は左右のどちらを取れば自分にとって望ましいかを2通りから選べる。

数列が複数個のとき

奇数長の数列は先に手を着けた方が不利。

奇数長の数列しか残っていない状況になると、 その時点での先手(奇数長の数列に手を付ける側)はその状況を覆せず、ずっと不利な状況のまま終わってしまう。

また、どちらがその可哀想な方になるかは、初期で偶数長の数列の個数によって決まっている。
偶数個ならA、奇数個ならBとなる。

偶数長の数列は先に手を着けた方が2通りから望む方を取れるので、率先して1回手をつけるべき。
よって、ゲームの流れは「偶数長の取り合い」→「奇数長の処理」となる。

どの偶数長の数列から手を付ければよいかは、利得の大きい方となる。

つまり、2通りの結果を a,b として \max(a,b)-\min(a,b) を計算する。 AもBもこの利得が大きい方から取っていくことになる。

Python3