ABC140-B - Buffet を解く
ABC140-B - Buffet
問題文を理解するのが難しい… サンプルにも説明があるので参考にしよう
i 番目の料理を食べると満足度 Bi を得ることができるのだが
i 番目の料理、i + 1 番目の料理、の順で食べた場合は追加で満足度 Ci も得ることが
できるという問題
2 番目の料理を食べて、次に 3 番目の料理を食べて…
のように、食べた料理の数字が連続している場合に追加で満足度を足す
（上記の場合は C2 を足す）ということを忘れないように実装する
以上を踏まえて書いたコードを以下に示す
提出したコード
# 入力 n=int(input()) A=list(map(int,input().split())) B=list(map(int,input().split())) C=list(map(int,input().split())) # 答えを入れる変数 ans=0 # 連続している場合をチェックするために直前の値を持つ必要がある # 負の値にしておけば被らない # 100000000000000000000のようなとても大きな値にしてもいい before=-1 # 順番に見ていく for a in A: # 満足度を足す（0-indexなので-1するのに注意！） ans+=B[a-1] # 連続しているかチェック if before+1==a: ans+=C[before-1] # 次の「直前の値」として今見た値をAiを保存 before=a # 出力 print(ans)
提出結果はACでした
ABC139-B - Power Socket を解く
ABC139-B - Power Socket
1 口しかない電源プラグに A 口のタップを差していき B 口以上にする
最小でいくつのタップが必要か（タコ足配線…）
とりあえずシミュレーションで1つずつ増やしていき
初めて B 口を超えた時のタップの数を出力すればいい
差し方に関わらず「1 つ差すと合計 A 口増えて 1 口減る（A - 1 口増える）」
ことになる
タップを差すために 1 つ口が減ることに注意する
以上を踏まえて書いたコードを以下に示す
提出したコード
# 入力 a,b=map(int,input().split()) # 初期状態（1口） n=1 # タップの数 ans=0 # タップを1つずつ差していく while True: # b口以上になったら終了 if n>=b: print(ans) exit() # 差すことでa口増えるが、差した口も1つ減る n+=a n-=1 ans+=1
提出結果はACでした
ABC138-B - Resistors in Parallel を解く
ABC138-B - Resistors in Parallel
A1, A2, ... , An の逆数の総和の逆数を求める問題
逆数は 3 に対する 1/3 のような数のことだ
まずは画数の逆数を求め、それらの和を取り、最後にまたその逆数を取ればいい
難しそうな式が書いてあるが、式変形を考えるよりは
言われたままに実装する方が簡単だろう（なんか誤差が怖いけど）
以上を踏まえて書いたコードを以下に示す
提出したコード
# 入力 n=int(input()) l=list(map(int,input().split())) # 各項の逆数の和を取る sm=0 for x in l: sm+=1/x # 和の逆数を出力 print(1/sm)
提出結果はACでした
ABC137-B - One Clue を解く
ABC137-B - One Clue
数直線上に 2000001 個の石が置かれている
石の座標は -1000000, -999999, -999998, ... , 999999, 1000000 である
これらの石の内、連続する K 個が黒で塗られており
それ以外は白で塗られている
座標 X が黒であることがわかっているとき
黒で塗られている可能性のある座標を全て求めて、小さい順に出力する
まずは、黒で塗られている座標 X の石は
連続する K 個の石のどの順番の石であるか考えてみる
例えば、左端の石であった場合、その右にある K - 1 個の石も黒であるとわかる
右端の石であった場合も同様に、その左にある K - 1 個の石も黒となる
したがって、X - ( K - 1 ) 〜 X + ( K - 1 ) の範囲を
全て出力すればそれが答えになると考えられる
ただし、石の座標は -1000000, -999999, -999998, ... , 999999, 1000000
と範囲に制限があるので、上記の範囲がこの制限内に納まることを
チェックする必要がある
以上を踏まえて書いたコードを以下に示す
提出したコード
# 入力 K,X=map(int,input().split()) # 左端・右端を求める l=X-(K-1) r=X+(K-1) # 左端・右端が制限をオーバーする場合は置き換える if l<-1000000: l=-1000000 if 1000000<r: r=1000000 ans=[] for i in range(l,r+1): ans.append(i) # 出力 print(' '.join(str(x) for x in ans))
提出結果はACでした
ABC136-B - Uneven Numbers を解く
ABC136-B - Uneven Numbers
N 以下の正の整数について、桁数が奇数になる数字の個数を数える問題
制約が 1 <= N <= 10^5 とそれほど大きくないので
1つ1つについて条件を満たすかどうかをチェックしてその個数を数えていけばいい
数字の桁数を取得する場合は
いったん文字列に変換して len 関数を使えばよい
>>> a 123 >>> b=str(a) >>> b '123' >>> len(b) 3
以上を踏まえて書いたコードを以下に示す
提出したコード
# 入力 N=int(input()) # カウンタ c=0 # 1〜Nまでの数字について条件を満たす場合をカウント for i in range(1,N+1): # 桁数が奇数の場合 if len(str(i))%2==1: c+=1 # 出力 print(c)
提出結果はACでした
ABC135-B - 0 or 1 Swap を解く
ABC135-B - 0 or 1 Swap
数列 { p1, p2, ... , pn } が与えられる
一度だけ、 pi, pj を入れ替えることができる（入れ替えなくてもいい）とき
数列を昇順に並べることが可能かどうかを調べる問題
まずは昇順に並べた場合の数列を作ってみて
与えられた数列と完全に一致した場合は可能である（入れ替え不要）
また、ソートした数列が与えられた数列と 2 箇所 不一致であり
不一致であった 2 箇所を並べ換えることで一致させることができるならば
これも昇順に並べることが可能である
この条件は
昇順に並んだ数列から 2 つを選んで入れ替えたときの条件に等しい
上記 2 通りの方法について確認するコードを書けばいい
以上を踏まえて書いたコードを以下に示す
提出したコード
# 入力 N=int(input()) l=list(map(int,input().split())) # ソートした数列 sl=sorted(l) # 一致するなら 'YES' if l==sl: print('YES') exit() # 一致しない回数をカウント c=0 # 一致しない数字を保持するリスト a=[] b=[] for i in range(N): # 不一致のとき if l[i]!=sl[i]: c+=1 a.append(l[i]) b.append(sl[i]) # 不一致の回数が2回であり、同じペアの数字であれば 'YES' if c==2: if a[0]==b[1] and a[1]==b[0]: print('YES') exit() # それ以外の場合は 'NO' print('NO')
提出結果はACでした
ABC134-B - Golden Apple を解く
ABC134-B - Golden Apple
N 本の木があり、1 から N まで番号が振られている
これらの木に対し監視員を配置する
1 人の 監視員は番号 i の木のに配置させたとき
番号 i - D 以上 i + D 以下のすべての木を監視することができる
全ての木を監視するためには最低何人の監視員が必要かを求める
一人の監視員は番号 i - D 以上 i + D 以下の木を監視できる
つまり、i + D - ( i - D ) + 1 = ( 2D + 1 ) 本の木を監視することができる
1人 ( 2D + 1 ) 本の木を監視できるということは
N 本の木を監視するには N / ( 2D + 1 ) 人の監視員が必要であるということになる
このとき、答えが小数になる場合は切り上げる必要があることに注意する
以上を踏まえて書いたコードを以下に示す
提出したコード
# 入力 N,D=map(int,input().split()) # 出力 print(-(-N//(2*D+1)))
上記では、割る数を負の数にすることで
商を切り上げることができることを利用している
>>> 8//3 2 >>> -8//3 -3 >>> -(-8//3) 3
提出結果はACでした
