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

青コーダーと黄コーダーの間を彷徨う社会人プロコン勢が余力のあるときに復習した内容をまとめるブログ

TCO2014 R2B

350-500-900とか350諦めて500目指すのワンチャンあるか？　とか思っていたら350も激ムズだったし500は問題文の意味が解らなくて0点レート急降下回。
350のチャレンジとかもうチョット頑張れたりしたんだろうか。Failed System Testの人は何人かいたのだけれど。

Level ProblemName Status Point
Easy SwitchingGame Failed System Test(Practiced) 0.0
Medium SumAndProductPuzzle Opened(Practiced) 0.0
Hard --- Unopened 0.0

Easy SwitchingGame

問題

すべてオフになったN個のランプがある。
L番目に満たすべきランプの状態を+(ランプがON),-(ランプがOFF),?(どちらでも良い)からなるstring配列states[]で表現する。
ユーザは以下の操作を繰り返して与えられた条件statesを順番にクリアしていきたい

  1. ONのランプを複数個選択して一気にOFFにする
  2. OFFのランプを複数個選択して一気にONにする
  3. 現在のランプが満たすべき条件を満たすかチェックする

最小の操作数を求めよ

考えたこと

な　ん　や　こ　れ！
とりあえず、li個の条件をクリア済みとした時に、
ni番目のランプの満たすべき条件states[li][ni]が +の時や-の時は何やかんやすれば良さそうなので、
states[li][ni]が?である場合を中心に考えることにする。
もっとも、states[li][ni]が?だとしても、将来的にni番目のランプが充たさなければいけない状態と現在のランプの状態が一緒ならば、
そのランプについては常に状態を保存すれば良いので考えなくても良い。
よって、一番厄介なのは states[li-1][ni]が+、states[li][ni]からstates[li+X-1][ni]が?、states[li+X][ni]が-の時(または+-が逆の時)というケース
さらに、この場合でも、他のランプの状態具合に変更 li-1+k個の条件をクリアした段階で+から-へと変更せざるを得ない時は、
便乗してランプの色を変えれば良い。
以上の操作をして、残ったケースについて最適なランプ変更タイミングを考えれば何とかなりそう。
…ケース集合とクリア状況集合の二部グラフとか作って最大フローとか流せばいいんですか？（←間違い）
ゴリッと書いてSummaryチラ見したらみんな早々に提出してて絶望しつつsubmitする
→落ちた＼(^o^)／

復習

フローとか流さないで極力状態保存するように粘る貪欲でおｋだった…orz
と言うかフローで最適なランプ変更タイミングが出せるかというとそんなことは全然なかった。
あと極力状態保存する貪欲で何か問題が発生することも無かった。

コード(system test通過済み)
   int timeToWin(vector <string> states){
     vector<string> S;
     int L = states.size();
     int N = states[0].size();
     string start(N,'-');
     S.push_back( start );
     for( int i = 0 ; i <(int)states.size(); i++ ) S.push_back( states[i]);
     bool sw[L][2];
     memset( sw, false, sizeof(sw));
     for( int li=0; li < L; li++ ){
      for( int ni=0; ni<N; ni++ ){
        if( S[li][ni] != '?' && S[li+1][ni] != '?' &&  S[li][ni]!=S[li+1][ni] ){
          if( S[li][ni] == '+' ) sw[li][0] = true;
          else sw[li][1] = true;
        }
      }
     }
     int ans = L;
     for( int i = 0 ; i < L ; i++ )
       for( int j = 0 ; j < 2; j++ ){
        if( sw[i][j] ) ans++;
       }

      for( int li=1; li <= L ; li++ ){
      for( int ni = 0 ; ni < N ; ni++ ){
        if( S[li][ni] == '?' && S[li-1][ni]!='?' ){
          char s = S[li-1][ni];
          int curL = li;
          while( curL <= L && S[curL][ni] == '?' ) curL++;
          if( curL > L || s == S[curL][ni] ){
            for( int l = li ; l < curL; l++ ) S[l][ni] = s;
          }
          else{
            int bit = 0;
            if( s == '-' ) bit = 1;
            if( sw[li-1][bit] ){
              S[li][ni] = S[curL][ni];
            }
            else{
              S[li][ni] = s;
              if( li+1 <= L && S[li+1][ni]!='?'&&S[li+1][ni]!=S[li][ni] && !sw[li][bit]){
                ans++;
                sw[li][bit]=true;
              }
            }
          }
        }
      }
      /*
      for( int ni = 0 ; ni < N; ni++ ){
        cout << S[li][ni];
      }
      for( int bit = 0 ; bit < 2; bit++){ cout << sw[li-1][bit]<<" ";}
      cout << endl;*/
     }
     return ans;
  }

