Codeforces Round #667 (Div. 3)

ABCD4完．Eは解けなかった．

以下問題ごとの感想とACコード．

A問題

問題概要

正整数 $a$ と $b$ が与えられる． $a$ に $1$ から $10$ の数を足したり引いたりして， $b$ にしたい．必要な最小の操作回数はいくつか求めよ．

解法

できるだけ $10$ を足したり引いたりする方がお得．いつまで $10$ を足したり引いたりするかというと， $a$ と $b$ の差が $10$ より小さくなるまでその操作を行う． $a$ と $b$ の差が $10$ より小さくなったとき，その差が $0$ でなければもう一度だけ追加の操作を行う．

$10$ を使う操作を何回できるか，というと $\lfloor \frac{|a-b|}{10} \rfloor$ となる．例えば $a = 2, b = 22$ だったら $2$ 回．追加の操作が必要かは $|a-b|$ を $10$ で割った余りが $0$ かどうか判定すればよい．例えば $a=2, b = 25$ だったら追加の操作も必要になり答えは $3$ 回．

より短くコードを書くならば， $\lceil \frac{|a-b|}{10} \rceil$ が答えになる．

Tips

Pythonで切り捨てを書くなら，vを整数の値として

v // 10

と書けばよいし，切り上げを書くなら

0 -- v // 10

と書けばよい．もちろん切り上げは次のように書いてもよい．

(v + 10 - 1) // 10

コード

def main():
    T = int(input())
    for _ in range(T):
        a, b = (int(i) for i in input().split())
        if a < b:
            a, b = b, a
        ans = abs(b - a) // 10
        if abs(b - a) % 10 != 0:
            ans += 1
        print(ans)


if __name__ == '__main__':
    main()

C++コード

// #define _GLIBCXX_DEBUG
// #pragma GCC optimize("Ofast")
#pragma GCC diagnostic ignored "-Wsign-compare"
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, n) for (i64 i = 0; i < (i64)(n); ++i)
#define reps(i, s, n) for (i64 i = s; i < (i64)(n); ++i)

void solve() {
    int t;
    cin >> t;
    while (t--) {
        int a, b;
        cin >> a >> b;
        int d = abs(a - b);
        cout << (d + 10 - 1) / 10 << "\n";
    }
}
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    // cout << fixed << setprecision(15);
    solve();
}

B問題

これは何ですか？コンテスト中は地獄のような実装をした．

問題概要

正整数 $a,b,x,y,n$ が与えられる． $n$ は操作回数で， $a$ を $1$ 減らす操作か $b$ を $1$ 減らす操作ができる．ただし， $a \ge x$ と $b \ge y$ を満たすようにしなければならない．このとき $a$ と $b$ の積の最小値はいくつか．

解法

公式解説を見ると簡潔に書かれていて， $a$ をできるだけ減らしてから $b$ を減らすか，その逆をやればよい．そして小さい方を出力する．

感想

この問題で苦しんだのは，どうやったら積が最小になるかをあまり考えずにとりあえず実装したのが理由だと思う．初めは $a$ と $b$ をできるだけ等しくなるようにも操作をしようとしていた．

ただ公式解説を読んで改めて小さな例を考えてみると，できるだけ等しくなるように操作をするのは無駄だったことがわかった． $a = 9, b = 7$ でどちらを減らした方が得するか考えたい．減らす前の積は $63$ である． $a$ を減らすと $a=8, b=7$ となり，積が $56$ になる．一方， $b$ を減らすと $a=9, b=6$ となり，積が $54$ になる．このように一方を減らすと，もう一方の減らしていない数だけ積の結果が減る．よって小さい数を減らし続ける方が得なので，操作は二種類しか考えれられなくなる．

一回の操作の影響を考え，どうすれば得をし，最適な値が得られるか方針を立ててから実装すべきだった．

$a$ を先に減らす方針を関数で書いた後，コピペして引数を書き換える実装をした．

コード

def check1(a, b, x, y, n):
    s = a - max(x, a-n)
    a -= s
    n -= s
    t = b - max(y, b-n)
    b -= t
    n -= t
    return a*b


def check2(b, a, y, x, n):
    s = a - max(x, a-n)
    a -= s
    n -= s
    t = b - max(y, b-n)
    b -= t
    n -= t
    return a*b


def main():
    T = int(input())
    for _ in range(T):
        a, b, x, y, n = (int(i) for i in input().split())
        print(min(check1(a, b, x, y, n),
                  check2(a, b, x, y, n)))


