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

EasyとMedium解いたのにみんなMedium解いてて何これ怖い状態だった。両方通ってたのが救いか。

結果報告

Level	ProblemName	Status	Point
Easy	getLongest	Passed System Test	245.51
Medium	minPacks	Passed System Test	284.41
Hard	isFairTree	Opened	0.0

Easy getLongest

問題

任意のkにおいて、k個の'>'の後にk個の'<'が続く文字列をここでは呪文という。
'>'と'<'からなる文字列を与えるので、そこから文字を削除することによって得られる呪文の最長の長さを答えよ

考えたこと

左から>を探して右から<を探して行くgreedyでok。

コード

int getLongest(string S){
     int size = S.size();
     int head = 0;
     int tail = size-1;
     int ans = 0;
     while( head < size && S[head]=='<' ) head++;
     while( tail >= 0 && S[tail] == '>' ) tail--;
     //while( S[head]!='>' ) head++;
     //while( S[tail]!= '<' ) tail--;
     while( head < tail ){
      ans += 2;
      head ++;
      tail --;
     while( head < size && S[head]=='<' ) head++;
     while( tail >= 0 && S[tail] == '>' ) tail--;
     }
     return ans;
  }

Medium minPacks

問題

K種類の色のボールがある。
第i色のボールの個数X[i]は以下の漸化式で定義される
X[0]=A, X[i+1]=(X[i]*B+C)%D+1 (for all i)
このボールをいくつかのpackに分類したい。
各packは必ずK以下のボールからなり

全て同じ色のボールである
全て違う色のボールである(variety)

のどちらかが充たされていなければならない。
最小のpack数を答えよ

考えたこと

varietyを使う場合は全部の色を1個ずつ使ったほうが得である(使わない理由がない)。
またvariety packを何個使うかで必要pack数が確定。
もし、variety packをY個使うとすると、
必要pack数は $Y+\sum_i \lceil\frac{X[i]-Y}{K}\rceil$

というわけで、各色をKで割った時の数（端数切り上げ）が鍵となってくる予感がするので、X[i]をmod Kごとに管理しようと考える。
modcount[j] = (X[i]%K==jなiの数)とすると、
varietyをj個使えば[tex: \sum_{k0は定義より明らかなので、variety=0,1,...K-1個まではとりあえずこれで計算可能。
その後は、ボール数が0になった色があれば適宜modcount[j]を調整しつつ、
どうあがいても得をしなくなるvarietyの数を考えれば良いが…
何とかしてvarietyの範囲を決めないとTLEになる香りしかしない。
そこでふと、varietyをK個使った時に必要pack数はたかだかK個しか少なくならないことに気がつく。
ボール数が0になる色ができるとvariety packを使う意味はどんどん薄れてくることも加味すると、
これはつまり、varietyをK個以上使う意味は無い、ということを意味するとわかる。

…つまり、varietyが0〜K-1個の時だけ調べればいいんじゃーん、とわかる。

コード

int minPacks(int K, int A, int B, int C, int D){
    long long X[K];
    X[0]=A;
    for( int i = 1 ; i < K ; i++ ){
      X[i] = (X[i-1]*B+C)%D +1;
    }
    int modcount[K];
    memset(modcount, 0 , sizeof(modcount));
    for( int i = 0 ; i < K ; i++ ){
      modcount[X[i]%K]++;
    }

    int ans = 0;
    for( int i = 0 ; i < K ; i++ ){
      ans += (X[i]+K-1)/K;
    }
    int ret= ans;
    int sum=0;
    for( int i = 1 ; i < K ; i++ ){
      sum += modcount[i];
      //cout << (i) << " varieties" << sum << "reduction "<<endl;
      ret = min( ret, ans+(i)-sum ); 
    }
    return ret;
  }

Hard isFairTree

問題

親ノード番号を指定する配列を用いて木構造が与えられる。
子ノードは親ノードの下方にあることが約束されており、葉ノードは一直線上に並ぶよう配置しているとする。
今、葉ノードをp子の小領域（各領域無いは連続的であるものとする）に分割し、各分割領域の葉ノードに1〜Pの番号を降る（同じ領域のノードは同じ番号）
ナンバリングされてない各ノードについては、子ノードの番号のどれかが当確率で伝搬するものとする。
根ノードに各番号が等確率で伝搬するような葉ノードの分割方法があれば"YES"を、でなければ"NO"を返せ。

考えたこと

解けないけど面白そうな問題だなあと思います（小並感）

答えが"NO"になる例ってのは

そもそも確率をP等分できない
できるけど各領域が連続領域である、という規則に違反する…のどちらか。

各葉ノードに書かれた番号が根ノードに行き着く確率は子供がn兄弟なら1/n…という計算を根からひたすらやり直せば計算可能。
テストケース2を観てると、根ノードに行き着く確率が1/Pより小さい3兄弟を全て違う番号が取り合うような形だったら"NO"なんだなーと漠然と思う。
兄弟はなんかうまい感じでまとめないと行けないってことは分かった。でもだからどうしろ、って感じ。