13時から19時までAHC004に参加して少し頭がつかれているように感じましたが、せっかくなのでABC207にも参加しました。
レートは茶色中位のPython3を使用したACコードとともにコンテストを振り返ります。
A – Repression
標準入出力と数の大小について、プログラミングで扱えるかを問われる問題。
私は一つの配列として受け取って、大きいほうからソート、前二つを足し合わせる方針で提出しました。
# AtCoder Beginner Contest 207
# A - Repression
ABC=list(map(int,input().split()))
ABC.sort(reverse=True)
print(sum(ABC[:2]))このほかにも、3つのうち二つを足した数の最大値を出力する。というコードでもACしますね。
A,B,C=map(int,input().split())
AB=A+B
BC=B+C
CA=C+A
print(max(AB,BC,CA))B – Hydrate
難しい問題。
何度読んでも理解できませんでした。
日本語で書かれているからわからないのかな。と思って英文の問題文を見ましたが日本語同様にわからなかったので、問題文と、入力例からなんとか状況を読み取って、シミュレーションしました。上限も分からなかったのですが、ひとまず10**6くらいで出してみよう。と思って出したらACしました。
# AtCoder Beginner Contest 207
# B - Hydrate
a,b,c,d=map(int,input().split())
u=a
r=0
for i in range (10**6):
if u<=r*d:
print(i)
exit()
u+=b
r+=c
print(-1)
改めて考えると、これは、連立方程式を2本立てて、正の整数になるxの値を求めればよいですね。
- y=(D*C)x …①
- y=Bx+A …②
上記二つの式の①が②以上になるような正の整数xの値が答えになります。
(D*C)x>=Bx+A この式を変形して、 (D*C)x-Bx>=A となり、 x((D*C)-B)>=A から、x>=A/((D*C)-B) となる正の整数が答えですね。
分母の(D*C)-Bが0以下の場合はどのような正の数xをかけても正の整数Aよりも大きくすることは出来ないので、答えは-1になります。
A,B,C,D=map(int,input().split())
if (D*C)-B<=0:
print(-1)
else:
if A%((D*C)-B)==0:
print(A//((D*C)-B))
else:
print(A//((D*C)-B)+1)C – Many Segments
閉空間や開区間、半開区間などの概念を知っていますか？(知らなければ、問題文に書いておくので、覚えてくださいね。)また、区間の重複判定ができますか？という問題。
まず、問題文に書かれいてる内容が見慣れないですよね。でも半開区間 [l,r) というのはおなじみですね。range(0,10)とした時も、半開区間で、[0,1,2,3,4,5,6,7,8,9]というrange object が作成されます。
今回は、すべての区間を両端が含む形の閉空間にして考えます。開区間は、0.1ずらして考えるとよさそうです。
二つの区間の重複判定は、以下の条件で判定できます。
正確には、以下の二つの条件は、重複していない条件です。
- 一方の右端が、他方の左端よりも小さい場合
- 一方の左端が、他方も右側よりも大きい場合
この部分は単独で関数として定義すると以下のようなコードで実装されます。
def is_there_overlapping_section( l1, r1, l2, r2 ) :
if r2 < l1 :
return False
if l2 > r1 :
return False
else :
return Trueあとは、二重のforループで各組を判定して答えの数を数えていけばOKですね。
# AtCoder Beginner Contest 207
# C - Many Segments
def is_there_overlapping_section( l1, r1, l2, r2 ) :
if r2 < l1 :
return False
if l2 > r1 :
return False
else :
return True
N=int(input())
ls=[]
# 全てを閉空間で考える。
for i in range (N):
t,l,r=map(int,input().split())
if t==1:
pass
if t==2:
r-=0.1
if t==3:
l+=0.1
if t==4:
l+=0.1
r-=0.1
ls.append([l,r])
ans=0
for i in range (N):
# li,riをlistから取得
li, ri = ls[i][0], ls[i][1]
for j in range(i+1,N):
# lj,rjをlistから取得
lj, rj = ls[j][0], ls[j][1]
if is_there_overlapping_section(li,ri,lj,rj):
ans+=1
print(ans)私は、区間の判定を0.1ずらしてすべて閉空間で考えるところまではコンテスト中に思い至るも、解けませんでした。
lとrを間違って格納していました。
そんなところで間違うはずがないと思い込んで、ずっと重複判定でどこかおかしなところがあるのだろうか。と考えていて時間が過ぎていきました。
落ち着いて、思い込みを排除してデバックするのが大事ですね。
コメント