cafelier@SRM

TCO10 R1

SRM | 12:11 |

TCO10 R1 の成績・ソース (要ログイン) : AC/AC/WA : １週間日記書くの放置してしまったので記憶が曖昧

500開く

• 『XとYの２つのレジスタがあり、X命令(X:=X+Y)とY命令(Y:=X+Y)の２つの命令がのみがあるマシンがある。初期値はX=Y=1。与えられた目的値rを最小の命令数で作るゴルフしてください』
  • rはたしか最大10万くらいだった記憶

• rが小さければDPだなあ。
• dp[x,y] = 状態X=x,Y=yにたどり着くまでの最小回数
• を計算して min(dp[r,y] for y in 1..r-1)
• でも10万かける10万は…

• まあしかし一応、dp[x,y] を計算するには…と考えてみよう
  • お！
  • 直前の状態は dp[x-y,y] か dp[x,y-x] しかない
  • けど、0 や負になることはありえないから、結局１通りしか直前の状態がない。決定的だ

• これ要するにユークリッドの互除法的に動くから、
• min(dp[r,y] for y in 1..r-1)
• の各yに対してはO(log r)で計算できる
• てことは計算量 O(r log r) で求まる

• よし解ける
• あ、答えは最小コードの長さではなくてコード自体を返さなきゃいけないのか
• まあさっきの計算をstringでやれば…
• dp[10万,1] とか長さ10万になるしそれはいかん
• まず一週目で最小コードの長さだけ求める
• 最小値を記録したものについてだけ、文字列で求める
  • で辞書順最小を普通にとる
• これならざっと見積もって全部が最小値を記録するとしてもO(r log r log r) だし実際はもっと小さいはず。

• できた
• submit

250開く

• 『長さが同じ文字列xと文字列yが与えられたとき、距離|z-x|+|z-y|が最小になるようなzのうち辞書順最小のを見つけてね』
  • 文字列は全部小文字で、距離は文字毎の距離の和。ただし'a'と'z'の距離は1というようにリング状にくっつく

• z[i] = x[i]とy[i]の距離が13以内だとminで、13以上だと'a'
• とかそんな感じだと思うけど13と14の場合がどっちに行くかちょっと迷いそう

• こういう時は賢く書こうとせず、素直に書く方が美しいというポリシーです
• z[i] = 'a' .. 'z' を全部試す
• 左回りと右回りでx[i]との距離を両方計算してmin、y[i]との距離も同様
• の和を取ってminを採用
• 定義どうり

• できた
• submit

1000開く

• 『有向グラフが与えられる。頂点0を通るサイクルを何個か書いて、全部の頂点をたどりたい(0以外は一度ずつしか通らないこと)。そのとき、サイクルの個数*F - 通ったエッジコストの和、を最大にしたい。どうしましょう』
  • たしか50頂点まで

• うおー？巡回セールスマン問題を含んでたり…はしないのか…？
• わからん
• わからんけどみんな解きまくってる
• でもわからん
• いい加減解法でも書いてみるか
  • 0-1-0, 0-2-0, 0-3-0, ...
  • という全部別個に回るツアーから始める
  • ツアーをマージした方が良さそうならマージする
  • というのを改善できなくなるまで繰り返す
  • クラスカルのMSTみたいな感じ
• 書けた
• なんとなくサンプルが通った
• 絶対間違ってる気がするけど出しちゃえ
• 出した

感想

• 1000は当然死亡
• フローなのか。うわーなんでこれが解けない俺