tmori’s blog

公開メモ帳くらいの感覚で書いています。技術系多め。日常少なめ。

Atcoder Beginner Contest 144 振り返り 【Python】

はじめに

AtCoder Beginner Contest 144の振り返りをします。
初の4完出来ました!! 今回は数学重視(?)のコンテストだったので得意不得意がかなり分かれたのではないでしょうか。

atcoder.jp

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の代表がこんなこと言ってましたね。

まさにその通りな気がします。
そんな話は置いといてプログラムについて書いていきます。

提出したプログラム

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) であること。

f:id:tmoribanner:20191029194939j:plain
3dから2dへ

2. 条件式

溢れるときの水の形は台形になるAと三角形になるCがあります。この2つ境目はBの状態であり、その時の水の面積は (ab/2) となる。この値を使って回答時の水の状態を確認します。後は計算するだけ。

f:id:tmoribanner:20191029195045j:plain
条件

3. Aの場合

f:id:tmoribanner:20191029195115j:plain
Aの図

4. Bの場合

f:id:tmoribanner:20191029195159j:plain
Bの図

終わりに(余談)

ブログ内の図作成にはiPadapple pencil+ GoodNotes 5 を使用しました。ちなみにコンテスト中に書いた図も下に貼っておきます。よくこんな汚い図で正解できたなぁと後になって思います。

f:id:tmoribanner:20191029201219j:plain
頭の中で必死に水をこぼしている図