AtCoder Regular Contest 099

C - Minimization

問題

$1,2,...,N$ を並べ替えた数列 $A$ と、整数 $K$ が与えられる
連続する $K$ 個の数字を選び、それらを全て、その中の最小値で置き換える
全てを同じ数にするのに、最低何回の操作が必要か。

例

K=3
9  8  2  1  3  7  5  4  6
↓
9  8  1  1  1  7  5  4  6
      ~~~~~~~
↓
1  1  1  1  1  7  5  4  6
~~~~~~~
↓
1  1  1  1  1  1  1  4  6
            ~~~~~~~
↓
1  1  1  1  1  1  1  1  1
                  ~~~~~~~

4回の操作で等しくなった。

解法

「全ての値を同じ値にする」「1はどんな操作でも変わらない」ので、結局全てを1にすることになる。また、1は1つしかないことが保証される。

範囲をダブらせつつ、 $N$ 個の数字を左端から右端まで長さ $K$ の区間で覆う時の、最小個数が答えとなる。

      _______     _______
9  8  2  1  3  7  5  4  6  10
~~~~~~~     ~~~~~~~  ~~~~~~~~
→ 5個

まず1を含む区間に対して操作し、以降、左と右にずらしながら順次操作していくと、全てを1に出来る。

範囲をダブらせつつの最小個数は、 $(N-1)/(K-1)$ （繰り上げ）で求められる。

        
              n, k = map(int, input().split())
