Magicode logo
Magicode
6 min read

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

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

AtCoder Beginner Contest 223

ABC223の問題を、本番で自分が解けた所までの解説です。
602 → 677 (+75)
4完に戻りました…!!!
+75は大きい。過去最大パフォ。
(昨日のARCで0完やらかしてなければ今頃730位あったんですけどね…)
来週のARC129/ABC223で緑パフォが出せたら、3ヶ月入緑の可能性もまだあります…!
追記: ARC129が無くなったため、3ヶ月で入緑の可能性がほぼほぼなくなりました…。
3ヶ月ちょっとでの入緑を目指します…。

A - Exact Price

条件から、あり得る状態とありえない状態

  • 100円硬貨が1枚以上入っている
    • 高橋くんの財布の中身が一番少ない状態でも100円はあるよね
      • 100円未満(99円以下)の状態はありえないね
  • 100円硬貨以外は何も入っていない
    • 100円、200円、300円………N×100N \times 100円なら、あり得る状態だね

何を聞かれてる?

財布の中の合計金額がX円である可能性はありますか?
  • X円が、上記の「あり得る状態」であるかをif文で判定すればOK
python
# 入力
X = int(input())

# もし100円未満なら「あり得ない状態」
if X < 100:
    print('No')
else:  # X:100円未満ではない
    if X % 100 == 0:  # もしXが100の倍数であるなら、あり得る状態
        print('Yes')
    else:  # 100の倍数ではないなら、あり得ない状態
        print('No')

B - String Shifting

左シフトと右シフトについて

  • abcdeを左シフトしていくと、
    • abcdebcdeacdeabdeabceabcdabcde→以下ループ
  • 逆に、abcdeを右シフトしていくと、
    • abcdeeabcddeabccdeabbcdeaabcde→以下ループ
  • 以上の観察を踏まえると、以下の事が分かる
    • 文字列の長さ回数でループしてる(右シフト5回で最初に戻る)
    • 右シフト、左シフトどちら向きに動かしても順番が変わるだけで、成立する文字列は一緒

条件を確認する

  • 文字列の長さは最大1000文字
    • 最大1000回シフトして、全部一覧にしてあげてソートしたら最小(辞書順最小)、最大(辞書順最大)が出てくるね
      • 0回シフトと1000回シフトは同じ文字列が出てくるので、999回(=N-1回)のシフトで良いね。
python
# 入力
S = input()

# 変数準備
N = len(S)  # 文字列の長さ:ループ回数に使用するよ
L = []  # リスト:シフト操作を行ってできた文字列を確保していくよ

# シフト操作ループ
for i in range(N):

    # シフト操作部
    left_S = S[:i]  # i回左シフト操作を行う時、先頭から末尾へ送られる文字列:先頭からi文字目まで
    right_S = S[i:]  # i回左シフト操作を行う時、動かない文字列:i文字目から末尾まで

    new_S = right_S + left_S  # 先頭からi文字目までを、末尾に移動

    L.append(new_S)  # シフト操作を行った後の文字列をリストに確保

print(min(L))  # 辞書順最小値:文字列でもminが使える
print(max(L))  # 辞書順最大値:文字列でもmaxが使える

C - Doukasen

実装面倒くさい系シミュレーション

  • 前回のABCもシミュレーション系の実装だったような…?
  • 導火線の両端に火をつけて、2つの火がぶつかるまでの時間=「導火線の片方に火をつけて、全部燃え尽きるまでの時間」の半分
    • 初手で全部燃え尽きるまでの時間を記録しておくと楽ですね
python
# 入力部
N = int(input())
L = []

sum_sec = 0  # 左端に火をつけて、この導火線が燃え尽きるまでにかかる時間

for i in range(N):
    a, b = map(int, input().split())
    L.append([a, b, a/b])  # a/b:この導火線が燃え尽きるまでにかかる時間。距離/速さ
    sum_sec += a/b

time_limit = sum_sec/2  # 左端、右端につけた火が中央でぶつかる時間:残り時間
left_length = 0  # 左端からの長さを測るよ

for a, b, c in L:  # 左端の導火線から1本ずつ測定
    if time_limit > c:  # もし、残り時間よりも、導火線が燃え尽きる時間が短い場合
        # i本目の導火線が燃え尽きた認定:左端からの長さを確保、残り時間から導火線が燃え尽きるまでの時間を引く
        time_limit -= c
        left_length += a

    else:  # もし、残り時間よりも、導火線が燃え尽きるまでの時間が長い場合:その導火線の途中に答えがある
        left_length += (a/c)*time_limit  # (導火線の長さ/導火線が燃える速さ)*残り時間
        print(left_length)
        exit()

D - Restricted Permutation

解説したくない…WAKARANAI…

  • 公式(想定解)は、有向グラフに見立てて、トポロジカルソートした結果として辞書順最小のものが答え
    • 辞書順最小のものに関する問題は、heapqが優秀。全部出して全部入れてもO(NlogN)O(N\log N)
      • 計算量周りの考えは自信がないです…

公式の条件を言い換えてみる

  • AiA_iBiB_iよりも先に現れる
    • 数列において、BiB_iが出てこないとAiA_iが出せない

実装どうしよう…

* heapqで辞書順最小の配列を作る
    * heappopで最小値が出てくる便利
* dictを2種類使って、heapqに追加できる数字、出来ない数字を管理する
    * lock_d_a:キーに数字を入れると、「その数字を使うには、使ってないといけない数字」の一覧(set)
    * lock_d_b:キーに数字を入れると、「その数字を使用すると、使えることに成る数字」の一覧(set)
python
from collections import defaultdict
import heapq

# 入力1
N, M = map(int, input().split())

# 変数設定
lock_d_a = defaultdict(set)  # キーに数字を入れると、「その数字を使うには、使ってないといけない数字」の一覧(set)
lock_d_b = defaultdict(set)  # キーに数字を入れると、「その数字を使用すると、使えることになる可能性のある数字」の一覧(set)
cant_s = set()  # 使えない数字一覧
all_s = set(range(1, N+1))  # 1~Nまでのset
ans = []  # 答えを確保するための配列

# 入力2
for i in range(M):
    a, b = map(int, input().split())
    cant_s.add(b)  # 使えない数字一覧にbを追加
    lock_d_a[b].add(a)  # lock_d_a/lock_d_bにa,bの組み合わせを追加
    lock_d_b[a].add(b)

can_s = all_s - cant_s  # 使える数字=全体集合 - 使えない数字一覧
can_l = list(can_s)  # 使える数字をリストに戻して
heapq.heapify(can_l)  # heapqで小さい順に出す


# 数列Pの長さがNなので、N回処理していくよ
for i in range(N):

    # もし、使える数字が存在しない場合、そこで強制終了
    if len(can_l) == 0:
        print(-1)
        exit()

    # heapqから最小値(=現在使える数字の中で一番小さい数字)を答えの配列に追加
    lower = heapq.heappop(can_l)
    ans.append(lower)

    # 今答えに入れた数字をキーに、「その数字を使用すると使えることになる可能性のある数字」一覧を取得
    for i in lock_d_b[lower]:

        # もし、「使えることに成る可能性のある数字」を使うには、使ってないといけない数字が1つなら、たった今その数字は使えることに成るのでheapqに追加
        if len(lock_d_a[i]) == 1:
            heapq.heappush(can_l, i)
            # 使ってないといけない数字一覧から削除
            del lock_d_a[i]
        else:
            # 2個以上であれば、「その数字を使うために使ってないといけない数字一覧」から、最小値:lowerを削除
            lock_d_a[i].discard(lower)

# 出力部
print(*ans)

Discussion

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