ABCのA-D問題の解説。

目次

A - Seismic magnitude scales
B - typo
C - Select Mul
D - Online games

A - Seismic magnitude scales

解説

マグニチュードAの地震のエネルギーの大きさはマグニチュードBの自身のエネルギーの大きさの何倍かを求める問題。

このときAはB以上であることがわかっているので、AからBを引いてあげた値分、32倍してあげるとよい。

コード

def main():
    a, b = map(int, input().split())

    print(32**(a-b))

if __name__ == '__main__':
    main()

B - typo

解説

文字列SとTが与えられ、Sの隣り合う2文字を入れ替える操作を1回以下行うことで、Tと一致するか求める問題。

まず、そもそもS == Tであれば、入れ替える必要がないため、この時点で答えはYesとなる。

次に、入れ替える操作であるが、連続する2文字をいれかえればいいだけなので、S[i], S[i+1] = S[i+1], S[i]とし、値を入れ替えて判定する。SとTが合わなければ、また文字列をもとに戻し、文字列の長さまでこの操作を繰り返す。

コード

def main():
    S = list(input())
    T = list(input())

    ans = 'No'

    if S == T:
        ans = 'Yes'

    for i in range(len(S)-1):
        S[i], S[i+1] = S[i+1], S[i]
        if S == T:
            ans = 'Yes'
        S[i], S[i+1] = S[i+1], S[i]

    print(ans)

if __name__ == '__main__':
    main()

C - Select Mul

解説

入力した数字の文字列の中から、値を2つにわけ、その積の最大値を求める問題。

まず、積の最大値を求めたいので、入力した数字を降順に並び替える。さらに、積の最大値をとるためには、それぞれの桁数を最大にする必要がある。例えば、$1234$という数字があれば、$1 \times 234$よりも$12 \times 34$のほうが大きいことから明白である。

したがって、先程降順にソートした数字を1つずつ順番に、新たに2つの数字として振り分ける。

振り分けられた2つ数字の積では、まだ最大値とはえいえない。このとき桁数の少ない方の数字をできるだけ最大化してあげることで、積の最大値を求めることができる。つまり、2つの数字を桁数が高い方から順番に見ていき、その桁の値が異なる場合、値を入れ替えてあげることで、積の最大値となる2つの数字を求めることができる。

コード1（for）

def main():
    n = input()
    nsort = sorted(n, reverse=True) # 降順に並び替え

    a = nsort[0::2] # インデックス0から1つ飛ばしでリストわけ
    b = nsort[1::2] # インデックス1から1つ飛ばしでリストわけ
    
    for i in range(min(len(a), len(b))):
        if a[i] != b[i]:
            a[i], b[i] = b[i], a[i]
            break

    print(int(''.join(a)) * int(''.join(b)))

if __name__ == '__main__':
    main()

コード2（bit全探索）

def main():
    n = input()
    nsort = sorted(n, reverse=True)

    ans = 0

    for i in range(1 << len(nsort)):
        l = 0
        r = 0
        for j in range(len(nsort)):
            if i & (1 << j):
                l = l * 10 + ord(nsort[j]) - ord('0')
            else:
                r = r * 10 + ord(nsort[j]) - ord('0')

        ans = max(ans, l * r)

    print(ans)

if __name__ == '__main__':
    main()

D - Online games

解説

i番目のプレイヤーは、$A_i$日目から$B_i$日間連続でログインしている。このとき、1日目からN日目までのなかで、ちょうどk人がログインしていた日数を求める問題。

これは、ログインした日とログアウトした日に注目すると問題がとける。

まず、入力値であるaとbについて、i番目の人がログインした日を$a$で日数を+1、ログアウトした日を$a+b$で日数を-1とし、タプルとして管理する。

これら入力した値を昇順にソートしてあげることで、ログイン・ログアウトの情報が日付順になっているため、一つの配列で管理することができる。

この配列内のタプルを前から一つずつ見ていく。

まず、その日は、ログインしたのか、ログアウトしたのかを確認する。つまり、配列内のタプルの2番目の要素が+1か-1かを考える。これをある変数（cnt）で管理してあげることで、その日は何人がログインしているかを把握することができる。

このcntは、次の日、つまり、配列内の次のタプルの1番目の値までの日数続くので、差分を計算して、事前に用意しておいた各日の人数を保存する配列ansのcnt番目に値をいれてあげるとよい。このときansは、Nの最大値である、$2 \times 10 ^ 5$よりも多く要素を準備しておく。

これで求めたansを1人からn人まで分出力するとAC。

コード

def main():
    n = int(input())
    x = []
    temp = 200010

    for _ in range(n):
        a, b = map(int, input().split())
        x.append((a, 1))
        x.append((a+b, -1))

    xsort = sorted(x)

    cnt = 0
    ans = [0 for _ in range(temp)]

    for i in range(len(xsort)-1):
        cnt += xsort[i][1]  # cnt人がログイン
        ans[cnt] += xsort[i+1][0] - xsort[i][0]

    ans = ans[1:n+1]  # 1人からn人までの答えを出力
    print(*ans)


if __name__ == '__main__':
    main()

編集後記

復習サボったらいけないですね...。