Codeforces Good Bye 2015 - ei1333の日記

AをHackされた。
1580 -> 1565

A. New Year and Days

問題概要

以下のクエリが与えられるので,2016年において該当する日数の合計を答えよ。

"x of week" (1 ≤ x ≤ 7)
x 曜日の日数 x = 1 を月曜日, x = 7 を日曜日とする)
"x of month" (1 ≤ x ≤ 31)
x 日の日数

解法

googleカレンダー。x = 1 を日曜日として Hack されて落ちたのでダメ。

頭が悪いソース(Hackされた

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
const int INF = 1 << 30;
int main()
{
  const int manth[] = {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  const int hoge[] = {52, 52, 52, 52, 52, 53, 53};
  int N;
  cin >> N; 
  string S;
  getline(cin, S);
  if(S.find("week") != string::npos) {
    cout << hoge[N - 1] << endl;
  } else {
    int ret = 0;
    for(int i = 0; i < 12; i++) {
      if(N <= manth[i]) ++ret;
    }
    cout << ret << endl;
  }
}

B. New Year and Old Property

問題概要

a ≤ x ≤ b (1 ≤ a, b ≤ 10¹⁸) を満たす x のうち, x を 2 進表記したとき, ちょうど 1 bitのみが 0 となるものの個数を答えよ。

解法

全 bit が 1 の mask を作って, それぞれの bit を 0 に変えて, 総当り。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
int64 strbin2i (string &s)
{
  int64 out = 0;
  for (int i = 0; i < s.size(); i++) {
    out = out * 2 + (s[i] == '1');
  }
  return(out);
}  
int get_value(int64 target)
{
  int ret = 0;
  for(int i = 1; i <= 62; i++) {
    string s = string(i, '1');
    for(int j = 1; j < s.size(); j++) {
      s[j] = '0';
      ret += strbin2i(s) <= target;
      s[j] = '1';
    }
  }
  return(ret);
}
int main(){  
  int64 a, b;
  cin >> a >> b;
  cout << get_value(b) - get_value(--a) << endl;
}

C. New Year and Domino

問題概要

大きさ w × h (1 ≤ w, h ≤ 500) の 2 次元マップが与えられる。
'.' は何もないところ, '#' は障害物を示す。

以下のクエリが q (1 ≤ q ≤ 10⁵) 個与えられるので, それに答えよ。

長方形 ( ${r_{1}, c_{1}}$ )〜( ${r_{2},c_{2}}$ ) 中で, 障害物を避けながら 1 つの ${2 \times 1}$ のタイル(向きは縦横自由) を置くとき, その置き方の数

解法

制約がゆるいので、 ${O(Q(H+W) + WH) = O(10^8)}$ で間に合いそうな感じがする(実際間に合う
まず, 1 次元の累積和を, 各行, 各列ごとにとる。
${x,y}$ を基点に, 横方向(あるいは下方向) に置けたら +1 をする。あとは, 適当にクエリに答える。
横方向について考えると, ( ${r_{1}, c_{1}}$ )〜( ${r_{2},c_{2}}$ ) において, ( ${r_{2},c_{i}}$ ) を含めるとはみ出すので, ( ${r_{1}, c_{i}}$ ),( ${r_{2}-1,c_{i}}$ ) の区間の和となる(縦方向も同様)。

ソース

#include<bits/stdc++.h>
using namespace std;
int main()
{
  int H, W;
  scanf("%d %d", &H, &W);
  bool mas[500][500] = {{}};
  for(int i = 0; i < H; i++) {
    string S;
    cin >> S;
    for(int j = 0; j < W; j++) {
      mas[i][j] = S[j] == '.';
    }
  }

  int yoko[501][501] = {{}}, tate[501][501] = {{}};
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W - 1; j++) {
      if(mas[i][j] && mas[i][j + 1]) yoko[i + 1][j + 1]++;
      yoko[i + 1][j + 1] += yoko[i + 1][j];
    }
  }
  for(int i = 0; i < W; i++) {
    for(int j = 0; j < H - 1; j++) {
      if(mas[j][i] && mas[j + 1][i]) tate[i + 1][j + 1]++;
      tate[i + 1][j + 1] += tate[i + 1][j];
    }
  }
  int Q;
  scanf("%d", &Q);
  while(Q--) {
    int r1, r2, c1, c2;
    scanf("%d %d %d %d", &r1, &c1, &r2, &c2);
    int ret = 0;
    for(int i = r1; i <= r2; i++) {
      ret += yoko[i][c2 - 1] - yoko[i][c1 - 1];
    }
    for(int i = c1; i <= c2; i++) {
      ret += tate[i][r2 - 1] - tate[i][r1 - 1];
    }
    printf("%d\n", ret);
  }
}

D. New Year and Ancient Prophecy

問題概要

N (1 ≤ N ≤ 5000) 桁の文字列 S を, 以下の条件に基づいて複数の数値 a_i に分割する方法の数を 10⁹+7 で割った余りで答えよ。

${a_i} \lt {a_j} ({i \lt j})$
数値の先頭に 0 はない

(例) 123434

"123434" = "123434"
"123434" = "1" + "23434"
"123434" = "12" + "3434"
"123434" = "123" + "434"
"123434" = "1" + "23" + "434"
"123434" = "1" + "2" + "3434"
"123434" = "1" + "2" + "3" + "434"
"123434" = "1" + "2" + "3" + "4" + "34"

解法

この問題解きたかったなぁ。

まず、コンテスト中にできたのは、DP部分。
${dp[i, j]: S[i, j)}$ で最初に分割した場合の数
というように定義する。
次の文字列は, この文字列より大きくなっていなければいけないので,

${S[i, j) \lt S[j, j + j - i)}$
$dp_{[i, j]}: \sum_{k = j + (j - i)}^{N} dp_{[j, k]}$
それ以外
$dp_{[i, j]}: \sum_{k = j + (j - i) + 1}^{N} dp_{[j, k]}$

となる。これは BIT 使えば ${O(N^{2}\log{N}) }$ で、これでも十分。
ちょっと工夫できて, 事前に累積させておけば, ${O(N^{2}) }$ となって高速。

${S[i, j) \lt S[j, j + j - i)}$ の判定に ${O(N)}$ かけてしまったらまずいので, これを早くしたいなぁっていう問題に帰着する(これサボったら落ちたよね
こっちは, 上より簡単で,下の DP っぽもの ( ${O(N^{2})}$ ) をして, 異なる位置までの距離を求めて実現することができる。
${ dp[i, j] = \left\{ \begin{array}{rcl} 0 (S[i] == S[j]) \\ dp[i + 1, j + 1] (S[i] != S[j]) \end{array} \right. }$

ソース

#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

string S;
int dp[5005][5005];
int sum[5005][5005];
bool on[5005][5005];

int main()
{
  int N;
  cin >> N;
  cin >> S;

  for(int i = N - 1; i >= 0; i--) {
    for(int j = 0; j < N; j++) {
      if(S[i] != S[j]) sum[i][j] = 0;
      else sum[i][j] = sum[i + 1][j + 1] + 1;
    }
  }
  for(int i = 0; i < N; i++) {
    for(int j = 1; j <= N; j++) {
      if(i + j + j > N) continue;
      int dist = sum[i][i + j];
      if(S[i] == '0' || S[i + j] == '0' || i + j + dist >= i + j + j) on[i][j] = false;
      else on[i][j] = S[i + dist] < S[i + j + dist];
    }
  }

  int ret = 0;
  for(int j = N - 1; j >= 0; j--) {
    if(S[j] == '0') continue;
    dp[j][N] = 1;
    for(int i = N - 1; i >= 0; i--) (dp[j][i] += dp[j][i + 1]) %= MOD;
    for(int i = j - 1; i >= 0; i--) {
      if(S[i] == '0' || j + j - i > N) continue;
      (dp[i][j] += dp[j][j + j - i - on[i][j - i] + 1]) %= MOD;
    }
  }
  cout << dp[0][0] << endl;
}