SRM609参加記 - プログラミング上級者を目指して

初めてdiv2の本番で全完出来てテンションが上がったので書いちゃいます．

MagicalStringDiv2(250)

'>'と'<'からなる偶数長の文字列が与えられる．これを'>''>'...'<''<'の形にするには最低何文字変換しなければならないか．

単に数えるだけ．

class MagicalStringDiv2 {
	public:
	int minimalMoves(string S) {
      int len = S.length();
      int ret = 0;
      Rep(i, len){
        if(i < len / 2){
          if(S[i] == '<') ret++;
        }
        else{
          if(S[i] == '>') ret++;
        }
      }
      return ret;
}

PackingBallsDiv2(500)

赤，緑，青のボールがそれぞれR，G，B個ある．それらを使って可能な限り少ないパッケージを作る．パッケージは
1. 1〜3個からなる
2. 全て同じ色か，全て異なる色からなる
の条件を満たさなければならない．

なんか前にこどふぉで解いた問題に似てるなあと思いつつ考察．
こどふぉの時は変な条件を考えて条件分岐したら死んだので答え列挙系にしたい．
そこで，試しに全部列挙してみたら最大ケースでもいけそうだったので提出．
しかし，ループ毎に変数の値を戻し忘れるという変なミスをしたせいで再提出．

class PackingBallsDiv2 {
	public:
	int minPacks(int R, int G, int B) {
      int ans = INF;
      Rep(i, 101){
        int res = 0;
        int rr = R, gg = G, bb = B;
        if(R >= i && G >= i && B >= i){
          res += i;
          rr -= i;
          gg -= i;
          bb -= i;
          Rep(j, 101){
            if(rr >= j && gg >= j){
              // printf("%d, %d\n", i, j);
              res += j;
              rr -= j;
              gg -= j;
              Rep(k, 101){
                if(rr >= k && bb >= k){
                  res += k;
                  rr -= k;
                  bb -= k;
                  Rep(l, 101){
                    // printf("%d, %d, %d, %d, gg = %d, bb = %d\n", i, j, k, l, gg, bb);
                    if(gg >= l && bb >= l){
                      // printf("%d, %d, %d, %d\n", i, j, k, l);
                      res += l;
                      gg -= l;
                      bb -= l;
                      int rrr = rr, ggg = gg, bbb = bb, rres = res;
                      rrep(m, 3, 1){
                        rres += rrr / m;
                        rres += ggg / m;
                        rres += bbb / m;
                        rrr %= m;
                        ggg %= m;
                        bbb %= m;
                      }
                      ans = min(ans, rres);
                      res -= l;
                      gg += l;
                      bb += l;
                    }
                  }
                  res -= k;
                  rr += k;
                  bb += k;
                }

              }
              res -= j;
              rr += j;
              gg += j;
            }
          }
          res -= i;
          rr += i;
          gg += i;
          bb += i;
        }
      }
      return ans;
}

VocaloidsAndSongs(950)

ボーカロイドのGumi，Ia，MayuはS曲からなるアルバムを作ることにした．
曲は1人〜3人が歌う．全ての組み合わせ数をXとしたとき，X mod 1,000,000,007を求めよ．

残り30分くらいだったのでさすがに厳しいかなーとオープンしたHardがボカロ題材だったのでちょっと嬉しかった（@semiexpさんの問題だったらしい．これからもボカロの問題を出してくれるといいなあ・・・）．しかも問題文短い．
はじめ，「全部列挙して歌ってる人数が0の曲が含まれている場合を引けばいけそう！」と思い，包除原理とか使うのかなーと考えてましたが，「あれ？これってDPじゃ無理なのか？」と思い至り，試しに実装してみたらテストケースパスしたので提出．
dp[i曲め][GUMIの歌った数][IAの歌った数][MAYUの歌った数]でDPします．

ll dp[52][52][52][52];

class VocaloidsAndSongs {
	public:
	int count(int S, int gumi, int ia, int mayu) {
      afill2(dp, 0, ll);
      dp[0][0][0][0] = 1;
      rep(i, 1, S+1){
        Rep(j, gumi+1){
          Rep(k, ia+1){
            Rep(l, mayu+1){
              if(i && j) dp[i][j][k][l] = (dp[i][j][k][l] + dp[i-1][j-1][k][l]) % MOD;
              if(i && k) dp[i][j][k][l] = (dp[i][j][k][l] + dp[i-1][j][k-1][l]) % MOD;
              if(i && l) dp[i][j][k][l] = (dp[i][j][k][l] + dp[i-1][j][k][l-1]) % MOD;
              if(i-1>=0 && l && j) dp[i][j][k][l] = (dp[i][j][k][l] + dp[i-1][j-1][k][l-1]) % MOD;
              if(i-1>=0 && l && k) dp[i][j][k][l] = (dp[i][j][k][l] + dp[i-1][j][k-1][l-1]) % MOD;
              if(i-1>=0 && j && k) dp[i][j][k][l] = (dp[i][j][k][l] + dp[i-1][j-1][k-1][l]) % MOD;
              if(i-1 >= 0 && l && j && k) dp[i][j][k][l] = (dp[i][j][k][l] + dp[i-1][j-1][k-1][l-1]) % MOD;
            }
          }
        }
      }
      return dp[S][gumi][ia][mayu];
}

初めて全完でチャレンジフェイズを迎えましたが，SRMは自信があってもよく落ちるので「どうせ落ちるんだろうなー」と思ってました．

チャレンジフェイズではMedで落とせそうなコードを発見．数行で書かれてるし，なんかおかしそう．でもPythonで書かれていたのでよく分からない．
そこで写経．しかし，初めてemacsでPythonを書きましたがオートインデントは効かないし，BackSpaceによるインデントの削除は出来ないし四苦八苦（僕のemacsだけ？）．
ようやく書けたものの結局落とせるケースはよく分からず（このコードはSystem Testで落ちてた）．

結局244.30，191.00，646.06の1081.36でRoom2位，全体72位でした（初めての全完で高まっていたけどそこまでいいわけでもなかった）．
1074 -> 1146

もしかしてDiv1戻れるかなーとか期待していましたが普通に無理でした．
Div1への道は本当に険しい・・・．