AtCoder Grand Contest 041 A~C問題メモ

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つの両方を試し、小さい方を答えればよい。

def solve(n, a, b):
    if a > b:
        a, b = b, a
    if (b - a) % 2 == 0:
        return (b - a) // 2
    top = (b + a - 1) // 2
    c, d = n - a - 1, n - b + 1
    boo = (c + d + 1) // 2
    return min(top, boo)


n, a, b = map(int, input().split())
print(solve(n, a, b))

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$ 以下であるという制約はあるが、今回の場合、その制約は必ず満たされるので考慮しなくてよい。

from collections import Counter


def solve(n, m, v, p, aaa):
    aaa.sort(reverse=True)
    count = Counter(aaa)
    scores = sorted(count.keys(), reverse=True)

    tmp_cnt = 0
    for pi, s in enumerate(scores):
        c = count[s]
        tmp_cnt += c
        if tmp_cnt >= p:
            ans = tmp_cnt
            rival = s
            htm_cnt = tmp_cnt - (p - 1)  # higher than me excluding top p-1
            htm_sum = s * htm_cnt
            break
    else:
        raise RuntimeError

    # print(ans)
    # print(rival)
    # print(htm_cnt, htm_sum)

    for s in scores[pi + 1:]:
        c = count[s]
        upper = s + m
        if upper < rival:
            break

        v4mtm = v - (n - htm_cnt)  # remaining vote for higher than s excluding top p-1
        if v4mtm <= 0:
            ans += c
        else:
            space = upper * htm_cnt - htm_sum
            if space >= m * v4mtm:
                ans += c

        htm_cnt += c
        htm_sum += s * c

    return ans


n, m, v, p = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(n, m, v, p, aaa))

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増える。

  011
0・・・
1・□□
0・・・

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

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

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

def search(field, xs, ys, n, q, c, r):
    if r == 0:
        return field
    for i in range(n):
        if xs[i] >= q:
            continue
        can_vertical = i < n - 1 and xs[i + 1] < q
        for j in range(n):
            if ys[j] >= q:
                continue
            if field[i][j] != 0:
                continue
            if can_vertical and field[i + 1][j] == 0:
                field[i][j] = field[i + 1][j] = c
                xs[i] += 1
                xs[i + 1] += 1
                ys[j] += 1
                result = search(field, xs, ys, n, q, c + 1, r - 1)
                if result is not None:
                    return result
                field[i][j] = field[i + 1][j] = 0
                xs[i] -= 1
                xs[i + 1] -= 1
                ys[j] -= 1
            if j < n - 1 and ys[j + 1] < q and field[i][j + 1] == 0:
                field[i][j] = field[i][j + 1] = c
                xs[i] += 1
                ys[j] += 1
                ys[j + 1] += 1
                result = search(field, xs, ys, n, q, c + 1, r - 1)
                if result is not None:
                    return result
                field[i][j] = field[i][j + 1] = 0
                xs[i] -= 1
                ys[j] -= 1
                ys[j + 1] -= 1
    return None


def search_main(n, q=3):
    print(n, q)
    field = [[0] * n for _ in range(n)]
    xs = [0] * n
    ys = [0] * n
    remain = n * 2 * q // 3
    result = search(field, xs, ys, n, q, 1, remain)
    if result is None:
        print(None)
    else:
        for row in result:
            print(' '.join('{:02d}'.format(x) for x in row))

search_main(3)
search_main(4)
search_main(5)
search_main(6)
search_main(7)

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

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

def solve(n):
    if n <= 2:
        print(-1)
        return
    if n == 3:
        print('aab\nc.b\ncdd')
        return
    field = [['.'] * n for _ in range(n)]
    r = n % 4
    repeat = [n, n - 5, n - 6, n - 7]
    for i in range(0, repeat[r], 4):
        field[i + 0][i:i + 4] = 'aacd'
        field[i + 1][i:i + 4] = 'bbcd'
        field[i + 2][i:i + 4] = 'efgg'
        field[i + 3][i:i + 4] = 'efhh'

    if r == 1:
        field[n - 5][n - 5:n] = 'abc..'
        field[n - 4][n - 5:n] = 'abc..'
        field[n - 3][n - 5:n] = 'deeff'
        field[n - 2][n - 5:n] = 'd.ghh'
        field[n - 1][n - 5:n] = 'iigjj'
    elif r == 2:
        field[n - 6][n - 6:n] = 'abc...'
        field[n - 5][n - 6:n] = 'abc...'
        field[n - 4][n - 6:n] = 'd.eeff'
        field[n - 3][n - 6:n] = 'dghh..'
        field[n - 2][n - 6:n] = '.g.ijj'
        field[n - 1][n - 6:n] = 'kk.ill'
    elif r == 3:
        field[n - 7][n - 7:n] = 'abc....'
        field[n - 6][n - 7:n] = 'abc....'
        field[n - 5][n - 7:n] = 'def....'
        field[n - 4][n - 7:n] = 'def....'
        field[n - 3][n - 7:n] = 'g..hhii'
        field[n - 2][n - 7:n] = 'g..jjkk'
        field[n - 1][n - 7:n] = '.llmmnn'

    print('\n'.join(map(''.join, field)))

n = int(input())
solve(n)

このウェブサイトはクッキーを使用しています。 Webサイトを使用することで、あなたはあなたのコンピュータにクッキーを保存することに同意します。 また、あなたはあなたが私たちのプライバシーポリシーを読んで理解したことを認めます。 同意しない場合はウェブサイトを離れてください。クッキーに関する詳細情報
programming_algorithm/contest_history/atcoder/2019/1228_agc041.txt · 最終更新: 2019/12/31 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0