るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

あけましておめでとうございます

あけましておめでとうございます。(もうすぐ1/2ですが)

正月といえば書初め(コード)ですね。
確か去年の書初めはアセンブラで書きました。 

今年は競技プログラミングをやっていく予定なので、普通にC++で問題を解こうと思いますw


~書初め~

SRM555 Div2
255: XorBoardDivTwo
(Score 243.21 / 255)

やるだけ

class XorBoardDivTwo {
public:
  int theMax(vector <string> board) {
    int h = board.size();
    int w = board[0].size();
    int ans = 0;
    for(int y = 0; y < h; y++){
      for(int x = 0; x < w; x++){
	vector<string>tmp = board;
	rep(i,tmp[y].size()) tmp[y][i] = (tmp[y][i] == '0' ? '1' : '0');
	rep(i,tmp.size()) tmp[i][x] = (tmp[i][x] == '0' ? '1' : '0');
	int res = 0;
	rep(k,tmp.size()) rep(l,tmp[k].size()) res += tmp[k][l] - '0';
	ans = max(ans,res);
      }
    }
    return ans;
  }
	
};


550: CuttingBitString
(Score 485.43 / 555)

5の累乗の個数の合計の最小値でdpした。

string S;
int dp[60][60];
class CuttingBitString {
public:
  bool isFive(string s){
    if(s[0] == '0') return false;
    ll ans = 0;
    ll d = 1LL;
    rep(i,s.size()){
      if(s[s.size() - 1 - i] == '1') ans += d;
      d *= 2LL;
    }
    while(ans % 5 == 0) ans /= 5;
    return ans == 1;
  }
  int dfs(int l,int r){
    if(dp[l][r] != -1) return dp[l][r];
    string sp = S.substr(l,r - l + 1);
    if(isFive(sp)) return 1;
    if(r - l <= 0) return INF;
    int ans = INF;
    for(int i = l; i < r; i++){
      int ll = dfs(l,i);
      int rr = dfs(i + 1,r);
      ans = min(ans,ll + rr);
    }
    return dp[l][r] = ans;
  }
  int getmin(string tmp) {
    S = tmp;
    memset(dp,-1,sizeof(dp));
    int ans = dfs(0,S.size() - 1);
    return ans == INF ? -1 : ans;
  }
};

955: MuddyRoad2
(Score: Opened)

個人的には1100くらいの難易度あると思います。

フィボナッチ数列の積に帰着できるらしいです。
解説→ SRM555 解説

すごく面白い問題だと思う。解説見て感動した。


新年早々から全完できませんでした。 先が思いやられる...