Medium SumAndProductPuzzle

問題

数学者SusanとPriscillaがいた。
Susanは二つの数x,yの総和x+yを持っており、Priscillaはx*yを持っていた。
Susanが「ふふふ…私の持っている数を特定することはできまい( ･´ｰ･｀)」
とドヤ顔したところ、Priscillaはこの発言によってSusanの数字を特定することができたという。

このような会話が成立するSusanの持つ数字Sで、A以上B以下であるものの総和を返せ。

考えたこと

SusanとPriscillaの会話をどう解釈したらいいのかわけわからんのだが詰んだ

復習

TLを眺めていたところ、どうやらこう言う意味だったらしい。

これらの発言を読んだ上でもまだ解法とか色々解っていなかったんですが、少なくとも以上２ツイートのお陰で問題の会話の意図が以下だと理解しました。
Susanが持っていた数Sを分解したとき、a(S-a)は常に合成数であるため、SusanはPriscillaが自分の値を特定不可能と考えた。
しかし、Priscillaが持っていた数字をMとすると、M=x*yを満たしx+yが上の条件を満たすx,yの組合せはひとつしか存在しなかった。
数学っぽく書くと、このような会話が成立するSusanの手持ちSとは、
Q(S)\wedge( \exists M ( (\exists x, R(M,x)) \wedge (\forall x \forall x2, (R(M,x)\wedge R(M,x2))\to x=x2) \wedge (\forall x, R(M,x) \to x+M/x=S) ))
Q(S)=\forall a, S-a\geq a \to a(S-a)は合成数
R(M,x)= (M \% x = 0)\wedge (M/x\geq x) \wedge Q(x+M/x)
ということである。これを少しずつ解けそうな雰囲気まで持っていくのが今回の問題。

まず、Q(S)を簡単にする。a>=2の時a(S-a)が合成数なのは自明なので、Q(S)はS-1が合成数であると書き換えても構わない。
これを新たにP(S-1)と表記することにする。

次に、\exists x R(M,x)を満たすMは少なくとも合成数である。
何故ならば、Mが素数であったとすると、Mは1*Mとしか乗算に分解できないが、Q(1+M)は1+M-1が素数であることよりR(M,x)の三番目の条件が成立しないからである。
一方、Mが合成数とすると、x=1は1+M-1が合成数であることよりR(M,x)を成立させるとわかる。
このことより、後半の条件は、 (\forall x, x\geq 2 \to not R(M,x)) \wedge M+1=S と書き換える事ができる。
以上のことから、Sの満たすべき条件とは、
P(S-1) \wedge \exists M,( P(M)\wedge (\forall x, x\geq 2 \to not R(M,x))\wedge M+1=S)
すでにMとSの関係が得られているのでM=S-1を代入して
P(S-1)\wedge (\forall x, x\geq 2 \to not R(S-1,x))
これを計算すれば良い。
Pの判定はエラトステネスの篩をつかえばよく、
Rの判定は2以上の整数x,yを取り出した時にQ(x+y)=P(x+y-1)が成立する場合はR(x*y,x)がx>=2で成立する(つまりこの場合はx*yはNG)、といった具合に計算する。

コード
class SumAndProductPuzzle {
   public:
   long long getSum(int A, int B){
   bool isprime[5000001];
   memset(isprime,true,sizeof(isprime));
   vector<int> prime;
   for( int i = 2 ; i*i < 5000001; i++ ){
    if( isprime[i] ){
      prime.push_back(i);
      for( int j = i+i ; j < 5000001; j+= i ){
        isprime[j]=false;
      }
    }
   }
   bool ok[5000001];
   memset( ok, true, sizeof(ok) );
   for( int i = 2 ; i*i < 5000001; i++ ){
    for( int j = i ; i*j < 5000001; j++ ){
      if( !isprime[i+j-1] ) ok[i*j] = false;
    }
   }
   long long ans =0;
   for( int i = A; i <=B; i++ ){
    if( !isprime[i-1] && ok[i-1] ) ans += i;
   }
   return ans;
  }
感想

I hate math!!!