# AtCoder Beginner Contest 222
https://atcoder.jp/contests/abc222

![](https://cdn.apollon.ai/media/notebox/userimages/79adaa4c-2a37-4045-bd04-89797f412efa.png)

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 \leq N \leq 50$、$1 \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]$:要素iまで確認していて、$C[i]=j$である場合の数
* この時、計算量が$O(NM^2)$となりTLEとなってしまう。

* どこかで計算量改善をしなきゃいけない

## いもす法
* $dp[i][j]$から、$dp[i+1][A[i]:B[i]]$の要素を考える時にいもす法が使えるのでは？
    * $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)

```


AtCoder Beginner Contest 222
https://atcoder.jp/contests/abc222

ABC222の問題を、本番で自分が解けた所＋1問の解説です。  
3完

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

AtCoder Beginner Contest 222

A - Four Digits

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

文法一発ネタ

入力の型を確認する

B - Failing Grade

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

C - Swiss-System Tournament

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

Point1:関数を自作する

ソートに関して

D - Between Two Arrays

愚直にDPしてみると…

いもす法

Discussion

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