print((n - 2) // (k - 1) + 1)

コード的にはこっちの方がわかりやすいか。

        
              import math
 
n, k = map(int, input().split())
print(math.ceil((n - 1) / (k - 1)))

D - Snuke Numbers

問題

ちょっと意図を汲み取るのが難しい。

整数 $N$ に対し、10進表記での各桁の和を $S(N)$ とする
$T(N)=\frac{N}{S(N)}$ を考える
自分より大きい全ての整数 $M$ に対し、 $T(N) \le T(M)$ となっている数を「すぬけ数」とする
すぬけ数を小さい方から $K$ 個列挙せよ
出力する値は、 $10^{15}$ を超えない

例

$N = 123$ → $S(N) = 6$ → $T(N) = 20.5$

これに対し、

$M = 199$ → $S(M) = 19$ → $T(M) = 10.04...$

123にとって自分より大きい199で $T(123) \gt T(199)$ となってしまうため、123は当てはまらない。

解法

こういう問題が成り立つということは、 $T(N)$ は短期的には揺らぐが長い目で見れば増加する関数であることが予測できる。

まずは実験するのがよい。きちんと証明しようと思えば多分できるのだろう。~~やらんけど。~~

（整数は無限個なので無理だけど、イメージとして）全ての整数 $N$ に対する $T(N)$ を求め、ソートして小さい順に見ていって、ある値 $T(K)$ の時、自分より大きい数 $M$ による $T(M)$ がまだ出てきていなかったら、 $K$ は出力に該当する。

とりあえず範囲を小さくしてやってみる。

        
          実験コード
          
              
              buf = []
for n in range(1, 10000):
    s = str(n)
    t = sum(map(int, s))
    buf.append((n / t, n))
buf.sort()
tmp_max = 0
for v, n in buf:
    if tmp_max > n:
        continue
    print(n, v)
    tmp_max = n
 
# => 出力
# 1 1.0
# 2 1.0
# 3 1.0
# 4 1.0
# 5 1.0
# 6 1.0
# 7 1.0
# 8 1.0
# 9 1.0
# 19 1.9
# 29 2.6363636363636362
# 39 3.25
# 49 3.769230769230769
# 59 4.214285714285714
# 69 4.6
# 79 4.9375
# 89 5.235294117647059
# 99 5.5
# 199 10.473684210526315
# 299 14.95
# 399 19.0
# 499 22.681818181818183
# 599 26.043478260869566
# 699 29.125
# 799 31.96
# 899 34.57692307692308
# 999 37.0
# 1099 57.8421052631579
# 1199 59.95
# 1299 61.857142857142854
# 1399 63.59090909090909
# 1499 65.17391304347827
# 1599 66.625
# 1699 67.96
# 1799 69.1923076923077
# 1899 70.33333333333333
# 1999 71.39285714285714
# 2999 103.41379310344827
# 3999 133.3
# 4999 161.25806451612902
# 5999 187.46875
# 6999 212.0909090909091
# 7999 235.26470588235293
# 8999 257.1142857142857
# 9999 277.75

            

        
      

どうも末尾に9が続く数字が該当しやすいようだ。しかし、1099が該当したかと思えば、2099は該当しなかったり、規則性が分かりづらい。

これ、以降も見ていくと、100999999999999 など先頭が100でも該当してたりする。

えーい、面倒だ。「先頭の4桁以降、全部'9'が続く、 $10^{15}$ 以下の数」で同じことをして求めよう。

        
          
          
              
              def get_value(n):
    return int(n) / sum(map(int, n))
 
 
def solve(k):
    buf = set()
    for z in range(14):
        suffix = '9' * z
        for h in range(1, 10000):
            n = str(h) + suffix
            buf.add((get_value(n), int(n)))
    buf = sorted(buf)
    tmp_max = 0
    ret = []
    for v, n in buf:
        if tmp_max > n:
            continue
        ret.append(str(n))
        tmp_max = n
    return ret[:k]
 
 
k = int(input())
print('\n'.join(solve(k)))

            

        
      

E - Independence

問題

$N$ 個の街と $M$ 個の道路
街をAとBの2グループに分ける（片方が空集合でもいいとする）
分けた結果、各グループ内の街と道路は完全グラフになってないといけない
同じグループの街同士を結ぶ道路の本数が最小になるように分けた時の本数を求めよ
条件を満たすように分けられない時は-1を出力せよ

解法

各グループは完全グラフなので、同じグループの街同士を結ぶ道路の本数は、Aグループの街の数を $A_N$ 個として、 $\frac{A_N(A_N-1)}{2}$ で求められる。

なので答えは $\frac{A_N(A_N-1)}{2} + \frac{B_N(B_N-1)}{2}$ となり、これを最小にするには $A_N$ と $B_N$ をなるべく近い値にした方がよいことが分かる。

で、どう分けるか。

道路が通っていなくて許されるのは、異なるグループに属する街間のみ。

よって、補グラフ（辺の有無を逆転させたグラフ＝道路が通っていない街間を結ぶグラフ）を作り、それが二部グラフになっているかどうか判定すればよい。

ただし、補グラフは連結とは限らないため、連結成分が複数出来てしまう可能性がある。この場合、各連結成分について、どっちをどっちのグループに入れるか考える必要がある。

なるべく両グループの街の数を $\frac{N}{2}$ に近くしたい。これは、editorialでは動的計画法で求めると書いてある。一応、貪欲でも通った。正しいかは怪しい。

        
          
          
              
              def dfs(links, fixed, s):
    q = [(s, 0)]
    cnt = [0, 0]
    while q:
        v, c = q.pop()
        if fixed[v] > -1:
            if fixed[v] != c:
                return False
            continue
        fixed[v] = c
        cnt[c] += 1
        for u in links[v]:
            q.append((u, c ^ 1))
    return (max(cnt), min(cnt))
 
 
def is_bipartite(n, links):
    fixed = [-1] * n
    l, r = 0, 0
    can = []
    for i in range(n):
        if fixed[i] > -1:
            continue
        cnt = dfs(links, fixed, i)
        if cnt == False:
            return -1
        can.append(cnt)
 
    can.sort(reverse=True)
    for cnt in can:
        j = 0 if cnt[0] > cnt[1] else 1
        if l > r:
            j ^= 1
        l += cnt[j]
        r += cnt[j ^ 1]
    return (l * (l - 1) + r * (r - 1)) // 2
 
 
n, m = map(int, input().split())
links = [set(range(n)) - {i} for i in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    links[a].remove(b)
    links[b].remove(a)
print(is_bipartite(n, links))

            

        
      