if __name__ == '__main__':
    main()

C問題

問題概要

正整数 $n, x, y$ が与えられる． $n$ 要素の数列を構築する問題．数列の要素はすべて異なる正整数である．数列を昇順に並べたときに，隣り合う要素の差はすべて等しくしなければいけない．さらに，条件を満たすような数列のうちで，最大値が最小になる数列を出力せよ．このような数列が存在することは保証される．

解法

$x$ と $y$ の差の約数を計算して，その約数のいずれかを用いて条件を満たす数列を構築する．具体的には，ある約数を $d$ としたときにまず $y$ から $d$ を減らしていったものを数列の要素とする．つまり $(y, y-d, y-2d, ...)$ のような数列になる．要素数が $n$ になったら構築を終了し，要素が $1$ より小さくなったら逆側に構築する．つまり $(y+d, y+2d, ...)$ を追加すればよい．作った数列のうちで，最大値が最小の数列が答え． $x$ が含まれているか，もしくは $x$ が二個含まれていないか，数列の二要素間の差がすべて等しいかなどに注意する．

これはサンプルが親切で， $2, 1, 49$ や $5, 3, 8$ を見て最初は差だけを用いて数列が作れそうな気を感じ取る．ただ $5, 20, 50$ を見ると，単に差ではいけず，差の約数を用いれば作れそうだとわかる．

ただ、制約が小さいのでもっと愚直に解けて $O(n^3)$ 解法もある．これは数列の開始の数 $start$ と差 $d$ を全探索すればよい．

コード

