cafelier@SRM

SRM427 Div1

SRM | 22:26 |

SRM427 の成績・ソース (要ログイン) : AC/AC/AC : はじめて全完できた。嬉しい

250 開く

• 『自転周期 D 時間・公転周期 Y 時間の惑星で、うるう年（普通の年より日数が1多い年）を適宜入れてうまくつじつまをあわせると、最小で何年周期でうるう年パターンが一周するようになりますか』
• 問題はすぐ読めた

• Y/2 < D < Y の時って一体どういうことになるんだろうか？などとそんな惑星に暮らした気分になって混乱したりする
• 混乱が収まらないので式で書いてみることにした
  • 周期内で、普通の年が n 回、うるう年が m 回、普通の年の日数が x 日、うるう年の日数が x+1 日とする
  • D*x*n + D*(x+1)*m == Y*(n+m)
  • 式変形: D*x*(n+m) + D*m == Y*(n+m)
  • これを満たす n+m の最小値を求めればOK

• 式によると、Y*(n+m) は D の倍数だなー。そりゃそうか
• とすると Y*(n+m) は少なくとも lcm(Y, D) か。
• とりあえず考えるの面倒だから lcm(Y, D) / Y == D / gcd(Y, D) を返すプログラム書いてみた
• サンプル全部通った
• めんどくさいからsubmitしちゃえ

600 開く

• digという関数が定義されてる。10進表示で全桁の和をとる関数だ。（※ これは勘違いだったことはあとで判明）
• 『初期位置 (0,0) から北にdig(1)歩、東にdig(M)歩、南にdig(M^2)歩、西にdig(M^3)歩、以下繰り返し……で K 回くりかえした後どこにいるか求めましょう』という問題

• Kが最大10億なのでストレートに実装すると絶対死ぬね。高速ベキ乗に落とせるか、どっかで必ずループに入るのか…
• 並べ替えると 北にdig(1)+dig(M^4)+dig(M^8)+...歩、東にdig(M^1)+dig(M^5)+...歩、だなあ。等比数列？和の公式？？
• M=2 や 3 の場合の最初の方の値を手計算してみる。ダメだ。全然規則的な数列に見えない

600があまりにもわからないので250まで不安になってきた

• 再考
  • n+mをさっきの値に固定したとき、n or m と x を動かしてちゃんと D*x*(n+m) + D*m == Y*(n+m) にできるだろうか？
  • 左辺は D*(x*(n+m) + m) だから x*(n+m) + m を調整して lcm(Y,D)/D にできればいい。
  • これは、lcm(Y,D)/D を n+m で割った商と余りを x と m にすればいい。常に可能。よし合ってる

600 に戻る

• 相変わらず全くわからない。
• 600 ってことは普段の 500 より難しいわけで、ここはむしろ捨てて普段の 1000 より簡単なはずの 900 に向かうべきではないか
• 悩む
• うむむ

• よく見たら dig は全桁の和をとる作業を『1桁になるまで繰り返す』関数じゃないか
• 改めて M=2 や 3 の場合を手計算。なんと dig(M^k) の数列は思いっきりループしている！

• でも何故ループするのか全くわからない
• しかし a,b<=1000 で実験してみると、どうも dig(a*b) == dig(dig(a)*b) が成り立っているようだ
• これが成り立つならループする。dig(n) の値は10通りしかないし、上の等式が成り立つならdig(M^k+1)は直前の値dig(M^k)にのみ依存するので。

• これはもう、よくわからないけどループするものとしてコード書くしかない！
  • ループ部分全体でまとめてどっちに何歩進むか求めておけば、K 回で進む分は掛け算一発で求まるので速い
  • ループ長さは高々10なので、ループ１回で進む距離や余りの部分は、普通にfor文回して足し算しておーけー。
• サンプル通った。submit。

900 開く

• 『整数のリスト S と自然数 p が与えられる。隣り合う要素の差がpの倍数に決してならないような並べ替え方は何通りあるか』

• 第一感ではなにも思いつかない
• とりあえず「隣り合っていいよ関係」を辺にしてグラフなど描いてみるか
  • このグラフで言うと、問題はハミルトンパスの総数だ
  • はい無理
• て、書いてみて気づいた。p|(a-b) で p|(b-c) なら p|(a-c) だから、「隣り合ってはいけません関係」なら同値関係だねそういえば
• てことは同値類の要素どうしを区別する意味はあんまりない
  • ...p+k...2p+k... という配置が可能なら常に ...2p+k...p+k... という配置も可能なので。どれでも似たようなもの
