LoginSignup
26
12

More than 1 year has passed since last update.

@u2dayo

【AtCoder解説】PythonでABC238のA,B,C,D,E問題を制する！

Last updated at Posted at 2022-02-05

ABC238のA,B,C,D,E問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

  • シンプル：余計なことを考えずに済む
  • 実装が楽：ミスやバグが減ってうれしい
  • 時間がかからない：パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントかツイッター、マシュマロ、Discordサーバーまでお気軽にどうぞ！

Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー（質問や記事の感想・リクエストなどどうぞ！） : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます！

目次

ABC238 まとめ
A問題『Exponential or Quadratic』
B問題『Pizza』
C問題『digitnum』
D問題『AND and SUM』
E問題『Range Sums』

アプリ AtCoderFacts を開発しています

コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。

  • レート別問題正解率
  • パフォーマンス目安
  • 早解きで上昇するパフォーマンス

今後も機能を追加していく予定です。使ってくれると喜びます。

ABC238 まとめ

全提出人数: 9172人

パフォーマンス

パフォ AC 点数 時間 順位(Rated内)
200 A------- 100 8分 6311(6020)位
400 AB------ 300 52分 5107(4818)位
600 AB------ 300 19分 4183(3894)位
800 ABC----- 600 71分 3220(2939)位
1000 AB---F-- 800 75分 2389(2122)位
1200 ABCD---- 1000 72分 1725(1460)位
1400 ABCD---- 1000 43分 1225(962)位
1600 ABCDE--- 1500 97分 843(597)位
1800 ABCDE--- 1500 61分 571(341)位
2000 ABCD--G- 1600 108分 364(178)位
2200 ABCDEF-- 2000 64分 229(89)位
2400 ABCDEFG- 2600 111分 138(44)位

色別の正解率

色 人数 A B C D E F G Ex
灰 3161 92.2 % 54.4 % 15.9 % 5.7 % 0.3 % 0.0 % 0.1 % 0.0 %
茶 1489 98.1 % 84.3 % 59.3 % 26.8 % 2.1 % 0.1 % 0.1 % 0.0 %
緑 1102 97.1 % 89.8 % 80.6 % 64.6 % 10.2 % 1.6 % 0.9 % 0.0 %
水 705 97.6 % 95.2 % 91.3 % 90.6 % 36.9 % 5.7 % 2.8 % 0.0 %
青 396 95.7 % 95.0 % 95.5 % 94.4 % 73.5 % 30.3 % 14.7 % 0.2 %
黄 226 87.6 % 85.0 % 85.0 % 86.7 % 81.4 % 53.1 % 35.8 % 1.3 %
橙 48 95.8 % 89.6 % 89.6 % 89.6 % 95.8 % 85.4 % 70.8 % 2.1 %
赤 23 95.7 % 95.7 % 95.7 % 95.7 % 91.3 % 95.7 % 87.0 % 30.4 %

※表示レート、灰に初参加者は含めず

A問題『Exponential or Quadratic』

問題ページ：A - Exponential or Quadratic
灰コーダー正解率：92.2 %
茶コーダー正解率：98.1 %
緑コーダー正解率：97.1 %

入力

$n$ : $1$ 以上 $10^9$ 以下の整数

考察

一見そのまま判定すればよさそうですが、 $2^n$ は最大 $3$ 億桁ほどの巨大な数になりうるため、Pythonで提出するとTLEになります。（PyPyだとそのまま判定して通ります）

Pythonや他の言語では、直接計算せずに判定する必要があります。

正攻法

$n=1$ のとき、$2^1>1^2$ より Yes です。$n=2$ のとき、$2^2=2^2$ より No です。$n=3$ のとき、$2^3<3^2$ より No です。

$n\ge{3}$ のとき、$n$ を $1$ 増やしたときの増加量は $2^n$ のほうが常に大きいので、ある $k$ で $2^k\gt{k^2}$ であれば、それより大きい $k$ でもすべて $2^k\gt{k^2}$ です。

$n=4$ のとき、$2^4=4^2$ より No、$n=5$ のとき、$2^5\gt5^2$ よりYesです。つまり、$n=5$ 以上はすべてYesです。