def main():
    def enum_divisors(n):
        divs = []
        for i in range(1, n+1):
            if i*i > n:
                break
            if n % i == 0:
                divs.append(i)
                if n//i != i:
                    divs.append(n//i)
        return divs

    T = int(input())
    for _ in range(T):
        n, x, y = (int(i) for i in input().split())
        diff = y - x
        divs = enum_divisors(diff)
        ans = []
        ans_max = 10**18
        for d in divs:
            A = [y]
            v = y
            while len(A) < n and 0 < v - d:
                v -= d
                A.append(v)
            v = y
            while len(A) < n:
                v += d
                A.append(v)
            maxA = max(A)
            A.sort()
            if x not in A or any(A[i+1] - A[i] != d
                                 for i in range(len(A)-1)):
                continue
            if len(A) == n and maxA < ans_max:
                ans = A
                ans_max = maxA
        print(*ans)


if __name__ == '__main__':
    main()

全探索解法のコード

def main():
    T = int(input())
    for _ in range(T):
        n, x, y = (int(i) for i in input().split())
        ans = []
        ans_max = 10**12
        for start in range(1, 50):
            for d in range(1, 50):
                A = [start+i*d for i in range(n)]
                if x not in A or y not in A:
                    continue
                maxA = max(A)
                if maxA < ans_max:
                    ans = A
                    ans_max = maxA
        print(*ans)


if __name__ == '__main__':
    main()

D問題

問題概要

正整数 $n, s$ が与えられる． $n$ の桁和が $s$ 以下になるまでに必要な最小の操作回数を求めよ． $n$ に $1$ 足す操作が許されている．

解法

繰り上がりが起きると，繰り上がり前より桁和は小さくなるか変わらない．例えば $22$ と $30$ の桁和は $4$ と $3$ である．また $n$ が $18$ 桁くらいしかないので，毎回桁和を計算してよく，桁和が $s$ より大きいならば下の桁から繰り上がりを計算することを繰り返す．

具体的な実装は，何桁目を見ているかの0-indexedの変数 $d$ を持ちながら，各桁を $10$ で割った余りを計算していく． $d$ 桁目は $n // 10^d$ で表現できる．その余りを $dig$ とすると，計算した桁を繰り上げるために必要な数は $(10 - dig) \% 10$ になる． $dig = 0$ のことを考えて $10$ で割った余りとしている．ただし， $d$ 桁目を見ているときは，操作回数としては $(10 - dig) \% 10$ に $10^d$ を書けた数を足すようにすることに注意する．

ABC158Eを思い出した．

コード

def main():
    T = int(input())
    for _ in range(T):
        n, s = (int(i) for i in input().split())
        cur = sum(int(v) for v in str(n))
        ans = 0
        if cur <= s:
            print(ans)
        else:
            d = 0
            while cur > s:
                dig = (n//(10**d)) % 10
                # dig = int(str(n)[::-1][d]) でもOK

                ans += ((10-dig) % 10) * (10**d)
                n += ((10-dig) % 10) * (10**d)

                cur = sum(int(v) for v in str(n))
                d += 1

            print(ans)


if __name__ == '__main__':
    main()

E問題

koboshiさんの解説を見て通しました．これ以上に説明することはありません（え？）．

ただ自分でも整理するために言語化する．

問題概要

2次元平面上に $n$ 個の頂点が与えられる． $x$ 軸方向に水平なプラットホームの長さ $K$ も与えられ，プラットホームを2個配置したときに救える頂点の最大値を求めよ．頂点を救う，とは頂点が $y$ 軸の負方向に"落ちてくる"と想像し，落ちた頂点の下にプラットホームがあるときのことをいう．問題のサンプル下の絵を見るのが，よりよい理解のためになる．

解法

$y = - \infty$ にプラットホームを配置すると考えれば，頂点の高さを気にしなくてよくなる．よって， $y_i$ は無視する．

一つのプラットホームを固定したとき，救える頂点の個数は二分探索により求まる．これは，固定したプラットホームの左端を $x_i$ とすると $x_i + K$ を超えない頂点の最大の添え字を $j$ としたとき， $j - i + 1$ 個である．これを $count_i$ とする．なお $x_i$ を二分探索するため，先にソートしておくのを忘れないようにする．

また，その固定したプラットホームの左端より，Kよりも大きい距離が離れたプラットホームの左端で最大の値を $x_j$ とする．つまり， $x_j \lt x_i - K$ ． $j$ も二分探索によって求まる． $j$ 番目までのプラットホームが救える頂点の最大値を $countmax_j$ とし，これがわかっていれば， $i$ 番目のプラットホームを固定したときの救える頂点の個数は $count_i + countmax_j$ である． $count_i$ を計算するときには， $i$ より小さい $j$ について $count_j$ がわかっているので， $countmax_j$ も計算できる．

あとは $x_i$ から見て $K$ より大きい距離が離れている頂点がなければ $x_i + K$ までの頂点はすべて救えることに注意して，固定するプラットフォームを全探索し，上の計算をすれば答えが求まる．

感想

二つ操作できる対象があったときに，同時に動かそうとするのではなく，一方を固定するなどバラバラに考えるようにしたい．一方を固定したときに何が計算できるか，もう一方については簡単に最適な状況の値が求まらないかを考えたい．

コード

def is_ok(X, K, i, mid):
    if X[mid] - X[i] <= K:
        return True
    else:
        return False


def binary_search(X, K, i):
    ng = len(X)
    ok = i
    while abs(ok - ng) > 1:
        mid = ng + (ok - ng) // 2
        if is_ok(X, K, i, mid):
            ok = mid
        else:
            ng = mid
    return ok


def is_ok2(X, K, i, mid):
    if X[mid] < X[i] - K:
        return True
    else:
        return False


def binary_search2(X, K, i):
    ng = i
    ok = 0
    while abs(ok - ng) > 1:
        mid = ng + (ok - ng) // 2
        if is_ok2(X, K, i, mid):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    T = int(input())
    for _ in range(T):
        N, K = (int(i) for i in input().split())
        X = [int(i) for i in input().split()]
        _ = [int(i) for i in input().split()]
        X.sort()
        count = [0] * N
        for i in range(N):
            ret = binary_search(X, K, i)
            count[i] = ret - i + 1
        ans = count[0]
        count_max = [0]*N
        count_max[0] = count[0]
        for i in range(1, N):
            cur = count[i]
            if X[i] - X[0] <= K:
                cur += i
            else:
                j = binary_search2(X, K, i)
                # j までのcount のmax　を足す
                cur += count_max[j]
            ans = max(ans, cur)
            count_max[i] = max(count_max[i-1], count[i])
        print(ans)


if __name__ == '__main__':
    main()

こどふぉ参加前のくじかつが1完だったので調子悪いかと思ったけど、4完できてよかったぜ……．いや，KEYENCE String難しかったんだよ……．あとEを読んでいるときに作問者はFall Guysをやっていると思った．コンテスト中に思った．

f:id:ntk_ta01:20200905134127p:plain

ntk log ntk

競プロや非競技プロのやったことを書いています.

Codeforces Round #667 (Div. 3)

A問題

問題概要

解法

Tips

B問題

問題概要

解法

感想

C問題

問題概要

解法

D問題

問題概要

解法

E問題

問題概要

解法

感想