AtCoder Beginner Contest (ABC) 234 Pythonで参戦しました。 A,B,C問題解説あり。
前回の記事
前回の参戦
こんにちは。めりーです。
昨日から「新春！にじさんじ麻雀杯2022」が始まりましたね。
今年は生ライブで見てますが、去年よりもレベルが高い！！
「え？？？なんで面子崩すの？？？？」みたいな宇宙麻雀が少ない・・・・。
レベルが上がっているのはいいことなんでしょうが、役なしでポンしたりする「にじさんじらしい」麻雀も見たかったり・・・。
そんなこんなで、昨日のAtCoder Beginner Contest (abc) 234に参戦したので、その記録です。
結果はA,B,C三完で、パフォーマンスは610でした。
WAでの提出が1回もなかったので高めのパフォーマンスでした。
D問題解けそうで解けなかったのが悔しい。
言語はPython、提出はPyPyです。
目次
A問題 Weird Function
Weird Function
問題文
関数f(x) = x2 + 2x + 3 と定義します。
整数tが与えられた時、f( f ( f (t) + t ) + f ( f (t) ) )を求めよ。
という問題。
f(x)が滅茶苦茶入れ子になっていて、問題文読むのもめんどくさいですね。
解き方は2通り思いつきました。
1. f(x)を関数にする。
2. f(x)を全て数式にして実装。
自分は関数の実装があやふやだったので、2番目の方法で実装しました。
以下提出したコード
t = int(input()) f1 = t**2 + 2*t + 3 t2 = f1 + t f3 = t2**2 + 2*t2 + 3 f4 = f1**2 + 2*f1 + 3 t3 = f3 + f4 print(t3**2 + 2*t3 + 3)
f(t)をf1、f(t) + t をt2、f( f(t) + t)をf3、f( f(t) )をf4、f( f(t) + t) + f( f(t) )をt3として、内側から一つ一つ計算していきました。
愚直ですねぇ・・・。
というわけで、コンテストが終わった今、改めて1の解き方で実装したコードがこちら。
def f(x):
ans = x**2 + 2*x + 3
return ans
t = int(input())
ans1 = f(f(f(t) + t) + f(f(t)))
print(ans1)
こちらが正当法。(おそらく)
f(x) = x2 + 2x + 3 をそのまま定義して、それの計算結果を返り値にしてます。
こっちの方法は、そのまま問題文の通り、f( f ( f (t) + t ) + f ( f (t) ) )を出力して終了です。
こっちの方がスマートですね。
B問題 Longest Segment
Longest Segment
問題文
二次元平面上の点がN個あります。
N個の点の座標は(xi,yi)です。
2点間の距離の最大値を求めてください。
という問題。
2 <= N <= 100なので、全探索で余裕で間に合います。
というわけで問題文の通りに実装していきましょう。
2点間の距離は √(x1 - x2)2 +(y1 - y2) 2で求められます。(√は全体にかかってます。)
あとは、最大値を更新しながら全探索するだけ！
方針をまとめると、
1. 入力
2. 二重ループで全探索する。
3. 2点間の距離を求める。
4. ループの最後に最大値を更新する。
5. 最大値を出力する。
となりました。
コード↓
n = int(input())
x = []
y = []
for _ in range(n):
X,Y = map(int,input().split())
x.append(X)
y.append(Y)
ans = 0
for i in range(n):
for j in range(i+1,n):
nagasa = ((x[i]-x[j])**2 + (y[i]-y[j])**2)**(1/2)
ans = max(ans,nagasa)
print(ans)
jの範囲がi+1,nなのは、同じ２点間を何回も数えるのを防ぐためです。
例: i = 1,j = 2の場合、点1,2間の距離を求めることになる。
i =2, j = 1の場合、点2,1間の距離を求めることになる。
これらの距離は同じであるため、片方で十分である。
C問題 Happy New Year!
Happy New Year!
問題文
0,2のみからなる正の整数で、k番目に小さい数を求めよ。
という問題。
は？なに言ってんの？ってなると思うので、小さい順に書いていくと、
2 , 20 , 22, 200 , 202, 220 , 222 ・・・
というようになっています。
この数列、どこかで見覚えが・・・？？
2 , 20 , 22, 200 , 202, 220 , 222 ・・・ 1 , 10 , 11, 100 , 101, 110 , 111 ・・・ 1, 2, 3, 4, 5, 6, 7 ・・・
そうです。二進数と対応してますね。
二進数の1を2に変換すれば求められそうです。
というわけで方針は、
1. 入力
2. 1を二進数に変換
3. 2の「1」を「2」に変換
4. 3を出力
という感じです。
実際のコードがこちら
k = int(input()) a = bin(k)[2:] print(int(a)*2)
はい。たったの3行です。
行数だけ見たらA問題の方が多いですね。
簡単な解説を。
a = bin(k)[2:]
で、十進数のkを二進数に変換して、aに格納してます。
Pythonで、binを使うと、頭に"0b"という文字列が付きます。
今回は、この文字列が不要なので、"0b"以降のものを取り出しています。
print(int(a)*2)
で、int(a)にすることで、1行前で得られた二進数を十進数として扱えます。
例:a = 11(二進数) → int(a) = 11(十進数)
これに2をかけることで1を2に変換できます。
※1に2をかけるので、桁の繰上りは発生しません。0に2をかけても0なので、0は変化しません。
以上でした！
次回は簡単な茶色diffの問題も解けるようになりたいです！！！
では！
