AtCoder Grand Contest 041 A～C問題メモ

AtCoder Grand Contest 041

A - Table Tennis Training

• $2N$ 人が $N$ 卓で卓球を繰り返し行う
• 卓は順に $1～N$ のランクがついている
• ランク $i$ の卓で試合を行った2人のうち、勝者は $i-1$、敗者は $i+1$ へ移って次の試合を行う
• ただし、卓1の勝者は卓1に留まり、卓 $N$ の敗者は $N$ に留まる
• 今、友人同士である2人がそれぞれ卓 $A,B$ にいる
• 2人が出会うまでに必要な最小の試合数（2人同士の対戦は含まない）を求めよ
• $2 \le N \le 10^{18}$

このような移動では、基本的に2人の距離の偶奇は変わらない。$A-B$ は偶数ならずっと偶数、奇数ならずっと奇数である。

この距離を0にしたい。

偶数なら、ランクの小さい方が負け続け、大きい方が勝ち続ければ2ずつ縮まり、$\frac{|A-B|}{2}$ が答え。

厄介なのは奇数の時で、卓1で勝つか、卓 $N$ で負けることでのみ、2人の距離の偶奇が調整される。

• 最初にランクが小さい方が卓1で勝ってから負け続ける（大きい方は勝ち続ける）
• 最初にランクが大きい方が卓 $N$ で負けてから勝ち続ける（小さい方は負け続ける）

この2つの両方を試し、小さい方を答えればよい。

B - Voting Judges

• $N$ 問の問題があり、投票で $P$ 問を選ぶ
• 既にいくらかの票は入っており、$i$ 番目の問題には $A_i$ 票入っている
• 残り $M$ 人のジャッジが投票する
• ジャッジはそれぞれ独立に、好きな $V$ 問を(重複無く)選び、それに1票ずつ入れる
• $M$ 人全ての投票が終わった後、得票数の上位 $P$ 問が選ばれる。同率の場合は任意に選ばれる
• $N$ 問の内、選ばれる可能性のある問題の数を求めよ
• $2 \le N \le 10^5$
• $1 \le V,P \le N-1$

$A_i$ は、あらかじめ降順にソートしておき、改めてindexを振り直しておく。

最初から上位 $P$ 位以内の問題は、$M$ 人が全てその問題に投票すれば勝ち残れる。

それより下位の問題が選ばれるような状況を考える。

畢竟……這い上がれないッ……！ 誰かを蹴落とさなければ……現在の上位 $P$ 問の……誰かをッ……！

狙われるは……必然ッ……！ そう、最も弱い問題 $P$ !!

$M$ 人全てから得票しても$A_P$ に届かない問題は、選ばれる可能性が無い。

その間にある問題 $i$（$A_P-M \le A_i \lt A_P$）については、少し考える必要がある。

M=5  P=3
Ai    10  9  8 | 6  5  3 | 2  1
      最初から | ?  ?  ? | 5人全員が投票し、3位以内の問題に誰も投票しなくても
      上位P以内|         | その中の最低"8"に勝てないので敗退確定

問題 $i$ は、$M$ 人全てから得票するとして、最終得票可能数は $A_i+M$ となる。

問題 $i$ が選ばれるためにライバルとなる問題は、$P ～ i-1$ である。 $1～P-1$ とは競っても仕方ないし、$i+1～N$ には必ず勝てる。

Ai    10  9 | 8  6 | 5 | 3  2  1
      争わ  | rival| i | M人のジャッジの票が全て入っても、
        ない|      |   |   (同じく全ての票が入った) 5に勝つことは無い
      ↓  ↓             →M票獲得して問題ない
      M票獲得して問題ない

ライバル全員に勝つか同点で終われば、選ばれる可能性はある。 ライバル以外にはどれだけ票が入ってもいい、もっと言うとライバルに入らないよう、票を喰ってくれた方がありがたい。

ライバル以外の問題に、$M$ 人全てが投票するのが最適である。このような問題の数を $s$ とする。

$s \ge V$ であれば、ライバルには1票も入らないことが可能なので、通過できる。

そうで無い場合、ライバルのどれかに、ジャッジ1人あたり $V-s$ 票、合計 $M(V-s)$ 票入る。

ライバルも、$A_i+M$ 票までなら獲得してよい。これを「猶予」とすると、ライバル全員の猶予の合計が $M(V-s)$ 以下であればよい。

M=5
      rival   i
票    8   6   5
10   ・  ・  □    ■: 初期状態の得票(Ai)
 9   ・  ・  □    □: iが最大可能な得票
 8   ■  ・  □    ・: 猶予
 7   ■  ・  □
 6   ■  ■  □
 5   ■  ■  ■
...

1問あたりの得票が $M$ 以下であるという制約はあるが、今回の場合、その制約は必ず満たされるので考慮しなくてよい。

C - Domino Quality

• $N \times N$ のマス目状の盤面があり、ここにいくつかのドミノを置いていく
• ドミノは縦または横に、隣り合う2マスをぴったり覆うように置く
• 重ねては置けない
• 以下の条件を満たすような置き方を1つ構築せよ。無理ならその旨を示せ
  • ある列(行)について「その列(行)の1マス以上を占めるドミノの枚数」を、その列(行)の「クオリティ」とする
  • 全ての列・行でクオリティが等しい
• $2 \le N \le 1000$

小さい盤面の組み方が分かれば、それをつなぎ合わせれば任意の盤面を作れるので、小さい盤面を全探索しましょう、という問題。

偶然上手くいくことはあっても、理屈立てて成立する盤面を見つけるのは難しい（？）。

たとえば3×3と4×4で共通するクオリティを持つ盤面を作ることができれば、7×7の盤面を作れる。同様にこれを繰り返すと、6,8,9,10,… などどんどん広げられる。

■■■・・・・
■■■・・・・
■■■・・・・
・・・■■■■
・・・■■■■
・・・■■■■
・・・■■■■

なので、小さめのいくつかの $N$ で共通するクオリティを持つ盤面を見つけたい。

ところで、ドミノ1枚置くと行＋列のクオリティの総和は3増える。

  ０１１
０・・・
１・□□
０・・・

なので、3の倍数で無い $N$ で成立するクオリティがあるとすれば、それは3の倍数であるはずである。

小さい盤面なので6以上は考えづらいので、「共通するクオリティは3」と固定して、$N=2～8$ あたりを探索する。

すると、4以上の全てで可能であることが見つかる。

4の盤面をナナメに繰り返し、4～7で最後の1つの埋め方を調整すれば、$N$ が大きくなっても4以上の全てで可能であることがわかる。

また、$N=3$ については個別に可能であるパターンがある。（これはまぁ手探りでも見つかる）