AtCoder ABC112参戦記

今回はABDの3完でした。C問題は全探索することまでは思いつきましたが、実装の仕方が悪くWAでした。以下C問題とD問題のコードです。

C問題(Pyramid)

def dist(a, b, x, y, h):
    return h + abs(a - x) + abs(b - y)

N = int(input())
P = []
for i in range(N):
    x, y, h = map(int, input().split())
    P.append([h, x, y])
P.sort(reverse = True)

for i in range(101):
    for j in range(101):
        H = dist(i, j, P[0][1], P[0][2], P[0][0])
        for p in P[1:]:
            if max(H - abs(p[1]-i)-abs(p[2]-j), 0) != p[0]:
                break
        else:
            print(i, j, H)
            break

少なくとも一つは1以上の高さを持つので、hの順にソートして、最初の座標情報からすべてのマスの仮の高さを設定します。その高さが残り全ての座標情報と矛盾しなければ、そのマスが求めたい頂点となります。

D問題(Partition)

import math
N, M = map(int, input().split())
ulim = M//N
mid = int(math.sqrt(M))
if ulim >= mid:
    ans = []
    for i in range(1, mid+1):
        if M%i == 0:
            ans.append(i)
            if M//i <= ulim:
                ans.append(M//i)
    print(max(ans))
 
else:
    for i in reversed(range(1, ulim+1)):
        if M%i == 0:
            print(i)
            break

こちらのほうがC問題より簡単だったと思います。M//N以下のMの最大の約数は何かという問題に言い換えることができます。あとは√M とM//Nの大小関係に注意して実際に約数を探索すれば良いです。