AtCoder Beginner Contest 144(参加)
めちゃめちゃサボってしまった(反省)
はじめて4完できたので良かったけど凡ミスで順位すごい下がった気がする(反省)
A問題
与えられた2数が一桁の自然数なら積を、それ以外なら-1を返す atcoder.jp
コード
#!/usr/bin/env python3 import sys input = sys.stdin.readline A, B = map(int, input().split()) if A < 10 and B < 10: print(A*B) else: print("-1")
B問題
与えられた数が九九の答えならYes、違ったらNoを返す atcoder.jp
コード
#!/usr/bin/env python3 import sys input = sys.stdin.readline N = int(input()) for i in range(1,10): # 1〜9の数字で割り切れて商が10未満 if N // i < 10 and N % i == 0: print("Yes") exit() else: continue print("No")
C問題
a,bを自然数として、ある座標(a,b)に積abを対応付ける。座標(1,1)にいる時、与えられた数Nが対応付けられた座標まで移動するために最小で縦横何マス移動しなければならないか。 atcoder.jp
所感
積がNとなる2自然数の組み合わせをすべて列挙した上で、各組のうち最小の和を考えれば良い
座標の出発点は(0,0)ではなく(1,1)なので注意
コード
#!/usr/bin/env python3 import sys import math input = sys.stdin.readline N = int(input()) facts = [] # 積のペアを格納するリスト # 列挙にはNの平方根まで割れば十分 for i in range(1, math.ceil(math.sqrt(N))+1): if N % i == 0: facts.append([i, N//i]) sums = [] for fact in facts: sums.append(sum(fact)) print(min(sums)-2) # 出発点を考慮して1+1 = 2を引く
D問題
底面が1辺aの正方形、高さbの直方体の中に体積x3の水が入っている。底面の1辺を床につけたまま直方体を傾けていく時、水をこぼさずに角度何度まで傾けられるか atcoder.jp
所感
どう見ても数学の問題なので、愚直に計算をした。
絵を書くのが面倒(iPad買ったので次から書きたい)なので割愛するけど、
1.(側面の長方形で切断した)断面は三角形or台形
2.断面の対角線が水平になるところが三角形と台形の境目
3.水面は地面と平行になる
の3つを用いればOK
1回目の提出では満杯(=傾けられない)時の場合分けを忘れてミスし、更に分数の計算ミスでまたWAしてしまったことで無駄に10分のペナルティを食らってしまった(反省)
コード
#!/usr/bin/env python3 import sys import math input = sys.stdin.readline a, b, x = map(int, input().split()) if a**2*b == x: print(0) exit() if 2*x <= a**2*b: t1 = a*b**2 t2 = 2*x ans = math.degrees(math.atan(t1/t2)) else: t1 = a**3 t2 = 2*a**2*b - 2*x ans = 90 - math.degrees(math.atan(t1/t2)) print(ans)
E問題
要点は下記
1.長さNの2つの数列AとFがある
2.Aの数列の任意の項の値を1減らす操作をK回できる
3.数列AとFの項を1つずつ取り出し、その積から長さNの数列を新しく作る
4.新しく作った数列の最大の項を最小化する取り出し方が存在し、その時の最大の項の値を求める
\( 1 \leq N \leq 2 \times 10^5, 0 \leq k \leq 10^{18} \)
所感
上記2の操作を考えないのであれば、直感的にはAを降順ソート、Fを昇順ソートして第k項同士の積から新しい数列を作り、この数列の最大の項(既に最小化されている)を求めればいい。
上記2の操作を考える場合、上記のソートを通じてできた数列の中で最大の項について、対応するAの値を1減らす操作をK回繰り返す。
ただし、このやり方だと計算量がO(NK)となり間に合わない、というとこまで来て何も思い浮かずギブアップ
解説を見て解法に納得したので気が向いたら書く。二分探索を使うらしいけど名前だけ知っててちゃんと使ったことなかった(反省)
解説を見るとこのE問題は解けてよかったなぁ〜と思ってしまった