3問でした。Dに1時間使えそうだったので「落ち着いてやれば大丈夫」と素朴解法を実装して状態遷移図を作り始め、残り15分くらいでミスに気づいて落ち着きを失ってアウト(苦笑)
- どのタイミングでビルを移ってもコストは変わらないのだから最初に移ると考えて良い
- ビルを移った後の上下移動に、廊下を使うコスト2xの方法と階段を使うコストyの方法がある。どちらが安いのか判断して安い方を使う 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を超えない最大の三角数を求める問題
- であるようなxを求める問題になる 三角数 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回勝敗判定すれば良いので富豪的に解いた python
def solve(N, K, S):
last = [0 if c == "R" else 1 if c == "P" else 2 for c in S]
match = [0, 1, 0, 1, 1, 2, 0, 2, 2]
for _k in range(K - 1, -1, -1):
next = []
for i in range(0, 2 * N, 2):
next.append(match[last[i % N] * 3 + last[(i + 1) % N]])
last = next
return "RPS"[last[0]]
- 1時間使えそうだったので「落ち着いてやれば大丈夫」と素朴解法を実装して状態遷移図を作り始め、残り15分くらいでミスに気づいて落ち着きを失ってアウト(苦笑)
- 「最低2手でどの向きにもなれる」「3手以内に解があるかを探索して、なければ2手以下で平行移動に都合のいい向きになって2手以下で戻れば良い」と考えてたけど、途中で都合の良い向きが変わるケースがあるのでは？と気づいて以下略
- 考えたこと
- 中心の位置と4方位で状態遷移図を作ろう
- 小さい範囲の状態遷移を手で描いてみる
- ミスしそう
- 1ステップ後の遷移先を出力するコードを作った
- 各状態7つの状態に遷移する
- 2ステップでどの向きにもなれる
- 3ステップ後まで前計算しておいて、それに含まれない4ステップ以上の解なら、スタートから2ステップ、ゴールから2ステップ、間は姿勢を維持して移動、で行けるだろう…行けるか？？
- 公式解説
- 初期状態から1〜3ステップ後にどの状態にいるかを求めるコード( step→(position, rotation) )は作ったのだが、それを反転させたもの( (position, rotation)→step )を観察することは思いつかなかった
- 値域と定義域の交換