・5 min read
ABC220 茶色コーダーが解けた所まで
AtCoder Beginner Contest 220
ABC219の問題を、本番で自分が解けた所までの解説です。
無事レート微増。
このペースをちゃんと維持できれば、年内８００＝入緑はなんとか達成できそうです。
A - Find Multiple
数学的解決法（想定解）
- (Bを割ってあまりを捨てた値）
-
- この時点でのY：B以下で一番大きいCの倍数
- YがA以上であれば、答え：Yとして出力
- YがA未満であれば、答え：-1として出力
- この時点でのY：B以下で一番大きいCの倍数
# 入力
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を超えた場合、ループを終了する
# 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)# 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の先頭の桁から見ていき、順番に以下の操作を行う
- ansをn倍する
- ansに今見ている桁の数字を加える
-
Sの最後の桁まで見終わった時、ansが求めたい値になる
-
具体例として、
-
5進数で書かれた'１２３'を、１０進数表記で表したい
- ans=0と置く
- 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
- 1桁目を見る＝１
- ans=0と置く
-
「n進数 変換」などで検索して、ツールで確認してみると確かに正しい。
-
後は入力A、Bを、K進数から10進数表記に戻して、積を求めると答えになる
# 入力
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進数から１０進数表記にしたものの積が答え
print(ans) # 出力Python限定？裏技解法：int関数
- 公式ドキュメントより https://docs.python.org/ja/3/library/functions.html?highlight=int#int
- int(文字列,n)
- n進数表記で書かれた文字列sを、一発で10進数表記に変換してくれる優れもの。
- これを使えばわざわざ関数を作成しなくてもヨシ！
# 入力
K = int(input())
A, B = map(int, input().split())
# 直接出力
print(int(str(A), K) * int(str(B), K))C - Long Sequence
制約から裏道を考えて…
- 数列の長さが最大、このを回連結したものをと置く
- 数列和とかループとか、真面目にやる問題じゃなさそう
- Xまでに、数列Aがまるごと入る個数を考える
- 数列A全体の総和を先に取得しておけば、XまでにAが入る個数*総和でショートカットできそう
- 後は実装の問題
- あまりを切り捨てた除算から考えるのはA問題と近いかもしれない
# 入力
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 # 答えの○項目に１を足す
if X < 0: # もしXが０を下回ったら打ち切り
break
# 出力
print(ans_cnt)D - FG operation
2次元DP
- DはDPのD（らしい）
- dpを考える。
- iとjの設定で少し躓いた。
- ：
- まで操作が終わった
- 数列の先頭がである
- の中身その状態になるような操作手順は何通りあるか？
- 添字の取り扱い注意
- もうちょっと2次元DPをさらさらーっと組めるようになりたいですね
- mod忘れ注意
- あまりを出す、大事（本番にmod忘れて1WA)
# 入力
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：操作を１つも行っていない状態で、j=A[0]：列の先頭がA[0]である状態：１通り
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)