以上より、Noとなるのは $n=2,3,4$ の場合のみです。

雑な方法

Microsoftの数式ソルバーや、Wolfram Alphaを使って、 $f(x)=2^x-x^2$ のグラフを書きます。

$f(x)\gt0$ ならば $2^x$ のほうが $x^2$ より大きいので Yes で、$f(x)\le0$ ならば No です。

グラフを見ると、およそ $10$ より大きな $x$ では、$2^x$ のほうが $x^2$ より圧倒的に大きいことがわかります。

$n=10$ くらいまでは実際に計算して判定し、$n>10$ ならば Yesを出力すればいいです。

PyPyの場合

$2^n$ はおよそ $3$ 億桁ほどの巨大な数になる場合があるので、Pythonではそのまま判定するとTLEになりますが、PyPyを使えば通ります。

コード

正攻法

N = int(input())
print("No" if 2 <= N <= 4 else "Yes")

雑な方法

N = int(input())
if N <= 10:
    print("Yes" if 2 ** N > N ** 2 else "No")
else:
    print("Yes")

PyPyの場合

N = int(input())
print("Yes" if 2 ** N > N ** 2 else "No")

B問題『Pizza』

問題ページ：B - Pizza
灰コーダー正解率：54.4 %
茶コーダー正解率：84.3 %
緑コーダー正解率：89.8 %

入力

$N$ : 操作の回数
$A_i$ : $i$ 回目の操作では、ピザを $A_i$ 度回転させてから切れ込みを入れる

  • 同じ場所に複数回切れ込みを入れることはない

考察

※コードは10行程度なので、コードを読んだほうがわかりやすいかもしれません

$12$ 時の位置を基準の $0$ 度とします。

切れ込みの位置

各切れ込みの $0$ 度を基準とした角度は、操作をシミュレートすれば求めることができます。

具体的には、$i$ 回目の操作で切れ込みを $D$ 度に入れたとき、$i+1$ 本目の操作では切れ込みを $D+A_i$ 度に入れます。ただし、角度は $360$ 度で割ったあまりを実際の角度とします。これは、$360$ 度でピザが $1$ 周して元の位置に戻ってくるからです。例えば、$180$ 度と $480$ 度は同じ角度を表します。

なお、$i=0$ のときは $D=0$ とします。

つまり、以下のようなコードで切れ込みの角度がすべてわかります。

B = [0]  # 最初は0度
D = 0
for x in A:
    D += x
    D %= 360
    B.append(D)

切れ込みの位置から答えを求める

切れ込みの位置がすべてわかったところで、そこから答えを求めます。

$0$ 度の位置の $1$ 本と、操作による $N$ 本の、$N+1$ 本の切れ込みが入ったピザは $N+1$ ピースに分けられます。各ピースの中心角は、$(今の切れ込みの角度)-(前の切れ込みの角度)$ で求められます。すべてのピースの中心角を計算して、最大の値を求めればいいです。

今の切れ込みの角度、前の切れ込みの角度を求めるために、切れ込みの位置をソートします。そうすると、B[i+1]-B[i] で各ピースの角度を求めることができます。

なお、最後の切れ込みは最初の切れ込みとペアになります。$0$ 度の切れ込みに加えて、$360$ 度の切れ込みもあることにすると実装が楽です。

まとめ

まとめると、この問題は以下の手順で解くことができます。

  1. 切れ込みの位置を保存する配列 $B$ を作る
  2. $B$ に $0$ と $360$ を追加する（最初から入っている、$12$時の位置の切れ込みです）
  3. 操作をシミュレートして、 $N$ 本の切れ込みの角度を $B$ に追加する
  4. $B$ をソートする
  5. $N+1$ ピースのピザの中心角を計算し、最大値を出力する

コード

N = int(input())
A = list(map(int, input().split()))
B = [0, 360]

curr = 0
for x in A:
    curr += x
    curr %= 360
    B.append(curr)
B.sort()

C = [B[i + 1] - B[i] for i in range(len(B) - 1)]
print(max(C))

