Atcoder Beginner Contest 144 振り返り 【Python】
はじめに
AtCoder Beginner Contest 144の振り返りをします。
初の4完出来ました!!
今回は数学重視(?)のコンテストだったので得意不得意がかなり分かれたのではないでしょうか。
A - 9x9
提出したプログラム
a,b=map(int,input().split()) if a >= 10 or b >= 10: print("-1") else: print(a*b)
特にコメントなし。
B - 81
提出したプログラム
N=int(input()) flag = False for i in range(1,10): for j in range(1,10): if i*j == N: flag = True print("Yes") if flag else print("No")
for×2でも81回で終わるので安直に書きました。
C - Walk on Multiplication Table
提出したプログラム
N=int(input()) def make_divisors(n): divisors = [] for i in range(1, int(n**0.5)+1): if n % i == 0: divisors.append(i) if i != n // i: divisors.append(n//i) return divisors N_list = make_divisors(N) if N_list[-1]*N_list[-2] == N: print(N_list[-1]+N_list[-2]-2) else: print(N_list[-1]+N_list[-1]-2)
Nの約数を求めるためにググって出てきた記事*1を参考に書きました。
参考記事の関数を読んだときに作成されるリストが[最小, 最大, 次点の最小, 次点の最大, ...]となることが分かったので、リストの最後周辺を参照すれば楽に求めそうだと気が付きました。他の人の解答も概ね同じでしたね。
D - Water Bottle
この問題について色々議論されてますが、僕はコンテスト内容に多様性が出てよかったように思えます。(自分的にアルゴリズムより数学のほうが得意分野だったので、あんまりマイナスの側面が感じられなかっただけかも知れません。)
atcoderの代表がこんなこと言ってましたね。
そりゃ自分の得意な問題が出たら神ゲーだし、苦手な問題が出たらクソゲーよ。そんなもんよ。
— chokudai(高橋 直大)🌸🍆🍡 (@chokudai) October 29, 2019
まさにその通りな気がします。
そんな話は置いといてプログラムについて書いていきます。
提出したプログラム
import math a,b,x=map(int,input().split()) x_2d = x/a if a*a*b == x: print(0) exit() if x/a > (a*b)/2: print(90-math.degrees(math.atan(a/(2*b-2*x/(a*a))))) else: print(math.degrees(math.atan(b/(2*x/(a*b)))))
ちなみにに2回REしてます。一回目はデバッグのときに使ってたprintの消し忘れで、二回目は水が容器一杯に入っていたときの処理が抜けていました。見直し大事。
簡単な解説したいんですけど文字だけじゃ無理そうなのでお絵かきします。
解説
1. 問題の簡略化
1辺を軸に回転させるので3次元での処理はいらない。なので2次元の容器に変換します。重要な値として水の面積が x/a 、空の面積が (ab-x/a) であること。
2. 条件式
溢れるときの水の形は台形になるAと三角形になるCがあります。この2つ境目はBの状態であり、その時の水の面積は (ab/2) となる。この値を使って回答時の水の状態を確認します。後は計算するだけ。
3. Aの場合
4. Bの場合
終わりに(余談)
ブログ内の図作成にはiPad+apple pencil+ GoodNotes 5 を使用しました。ちなみにコンテスト中に書いた図も下に貼っておきます。よくこんな汚い図で正解できたなぁと後になって思います。