ABC400の記録

はじめに

2週間ぶりの参加。

成績：AB2完（300）

A

400をaで割って整数なら商を出力し、整数でなければ-1。

A

a = int(input())
num = 400/a
if num == int(num):
    print(int(num))
else:
    print(-1)

整数かどうかの判定はis_integer()じゃなかったか？と思ったけどなんか予期した挙動にならなかったのでintで判定した。今試したら想定通り動いたので何か間違えていたのだろう。

B

これは言われたとおりにやるとしか言いようがない気がする。Aより簡単かもしれない。

B

n,m = map(int,input().split())
total = 0
for i in range(m+1):
    total += n**i
    if total > 10**9:
        print("inf")
        break
else:
    print(total)

C

すぐには分からなかったが、実験しているうちに$a=1$と$a=2$の時だけ考えればいいことが分かった。$a=3$以上の時にできる数はすべて$a$が1か2の時に出てきている。という訳で$n/2$以下および$n/4$以下の平方数を数えて終わり……

C_WA

import math
n = int(input())
ans = 0
ans += math.floor(math.sqrt(n//2))
ans += math.floor(math.sqrt(n//4))
print(ans)

と思ったらWAになってしまった。5WAだったのでコーナーケースかと思って探索用のプログラムを書くなどいろいろやっていたが間違いが見当たらずに45分ほど経過し、そのまま時間切れ。

オチとしては公式解説にあるようにsqrtを使ったことによる誤差が原因で、考察は合っていた。平方根の整数部分が欲しい場合はisqrtを使うらしいが、全然知らなかった。python3.8以降で使えるらしいが、こういう情報ってどこで仕入れてくるんでしょうね。
isqrtに変えただけでACとなった。

C_AC

n = int(input())
ans = 0
ans += math.isqrt(n//2)
ans += math.isqrt(n//4)
print(ans)

D

(20250419追記)
2週間ほど考えてみたがACできず！このためにダイクストラ法を勉強したのに……
考え方としては公式解説にある通り壁を壊せずに行けるグリッドに対してコスト0、壁を壊す必要のあるグリッドに対してコスト1の辺を張る。で、ダイクストラをやるという形。サンプルは合っているのだが11AC23TLEで、計算量を削減しないといけないっぽい。一応$O(hwlog(hw))$なので間に合うと思ったが……

D_TLE

import heapq
h,w = map(int,input().split())
grid = []
for _ in range(h):
    grid.append(input())
a,b,c,d = map(int,input().split())
start = (a,b)
finish = (c,d)
#隣接リストを作る。
G = [[] for _ in range(h*w)]
#隣が道の場合はコスト0の辺を張る。隣が壁の場合はコスト1で、隣の隣が壁の場合もコスト1の辺を張る。
#i番目の頂点はgrid[i//h][i%h]
for i in range(h*w):
    y = i//w
    x = i%w
    #grid[y][x]の左隣
    if x-1 >= 0 and grid[y][x-1] == '.':
        G[i].append((0,i-1))
    elif x-1 >= 0 and grid[y][x-1] == '#':
        G[i].append((1,i-1))
        if x-2 >= 0:
            G[i].append((1,i-2))

    #grid[y][x]の右隣
    if x+1 < w and grid[y][x+1] == '.':
        G[i].append((0,i+1))
    elif x+1 < w and grid[y][x+1] == '#':
        G[i].append((1,i+1))
        if x+2 < w:
            G[i].append((1,i+2))
    
    #grid[y][x]の上隣
    if y-1 >= 0 and grid[y-1][x] == '.':
        G[i].append((0,i-w))
    elif y-1 >= 0 and grid[y-1][x] == '#':
        G[i].append((1,i-w))
        if y-2 >= 0:
            G[i].append((1,i-2*w))

    #grid[y][x]の下隣
    if y+1 < h and grid[y+1][x] == '.':
        G[i].append((0,i+w))
    elif y+1 < h and grid[y+1][x] == '#':
        G[i].append((1,i+w))
        if y+2 < h:
            G[i].append((1,i+2*w))
inf = float('inf')
seen = []
visited = [inf for _ in range(h*w)]
visited[(start[0] - 1) * w + start[1] - 1] = 0

heapq.heappush(seen,(0,(start[0] - 1) * w + start[1] - 1)) #始点を入れる。重みを0にしておく
while seen:
    _, goto = heapq.heappop(seen)
    for factors in G[goto]:
        goal = factors[1]
        cost = factors[0]
        if goto < 0:
            print(goto)
#更新条件
        if visited[goto] + cost < visited[goal]:
            visited[goal] = visited[goto] + cost     #更新
            #ヒープに登録
            heapq.heappush(seen, [visited[goto] + cost, goal])

print(visited[(finish[0] - 1) * w + finish[1] - 1])

こんなんでもBまで解くのが早かったのでレートはプラスになっている。嬉しいやら悲しいやら……