2018-09-20

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;
}

2018-09-20

AOJ 2896 - Aizu Competitive Programming Camp 2018 Day 1 A テスト

未分類

問題

解法

最終的には全員前に詰めることになっているので、前からM人分をチェックして初期状態が空の椅子をカウントすると、それが答えになります。
提出コードはこちらになります。

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

int n, m, cnt = 0;
bool a[1005] = {0};

int main() {
  int i, x;
  cin >> n >> m;
  for(i = 0; i < m; ++i) {
    cin >> x;
    --x;
    a[x] = 1;
  }
  for(i = 0; i < m; ++i)
    if(!a[i]) ++cnt;
  cout << cnt << endl;
  return 0;
}

2018-09-20

AOJ 1522 - Planarian Regeneration

動的計画法(DP) 考察系

問題
 提出コード
数ヶ月放置してから考察しなおしたらすんなりいきました。
解説がなくてわからない問題は寝かせるのも大事だと思います。

解法

まず、サンプルケースなどを利用して手元で計算すると、
(縦における原点からの距離×縦の辺の長さ、の総和)×(横における原点からの距離×横の長さ、の総和)
のように、縦と横にわけて考えてから、最後に積をとると答えになることがただちにわかります。
縦と横でやっていることは同じなので、あとは1方向に対しての求め方を探ればよいです。
具体例として、2:3で $x$ 回切るパターンについて考えます。
初期状態は、(原点からの距離,辺の長さ)のペアは(1,1)の一つのみです。
1回切ると、
(1,2/5)と(3/5,3/5)に分かれます。
2回きると、
(1,4/25)、(21/25,6/25)、(15/25,6/25)、(9/25,9/25)の4つに分かれます。
全ての部分を2つに切っていくので、 $x$ 回切ったとき、 $2^{x}$ 個の辺ができます。
また、 $m:n$ に切断していくとき、現在辺の長さが $p$ の部分を切ると、あたりまえですが
$p×\frac{m}{m+n}$ と $p×\frac{n}{m+n}$ の2つに分かれます。辺は最初1ですので、全ての辺は

$m:n$ で $x$ 回切断するうち、何回 $n$ を選んだか

