ARC109
3問でした。Dに1時間使えそうだったので「落ち着いてやれば大丈夫」と素朴解法を実装して状態遷移図を作り始め、残り15分くらいでミスに気づいて落ち着きを失ってアウト(苦笑)
どのタイミングでビルを移ってもコストは変わらないのだから最初に移ると考えて良い
ビルを移った後の上下移動に、廊下を使うコスト2xの方法と階段を使うコストyの方法がある。どちらが安いのか判断して安い方を使う
pythondef 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を超えない最大の三角数を求める問題
pythondef 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回勝敗判定すれば良いので富豪的に解いた
pythondef 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 )を観察することは思いつかなかった
Related Pages
- →atcoderエントリーポイント×atcoder失敗リスト×二分探索チェックリスト×列に対して決まる値→列の区間でdp×最大化を二分探索で×実数に対する大小判定×値域と定義域の交換×最小カットに帰着×競技プログラミングで解法を思いつくための典型的な考え方×問題変換→
- →帰着する力×小さい制約の問題×nが8前後の制約×nが10~20前後の制約×n_が_30~40前後の制約×n_が_50前後の制約×n_が_300~500前後の制約×n_が_1000_前後の制約×小さな定数に注目×変数を一つ固定する×3つのものの真ん中を固定×行列の半分×xとyにわける×操作の不変量に注目×偶奇に注目×偶奇で場合わけ×操作の順番によらない×時間軸反転×元に戻せる操作×左右から累積積×等差数列の加算は差に注目×区間反転の合成はxor×grundy数×余事象を引く×k番目の数を二分探索×xorは繰り上がりのない足し算×xorは桁ごとに分割可能×45度回転×差の最小化は中央値×代表的なグラフで考察×木は二部グラフ×木の直径×最大化を二分探索で×選択肢が少ない方から貪欲×二次元座標を二部グラフにする×順序を有向グラフにする×凸関数の極値は三分探索×単調増加ならしゃくとり法×等比数列は剰余に注目×n進数は剰余に注目×括弧列は上り下り×競技プログラミングで解法を思いつくための典型的な考え方×keyence2020_d×abc152_f×agc026_c×arc060 a×joi2008ho_c×abc034d×abc138e×abc023d→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]