C問題『digitnum』

問題ページ：C - digitnum
灰コーダー正解率：15.9 %
茶コーダー正解率：59.3 %
緑コーダー正解率：80.6 %

入力

$N$ : $1$ 以上 $10^{18}$ 以下の整数

考察

桁数が同じ整数をまとめて考えます。例えば $N=16$の答えは

$f(1)+f(2)+\dots+f(9)+f(10)+f(11)+\dots+f(16)=(1+2+\dots+9)+(1+2+\dots+7)=45+28=73$

となります。桁数ごとにまとめた()内が $1,2,3,\dots$ と、$1$ から $k$ までの総和になっていることに注目してください。

$1$ から $x$ までの総和を $g(x)=\frac{x(x+1)}{2}$ とします。ちょうど $i$ 桁で、しかも $N$ 以下である整数の数を $k_i$ とします。$N$ の桁数を $L$ とすると、答えは $g(k_1)+g(k_2)+\dots+g(k_{L})$ です。

ちょうどi桁で、N以下の整数の数を求める

$k_i$ を求めます。$d(j)$ を $j$ 桁以下の整数の数とすると、$k_i=\min(N,d(i))-d(i-1)$ です。

例えば、$N=10^{15}$ のとき、$k_4=\min(10^{15},9999)-999=9999-999=9000$ です。$4$桁の整数 $1000$ ～ $9999$ は $9000$ 個あるという意味です。

$N=1234$ のとき、$k_4=\min(1234,9999)-999=235$ です。$1000$ ～ $1234$ の整数は $235$ 個あるという意味です。

$d(j)=10^j-1$ です。例えば、$d(1)=10-1=9,d(2)=100-1=99$ です。

以上より、$k_i=\min(N,10^i-1)-(10^{i-1}-1)$ です。各 $k_i$ について、$1$ から $k_i$ までの総和を求めて、足した値が答えです。

コード

MOD = 998244353


def g(x):
    # 1+2+...+xを求める
    return x * (x + 1) // 2


def solve():
    N = int(input())
    L = len(str(N))
    ans = 0
    for i in range(1, L + 1):
        k = min(N, 10 ** i - 1) - (10 ** (i - 1) - 1)
        ans += g(k)
        ans %= MOD
    return ans


print(solve())

D問題『AND and SUM』

問題ページ：D - AND and SUM
灰コーダー正解率：5.7 %
茶コーダー正解率：26.8 %
緑コーダー正解率：64.6 %

入力

$T$ : テストケースの数
$a,s$ : $x\ AND\ y=a$, $x+y=s$ となる $(x,y)$ の組が存在するか判定する

考察

bit演算のANDが出てくるので、$a,s,x,y$ を $2$ 進数表記したときの桁ごとに考えます。

$a$ が $1$ である桁は、$x,y$ どちらも $1$ にしなければいけません。$a$ が $0$ である桁は、$x,y$ 両方を $1$ にしてはいけません。

先に、 $a$ が $1$ の桁と同じ桁の $x,y$ をどちらも $1$ に確定させます。すると、$s=x+y=(a+x')+(a+y')$ と表されます。ただし、$x',y'$ は以下の $2$ つの条件を満たす必要があります。そうでなければ、ANDの条件を満たせないからです。

  • *$x',y'$ 両方が $1$ の桁はない（どちらも $1$ だと、ANDを取って $1$ になるため） *
  • $a$ が $1$ である桁は、 $x',y'$ の両方が $0$ （繰り上がってその桁のANDが0になってしまうため 上の条件より、下の桁からの繰り上がりも許さない）

移項すると、$s-2a=x'+y'$ となります。 $s-2a=s'$ とすると、$s'=x'+y'$ です。明らかに、$s'<0$ であれば Noです。

$s'\ge0$ の場合を考えます。$s'$ が $0$ の桁は、$x',y'$ ともに $0$ にすればいいです。$s'$ が $1$ で、 $a$ が $0$ の桁は、$x'$ か $y'$ の片方を $1$ にすればいいです。