という回数で場合分けをすることが可能です。
$cnt[i][j] = i$ 回切断したときに、 $j$ 回 $n$ を選んだものの個数
とすると、
$cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1]$
となります。
次に、 $j$ 回 $n$ を選んだ場合の長さを求めます。
$dis[i][j] = i$ 回切断したときに、 $j$ 回 $n$ を選んだものの辺の長さ
とすると、
$dis[i][j] = \left\{ \begin{array}{} dis[i-1][j]×\frac{m}{m+n}　( i> j)\\ dis[i-1][j]×\frac{n}{m+n}　(i \leqq j) \end{array} \right.$
となります。
辺の長さが出せたので、あとは原点からの距離を求めれば終わりになります。
先ほどの続きとして、現在辺の長さが $p$ であり、原点からの距離が $q$ である部分についてみてみます。先ほども述べたように、これを $m:n$ で切ると $\frac{p×m}{m+n}$ と $\frac{p×n}{m+n}$ の2つに分かれます。このとき、長さが $\frac{p×m}{m+n}$ になった辺は、原点からの距離は $q$ のままであり、もう片方の辺の原点からの距離は、 $q$ から左側の辺の長さ、すなわち $\frac{p×m}{m+n}$ だけ引いたものになります。
もうすこし見やすくすると、
今原点からの距離が $q$ の辺について、 $i-1$ 回までで $j$ 回 $n$ を選んで切断していた場合、次の切断をしたときに辺の原点からの距離は、

$m$ を選んだ側
$q$
$n$ を選んだ側
$q-dis[i][j]$

の2つに分かれます。
これを、 $n$ を選んだ回数ごとに距離を先に合計しておきます。
$sum[i][j] = i$ 回切断したときに $j$ 回 $n$ を選んだものの原点からの距離の合計
とすると、
$sum[i][j] = sum[i-1][j] + sum[i-1][j-1] - cnt[i-1][j-1]×dis[i][j-1]$
となります。
これで必要なものがそろったので、あとは
(原点からの距離)×(辺の長さ)
の総和を求めます。これは
$dis[x][j]×dis[x][j]$
を $j$ について全探索して合計していけば求まります。
最後に、縦と横それぞれについてこの操作を行い、かけあわせれば答えとなります。

2018-09-19

Benelux Algorithm Programming Contest 2016 I Older Brother

未分類

問題

整数 $q$ が与えられたときに、なんかしらの素数を $p$ とおいて、 $q = p^{k}$ となるかどうかを調べろ、という問題です( $k$ は1以上です)。

解法

まずは $q$ =1の場合をコーナーケースとしてはじきます。
次に、その他の数を調べていきます。
単純に素数を1つずつみていき最後までループをしてしまうと間に合わないので、どうにかして途中でうちきる必要があります。
実は、 $\sqrt{q}$ までを見てしまえば答えがわかってしまいます。
それより大きい数を素因数にもつとき、残りの素因数はすべて $\sqrt{q}$ 未満になるからです。
ということで、mapを利用し、素因数をキーにしつつ、使った素因数の個数を記録します。素因数が見つかるたびに $q$ からその素因数を割ってしまいましょう。
$\sqrt{q}$ まで調べたら、今のこっている $q$ も素因数としてカウントし、最後にmapのサイズが1であれば条件を満たす、そうでなければ条件を満たしていない、と判定して答えを出力したら終わりになります。

提出コードは以下になります。

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

void prians(bool answer) {
  if(answer)
    cout << "yes" << endl;
  else
    cout << "no" << endl;
}
int q;
map<int, int> mp;

bool solve();

int main() {
  cin >> q;
  prians(solve());
  return 0;
}

bool solve() {
  int i = 2;
  if(q == 1) return 0;
  while(q != 1 && i * i <= q) {
    while(q % i == 0) {
      q /= i;
      ++mp[i];
    }
    ++i;
  }
  if(q != 1) ++mp[q];
  return mp.size() == 1;
}

2018-09-19

Benelux Algorithm Programming Contest 2016 E Charles in Charge

二分探索ダイクストラ法

問題

N個の頂点と、M個の重み付きの辺があるグラフが与えられます。
頂点1から頂点Nに行く最短経路に、X%加えた新しい距離以内で、頂点1から頂点Nにたどる道の中で辺の重みの最大値が、最も小さくなるときの、辺の重みの最大値を求めなさい、というものです。

解法

まずは素直にダイクストラ法を利用して最短経路を求めます。
その後、X%加えた新しい距離を出します。これをXとします。
今回求めるのは辺の重みの最大値を最小化したものになるので、二分探索を利用します。
現在見ている値をDとしたとき、

辺の重みがD以下のもののみを使用して、X以内に頂点1から頂点Nにたどり着くことができるか

という判定方法を利用して二分探索をします。
最終的に残ったDが答えになります。
やっていることはすごくシンプルなダイクストラ法と、ときどき見かける二分探索の組み合わせになります。最近二分探索をちょくちょく書いていたので、バグ無しで通すことができました。うれしいです。

提出コードは以下になります。

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

long long memo[10005] = {0};
vector<pair<long long, long long>> edge[10005];
long long n, m, x, minn, maxd = 0;
long long c1, c2, t;
priority_queue<pair<long long, long long>,
               vector<pair<long long, long long>>,
               greater<pair<long long, long long>>>
    pq;

void dk(long long d);
long long solve();

int main() {
  int i;
  cin >> n >> m >> x;
  for(i = 0; i < m; ++i) {
    cin >> c1 >> c2 >> t;
    --c1;
    --c2;
    edge[c1].push_back(make_pair(t, c2));
    edge[c2].push_back(make_pair(t, c1));
    maxd = max(maxd, t);
  }
  dk(inf);
  minn = memo[n - 1] * (double)(1 + 0.01 * x);
  cout << solve() << endl;
  return 0;
}

void dk(long long d) {
  long long nd, np;
  pair<long long, long long> now, nextn;
  memo[0] = 0;
  for(int i = 1; i < n; ++i) memo[i] = inf;
  pq.push(make_pair(0, 0));
  while(pq.size() > 0) {
    now = pq.top();
    pq.pop();
    nd = now.first;
    np = now.second;
    for(int i = 0; i < edge[np].size(); ++i)
      if(edge[np][i].first <= d) {
        nextn = make_pair(edge[np][i].first + nd,
                          edge[np][i].second);
        if(nextn.first < memo[nextn.second]) {
          memo[nextn.second] = nextn.first;
          pq.push(nextn);
        }
      }
  }
}

long long solve() {
  long long l = 0, r = maxd, now;
  while(r - l > 0) {
    now = (l + r) / 2;
    if(r - l == 1) {
      dk(l);
      if(memo[n - 1] <= minn)
        now = l;
      else
        now = r;
      break;
    }
    dk(now);
    if(memo[n - 1] <= minn)
      r = now;
    else
      l = now;
  }
  return now;
}

2018-09-18

Benelux Algorithm Programming Contest 2016 D Bridge Automation

動的計画法(DP)

問題

橋の下をN隻の船がくぐります。船がくぐるには、橋を上げないといけません。
橋を上げる、もしくは下すのには60秒かかります。
船が橋をくぐるのには20秒かかります。
また、船は橋の前に到着してから1800秒(30分)待機することができます。
船が到着する時刻が昇順で与えられるので、橋を上げている時間を最小にしたうえで出力してください、というものです。

解法

DPを考えます。

dp[i] = i番目までの船がくぐり終えるまでの、橋があがっている時間の最小値

とすると、

dp[i] = min(dp[j-1]+jからiを一度の橋の上げ下ろしですべて通したときにかかる時間)
となります。
j番目からi番目の船をいっぺんに通すことを考えると、
橋をあげておろすのに120秒、そしてj番目の船が通過を開始してからi番目の船が通過を終えるまでが
20+ max(i番目の到着時刻 - j番目の到着時刻 - 1800 , 20 × (i - j) )
となります。
max()の右側が、j番目からi番目までの船がきれいに連続して通過できた場合、左側がきれいに通過できずにどこかで待機時間が生じてしまった場合になります。
ということで、あとはこの計算を繰り返していけば答えが求まります。

提出コードは以下になります。

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

int n;
int memo[4005] = {0};
int dp[4005] = {0};

int solve();

int main() {
  int i;
  cin >> n;
  for(i = 0; i < n; ++i) cin >> memo[i];
  for(i = 0; i < n; ++i) dp[i] = 100000000;
  cout << solve() << endl;
  return 0;
}

int solve() {
  int i, j, now = 0;
  // j~i go one time. dp[i] = min(dp[j-1] + j~i time).
  for(i = 0; i < n; ++i)
    for(j = 0; j <= i; ++j) {
      now =
          140 + max(memo[i] - memo[j] - 1800, 20 * (i - j));
      if(j == 0)
        dp[i] = now;
      else
        dp[i] = min(dp[i], now + dp[j - 1]);
    }
  return dp[n - 1];
}

2018-09-17

Benelux Algorithm Programming Contest 2016 C Brexit

幅優先探索(BFS)

問題

N個の国と、P個の友好関係があります。
自分の国はXです。今、ある団体からLという国が脱退することを表明したので、回りの国も脱退するかどうかを考えています。
ある国は、友好関係を結んでいる国のなかで半分以上が脱退を表明していたら、その国も脱退することを表明します。
自分の国が脱退することになるかどうかを判定してください、という問題です。

解法

着火地点であるLから順番に幅優先探索で見ていきます。
現在見ている、脱退を決めた国をYとします。Yと友好関係を結んでいる国をすべて調べ、まだ脱退を表明していない国があったら、Yの国の分だけカウントを増やします。そして、その国が半数を超えたら、あらたに脱退を表明した国として、キューに挿入します。
キューがすべてなくなるか、自分の国が脱退を表明した時点で探索を切り上げ、答えを出力します。
既に脱退を表明して処理を行ったかどうかのメモをするあたりがポイント…かなと思います。

提出コードは以下になります。

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

struct data {
  bool used;
  int sum;
  int num;
  vector<int> v;
};
void prians(bool answer) {
  if(answer)
    cout << "leave" << endl;
  else
    cout << "stay" << endl;
}

bool solve();

int c, p, x, l;
data memo[200005];
queue<int> qu;

int main() {
  int i, a, b;
  scanf("%d %d %d %d", &c, &p, &x, &l);
  --x;
  --l;
  for(i = 0; i < c; ++i) {
    memo[i].sum = memo[i].num = 0;
    memo[i].used = 0;
  }
  for(i = 0; i < p; ++i) {
    scanf("%d %d", &a, &b);
    --a;
    --b;
    ++memo[a].sum;
    ++memo[b].sum;
    memo[a].v.push_back(b);
    memo[b].v.push_back(a);
  }
  prians(solve());
  return 0;
}

bool solve() {
  int now, i, nextn;
  qu.push(l);
  memo[l].used = 1;
  while(qu.size() > 0 && (!memo[x].used)) {
    now = qu.front();
    qu.pop();
    for(i = 0; i < memo[now].v.size(); ++i) {
      nextn = memo[now].v[i];
      ++memo[nextn].num;
      if(((memo[nextn].sum + 1) / 2 <= memo[nextn].num) &&
         (!memo[nextn].used)) {
        memo[nextn].used = 1;
        qu.push(nextn);
      }
    }
  }
  return memo[x].used;
}

ツバサの備忘録

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

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

解法

AOJ 2896 - Aizu Competitive Programming Camp 2018 Day 1 A テスト

解法

AOJ 1522 - Planarian Regeneration

解法

Benelux Algorithm Programming Contest 2016 I Older Brother

問題

解法

Benelux Algorithm Programming Contest 2016 E Charles in Charge

問題

解法

Benelux Algorithm Programming Contest 2016 D Bridge Automation

問題

解法

Benelux Algorithm Programming Contest 2016 C Brexit

問題

解法