yatabis' Archives

後世のために書き記しておく

【AtCoder】 ABC178 参加記録

はじめまして。yatabis です。 私事ですが、先日参加した ABC178 で初の全完を達成し、驚異の1 228位・パフォーマンス2092 という結果を叩き出して水色に突入しました。

これを記念して、ブログを開設しました。 今回は、ABC178 で出題された問題について振り返ります。
(全問題についてかなり丁寧に振り返ったので、そこそこの分量あります。)

前提

私は基本 AtCoder には Python で参加しています。 そのため、問題に対する考え方等が Python に寄っている部分があります。 また、付記するソースコードはすべて Python で記述します。

問題A - Not

0 か 1 の入力 x が与えられて、 x が 0 ならば 1を、x が 1 ならば 0 を出力するという問題です。

これは単純に 1 - x を出力すれば良いです。フラグの立て下ろしの時とかによくやりますね。

\mathrm{not}\, xx \,\mathrm{xor}\, 1 などの方法もありますが、個人的には 1 - x が一番好みです。

結果は 39秒で AC でした。A問題を 1分以内に解けるのは悪くはないです。 ただ、問題自体がシンプルであることに加えてタイプ量も少なく最も早く解ける類の問題でしたが、そのわりに時間がかかってしまったなという感じはします。まあそこまでこだわるところでもないでしょう。

問題B - Product Max

a \le x \le b, c \le y \le d を満たす整数 x, y について、x \times y の最大値を答える問題です。

x \times y が最大になるためには、 xy は取りうる値の範囲の境界値であるはずなので2(a \times c,\, a \times d,\, b \times c,\, b \times d) のうち最も大きいものを答えました。

a,\, b,\, c,\, d の符号によって場合分けすることも考えましたが、かなりめんどくさいことになりそうだという直感のもと、楽な実装を選びました。 今考えても、符号で場合分けする方法にメリットはあまりないように思います。

結果は 1分45秒で AC でした。この問題に 1分6秒かけたことになります。 複数思いついた解法の中から最善だと思われるものを迅速に選び、ミスなく解答できたので上々の結果だと言えるでしょう。 タイポとかの単純ミスでペナルティを出さなくてよかったです。本当に。

問題C - Ubiquity

0以上9以下の N 個の整数からなる数列のうち、0 と 9 がそれぞれ 1回以上現れる数列のパターン数を 10 ^ 9 + 7 で割った余りを答える問題です。

ほとんど公式の解説と同じことを書きますが、まず長さ N の数列のパターン数は 10 ^ N 個あります。
そして、0 が 1回も現れない数列のパターン数は 9 ^ N 個です。
9 が 1回も現れない数列のパターン数も同じく 9 ^ N 個です。
さらに、0 も 9 も 1回も現れない数列のパターン数は 8 ^ N 個です。
よって求めるパターン数は、すべてのパターン数から 0 が現れないパターン数と 9 が現れないパターン数を引き、この時点で 0 も 9 も現れないパターン数が重複して 2回引かれているので、これを足したものとなります。
すなわち 10 ^ N - 2 \times 9 ^ N + 8 ^ N です。

数学的にはこれで良いのですが、これをそのまま実装してしまうと TLE になります。 制約上 N10 ^ 6 まで大きくなり得るため、多倍長整数の計算となってしまうためです3

とはいえ、Python での実装は少し工夫をするだけで大丈夫です。 計算の都度 10 ^ 9 + 7 で割る操作を入れるだけです。

特に N 乗の計算が重いですが、Python だと pow(base, exp, mod) が使えます。

Python での実装例 https://atcoder.jp/contests/abc178/submissions/16682422

n = int(input())
mod = 10**9 + 7
print((pow(10, n, mod) - 2 * pow(9, n, mod) + pow(8, n, mod)) % mod)

結果は 6分2秒で AC でした。この問題に 4分17秒かけたことになります。かなり早いんじゃないでしょうか。まあ数学を知っていればこれぐらいでできるのかもしれません。この問題に対しては特に感想はないです。Python は余りの計算も簡単にできて便利ですねというぐらいです。

問題D - Redistribution

3 以上の整数からなる数列のうち、その総和が S であるような数列のパターン数を 10 ^ 9 + 7 で割った余りを答える問題です。

公式の解説では DP による解法が挙げられていましたが、私は数学的に解きました。

