本エントリーは、私の備忘録的な日記であり、競プロ初心者が同様の競プロ初心者の方に、もしかしたら役に立つかもしれないし立たないかもしれない感じのものです。
記事に書かれている内容に数学的な厳密性は含まれないため、ご注意下さい。
記載しているコードの言語はPython3です。
ABC170参戦に当たって
2週間ぶりのABC(AtCoderBeginnersContest)。ABCは競プロ新規参入者の私にはちょうど良いレベルのコンテストです。
先週は運営の方々がGoogleCodeJamに参戦する方が多く、ABCの開催は見送られました。
直前まで今週のABC開催告知がなかったため、今週もないのかなぁ。と残念に思っていたら、2日前に告知されました！うれし～！運営の方々に感謝しつつ精進する。
ABC170の前日には、東京海上日動プログラミングコンテストも開催されて参加しましたが、私にはちょっと難しいレベルの問題が多かったです。
ABCは、大体ABC3完を目指せるくらいになってきたと思うため楽しみですね！
さあ、いざABC170スタート！
A – Five Variables
配列の要素の番号を取得する問題。
問題を読んだだけでは一寸わからなかったけれども、入力例を見て理解しました。
リストで受け取って 0 になっているindexを探して出力。
a=list(map(int,input().split()))
print(a.index(0)+1)indexは0から数えられるため、目に見える形での順序にするために最後の+1しないと駄目なことに注意。
B – Crane and Turtle
つるかめ算。
問題を見て、鶴をC、亀をTとすると、以下の様なTが存在すればOKと考えました。
①：2C+4T=Yと、②：C+T=Xがあり、②を変形して、②’：C=X-T が得られて、これを①に代入することで、2*(X-T)+4T=Yとなり、2T=Y-2Xを得ることができます。
ここで、YとXは標準入力より与えられているため、Tが整数として存在するためには、Y-2Xが2の倍数であることが分かります。
判定は、2で割った余りが0であることで判定可能なので、次の条件式で出来ますね。
(Y-2X)%2==0
この条件だけだと、X=10,Y=50といった条件や、X=4,Y=6といった条件でも満たしてしまいます。
X=10,Y=50の場合、なぜNGなのかというと、動物の合計は10匹で足が50本となるような鶴亀の組み合わせは存在しないからです。
動物すべてが亀の場合が、動物の足の最大値です。
それを越す場合は、4本足以上の動物が存在しないと条件が成立しなくなります。
このため、Yの取りえる値の最大値は4Xだとわかります。
同様に、X=4,Y=6の場合、動物の合計は4匹で、動物の足が6本になるような鶴亀の組み合わせも存在しません。
動物すべてが鶴の場合が動物の足が最小になります。
それ以上少ない数の場合は、もう片方の動物の存在がマイナスになってしまうか、隻脚の鶴を考えなくてはならなくなってしまうため、問題の条件から外れてしまいます。
このため、Yの取りえる値の最小値は2Xだとわかります。
これら3つの条件を満たすX,Yの組み合わせの場合’Yes’を出力して、条件に１つでも当てはまらなければ’No’を出力すればOKです。
X,Y=map(int,input().split())
if Y>4*X or Y<2*X:
print('No')
exit()
else:
pass
if (Y-2*X)%2==0:
print('Yes')
else:
print('No')
私は最小値の条件になかなか気づけなかったのと、
Yの範囲で判定する条件式で処理を抜ける処理のexit()を書かなかったためにWA連発しました。
C – Forbidden List
条件に合ったリストの作成と距離(絶対値)の計算問題。
競プロ始めたばかりの人は問題文だけを見て内容を瞬時に理解することは難しいと思います。(思いたい！ｗ)
こういう場合は、入力例を見ていって、実際に紙などに書いてみるのが良いと思います。
問題を私なりに解釈した内容で書き直しすると、以下の2つに要約されます。
- 始めに与えられた整数を含まない数列を作ってね。
- 作った数列と整数Xとの距離で最小の数字を答えてね。
注意点としては以下の3つ。
- 始めに与える整数列はない場合もあるよ。
- 答えはXになる場合もあるよ。(距離＝0)
- 作る整数の範囲はよく考えてね。
注意点1が満たされている場合は、必ず注意点2も満たされているので、
入力の1行目を受け取った時点で、2行目が存在しない(N==0)の場合は答えはX自身になるので、
Xを出力してプログラムを終了。
注意点2が満たされるには、受け取った2行目の数列にXが含まれていない場合なので、
2行目を受け取った時点で、Xが入っていなければX自身が答えになるので、
Xを出力してプログラムを終了。
ここからが、この問題のメイン部分だと思います。
とはいっても、特に注意する部分は、注意点3にも上げている部分で、問題文にも、”(正とは限らない)”と言及されています。(0は正の整数ではないです。)
具体的な例でいうと、
X=1,N=100
p1,・・・,p100=[1,2,3,4,5,・・・,96,97,98,99,100]
この場合、作るべき数列は、[・・・,-5,-4,-3,-2,-1,0,101,102,102,・・・]です。
Xの制約から、必要な部分は0から101までであることが分かります。
XやPiの制約が1<=X,Pi<=100のため、作るべき数列も同様に1から100までを想定して私はWA出しました。
問題文を見直して作るべき数列は0から作ればよいことに気づいたけれども、上限を100だと思い込んでさらにWA連発しました。
作るべき数列の作り方は、素になる数列(上述の通り、必要な部分は0から101まで)を作っておいて、
入力の2行目で受け取った数列含まれていなければ、空のリストに追加する形で作りました。
あとは、作られた数列にXを投入、ソートして、Xの前後の数字の差を確認して差が小さいほうを出力すればOKです。
X, N = map(int,input().split())
if N == 0:
print(X)
exit()
# titleの通り、使用を禁止された数字のリストが与えられる。
flist = list(map(int,input().split()))
if flist.count(X) == 0:
print(X)
exit()
# 使用禁止の数字を除いたリストを作るために、リストの素を作る。
l = list(range(0,102)) # ここの範囲設定が一番難しい部分だと思う。
# 使用を許可された数字のリストを作成する。
plist = []
for i in range(len(l)):
if flist.count(l[i]) == 0:
plist.append(l[i])
# Xを投入して、前後の数字との距離を計測していく。
plist.append(X)
anslist = sorted(plist)
t = anslist.index(X)
dist1 = anslist[t] - anslist[t-1] # Xと1つ前の数字との距離
dist2 = anslist[t+1] - anslist[t] # Xと1つ後ろの数字との距離
if dist1 <= dist2:
print(anslist[t-1])
else:
print(anslist[t+1])
ABC170を終えて
B問題も、C問題も回答するべき範囲を見誤ったためにWAの回数多かったのが悔やまれますが、なんとかABC3完できたので良かったです。
時間制限を気にして、焦っていた自覚もあり、焦りにより考慮すべき部分の一部が抜けていた感じですね。
結果は、パフォーマンス189っていう今まで参加した中で一番低かったけど、学ぶことも多かったし楽しかったー！
ABCはWA無し40分くらいで終わらせてD問題に取り組めるようにしたいなぁ。
AtCoderProblemsさんを参考にしつつ、D問題も解いていこっと。
コメント