• ……
• ……
• 解けた！

• まずpで割ったあまりで入力リストの要素を同値類分解する
  • それぞれの同値類の要素数を X[0], ..., X[p-1] とする
• それぞれの同値類内部の並べ替え方は、X[0]! * X[1]! * ... * X[p-1]! と階乗で求まる
• 同じ同値類の元を同一視する場合、全体の並べ方は要するに、『赤色ボールが X[0] 個、青色ボールが X[1] 個、…、紫色ボールが X[p-1] 個、あります。同じ色のボールが隣り合わない並べ方は？』ってな問題と同じことだ。
  • 解けた！といいながらこの部分問題の解き方思いついてない
  • うまい式で計算できるかな？思いつかない。ま、メモ化探索で間に合うでしょ多分。それで解けなきゃこの問題絶対解けないよ

• メモ化探索書く
  • 個数リストが {X[0], X[1], ..., X[p-1]} の場合の並べ方は、一番左にどの色のボールを使うかで場合分けして、{X[0]-1, X[1], ..., X[p-1]} の並べ方 + {X[0], X[1]-1, ..., X[p-1]} + ... みたいな再帰…だと思ってそのまま実装
  • サンプル通らないよー
  • 隣り合っちゃいけないって条件どこでも加味してないじゃん
  • 慌てて、引数を「個数リスト{X[0], X[1], ..., X[p-1]} と次に置いちゃいけない色 f のペア」に変えて再帰
  • サンプル通った！

• 最悪ケースの状態数ってどんなもんかな。
  • 真ん中辺りがやばそうだから同値類の元の数が 5+5+5+5+5+5 の時とか。
  • この場合状態数は 6^7 だから行けるような気がする。submit！

時間まだある

• 落ち着いて、最悪ケースの状態数もっと真剣に考えておこう
  • 2+2+...+2 だと 3^15*15 になるぞ。pair<vector<int>,int> がメモ化のキーとかですごい遅いから、これはヤバイ
  • そのケース {0,2,3,...,29}, p=15 を動かしてみた。帰ってこない。これはやばい。直さねば
  • (※あとで思ったんですが 1+1+...+1 で 2^30*30 の方がもっとまずいですかね）

• やっぱり賢い数式あるんじゃない？
  • 全部でM個のうちX[0]の置き方は M_C_X[0] 通り。残りM-X[0]個からX[1]の置き方は (M-X[0])_C_(X[1]) 通り。……って掛け算していくだけでよいのでは。mod があるときの Combination の計算が一見面倒そうだけどたぶん long long におさまる範囲。
  • 書いた。サンプル合わないよー
  • って、隣り合うの禁止って条件また忘れてた！！！！

• 賢い式は無理だ。なんとかしてメモ化再帰を高速化すべし
  • つまり状態数を減らす。実は同じ答えを返す状態がないか。あったら融合させる。
  • あ、{1,1,2},f=2 と {1,2,1},f=1 って状態、意味的には同じだよね。ボールの個数だけが問題で順番はどうでもいい。
  • てことは個数リストは常にsortしておけばオーケー！

• 実装
  • さっきの最悪ケース（{0,1,2,3,...,29}, p=15）も一瞬で終わった！
  • おおざっぱに楽観的に考えてsortしたら状態数 1/p! くらいに減ってくれるだろうから 3^15*15 をそのくらい割ればいくら何でも大丈夫だろうと期待
  • 時間ももうないし、resubmit！

撃墜タイム

• 嬉々として {0,1,2,3,...,29}, p=15 を打ち込む準備をしてました。sort してない人がいたら即叩き込む！
  • 全員 sort してた
• 600点問題で、digを毎回とらずにdig(M^k)のためのM^kをそのまま計算してる人がいらっしゃる
  • M≦1000なので、ループ長7以上あったらlong longあふれるんでは？と思って手元でそういうMを探す
  • ない
  • どうも6以内に必ずおさまるらしい。へー
• でも同じ人のコード、ループが途中からはじまるケースを考慮してないような…
  • と考えてデータを用意してるうちに先を越されて撃墜されてしまった

感想

• dig(n) って n%9 (ただし余り0の場合は9) なんですね！確かに1も10も100も9で割った余りは1だから、全部1の位に落としたところで9で割ったあまりは変わらない。なので一桁になるまで繰り返すと、まさに9で割った余りが出てくる。

• これなら掛け算や足し算と可換性があるから、なるほど dig(a*b) == dig(dig(a)*b) が成り立つわけだ…