cafelier@SRM

SRM454

SRM | 04:25 |

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 くらいだから実行時間も問題ないはず
• 書いた

• 最大ケースも時間は十分だし、答えもだいたいあったけど
• １個だけあわない。なんで？
• あ、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万まで
  • ^^ は左結合です

• ちょうどついさっきD言語に^^という演算子が増えたというニュースを見たばっかりだったのでちょっと面白い

• 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 .

• に２次元平面を数字が埋めてます。数字 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) がほぼ対称な場合に対称性をうまく利用してコードを整理するのができない。やたらと場合分けしてしまう。なんとかしたい。
  • いや場合分けでいいのかもしれないけど、その場合も自分の頭が混乱しないように整理する考え方を…