Ccmmutty logo
Commutty IT
5 min read

ABC221 茶色コーダーが解けた所まで

https://picsum.photos/seed/af20febf8dd243c19fd73df6849f5f21/600/800

AtCoder Beginner Contest 221

ABC221の問題を、本番で自分が解けた所までの解説です。
レートが74上がって655になりました。
緑まであと150…!年内入緑まで頑張ります…!
自分の中でも中々正確に理解できていない部分を、文字として起こすのは大変難しいですね…。

A - Seismic magnitude scales

n乗する話

  • マグニチュードが1大きくなる度に32倍する
    • マグニチュードの差だけ、32を掛けていくと答え
  • コーナーケースも考える
    • A=Bの時は…?
      • n0=1n^0 = 1となるので、やっぱり差で大丈夫
python
# 入力
a, b = map(int,input().split())

ans = 32**(a-b)

# 出力
print(ans)

B - typo

操作

  • 文字列SSの隣り合う2文字を選び、入れ替える
    • 上記操作を0回、もしくは1回行う
      • 行わない事もある
  • 文字列SSと文字列TTが等しいならYes、そうでないなら、操作を行う

どこで操作を行う?

  • 文字列SSTTを先頭から1文字ずつ見ていき、最初に異なった文字と、その1つ右の文字列で操作を行う
    • 最初に異なった文字が、文字列の一番最後の文字なら操作をするまでもなくNo
    • 操作を行った結果、SSTTが等しいならYes
      • 操作を行った後も、SSTTが等しくないなら、No
python
# 入力
S = input()
T = input()

# SとTが等しいならYes、それ以降の操作は行わない
if S == T:
    print('Yes')
    exit()

# 文字列をリスト化する
s = list(S)
t = list(T)

# 1文字目から見ていく
for i in range(len(S)):
    if S[i] == T[i]:  # もしS、Tのi文字目が等しいなら継続
        continue

    if i == len(S)-1:  # 最初に異なる文字数が文字列の一番最後の文字であるならNo、入れ替える操作は行わずに終了
        print('No')
        exit()
    s[i], s[i+1] = s[i+1], s[i]  # 一文字目が見つかった時点で入れ替え、ループは打ち切り:それ以降の文字は見ないで良い
    break

if s == t:
    # 入れ替えた後のSとTを比較し、一致していればYes、一致していないならばNo
    print('Yes')
else:
    print('No')

C - Select Mul

積の最大値

  • ちっちゃいケースで考える
  • 集合A:{1,4,6,8,14}と、集合B:{3,5,6,8}が存在した時、
    • Aの中から1つ、Bの中から1つ選んでA×BA\times Bを行った時の最大値は?
      • Aの中で一番大きい数字:14と、Bの中で一番大きい数字:8をかけ合わせた値が答え=112
    • 一番大きい数と一番大きい数をかけ合わせたら一番大きくなる!

大きな数の作り方

  • これもちっちゃいケースで考える
  • 文字列:'521357'の順序を並べ替えて、一番大きい数を作ってみよう
    • 左から順に大きい数字を置いていくと、755321
    • これ以上大きい数字は作れないので、これが答え
    • 降順にソートしてあげると一番大きい数ができる!

整数Nを2つの数に分離する分け方:Bit全探索

  • Nの数値が大きい…?
    • 結局桁数毎にグループ分けするので、999999999:9桁で済む
    • Bit全探索が使えそうですね
      • 292^9個の分離で全パターン網羅できるので、間に合いそう
python
# 入力
N = input()  # 今回は文字列で入力
L = list(N)  # 文字列をリスト化

# 最大値を答えとして保存
ans = 0

# 2^(Nの桁数)分ループ
for i in range(2**len(N)):

    # 数値A、数値Bの変数を文字列として用意
    a = ''
    b = ''

    # bit全探索
    for j in range(len(L)):

        # もしbitが1ならaグループに、そうでないならbグループに連結する
        if ((i >> j) & 1):
            a += L[j]
        else:
            b += L[j]

    # もしaグループ、bグループのどちらかが空白ならスキップ
    if len(a) == 0 or len(b) == 0:
        continue

    # a,bをそれぞれリストに直して降順ソート、joinして数値に戻す
    a = list(a)
    a.sort(reverse=True)
    a = int(''.join(a))
    b = list(b)
    b.sort(reverse=True)
    b = int(''.join(b))

    # 積を求めて最大値であれば更新
    tmp = a*b
    ans = max(ans,tmp)

# 出力
print(ans)

D - Online games

1日ずつシミュレーションすると…

  • 最大で10910^9+10910^9の長さの配列が必要
    • もちろんTLEする。さてどうしよう…

ログインしている人数が変化する日を考える

  • Aさんがログインした日、Aさんがログアウトした日
    • Aさんがログインする日より前、Aさんがログアウトした日より後にAさんは居ない
    • Aさんがログインした日〜Aさんがログアウトした日、Aさんは常に居る
  • 人数が変わる日に、何人増えた?何人減った?を記録しておく
  • 日付の順番で以下の処理を行う
    • 答えの配列[今ログインしている人数] += 人数が変動した日 - 前回人数が変動した日
    • 今ログインしている人数 += 変動した人数[人数が変動した日]
    • 前回人数が変動した日 = 人数が変動した日
  • いもす法、座標圧縮の考え方…?であってる、と思われる(自信無い)
python
from collections import Counter

# 入力
N = int(input())

C = Counter()

for i in range(N):
    a, b = map(int, input().split())

    start = a
    end = a + b

    C[start] += 1  # a日目に1人ログイン者が増える
    C[end] -= 1  # a+b日目に、1人ログイン者が減る

days = sorted(C.keys())  # 変動のあった日をリストとして取得
ans = [0] * (N+1)  # 答えを格納するための配列(1-indexにしたいので、N+1)
prev_day = 0  # 前回人数が変動した日を設定
cnt = 0  # ログインしている人数を設定

for curr_day in days:

    # 0人ログインしている日に、「最初人数が変動した日 - 前回人数が変動した日」を足す
    ans[cnt] += curr_day - prev_day
    cnt += C[curr_day]  # ログインしている人数に、「最初人数が変動した日」に何人変動したかを足す
    prev_day = curr_day  # 最初に人数が変動した日を、前回人数が変動した日として保持しておく

# 出力
print(*ans[1:])  # 0人ログインしている日は出力しないので、「1」から。

Discussion

コメントにはログインが必要です。