Hatena::Grouptopcoder

cafelier@SRM

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

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

 | 

2009-12-06

SRM454

| 04:25 | はてなブックマーク -  SRM454 - cafelier@SRM

SRM454 の成績・ソース (要ログイン) : AC/AC/- : 惜しかった

500開く

  • 『7segのデジタル表示の形にマッチ棒を置いてNという数字が書いてあります。マッチ棒をK本以下動かして作れる別の数字は何個ありますか』
    • ただし桁数変えちゃだめ
    • 頭が 0 になるのはOK
    • N は long long におさまる程度
    • K <= 126

  • えーと。
  • 典型的なダイナミック計画法。

  • まず一番左の文字をどれに変えるか(もしくは変えないか)全通り試してみる
  • で、もとの形と比べてマッチ棒が何本少ないか(多いか)数える
  • K本少ない作り方がdp[-K]通り、...、1本少ない作り方がdp[-1]通り、同じ本数のがdp[0]通り、...、K本多い作り方がdp[+K]通り
  • っと表で覚えておく。
  • …という表を左から順に、各文字で変え方考えながら更新していったら、
  • 最後に過不足無くマッチの本数があってるdp[0]が答え

  • 書いた
  • はい全然サンプルと答えがあいませーん

  • これだと 68 を 86 に変えるパターンが dp[0] に記録されるから、
  • つまりマッチを一本も動かさないでできることになっちゃってる。
  • これはダメだ。
  • 少ない方と多い方を別々に数えなければ
    • 元の形と比べてマッチ棒がm本増えててf本減ってるパターンは dp[m][f] 通り
    • という表で数える
    • 答えは Σdp[i][i] for 0<=i<=K

  • K*K*18 くらいだから実行時間も問題ないはず
  • 書いた

  • 最大ケースも時間は十分だし、答えもだいたいあったけど
  • 1個だけあわない。なんで?
  • あ、leading zero は allowed か!(※この時点まで勘違いしてました)
  • 修正修正

  • よし、サンプル通った。submit

  • で、7セグのパターン手打ちを間違えてないか一応確認しておこう…
  • どうやってチェックしようか
  0
 1 2
  3
 4 5
  6 
  • という順で文字列にエンコードしたんだけど、
    • 0 なら "1110111" で…と
    • 文字ごとに作るんじゃなくて、セグメントごとに作って
      • つまり 0 番の横棒を使ってるのは 0 と 2 と 3 と …
      • 的に作ったのとあってるかどうかチェック
  • あってた
  • まあ大丈夫ということにしよう

250開く

  • 『double xor ^^ という演算を考えます。10進数の各桁を普通のxorする(ただし10を越えたら%10)演算です。入力Nに対してN ^^ N-1 ^^ N-2 ^^ ... ^^ 1を計算してね』
    • Nは100万まで
    • ^^ は左結合です


  • 100万までなら、普通に100万回ループして計算するだけだな
  • えーと、^^ の計算も、まあ普通に10進の各桁を計算して…

  • できた
  • サンプル通った
  • submit

  • 念のため小さいNは網羅的にテストしておくか
    • 一桁のときはただの普通のxorだよね
    • 1,2,3,4,5,6,7,...
    • あれ?
    • 1^2^3^4^5^6^7^8 = 8 なのに自分のルーチンは 2 を出す
    • なにか間違えたかな?

    • double xorはともかく、xorは結合律満たすから、ちゃんと8^7^6^5^4^3^2^1の順で計算しても同じだよなあ…
    • 念のため手計算…

    • あ! 8^7 は 15 だから %10 されて 5 になるのか
    • 普通の xor と違うじゃん。合ってる合ってる。

    • よかったよかった。
    • しかしこれは撃墜に使えそう
      • %10 を忘れると N=8 で間違える
      • 右結合で計算すると N=8 で間違える
    • これは絶対大量にいるはず…

1000開く

  • 『こんな規則
 1 2 9 10
 4 3 8 .
 5 6 7 .
  • に2次元平面を数字が埋めてます。数字 X の書いてあるマスより左上にある数字全部の総和をS(X)とします。入力Nに対してNの左上のS(X)の総和を求めてね。mod 1000000007で。』
    • N≦10^10

  • むむむ?1000にしては簡単じゃね?
    • 点(y,x)はmin(y,x)列目にのっている、と列を定義すると、
    • 1以下なら1列目、4以下なら2列目、9以下なら3列目、n*n以下ならn列目、
    • だから、平方根とればNが何列目に載ってるかはすぐわかる。
    • すると、Nの具体的な座標(Ny,Nx)もすぐわかる。
    • すると、各列ごとには数字は連続してるから、
      • 列の中で(Ny,Nx)より左上にあるものの総和、もちょっと場合分けすれば分かる
      • 列はsqrt(N)くらいまで考えればいいから計算量的にこれで間に合う

  • 500も簡単だったし、最近は簡単めにする傾向なのかも。
  • よしやるぞ

  • 「ちょっと場合分け」にすさまじく手間取ったけど、できた
  • サンプル通らない~

  • なぜだ。
  • 手計算してみたS(N)とプログラムの答えもちゃんとあってる…
  • !!!
  • 違う!求めるのはS(N)じゃなくてそのさらに総和だった!

  • やり直し。
  • といっても、総和の総和になっても
    • N自身は1回だけ足される
    • Nの(i,j)左上にあるマスの数字は(i+1)*(j+1)回足される
  • と重みがかかるだけの総和
  • この重みは各列の上では線形だから、
    • 列の中で(Ny,Nx)より左上にあるものの重み付き総和、は
    • 2次の数列の和の公式 1/6 n(n+1)(2n+1) とかで O(1) で求まる系

  • やっぱりできそう。やるぞ!
  • また場合分けにすさまじく手間取っているうちにタイムアップorz

撃墜タイム

  • 250で、右結合してる人ひとり、%10忘れひとり撃墜

感想

  • 奇跡的に6位。過去最高ランクです。やった!年内に2500に戻す目標に首の皮をつなげた…
  • ただ、1000に手間取りすぎだなあ。
    • 平面上の点の扱いで、(x,y) と (y,x) がほぼ対称な場合に対称性をうまく利用してコードを整理するのができない。やたらと場合分けしてしまう。なんとかしたい。
    • いや場合分けでいいのかもしれないけど、その場合も自分の頭が混乱しないように整理する考え方を…
トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20091206
 | 

presented by cafelier/k.inaba under CC0