ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2889 - Aizu Competitive Programming Camp 2018 Day 3 A IPアドレス (Internet Protocol Address)

問題

解法

分ける点が3つのみなので、for文の3重ループで点をうつ場所を決めてから、それぞれが条件を満たしているかどうかチェックすることになります。
開始位置と終了位置、そして細かい条件のどれかでミスが生じると、デバッグが大変になるので気を付けます。
自分もかなりバグが多かったので、チームメイトだったばたこ(@btk15049)さんにデバッグをしていただきました。
提出コードはこちらになります。

#include <bits/stdc++.h>
using namespace std;

string s;

long long solve();
bool ch(int x, int y);

int main() {
  cin >> s;
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long cnt = 0;
  for(int i = 0; i < s.size() - 2; ++i)
    for(int j = i + 1; j < s.size() - 1; ++j)
      for(int k = j + 1; k < s.size(); ++k) {
        if(ch(0, i) && ch(i + 1, j) && ch(j + 1, k) &&
           ch(k + 1, s.size() - 1))
          ++cnt;
      }
  return cnt;
}

bool ch(int x, int y) {
  if(x > y) return 0;
  if(x != y && s[x] == '0') return 0;
  long long now = 0;
  for(int i = x; i <= y; ++i) {
    now *= 10;
    now += s[i] - '0';
  }
  return now <= 255;
}

AOJ 3042 - Aizu Competitive Programming Camp 2018 Day 2 D Gridgedge

問題

解法

縦と横に分けて考えます。
座標aからbに移動するとき、考えられるパターンは3つあり、

  1. そのままaからbに直接いくパターン

  2. 座標0に移動してからbにいくパターン

  3. 座標r-1(およびc-1)に移動してからbにいくパターン

になります。
また、座標をワープしてから移動する2、3番目のパターンは、必ず最初にワープを行わなければなりません。
ので、ワープする順番は特に考える必要がありません(この部分はコンテスト中に気づいていないため、ワープするパターンで場合分けをしてしまったのでコード量が増えています)。
あとは、3つのパターンのうち最も少ないコストで移動できるパターンを縦と横について求め、その縦と横のパターンの組み合わせについて、個数制限のある重複順列のパターン数を求めれば答えになります。

コンテスト後に書き直したコードはこちらになります。

#include <bits/stdc++.h>
#define N (long long)(1e9 + 7)
#define MAX 250005
using namespace std;

long long factorial[MAX] = {0}, finverse[MAX] = {0},
          inverse[MAX] = {0};

void smodfact() {
  factorial[0] = factorial[1] = 1;
  finverse[0] = finverse[1] = 1;
  inverse[1] = 1;
  for(int i = 2; i < MAX; ++i) {
    factorial[i] = factorial[i - 1] * i % N;
    inverse[i] = N - (inverse[N % i] * (N / i)) % N;
    finverse[i] = finverse[i - 1] * inverse[i] % N;
  }
}

long long calccomb(long long n, long long k) {
  if(n == k && n == 0) return 1;
  if(n < 0 || k < 0 || n < k) return 0;
  return factorial[n] * finverse[k] % N * finverse[n - k] %
         N;
}

long long rc[2], a[2], b[2], ch[2], data[2][3] = {0},
                                    cost = 0, ans = 0;
long long solve();
long long calc(int x, int y);
long long setd(int x);

int main() {
  smodfact();
  cin >> rc[0] >> rc[1] >> a[0] >> a[1] >> b[0] >> b[1];
  ans = solve();
  cout << cost << " " << ans << endl;
  return 0;
}

long long solve() {
  long long xy[2], ans = 0, nowx, nowy;
  for(int i = 0; i < 2; ++i) xy[i] = setd(i);
  cost = xy[0] + xy[1];
  for(int i = 0; i < 3; ++i)
    for(int j = 0; j < 3; ++j) {
      nowx = data[0][i];
      nowy = data[1][j];
      if(xy[0] == nowx && xy[1] == nowy) {
        ans += calc(i, j);
        ans %= N;
      }
    }
  return ans;
}

