読者です 読者をやめる 読者になる 読者になる

ei1333の日記

ぺこい

Codeforces Good Bye 2015

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 ≤ 1018) を満たす 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 ≤ 105) 個与えられるので, それに答えよ。

  • 長方形 ({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 に分割する方法の数を 109+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)}
     {\displaystyle dp_{[i, j]}: \sum_{k = j + (j - i)}^{N} dp_{[j, k]} }
  • それ以外
     {\displaystyle 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;
}