まず、数列の項数 n の制限について考えると、n\left\lfloor\frac{S}{3}\right\rfloor 以下であることがわかります。 n\left\lfloor\frac{S}{3}\right\rfloor より大きければ、すべての項が 3 であってもその総和は S を超えてしまうからです。 よって数列の項数 n について 1 から \left\lfloor\frac{S}{3}\right\rfloor まで forループを回し、各 n についてのパターン数を計算して足し合わせていきます。

数列の項数が n のときの求める数列のパターン数は、単純な組み合わせ計算になります。 すべての項は 3 以上なので、残りの S - 3n をどこに振り分けるかを考えます。m = S - 3n とおきます。 この組み合わせ数は m 個のボールを n - 1 個の仕切りで分ける組み合わせと同じで、m + n - 1 個の ボール / 仕切り の候補から n - 1 枚の仕切りの位置を選ぶ組み合わせと同じです。
すなわち  _ {m + n - 1} \mathrm{C} _ {n - 1} です。

数学的にはこれでOKで、次に実装について考えます。こちらも数が非常に大きくなるので 10 ^ 9 + 7 で割ったあまりを答えるのですが、そのまま計算すると時間がかかります。 具体的には、 _ {m + n - 1} \mathrm{C} _ {n - 1} を高速に計算したいです。  _ {m + n - 1} \mathrm{C} _ {n - 1} = \frac{(m + n - 1)!}{m!(n - 1)!} なので、階乗の計算を多数回行うことになり、これをまとめて先に計算しておくと良いです。 割り算もあるので逆元も同時に求めておきます。 これをしておくことで組み合わせ数が O(1) で計算でき、十分高速に解くことができます。

Python での実装例 https://atcoder.jp/contests/abc178/submissions/16703788

