今までで一番充実していたかもしれない
A問題(2分49秒)
問題の概要
AからBにP,BからCにQ,CからAにRそれぞれかかるときの移動時間の最短
方針
min(P+Q, Q+R, R+P)を考える
実際のコード
a, b, c = [int(i) for i in input().split()]
d = a + b
e = a + c
f = b + c
print(min(d, e, f))
d,e,fのところそのまま入れてもよかった気がする
B問題(18分30秒)
問題の概要
リストのなかで1つ切れ目を入れた時の前半部分の和と後半部分の和の差の絶対値の最小値を求める
方針
制約がN<=100と少ないので素直に全パターンにおいて前半部分の和と後半部分の和の差の絶対値を求め、その最小値を考える
備考
最初勘違いしていてTを整数じゃなくて指定した重さだと考えていて(重さT以上のものの和)-(重さT未満のものの和)の絶対値の最小値だと思っていて10分くらいよけいなコードを作っていました。勿体無い...
コード
n = int(input())
w = [int(i) for i in input().split()]
weight = []
dif = 100000000
for i in range(len(w)):
memory = abs(sum(w[:i+1]) - sum(w[i+1:]))
weight.append(memory)
print(min(weight))
最近[int(i) for i in input().split()]って打つのがめんどくさくなっているのでそろそろ違う入力の方法を探りたい
C問題(26分21秒)
問題の概略
N段の階段にM個の壊れた段があり、それ以外を1段or2段ずつ上るときの上り方の総数 % 1000000007
方針
- 連続して壊れていた場合は0
- それ以外の場合について、壊れていない段が連続して何段あるかをリストにまとめ、それについてそれを項数としたフィボナッチ数を計算し、その積を求める。
なんだか高校数学チックな問題だなーと思いました。1段or2段ずつ進むって言われてフィボナッチ数列は頭にすぐ浮かんだのであとはそれをTLEしないように気を付ける感じで(再帰だと嫌な感じがしたのでググってでてきた早そうなやつをコピペしました)
コード
def fib(n):
if n <= 1:
return n
result = [1, 0, 0, 1]
matrix = [1, 1, 1, 0]
while n > 0:
if n % 2:
result = mul(matrix, result)
matrix = mul(matrix, matrix)
n //= 2
return result[2]
def mul(a, b):
return [a[0]*b[0] + a[1]*b[2],
a[0]*b[1] + a[1]*b[3],
a[2]*b[0] + a[3]*b[2],
a[2]*b[1] + a[3]*b[3]]
n, m = [int(i) for i in input().split()]
a = []
frag = 1
ans = 0
step = []
for i in range(m):
a.append(int(input()))
for i in range(m-1):
if(a[i] == a[i+1] - 1):
frag = 0
if(frag == 0):
ans = 0
else:
ans = 1
sirusi = 0
for i in range(len(a)):
step.append(a[i] - 1 - sirusi)
sirusi = a[i] + 1
step.append(n - sirusi)
for i in range(len(step)):
ans = ans * fib(step[i]+1)
ans = ans % 1000000007
print(ans)
Dは少し考えたんですけどTLEしない方法が検討が付かなかったので飛ばしました。
E問題(TLE)
問題の概要
あたえられたlに対してa+b <= lかつa+b = aXORbとなるような(a, b)の組み合わせを求める
方針
実際にl=101(5)くらいまで考えて、「a+b = aXORb」ってこれa,b同じ桁に1があったらダメじゃん！」ってことは分かりました。つまり、1~lまでの各iに対して2^(iを2進法に直した時の1の個数)でいいんだなと分かりました。
コード
l = int(input(), 2)
i = 0
ans = 0
while(i<=l):
ans += 2**bin(i).count('1')
i += 1
print(ans % 1000000007)
lが2^100001までなので当然TLE。その後TLEしないようなものを1時間くらい考えましたが時間が足りませんでした。
def keisan(n): #n >= 2で有効
a = 2 + 2 ** n
for i in range(n-2):
a += 2**(i+2) * (n - i -1)
return a
l = int(int(input()), 2)
m = l
cnt = 1
while(l // 2 > 0):
cnt += 1
l //= 2
ans = 0
if(l == 0):
ans = 1
elif(l == 1):
ans = 3
elif(l == 2):
ans = 5
elif(l == 3):
ans = 9
else:
ans = 3
while(cnt > 2):
ans += keisan(cnt - 1)
cnt -= 1
for i in range(2**(cnt-1), m+1):
ans += 2**bin(i).count('1')
print(ans % 1000000007)
上でnビットのすべてに対する組み合わせの数を計算して、それをlのビット数-1までやったあとlまではfor文で計算しようと思いましたがlが小さいうちはいいんですけど大きくなると答えが合わなくなりました...オーバーフローしたのかな。理由がわかりません。
結果
3完+1TLEの1760位でした。次は400点以上の問題も解けるといいなと思いました。
レート
次回には茶色ネームになれるかな...？最近C++を勉強し始めたので次々回くらいからはC++を使ってコンテストに参加したいと思いました。