long long setd(int x) {
  long long minn;
  data[x][0] = max(a[x] - b[x], b[x] - a[x]);
  minn = data[x][0];
  data[x][1] = b[x] + 1;
  minn = min(minn, data[x][1]);
  data[x][2] = rc[x] - b[x];
  minn = min(minn, data[x][2]);
  return minn;
}
long long calc(int x, int y) {
  return factorial[data[0][x] + data[1][y]] *
         finverse[data[0][x]] % N * finverse[data[1][y]] % N;
}


コンテスト中に提出コードはこちらになります。

#include <bits/stdc++.h>
#define N (long long)(1e9 + 7)
#define MAX 250005
using namespace std;

long long factorial[MAX] = {0}, finverse[MAX] = {0},
          inverse[MAX] = {0};

void smodfact() {
  factorial[0] = factorial[1] = 1;
  finverse[0] = finverse[1] = 1;
  inverse[1] = 1;
  for(int i = 2; i < MAX; ++i) {
    factorial[i] = factorial[i - 1] * i % N;
    inverse[i] = N - (inverse[N % i] * (N / i)) % N;
    finverse[i] = finverse[i - 1] * inverse[i] % N;
  }
}

long long calccomb(long long n, long long k) {
  if(n == k && n == 0) return 1;
  if(n < 0 || k < 0 || n < k) return 0;
  return factorial[n] * finverse[k] % N * finverse[n - k] %
         N;
}

long long rc[2], a[2], b[2], ch[2], data[2][3][2] = {0},
                                    cost = 0, ans = 0;
long long solve();
long long calc(int x, int y);
long long setd(int x);

int main() {
  smodfact();
  cin >> rc[0] >> rc[1] >> a[0] >> a[1] >> b[0] >> b[1];
  ans = solve();
  cout << cost << " " << ans << endl;
  return 0;
}

long long solve() {
  long long xy[2], ans = 0, nowx, nowy;
  for(int i = 0; i < 2; ++i) xy[i] = setd(i);
  cost = xy[0] + xy[1];
  for(int i = 0; i < 3; ++i)
    for(int j = 0; j < 3; ++j) {
      nowx = data[0][i][0];
      nowy = data[1][j][0];
      if(xy[0] == nowx && xy[1] == nowy) {
        ans += calc(i, j);
        ans %= N;
      }
    }
  return ans;
}

long long setd(int x) {
  long long minn;
  data[x][0][0] = max(a[x] - b[x], b[x] - a[x]);
  minn = data[x][0][0];
  data[x][1][0] = b[x] + 1;
  data[x][1][1] = 1;
  minn = min(minn, data[x][1][0]);
  data[x][2][0] = rc[x] - b[x];
  data[x][2][1] = 1;
  minn = min(minn, data[x][2][0]);
  return minn;
}
long long calc(int x, int y) {
  long long ans = 0;
  if(x == 0 && x == y)
    return factorial[data[0][0][0] + data[1][0][0]] *
           finverse[data[0][0][0]] % N *
           finverse[data[1][0][0]] % N;
  if(x != 0) {
    for(int i = 0; i <= data[1][y][0]; ++i) {
      ans +=
          factorial[data[0][x][0] + data[1][y][0] - i - 1] *
          finverse[data[0][x][0] - 1] % N *
          finverse[data[1][y][0] - i] % N;
      ans %= N;
    }
  }
  else if(y != 0) {
    for(int i = 0; i <= data[0][x][0]; ++i) {
      ans +=
          factorial[data[0][x][0] + data[1][y][0] - i - 1] *
          finverse[data[0][x][0] - i] % N *
          finverse[data[1][y][0] - 1] % N;
      ans %= N;
    }
  }
  while(ans < 0) ans += N;
  return ans;
}

AOJ 3041 - Aizu Competitive Programming Camp 2018 Day 2 C Round And Round

問題

解法