def main():
    s = int(input())
    if s < 3:
        print(0)
        return
    mod = 10**9 + 7
    f = [1] * (s + 1)
    for i in range(s):
        f[i + 1] = (f[i] * (i + 1)) % mod
    inv = [0] * (s + 1)
    for i in range(s + 1):
        inv[i] = pow(f[i], mod - 2, mod)
    c = 0
    for n in range(1, s // 3 + 1):
        m = s - 3 * n
        c = (c + (f[m + n - 1] * inv[m] % mod) * inv[n - 1] % mod) % mod
    print(c)

if __name__ == '__main__':
    main()

結果は 49分17秒で AC でした。この問題に 43分15秒かけたことになります。全問題の中で一番時間がかかりました。

私は以前 maspy さんの以下の記事を読んだことがあったので、形式的冪級数を用いた解法で考えていましたが、式変形で詰まっていました。

やはり付け焼き刃の知識を信用して時間を使いすぎるのは良くないなと思い、一から考え直すと上記の方法を思いつきました。助かりました。

ちなみに、形式的冪級数を用いたこの問題の解法は maspy さんが以下の記事で解説されています。読んでおきます。

問題E - Dist Max

二次元平面上にある N 個の点 (x_i,\, y_i) のうち異なる二点間のマンハッタン距離の最大値を求める問題です。

厳密な証明は公式の解説にある通り 45度回転と呼ばれる式変形を用いて行うようですが、コンテスト中は私はそこまでしませんでした。 代わりに以下のようなふわっとした考察を以て解答しました。

1 \le x_i,\, y_i \le 10 ^ 9 という制約より、N 個の点は正方形の領域の中に散らばっているというイメージを持ちます。 すると、その正方形の四隅に最も近い点を選べばいいような気がします。 すなわち、領域の右下に最も近い点と左上に最も近い点の距離か、右上に最も近い点と左下に最も近い点の距離の大きい方が答えであると思いました。
数学的な二次元の直交座標系にあてはめると、左下に最も近い点とは x_i + y_i が最も小さい点であるといえます。
同様に右上に最も近い点とは、左下から最も遠い点ということで、x_i + y_i が最も大きい点となります。
さらに右下に最も近い点は x_i が大きくて y_i が小さいということなので x_i - y_i が最大の点で、同様に左上に最も近い点は x_i - y_i が最小の点です。
最終的に求める答えは x_i + y_i の最大値と最小値の差と x_i - y_i の最大値と最小値の差の大きい方になります。

そうとわかれば、入力を読みながら x_i + y_ix_i - y_i の最大最小を持っておき、最後にその差を計算して大きい方を出力すれば良いです。

Python での実装例 https://atcoder.jp/contests/abc178/submissions/16705230

def main():
    n = int(input())
    s = [0] * n
    d = [0] * n
    for i in range(n):
        x, y = map(int, input().split())
        s[i] = x + y
        d[i] = x - y
    print(max(max(s) - min(s), max(d) - min(d)))

if __name__ == '__main__':
    main()

結果は 53分35秒で AC でした。この問題に 4分18秒しかかかっていないということです。速い!B問題と同じぐらいの時間でできました。
まあもちろんちゃんと証明していないのでペナる可能性はあるなとは思っていましたが、直感を信じて出してよかったです。 証明しようと思うと 5分以上はかかっていたと思うので。
あと実装が凄まじく軽かったのも助かりました。考察のみで解ける問題を直感のみで解いた形ですかね。

問題F - Contrast

長さが N の数列 A,\, B に対して、すべての i について A_i \ne B_i になるように B を自由に並べ替える問題です。

※はじめに断っておきますが、私がこの問題をコンテスト中に解けたのはたまたま運が良かったからだと思います。 考察もかなりいい加減であり、嘘解法かもしれません。

まず、B をうまく並べ替えることで A_i \ne B_i を満たすことができるかを判定する必要があります。
ある値 x について、B に含まれる x の個数が A に含まれる x でないものの個数よりも多い場合、明らかに不可能です。
そうでない場合は必ず可能なのかはコンテスト中に判断できませんでしたが、どうやらそうらしいです4

とにかく条件を満たすような B の並べ替え方が存在すると仮定して、その並べ替え方を探すことを考えたわけですが、AB もソートされているということなので、B をいくつかシフトしたものの中に条件を満たす並べ替えがあるだろうと思いました。
というわけで、B を順番にシフトしつつ、すべての i について A_i \ne B_i となるまで繰り返しました。
ただし、1つずつシフトしていくと最悪のケースで間に合わなかったので、B に含まれる値のうち A に含まれる個数の最大分ずつずらしていくことにしました。(本当は A_i = B_i となっている値の最大個数分ずつシフトしているつもりだったが、そうはなっていないことにコンテスト中は気付いていなかった。テストケースは通ったが、場合によっては間に合わないケースもあるかもしれない。)

この解法は計算量が重く見えますが、numpy の力を借りれば間に合います。A_i = B_i の項があるかの判定は

any(a == b)

を使い、B のシフトは

b = np.role(b, shift)

としました。numpy 便利ですね。

Python での実装例 https://atcoder.jp/contests/abc178/submissions/16757729
上記の通りで、この解法だとケースによっては落ちるかも。

from collections import Counter
import numpy as np

def main():
    n = int(input())
    a = np.array([int(i) for i in input().split()])
    b = np.array([int(i) for i in input().split()])
    ca = Counter(a)
    cb = Counter(b)
    for k in cb.keys():
        if cb[k] > n - ca[k]:
            print("No")
            return
    shift = max(ca[k] for k in cb.keys())
    while any(a == b):
        b = np.roll(b, shift)
    print("Yes")
    print(*b)

if __name__ == '__main__':
    main()

結果は 73分34秒で AC でした。この問題に 19分59秒かけたことになります。早いですね。D問題より早いです。
もちろん証明をちゃんとせず直感で出したためです。立ち回りが上手い。

実はコンテスト中に意図的に 2ペナ出しています。Yes か No かの判定条件が必要十分になっているのか自信がなかったので、そこを確かめるためのコードを書いて提出しました。F問題だしそもそも解けない可能性もあったので、証明時間を省略するためにそのような手段を取りました。
このようなやり方が良しとされるものなのかは分かりませんが、まあプログラミングを使った競技ですしペナルティも受け、そのペナルティに見合ったリターンがあるなと感じたのでそうしました。

条件を満たす並べ替えは B をシフトさせるだけでよい、というところには正直自信はなかったのですが、コード中ですべての i に対して A_i \le B_i であることは確かめているので、答えが出れば AC だということはわかっていました。 その上で、いくつか適当なケースを作って試してみるとそこそこ速く結果が出ていたので、試しに提出してみると AC でした。興奮しました。

まとめ

全体的に運が良かったですねという感じですね。あるいは圧倒的に得意なセットだったか。 少なくとも精進の結果ではないような気がします。
そうだとしても、時間内に正しい結果を導き出せたというのは自分の中に根付いている AtCoder における感覚のようなものがうまく働いたということだと思うので、そこは素直に嬉しいです。

ただし今回の結果は決して実力に伴うものではなく、次回も同じようにいい成績を残せるわけではないということは理解しているので、慢心することなく次もベストを尽くせるように頑張りたいですね。


  1. 個人の感想です。

  2. ここについては公式の解説がとても親切です。

  3. Python の場合。

  4. 公式の解説に証明があります。Hall の結婚定理 などと呼ばれるようです。