ARC109

3問でした。Dに1時間使えそうだったので「落ち着いてやれば大丈夫」と素朴解法を実装して状態遷移図を作り始め、残り15分くらいでミスに気づいて落ち着きを失ってアウト(苦笑)

https://gyazo.com/d2eb8e41a1e38f0e23cc2c8254dd5a8a

https://gyazo.com/e6a070f0d5974b30af3ad656f0bdda8c

どのタイミングでビルを移ってもコストは変わらないのだから最初に移ると考えて良い

ビルを移った後の上下移動に、廊下を使うコスト2xの方法と階段を使うコストyの方法がある。どちらが安いのか判断して安い方を使う

code:python

def solve(a, b, x, y):

ret = x

if b < a:

a -= 1

if 2 * x < y:

up = 2 * x

else:

up = y

ret += abs(a - b) * up

return ret

小さい方から考えて行って1〜5が欲しい時に6を買って1+2+3に分割するとお得だと気づく

つまりn+1を超えない最大の三角数を求める問題

code:python

def solve(N):

from math import sqrt

x = int(sqrt(2 * N + 2)) - 1

if (x + 2) * (1 + x) // 2 <= N + 1:

x += 1

return N - x + 1

平方根を取ることが精度的にアリなのかは怪しい

Nが10^18で、倍精度浮動小数点数の仮数部が52ビット、10進で16桁未満なので単純に計算すれば当然精度が足りない。

なので1つ増やしたものが解であるかどうか確認してるわけなのだが、これで本当に十分であるかはきちんと考察してない。

減る方向にズレるケースがあるのかないのか。

Sが周期的なのだから勝負の結果ももちろん周期的

細かい計算節約をしなくてもたかだか10000回勝敗判定すれば良いので富豪的に解いた

code:python

def solve(N, K, S):

for _k in range(K - 1, -1, -1):

next = []

for i in range(0, 2 * N, 2):

last = next

1時間使えそうだったので「落ち着いてやれば大丈夫」と素朴解法を実装して状態遷移図を作り始め、残り15分くらいでミスに気づいて落ち着きを失ってアウト(苦笑)

「最低2手でどの向きにもなれる」「3手以内に解があるかを探索して、なければ2手以下で平行移動に都合のいい向きになって2手以下で戻れば良い」と考えてたけど、途中で都合の良い向きが変わるケースがあるのでは？と気づいて以下略

考えたこと

中心の位置と4方位で状態遷移図を作ろう

小さい範囲の状態遷移を手で描いてみる

ミスしそう

1ステップ後の遷移先を出力するコードを作った

各状態7つの状態に遷移する

2ステップでどの向きにもなれる

3ステップ後まで前計算しておいて、それに含まれない4ステップ以上の解なら、スタートから2ステップ、ゴールから2ステップ、間は姿勢を維持して移動、で行けるだろう…行けるか？？

公式解説

初期状態から1〜3ステップ後にどの状態にいるかを求めるコード( step→(position, rotation) )は作ったのだが、それを反転させたもの( (position, rotation)→step )を観察することは思いつかなかった