$s'$ が $1$ で、 $a$ が $1$ の桁は、『$a$ が $1$ である桁は $x',y'$ ともに $0$』 の条件を満たしながら $s'$ のその桁を $1$ にすることができないので、条件を満たす $x',y'$ は存在しません。

以上より、『$s-2a\ge0$』 かつ『$s'=s-2a$ と $a$ がともに $1$ である桁が存在しない』ならYesで、そうでなければNoです。後者の条件は、$(s-2a)\ AND\ a=0$ と表すことができます。（forループで $1$ 桁ずつ判定してもいいです）

コード

def solve():
    A, S = map(int, input().split())
    T = S - 2 * A
    if T < 0:
        return False
    return T & A == 0  # forループで1桁ずつ判定してもいいです


T = int(input())
for _ in range(T):
    print("Yes" if solve() else "No")

E問題『Range Sums』

問題ページ：E - Range Sums
灰コーダー正解率：0.3 %
茶コーダー正解率：2.1 %
緑コーダー正解率：10.2 %

入力

$N$ : 整数列の長さ
$Q$ : 与えられる情報の数
$l_i,r_i$ : $i$ 番目の情報は、$a_{l_i}+a_{l_i+1}+\dots+a_{r_i}$ の値が与えられる

考察

$b_i=a_1+a_2+\dots+a_i$ 、つまり $a$ の第 $1$ 項からの累積和とします。ただし、$b_0=0$ とします。$a$ に含まれる全要素の総和は、$b_N=a_1+a_2+\dots+a_N$ です。$b_0=0$ であることと、与えられる $Q$ 個の情報を使って、$b_N$ の値を特定できるか判定すればいいです。

さて、与えられる情報は、 $b_{r_i}-b_{l_i-1}$ の値が与えられると言い換えることができます。（累積和で $a_l+a_{l+1}+\dots+a_r$ を求めるときの操作です）

この情報を使うと、以下の $2$​ つのことがいえます。$S = b_{r_i}-b_{l_{i-1}}$ とすると、$b_{r_i}=S+b_{l_{i-1}}$, $b_{l_{i-1}}=b_{r_i}-S$ だからです。

  • $b_{r_i}$ がわかれば、$b_{l_i-1}$ がわかる
  • $b_{l_i-1}$ がわかれば、$b_{r_i}$ がわかる

N+1頂点のUnionFindを使います。$i$ 番目の情報では、頂点 $l_i-1$と頂点 $r_i$ を連結します。

最終的に頂点 $0$ と頂点 $N$ が連結であれば、$b_0$ からたどって $b_N$ の値を特定できるので Yesで、そうでなければNoです。

コード

from typing import List


class UnionFind:
    """0-indexed"""

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n
        self.__group_count = n

    def unite(self, x, y):
        """xとyをマージ"""
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return False

        self.__group_count -= 1

        if self.parent[x] > self.parent[y]:
            x, y = y, x

        self.parent[x] += self.parent[y]
        self.parent[y] = x

        return True

    def is_same(self, x, y):
        """xとyが同じ連結成分か判定"""
        return self.root(x) == self.root(y)

    def root(self, x):
        """xの根を取得"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def size(self, x):
        """xが属する連結成分のサイズを取得"""
        return -self.parent[self.root(x)]

    def all_sizes(self) -> List[int]:
        """全連結成分のサイズのリストを取得 O(N)"""
        sizes = []
        for i in range(self.n):
            size = self.parent[i]
            if size < 0:
                sizes.append(-size)
        return sizes

    def groups(self) -> List[List[int]]:
        """全連結成分の内容のリストを取得 O(N・α(N))"""
        groups = dict()
        for i in range(self.n):
            p = self.root(i)
            if not groups.get(p):
                groups[p] = []
            groups[p].append(i)
        return list(groups.values())

    @property
    def group_count(self) -> int:
        """連結成分の数を取得 O(1)"""
        return self.__group_count


def solve():
    N, Q = map(int, input().split())
    uf = UnionFind(N + 1)
    for _ in range(Q):
        a, b = map(int, input().split())
        uf.unite(a - 1, b)
    return uf.is_same(0, N)


print("Yes" if solve() else "No")
26
12
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
26
12