Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-06-20

TCO10 R1

| 12:11 | はてなブックマーク -  TCO10 R1 - cafelier@SRM

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


500開く

  • 『XとYの2つのレジスタがあり、X命令(X:=X+Y)とY命令(Y:=X+Y)の2つの命令がのみがあるマシンがある。初期値は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 や負になることはありえないから、結局1通りしか直前の状態がない。決定的だ

  • これ要するにユークリッドの互除法的に動くから、
  • 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は当然死亡
  • フローなのか。うわーなんでこれが解けない俺
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100620
 | 

presented by cafelier/k.inaba under CC0