cafelier@SRM

SRM428 Div1

SRM | 23:44 |

SRM428 の成績・ソース (要ログイン) : AC/AC/- : 読んでて反省することしか見つからない思考ログ

250 開く

• 『文字列sの並び替えで、同じ文字が連続しないようなのは何通り？』

• SRM427の900の後半のルーチンそのまんま使えるんじゃないか！
  • 自分の過去ソース漁り始める

• 5秒後に我に返る。『sは10文字以下』って書いてあった
  • "梅干し⇒唾液"なみによく知られている反射反応として、"10要素の並び替え⇒next_permutation"、があります
  • というわけでnext_permutationするだけのコードを書く

• 要素に重複あるときのnext_permutationってどうなるんだっけ？
  • とりあえずsetに全部突っ込んどくか念のため

• 10秒後に我に返る
  • いや落ち着け重複無く列挙されるに決まってるよ。逆に重複込み列挙するアルゴリズムの方が組むの大変だよ
  • setとか要らんコード削除

• サンプル通った。
  • 一応最悪ケース（10文字全部違う場合）を確認しとくか…
  • サンプルにあった。余裕で大丈夫だ。submit

500開く

• 『アルファベット26種のうちk種類以下を使うような文字列長n以下の回文は何通り？mod 1234567891で。』

• とりあえず回文の個数を考える。
  • 半分まで自由に決められて、残り半分は反転で自動的に決まるから、
  • 文字種i、長さ2nの回文は i^n 通り。文字種i、長さ2n-1の回文も i^n 通り。

• ということは、だいたい大ざっぱには
  • Σi=1..k ( 26Ci * (i^1+i^1+i^2+i^2+...+i^n/2) )
  • だろ
  • 文字の種類を1～kまで全部考えて、26文字からの選び方は26Ci通りで、あとは1文字,2文字,…,n文字、の回文の個数の和
  • 絶対に重複カウントしてるけど、まあ、その辺はめんどいので、とりあえず後で考える
    • n が最大10億なので、こういう風に式を建てて解く以外の方針はありえないはず。根本的な方向は合ってるはずなので適当に踏み切ってよいと思ったのだった

• modで累乗やnCk演算をする必要があるな。自前ライブラリからコピペコピペ
  • ところでこの1234567891って素数だろうか。素数じゃないと割り算しにくいからめんどいぞ
  • 2から1000000までの数で割ってみたら割り切れなかった。よし素数だ。

• i^1+i^1+i^2+i^2+...+i^n/2 の部分は等比数列の和の公式を思い出す
  • (末項 - 初項) / (公比 - 1) とかだっけ。たぶんそんなんだ。

• さっきの大ざっぱなヤツ組めた
  • えーと、重複は…「文字種i、長さ2nの回文は i^n 通り」って言ったときに、iより少ない数の文字しか使ってないパターンも含んでしまってるのがヤバイ。
  • 文字種i-1の回文の個数に iC(i-1) くらいかけて引いておけば「ちょうどi個使う場合の数」になるんじゃないかな？
  • あ、i-2, i-3, ... と繰り返さないとダメか
  • 繰り返した
  • 動かしてみる。落ちた。
  • あー等比数列の和、公比が1だとゼロ割してるなーそこだけ特別扱い

• でも答え全然合わない
  • てか、基本的に全部 0 になっとる
  • とりあえずわかりやすいとこからバグ出しだ。等比数列の和の公式ルーチンを単体テスト
  • 公比1～4、項数3～4 辺りをテスト
  • 思いっきり間違ってる
  • 末項 - 初項、ってどう考えても項数1のとき0になっておかしいですがな
  • 落ち着いて考え直す。1-k^(n+1) の因数分解が (1+k^1+...+k^n)(1-k) になるのが公式の由来なはずだから云々かんぬん
  • 直った

• でも答え全然合わない
  • 色々あれやこれや試行錯誤（※何やったか覚えてない

• でも全然答え合わない
  • もう捨てて1000点問題行くかなー
  • 部屋のスコア表開いてみたら、こんな時間(50分くらい経過)になってもまだ1人しか500をsubmitしてない。苦戦してて問題ないっぽい
  • 500に戻ろう

• ちょっと落ち着いてサンプルを手計算で解きなおそう
  • n=3, k=2 の例
  • 文字種1長さ1: 26通り、文字種1長さ2: 26通り、文字種1長さ3: 26通り
  • 文字種2長さ1: (なし)、文字種2長さ2: (なし)、文字種2長さ3: 26*25 通り
  • これで答え(728)とあう

• この (なし) の部分考えてなかったなー。そりゃ合わんわ。
• あと 文字種2長さ3 の部分がどうやったらこの値になるのか
  • 自分の式の重複考えないバージョンだと 26C2 * 2^2 = 26*25*2 通り
  • ちょうど2種類つかうパターンは 2^2 通りじゃなくて 2 通りだから答えはその半分なんだよなー。えーと
  • (選んだ2種のうち1種類使う使い方 = 2C1) * (文字種1長さ3の作り方 1^2) = 2 通り分少ないからこうなってる。
  • そうだそうに違いない

• ↑の式を一般化して実装。
  • answer = r(1)+r(2)+...+r(k) where // ちょうど1種類使う場合+...+ちょうどk種類使う場合
  • r(i) = C(26,i) * (gss(i,i,n) - C(i,1)*gss(1,i,n) + C(i,2)*gss(2,i,n) - ...) // 包除原理だっけ
  • gss(b,i,n) = b^i + b^i + b^(i+1) + b^(i+1) + ... + b^(n/2) // これは和の公式で求める
• サンプル通った。
• もう疲れたsubmitだ。

1000開く

• 15分しかないぞー
• 『XとOとLからなる16文字以下の文字列でゲームをします。プレイヤーは交互にXをOまたはLに書き換える。"LOL" (読み:ワロス) って部分文字列を作った方の勝ち。初期状態が与えられたとき最適プレーしたら勝てるか負けるか引き分けるか判定せよ』
  • 勝てるときは最短手数を返せとかそんな感じ（ちゃんと読んでない

• えー状態数は 3^n で各状態で可能な手は高々 n 種類だから O(n*3^n) で全部ブン回せば解けるんじゃないのか
• えい考えてる時間はない組むぞ

• 組み終わった
• 答え全然合わない
• 時間切れ
• おわた

撃墜タイム

• next_permutationする前にはsortしておかないと全部列挙されないのだけど、今回用意されたサンプルはたまたまsortしなくても全部正しい答えがでてきてしまう。ということできっとsortしてない人が一人はいらっしゃるに違いない。"dcba" 打ち込み準備おーけー
  • 今日も全員 sort してた
    • 正確には一人 sort してない人がいたっぽいのだけど先を越された
• あとは個数カウントしてる人やビットDPしてる人のソースを丹念に読めども特にバグもみつからず

感想

• nCk の計算って別に割り算無くてもパスカルの三角形で求めればいいのか。なるほどー、と人のソースを見て思った。というか今回高々C(26,13)だから最後にmodとるだけで十分だ。
• 等比数列の和もどうにかなるかな
  • 行列のベキ乗に落とせばいいのか。ふむー
• 全体的に、もっと落ち着いて解くべきだ自分は。

• 250でadjacent_findしなかったのはSTLマニア失格もいいところ
• 500は行列乗算になるのか。なるほどなあ
• あ、そうか、素数ならb^(p-1)≡1 mod p だから /b は *b^(p-2) なのか。gcdなんて要らない