配列の中身をいじるクエリでは、処理後も配列の中身の順番自体は変わらず常に昇順になっています。
ということで、現在の先頭の数字のみがわかっていれば、出力のクエリに対応できます。
具体的には、配列をいじるクエリで、kが入力されたとき、先頭はkだけ大きいものに変わるので、kだけ加算すれば良いです。
出力のときはそのままk番目を出力するだけです。
あとは0-indexと1-indexに気を付けます。
提出コードはこちらになります。

#include <bits/stdc++.h>
using namespace std;

int now = 0, k, n, m, ch;

int main() {
  int i;
  cin >> n >> m;
  for(i = 0; i < m; ++i) {
    cin >> ch >> k;
    if(ch) {
      now += k;
      now %= n;
    }
    else {
      cout << (now + k - 1) % n + 1 << endl;
    }
  }
  return 0;
}

AOJ 3039 - Aizu Competitive Programming Camp 2018 Day 2 A Special Chat

問題

解法

大きい値段から貪欲に払えるだけ払えば答えが求まります。
じつは、求められているものが合計金額なので、500についてのみ考えればいいらしいです。
提出コードはこちらになります。

#include <bits/stdc++.h>
using namespace std;

int memo[4] = {10000, 5000, 1000, 500};
int ans = 0;
int p;

int main() {
  int i;
  cin >> p;
  for(i = 0; i < 4; ++i) {
    while(memo[i] <= p) {
      ans += memo[i];
      p -= memo[i];
    }
  }
  cout << ans << endl;
  return 0;
}

AGC027 C - ABland Yard

問題
提出コード
なんか最近すごい似た問題を見たような…(前日の練習会でこの問題を解いていました)
ある頂点から、AとBが書かれている頂点どちらか片方にしかいけなくなった時点でその頂点を消してしまいます。
これを繰り返していき、頂点が残っていればYes、残らなければNoになります。
これの実装方法として、幅優先探索があります。
入力の時点で、ある頂点につながっている別の頂点で、Aの文字であるものとBであるものを別にカウントしておきます。
次に、最初の入力直後に即消す頂点をスタックにいれます。
その後はキューから取り出した頂点について、その頂点とつながっている全ての頂点について、まだ消えずに残っていれば最初に記録したカウントを減らしていきます。そのカウントが0になったら、その頂点も消すことができるようになるので、新たにキューに格納します。
これを、全てのキューが空になるまで繰り返します。最後に、全ての頂点が消えたならNo、残っていればYesを出力して終わりです。
Bに気を取られていたのもありますが結構考えたのにも関わらず考察が全く進んでいなかったので少し悔しいです(900点なので仕方がないといえば仕方がないのですが…)。

AGC027 A - Candy Distribution Again

問題
提出コード
貪欲法です。
a_{i}を昇順にソートし、少ない方から順番に配っていけばよいです。配ったら残っているキャンディの量を減らしていきます。
最後だけ注意が必要で、残っている数と必要な数が等しいなら人数をカウントすることができ、そうでなければカウントできません。
人数をカウントしていき、答えを求めて終わりです。

AOJ 2898 - Aizu Competitive Programming Camp 2018 Day 1 C 素数

問題

解法

まずはエラトステネスの篩を適用して範囲内の素数をすべて求めます。
次にpとqのペアですが、素数同士の和が素数になるには、奇数と奇数の素数の和が偶数になる関係上、片方は2で固定されてしまいます。
ということで、片方を2に固定して、もう片方を1からNまで全探索をし、2とqの和が素数であったときに、カウントを2増やします。そして、探索が終わったらそのカウントを出力すれば答えになります。
提出コードはこちらになります。

#include <bits/stdc++.h>
using namespace std;

bool prime[10000005] = {0};

void sprime() {
  int i;
  prime[0] = prime[1] = 1;
  for(i = 2; i < sqrt(10000000); ++i)
    if(!prime[i])
      for(int j = 2; i * j <= 10000000; ++j)
        prime[i * j] = 1;
}

int n;
long long cnt = 0;

int main() {
  int i;
  sprime();
  cin >> n;
  for(i = 2; i <= n; ++i)
    if((!prime[i]) && (!prime[2 + i])) cnt += 2;
  cout << cnt << endl;
  return 0;
}