ここ最近、コンテストの振り返りが出来ていない状況が続いています。今回も参加したABC196の参加したメモ書きです。
なお、この記事を書いているのは、Python3使用の、茶色コーダーです。
A – Difference Max
標準入出力と、ちょっとした算数(数学？)知識が問われる問題。
x-y の最大値を求める計算は、xはなるべく大きく、yはなるべく小さい値を利用すればOKなことがわかります。
制約を見ると、a<=x<=b ,c<=y<=d と記載されているので、
xはbを、yはcを利用すればx-yが最大になります。
# AtCoder Beginner Contest 196
# A - Difference Max
a,b=map(int,input().split())
c,d=map(int,input().split())
print(b-c)B – Round Down
コンピュータが小数点を扱うときは近似値で保持していることを理解しているかが問われる問題。実装上は文字列操作が出来るかを問われます。
これは、十進法の小数点を二進数で保持することが難しいためです。
詳しくは、「 プログラミング 少数 誤差 」などでググってもらうとして、簡単な例としては、以下のようなコードで確認することができます。
print(0.1+0.1==0.2) # => True
print(0.1+0.2==0.3) # => False小数点を扱うときには誤差を意識する必要があることがわかります。
今回の問題は、文字列で受け取って、” . ” までの数字を出力すれば良いです。
私はコンテスト中は文字列を受け取り、for文で ” . ” までの数字をリストに格納して結合して出力しました。
# AtCoder Beginner Contest 196
# B - Round Down
X=str(input())
ans=[]
for i in range (len(X)):
if X[i]==".":
break
ans.append(X[i])
print(int("".join(ans)))勿論このコードでもACするのですが、Python3ではもっと簡単に書くことが可能です。
print(str(input().split('.')[0]))split()関数で ” . ” で入力を分割し、初めのindex分だけを出力すればOKですね。
C – Doubled
条件に合う整数を考えて、木構造を利用したDFS(深さ優先探索)で解く問題。
先日買って、学習していたPAST本に類似問題が出ていたおかげで解くことができました。
この問題分にある、偶数桁で前半と後半の文字列が等しいような数字は、数字を文字列として扱い、*2することで得られます。
print("1"*2)
# => 11あとはDFSで処理していけばOKです。
はじめ何もない状態のところから、1~9までの数字を文字列としてスタックに入れます。
スタックが空になるまで以下の操作を繰り返します。
- スタックから取り出した文字列を繰り返した数がNよりも大きければ何もしない。
- N以下なら答え用の変数に+1する。
- N以下ならスタックから取り出した文字列の末尾に、0~9を加えてスタックに入れる。
# AtCoder Beginner Contest 196
# C - Doubled
N=int(input())
ans=0
todo=[]
todo.append('1')
todo.append('2')
todo.append('3')
todo.append('4')
todo.append('5')
todo.append('6')
todo.append('7')
todo.append('8')
todo.append('9')
while len(todo)>0:
num=todo.pop()
if int(num*2)>N:
continue
ans+=1
todo.append(num+'0')
todo.append(num+'1')
todo.append(num+'2')
todo.append(num+'3')
todo.append(num+'4')
todo.append(num+'5')
todo.append(num+'6')
todo.append(num+'7')
todo.append(num+'8')
todo.append(num+'9')
print(ans)注意点としては、Python3で提出するとTLEします。
Pypy3で提出するとACします。
ちなみに、この解法は想定解法ではなかったようです。
普通にfor文で、i を繰り返した数がNを超えたら処理を抜けるようにしてもACします。
こっちのほうが簡単でした。。。
N=int(input())
ans=0
for i in range (1,N):
num=int(str(i)*2)
if num>N:
break
else:
ans+=1
print(ans)直前に覚えた解法の問題が出ると、つい、その解法を使いたくなってしまいますよね。
「ハンマーを持つ人にはすべてが釘に見える。」みたいな感じでしょうか。冷静に使用するアルゴリズムを見極めていきたいものです。
コメント
[…] […]