Ccmmutty logo
Commutty IT
・5 min read

ABC222 茶色コーダーが解けた所まで＋あと1問

AtCoder競技プログラミングアルゴリズム
https://picsum.photos/seed/90d0f2d663884404b8828b9dc4788a6a/600/800

AtCoder Beginner Contest 222

https://atcoder.jp/contests/abc222
ABC222の問題を、本番で自分が解けた所＋1問の解説です。
3完だったり、操作ミスでB問題にA問題のソース提出してREだったり、と散々でした…。
一応ギリギリHighestは+6で微増…しょっぱーい。
次は甘えずちゃんと4完…！

A - Four Digits

Difficulty: 5
https://atcoder.jp/contests/abc218/tasks/abc218_a

文字列としての長さを見る

  • len(S)で長さを測って、足りない分の0を補完する

文法一発ネタ

  • S.zfill(n)で、n桁の数値にしてくれる（右詰め、0埋め）
    • 今回は4桁なのでn = 4

入力の型を確認する

  • 最初からNをstrで入力させるとその後楽ですね
    • 脳死でintで入力させるのはよくない。つい手癖でint(input())してしまうの反省。
python
# 入力
N = input()

# 出力
print(N.zfill(4))

B - Failing Grade

Difficulty: 9
https://atcoder.jp/contests/abc222/tasks/abc222_b

愚直にループで1つずつ確認

  • forループで配列内要素を順に見ていく。条件以上であればカウント。
    • 内包表記で一括に書けると格好いいですね。
    • 可読性考えると愚直ループでも問題無い、かも、しれない。
python
# 愚直ループの例
# 入力
N, P = map(int, input().split())
A = list(map(int, input().split()))

# 変数初期化
ans = 0

# 愚直ループ
for i in A:
    # もし点数がP以下なら、答えに+1加算
    if i < P:
        ans += 1

# 出力
print(ans)
python
# 格好良く書いてみた例
# 入力
N, P = map(int, input().split())
A = list(map(int, input().split()))

# 一発出力
print(sum(i<P for i in A))

C - Swiss-System Tournament

Difficulty: 367
https://atcoder.jp/contests/abc222/tasks/abc222_c

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

  • 1≤N≤501 \leq N \leq 50、1≤M≤1001 \leq M \leq 100で制約小さいので、愚直に実装する方向。

Point1:関数を自作する

  • じゃんけんの結果を求める部分は関数として分けとこうね
  • ソースごちゃごちゃしちゃうからね
  • 2人の手を引数として与えると、どっちが勝ったか教えてくれる関数
    • Point2:2人の関数を文字列として「'GP'」みたいな引数1つにすると判定楽かも（スタイリッシュ？）
    • Point3:返り値を決める時にちょっと悩んで実装すると、後々のコードが楽になる
      • これ本番で悩む余裕は個人的にはまだ無さそう…実力が足りない。

ソートに関して

  • 2次元配列のソートはlambda式とか、色々手法がある。
  • 個人的には-1を掛けるのが楽かな、と思う
    • 勝数も選手番号も、小さい順にソートしたい
      • 勝ち数はみんな0からスタート
      • 1回かつ毎に「-1」してあげる
      • 3回勝ったら「-3」
python
# 入力部
N, M = map(int, input().split())
L = [] # L[選手番号][文字列(出した手一覧)]

# ソートの都合上、勝数はマイナスで扱う。
rank = [] # rank[i] = [x,y]：i位の人は、-x勝で選手番号y
for i in range(2*N):
    L.append(input())
    rank.append([0, i]) # 最初はみんな0勝 


# Point1:勝敗関数。両者の手を併せたものを2文字の文字列として引数にする
def judge(hands):
    if hands[0] == hands[1]: # あいこ
        return -1 # Point3
    if hands in ['GC', 'CP', 'PG']: # Point2:左側の手が勝った場合
        return 0 # Point3
    return 1  # Point3 その他＝右側の手が勝った場合


# シミュレーション
# ラウンドを進める
for round in range(M):
    # 勝数が多い人から順に見ていく。2人で戦わせるので、step2
    for i in range(0, 2*N, 2):

        playerA = rank[i][1]
        A_hand = L[playerA][round]
        playerB = rank[i+1][1]
        B_hand = L[playerB][round]

        # 勝敗判定
        result = judge(A_hand+B_hand)

        # もしあいこでは無かった場合、
        if result != -1:
            # 左側の手が勝った＝選手番号2Nの人が勝った。右側の人が勝った＝選手番号2N+1の人が勝った。
            # Point3：i+resultで勝った人に勝数を与える。
            rank[i+result][0] -= 1

    # 勝敗順にソートする。勝敗数が一緒であれば、選手番号が小さい順に並ぶ。
    rank.sort()

# 0-indexなので、選手番号に変換して出力
for _, i in rank:
    print(i+1)

D - Between Two Arrays

Difficulty: 865
https://atcoder.jp/contests/abc222/tasks/abc222_d

愚直にDPしてみると…

  • dp[i][j]dp[i][j]:要素iまで確認していて、C[i]=jC[i]=jである場合の数
  • この時、計算量がO(NM2)O(NM^2)となりTLEとなってしまう。
  • どこかで計算量改善をしなきゃいけない

いもす法

  • dp[i][j]dp[i][j]から、dp[i+1][A[i]:B[i]]dp[i+1][A[i]:B[i]]の要素を考える時にいもす法が使えるのでは？
    • dp[i+1]dp[i+1]行を、いもす法で一括計算すると割と余裕でAC
    • 計算量等の詳細な考察までは自分のちからが及ばず…。
    • これは時間内に解きたかった…！
python
# 入力
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 変数設定
mod = 998244353
M = 3001
dp = [[0]*(M+1) for i in range(N+1)]
# 便宜的に0,0を1に初期化する
dp[0][0] = 1

# ループ開始。A,Bのi要素目から一つずつ見ていくよ。
# 配るDPで考える。
for i in range(N):
    a = A[i]
    b = B[i]

    # dp内側のループ
    for j in range(M):
        now_cnt = dp[i][j]

        # もし0ならスキップ
        if now_cnt == 0:
            continue

        # ここからいもす法
        # 左側（プラス箇所）は、A[i]とjのうち大きい方
        left = max(a, j)
        right = b+1

        dp[i+1][left] += now_cnt
        dp[i+1][right] -= now_cnt

    # いもす法を累積和で整理。割った余りにしておく
    for j in range(1, M+1):
        dp[i+1][j] = (dp[i+1][j] + dp[i+1][j-1]) % mod

# 最終列の和を割った余り
print(sum(dp[-1]) % mod)

Discussion

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