Ccmmutty logo
Commutty IT
0 pv5 min read

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

https://picsum.photos/seed/6b0f2d1852ef43c1bf621de041f24d41/1200/630

AtCoder Beginner Contest 220

ABC219の問題を、本番で自分が解けた所までの解説です。
無事レート微増。 このペースをちゃんと維持できれば、年内800=入緑はなんとか達成できそうです。

A - Find Multiple

数学的解決法(想定解)

  • X=B//CX = B//C (Bを割ってあまりを捨てた値)
  • Y=X×CY = X\times C
    • この時点でのY:B以下で一番大きいCの倍数
      • YがA以上であれば、答え:Yとして出力
      • YがA未満であれば、答え:-1として出力
python
# 入力
A, B, C = map(int, input().split())

# X,Yを計算
X = B//C
Y = X*C

# YとAの関係によって条件分岐
if A <= Y:
    print(Y)
else:
    print(-1)

ループによる力技

  • Cの倍数を1つずつ順に呼び出していく
    • もし呼び出した倍数が、A以上B以下である場合、それが答え
    • もし呼び出した倍数が、Bを超えた場合、ループを終了する
python
# before
A,B,C = map(int,input().split()) 

for i in range(1,1005):
    check_num = i*C
    if A<=check_num<=B:
        print(check_num)
        exit()
 
print(-1)
python
# after
# 入力
A, B, C = map(int, input().split())

# ループ回数について
    # range(1000)で止めてしまうと、
    # A=1000,B=1000,C=1の時にWAが存在する
    # そもそもあまり大きい数ではないため、ちょっとだけマージンを持たせました
    # B回のループでも問題無い気はしますね
# ループのstartについて
    # 0倍=0を判定したとしても、
    # 制約よりAは1以上なので、そこで終わることはないから問題無いですね

for i in range(1005): 
    check_num = i*C #Cの倍数を生成
    
    if A <= check_num <= B: # もし、Cの倍数がA以上B以下であるなら、
        print(check_num) # 出力して
        exit() # 終了

print(-1)

B - Base K

n進数表記で書かれた文字列Sを、10進数表記で表すには…

  • ans=0とする
  • Sの先頭の桁から見ていき、順番に以下の操作を行う
    1. ansをn倍する
    2. ansに今見ている桁の数字を加える
  • Sの最後の桁まで見終わった時、ansが求めたい値になる
  • 具体例として、
  • 5進数で書かれた'123'を、10進数表記で表したい
    • ans=0と置く
      • 1桁目を見る=1
        • ansを5倍する→ans=0
        • ansに今見ている桁の数字を加える→ans=1
      • 2桁目を見る=2
        • ansを5倍する→ans=5
        • ansに今見ている桁の数字を加える→ans=7
      • 3桁目を見る=3
        • ansを5倍する→ans=35
        • ansに今見ている桁の数字を加える→ans=38
  • 「n進数 変換」などで検索して、ツールで確認してみると確かに正しい。
  • 後は入力A、Bを、K進数から10進数表記に戻して、積を求めると答えになる
python
# 入力
K = int(input())
A, B = map(int, input().split())

# 10進数への変換を行う関数を作成
def base10(x,K):
    S = str(x) # Lを文字列に変換

    ans = 0 # ans初期値
    for i in S: # 1桁目から確認していく
        ans *= K # ansをK倍する
        ans += int(i) # ansにiを加える
    return ans

ans = base10(A,K) * base10(B,K) # A,BをK進数から10進数表記にしたものの積が答え
print(ans) # 出力

Python限定?裏技解法:int関数

python
# 入力
K = int(input())
A, B = map(int, input().split())

# 直接出力
print(int(str(A), K) * int(str(B), K))

C - Long Sequence

制約から裏道を考えて…

  • 数列AAの長さNNが最大10510^5、このAA1010010^100回連結したものをBBと置く
    • 数列和とかループとか、真面目にやる問題じゃなさそう
  • Xまでに、数列Aがまるごと入る個数を考える
    • 数列A全体の総和を先に取得しておけば、XまでにAが入る個数*総和でショートカットできそう
    • 後は実装の問題
    • あまりを切り捨てた除算から考えるのはA問題と近いかもしれない
python
# 入力
N = int(input())
A = list(map(int, input().split()))
X = int(input())
 
Asum = sum(A) # 数列Aの合計値を取得

ans_cnt = (X//Asum)*N # XにAが入る数 * N = 答えの○項目までは確実に入る
X -= (X//Asum)*Asum # XにAが入る数 * Xの総和を、Xから引くa
# 残りのXを、数列Aの中で何項目まで入るか確認していく


for i in A: # 数列Aの要素ループ
    X -= i # Xから要素iを引く
    ans_cnt += 1 # 答えの○項目に1を足す
 
    if X < 0: # もしXが0を下回ったら打ち切り
        break

# 出力
print(ans_cnt)

D - FG operation

2次元DP

  • DはDPのD(らしい)
  • dpを考える。
    • iとjの設定で少し躓いた。
    • dp[i][j]dp[i][j]
      • iAii \dots A_iまで操作が終わった
      • jj \dots 数列の先頭がjjである
      • dp[i][j]dp[i][j]の中身\dotsその状態になるような操作手順は何通りあるか?
  • 添字の取り扱い注意
    • もうちょっと2次元DPをさらさらーっと組めるようになりたいですね
  • mod忘れ注意
    • あまりを出す、大事(本番にmod忘れて1WA)
python
# 入力
N = int(input())
A = list(map(int, input().split()))

mod = 998244353 # mod変数設定

dp = [[0]*10 for i in range(N)] # dp用配列の準備

dp[0][A[0]] = 1 # 初期値:i=0:操作を1つも行っていない状態で、j=A[0]:列の先頭がA[0]である状態:1通り


for i in range(N-1): 
    for j in range(10):
 
        # もしDP配列の値が0通り:その状態はありえない場合、スキップ
        if dp[i][j] == 0:
            continue
 
        # x,yを取り出し、操作F、操作Gの値を求める
        x = j
        y = A[i+1]
        F = (x+y) % 10
        G = (x*y) % 10
        
        # DPの値を更新する
        dp[i+1][F] += dp[i][j]%mod
        dp[i+1][G] += dp[i][j]%mod
 
 
# 操作終了後、数列の先頭が0~9である操作手順が何通りあるかを出力
for i in dp[-1]:
    print(i%mod)

Discussion

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