SRM537 - 不定期プログラミング覚え書き

賞金回だったそうな、wataさんが一位だったそうな。少しでもそんなレベルに近づきたいものです。

結果報告

275-500-925回でした。

Level	ProblemName	Status	Point
Easy	KingXNewCurrency	PassedSystemTest	174.76
Medium	KingXMagicSpells	Opened	0.00
Hard	PrinceXDominoes	Opened	0.00

チャレンジなんて無かった。

Easy KingXNewCurrency

問題

二種類の通貨A,B(A!=B)を用いている、すべての商品の価格がAx+Byで表せるような国がある。
今、通貨A,Bを新しい通貨X,Y(X!=Y)に変えたいと考えた。
ただし、これまで表現できた値段はX,Yを用いても表現可であることを条件とする。
入力としてA,B,Xをもらい、Yとして実現可能な値段が何種類あるかを答えよ。
Yが無限個存在する場合は-1を返せ。
制約は $1\leq A,B,X\leq200$ であるとする。

考えたこと

よーするにAx+By = Xp+Yq となるp,qが任意のx,yに対し存在するようなYの個数を示せば良いと。これは拡張ユークリッド互除法の可能性あるな。275問題だし。
まず、X,Yを用いてA,Bを表現できない場合はYは新規通貨として採用不可。
一方、X,Yを用いてA,Bを表現を満たす場合はYは新規通貨として採用可能。
つまり、「Xp+Yq=Zを満たすp,qが存在するか否か？」をする関数f(X,Y,Z)を作って、
f(X,Y,A)&&f(X,Y,B)をYの値を変えながら調べれば良い。
じゃあこれを拡張ユークリッドの互除法とかつかって書けばいいんだな。と考える。

……
…………
……………………
無理じゃね？もしかして拡張ユークリッドの互除法じゃない？

そもそも、A200以下でX,Yが1以上であることから、Xp+Yq=Aを満たすp,qは０以上200以下である。これなら200*200の全探索しても良いだろう。
Xp+Yqで表せるAが200以下であることから、Yは1から201まで見れば十分。200*200*200ならばまだ $8*10^6$ なので計算量としても問題ない。

また、Y=201でも条件が成立するような時はXのみでA,B共に表現可能ということである。つまりYは無限個存在するということである。逆にこの時Yは任意のケースで条件が成立するから、答えとして201を返そうとするのなら-1を返す、という条件をつければ良い。

コード

  bool solve( int Y , int X, int A ){
    //return Xp+Yq = A is possible or not where p ,q >= 0
    if( Y > X ) return solve( X, Y, A );
    if( Y == 1 ) return true;
    for( int i = 0 ; i < 200 ; i++ ){
      for( int j = 0 ; j < 200 ; j++ ){
        if( i*Y+j*X == A ) return true;
      }
    }
    return false;
  }
  int howMany(int A, int B, int X) {
    int result=0;
    for( int i = 1 ; i <=201; i++ ){
      if( solve( i,X,A) && solve( i, X, B ) ) result++;
    }
    if( result == 201 ) return -1;
    return result;
  }

Medium KingXMagicSpells

問題

複数個の部屋に、アヒルが何匹かずつ生活している。
毎日部屋には不思議な呪文がかかり、当確率で

i番目の部屋のアヒルの数duck[i]がSpellOne[i] XOR duck[i]に変わる
i番目の部屋のアヒルがSpellTwo[i]の部屋に移動する。

のどちらかが発生する(SpellTwoは0~部屋数のパーミュテーションが必ず用意されている）
K日後になって0番目の部屋に居るアヒルの数の期待値を返せ。

考えたこと(未完)

SpellOneは二回連続で発生すると元の数字に戻るんだなあ。
SpellTwoは部屋数回連続で発生すると元の数字に戻るんだなあ。
これを使って何とかできないかなあ………無理っぽいなあ……
念のため普通に深さ優先探索で書いてみるけどやっぱりTLEである。ぐぬぬ…

Hard PrinceXDominoes

問題

表と裏に数字が書かれたドミノが用意されている。
このドミノを使って、一個前のドミノの裏の数字＝現在のドミノの表の数字
といった条件が成り立つようなループを作りたい。
このようなループの最大長さを求めよ。

考えたこと（未完）

多重辺を含むグラフの最大閉路問題ですねわかります。
とは言え、どう解いたらいいかなんてわからんです