2018-09-17

Benelux Algorithm Programming Contest 2016 B Battle Simulation

実装系

問題

敵が3つの技をうってくるので、それに対応したコマンドをこちらが入力してください、という問題です。
RにはS、BにはK、LにはHを出力します。
基本的に、1対1でコマンドが対応していますが、それとは別に、
3つすべて違う技を連続してうってきた場合のみ、普段とは違ってCというコマンドを入力する、という条件があります。

解法

割と愚直に実装しました。
…のですが、かなりごちゃごちゃしてしまいました。
3種類の敵のコマンドをカウントして、3つたまったらその都度こちらも古い方からコマンドを出力していきます。
最後の端数だけ最後にいっぺんに出力します。
絶対もっと何か綺麗な実装方法があると思いますね…
提出コードは以下になります。

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

string s;
int cnt[3] = {0};
int lst[27] = {0};
int cmnd[3] = {0};

int main() {
  cin >> s;
  lst['R' - 'A'] = 0;
  lst['B' - 'A'] = 1;
  lst['L' - 'A'] = 2;
  cmnd[0] = 'S';
  cmnd[1] = 'K';
  cmnd[2] = 'H';
  for(int i = 0; i < s.size(); ++i) {
    ++cnt[lst[s[i] - 'A']];
    if(cnt[0] + cnt[1] + cnt[2] < 3)
      ;
    else if(cnt[0] * cnt[1] * cnt[2] == 1) {
      cout << 'C';
      cnt[0] = cnt[1] = cnt[2] = 0;
    }
    else {
      cout << (char)(cmnd[lst[s[i - 2] - 'A']]);
      --cnt[lst[s[i - 2] - 'A']];
    }
    if(i == s.size() - 1)
      for(int j = s.size() - (cnt[0] + cnt[1] + cnt[2]);
          j < s.size(); ++j)
        cout << (char)cmnd[lst[s[j] - 'A']];
  }
  cout << endl;
  return 0;
}

2018-09-16

ABC006 D - トランプ挿入ソート

Longest Increasing Subsequence (LIS) 二分探索動的計画法(DP)

問題
 提出コード

解法
基本的に、1つのトランプは1回操作するだけで必ず正しい位置に戻せるので、最悪N回の操作が必要になります。
そして、操作の回数を最小にするには、そもそも操作しないトランプの枚数を最大化すればいいことになります。
これはつまり、できるだけソート済みになっているようにトランプを選び、その他のトランプを挿入していくことになります。この、できるだけソート済みになっている、というのは
$i \lt j$ のとき $c_{i} \lt c_{j}$
という条件を満たす数列を選び出すときに、できるだけ多くの個数を選ぶ、というものになります。
ということで、LISに帰着させることができました。
LISを利用して部分列が最長になるようなものを選び、それをNから引いたものが、必要最小回の操作回数になります。

2018-09-15

SnackDown 2016 - Jealous Numbers

動的計画法(DP) エラトステネスの篩分けて考える bit bitDP

問題

与えられた集合から、任意の2つの元が互いに素になっているような部分集合をつくり、最大となる要素数を出力する、というものです。
これをT回繰り返します。

解法

まずはじめに、1はすべて部分集合にいれることができるので、1が入力された回数だけ別にもっておき、最後にたすことにします。この後は2以上の数について考えます。
任意の2つの要素について互いに素でなければならないので、2の倍数、3の倍数…は集合の中に1つずつしか存在してはいけません。いろいろ結局のところ、集合の全ての要素を素因数分解したときに、任意の素数はその集合の中で1回ずつしか使われてはいけません(4や8のように、1つの数字で複数回使われるものは全部で1回とします)。ということで、それぞれの素数について、すでに使われたかどうかをビットで管理したDPについて考えたいのですが、素数は100個を超えているため、それでは間に合いそうにありません。
そこで、素数を2種類に分類します。具体的には、31以下の素数と、37以上の素数です。
なぜこう分けるかというと、31以下の素数は、2乗しても1000以下になっているからです。
ある数xが37以上の素因数を持っていたとき、残りの素因数は31以下になっています。もちろん、ある数xが37以上の素因数を持っていないときも、素因数はすべて31以下です。
31までの素数は全部で11個しかないので、これならビットでうまく管理をすることができます。なので、入力された全ての数字について、

素因数の最大値
31以下の素因数をビットで表したもの

の2つを調べておきます。
さて、DPを考えていきます。
dp[i][S]とします。 iは現在見ている素因数の最大値、Sはすでに使った素数の集合(ビットで管理します)です。このときに入れることのできる要素数の最大値がここには格納されます。

今、入力された数字の中で、素因数の最大値がiとなっている数を1つもってきて、31以下の素因数のビットがBであるとしたとき、

SとBの論理和がSの場合
dp[i][S] = max(dp[i-1][S],1+dp[i-1][S-B])
1でない場合
dp[i][S] = max(dp[i-1][S])

となります。i-1は、実際にはi-1ではなく、iの1つ前の素数となります。
あとは、任意のiごとに入力された数を整理して、このDPの更新を繰り返していけば答えがもとまります。
途中で変なことをしたり、繰り返しの作業をかなり効率化しないと、時間オーバーになる可能性が高いです。 $2^{11}$ でいいところを $2^{12}$ で書いていてずっとTLEを連発していました(気づくのに数日かかりました)。

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

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

bool primels[N + 5] = {0};
vector<int> primes;
int prime[11] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
pair<int, int> memo[1005];
map<int, vector<int>> a;
int dp[2][5000] = {0};
int n;
void sprime() {
  int i, j;
  primels[0] = 1;
  primels[1] = 1;
  for(i = 2; i <= N; ++i)
    if(!primels[i]) {
      primes.push_back(i);
      for(j = 2; i * j <= N; ++j) primels[i * j] = 1;
    }
}

int solve();

int main() {
  sprime();
  int t, i, x, one = 0, j, now, maxp = 0;
  for(i = 2; i <= 1000; ++i) {
    x = i;
    now = 0;
    maxp = 0;
    for(j = 0; j < 11; ++j)
      if(x >= prime[j] && x % prime[j] == 0) {
        while(x > 0 && x % prime[j] == 0) x /= prime[j];
        now += (1 << j);
        maxp = prime[j];
      }
    maxp = max(maxp, x);
    memo[i] = make_pair(maxp, now);
  }
  cin >> t;
  while(t) {
    one = 0;
    cin >> n;
    for(i = 0; i < n; ++i) {
      cin >> x;
      if(x == 1)
        ++one;
      else {
        now = memo[x].second;
        maxp = memo[x].first;
        a[maxp].push_back(now);
      }
    }
    cout << solve() + one << endl;
    for(j = 0; j < 2; ++j)
      for(i = 0; i < (1 << 11); ++i) dp[j][i] = 0;
    a.erase(a.begin(), a.end());
    --t;
  }
  return 0;
}

int solve() {
  int ans = 0, now, nprime, bit = 0;
  for(int i = 0; i < primes.size(); ++i) {
    if(a.find(primes[i]) != a.end()) {
      for(int j = 0; j < (1 << 11); ++j)
        dp[bit][j] = dp[1 - bit][j];
      for(int j = 0; j < a[primes[i]].size(); ++j) {
        nprime = a[primes[i]][j];
        now = (1 << min(11, i + 1)) - 1 - nprime;
        for(int mask = now; mask >= 0; --mask &= now) {
          dp[bit][mask + nprime] =
              max(dp[bit][mask + nprime],
                  dp[1 - bit][mask] + 1);
          ans = max(ans, dp[bit][mask + nprime]);
          if(mask == 0) break;
        }
      }
      bit = 1 - bit;
    }
  }
  return ans;
}

2018-09-15

SnackDown 2016 - Robot Walk

bitset 分けて考える bit

問題

ロボットに2×N+1回の命令が与えられます。
奇数回目:数字が与えられるので、ロボットは指定された数字だけ、今向いている方向に移動します。
偶数回目:LまたはRの文字が与えられるので、ロボットは指定された方向に90度回転します。
これを、原点からスタートしたときに、命令をすべて終えた後再び原点にいるように、命令の中身を変更したいです。LとRを逆にするコストは0とし、数字を1追加、および減らすことをコスト1としたとき、最小のコストを求めなさい、というものです(もし無理であればNOを出力します)。
これをT回繰り返します。

解法

まず、Nが2以下のときはNOとなります。一周することができないので、戻ってくることができません。
それ以外のときを考えます。
偶数回目の移動と奇数回目の移動で、それぞれ横と縦の移動に分離しています。なので、それぞれで最小のものを求めて、最後に合算します。ということでとりあえず縦について考えます。
数直線上で考えます。正に進む場合と負に進む場合は、コスト0で変更できるので、全ての場合を試したうちの、一番原点とのズレが近いものを選び、そのズレだけ修正すれば、コストが最小になります。
ある地点Xにいるときに、コスト0で移動できる場所は、その次の命令の移動するマスの数をDとすると、X＋DまたはX-Dのどちらかになります。
次に移動するときのマスの数をEとすると、先ほどのX+DおよびX-Dから、さらに+E、もしくは-Eだけ移動した場所の4通りになります。
ということで、これを高速に計算する手段を探すと、bitsetというものがあったので使います(存在は知っていましたが、実は初めて使いました)
最初は原点に1というビットを立てておき、他は0とします。
そして、次に移動するマスの数をDとしたとき、現在のbitsetを左にDシフトしたものと右にDシフトしたもののORをとれば、移動後にたどり着ける場所にのみビットが立っています。
あとは、処理が完了したら原点に近いものから順番に、1が立っている場所を探して、その差を最小コストとすればよいです。
これを、縦と横についてすべて行い、合算すれば答えとなります。
bitsetは結構直感的というか、ほかのデータ構造や演算子とそのままな部分が多かったので個人的にはかなり使いやすいと思いました。

以下が提出コードとなります。

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

int t, n;

int solve();

int main() {
  cin >> t;
  while(t) {
    cin >> n;
    if(n <= 2) {
      solve();
      cout << "NO" << endl;
    }
    else
      cout << solve() << endl;
    --t;
  }
  return 0;
}

int solve() {
  char x;
  int i, a, k, now, ans = 0;
  bitset<(500 * 505)> bt[2];
  bt[0][500] = 1;
  bt[1][500] = 1;
  for(i = 0; i <= n; ++i) {
    cin >> a;
    if(i != n) cin >> x;
    now = i % 2;
    bt[now] = (bt[now] << a) | (bt[now] >> a);
  }
  for(k = 0; k < 2; ++k) {
    for(i = 0; i <= 500; ++i)
      if(bt[k][i + 500] || bt[k][-i + 500]) {
        ans += i;
        break;
      }
  }
  return ans;
}

2018-09-14

SnackDown 2016 - Coloring A Tree

mod N 逆元数え上げ

問題

N-1本の辺とN個の頂点からなる連結無向グラフが与えられます。それを、ある条件を満たすようにK色以下で塗り分ける場合の数を、 $10^{9}+7$ の余りで出力しなさい、というものです。
条件が、任意の頂点と同じ色の別の頂点は、ほかの同じ色の頂点のみをたどってそこにたどりつけるようにする、というものです。
これをT回繰り返します。

解法

まずは使う色の種類を固定します。 $i$ 色使うとします。
このとき、木は $i$ 個に分かれていないといけません。
ここでのポイントが、辺を $i-1$ 個取り除くと、木は $i$ 個になる、ということです。
ということで、 $_{N-1}C_{i-1}$ を計算すると、 $i$ 個の分け方を求めることができます。
あとは、色の使い方を求めますが、これは $K$ 色から $i$ 色を選んで並べる順列と同じになります。
ということで、
$_{N-1}C_{i-1} × _{K}P_{i}$ をどんどん足していき、 $i$ を1から $K$ までループさせれば終わりです。
提出コードはこちらになります。

#include <bits/stdc++.h>
#define N (long long)(1e9 + 7)
#define MAX 5000
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 < 0 || k < 0 || n < k) return 0;
  return factorial[n] * finverse[k] % N * finverse[n - k] %
         N;
}
int t, n, k, u, v;

int main() {
  long long ans = 0, now;
  smodfact();
  cin >> t;
  while(t) {
    ans = 0;
    cin >> n >> k;
    for(int i = 0; i < n - 1; ++i) cin >> u >> v;
    for(int i = 0; i < n; ++i) {
      now = calccomb(n - 1, i);
      now *= calccomb(k, i + 1);
      now %= N;
      now *= factorial[i + 1];
      now %= N;
      ans += now;
      ans %= N;
    }
    cout << ans << endl;
    --t;
  }
  return 0;
}

2018-09-13

SnackDown 2016 - VCake

条件の作成考察系

問題

縦と横が長さR,Cの長方形があり、それをいくつかの条件に基づいて切断し、指定された3つの面積(M,J,K)になるように分けろ、という問題です。
切断の条件は3つで、

長方形の辺と平行に切断する
一度切れ込みを入れたら、その部分は端から端まで切断する
切った後に二つに分かれる部分は、どちらも整数になるように切断する
というものです。
これをT回繰り返します。

解法

この問題は $O(log N)$ あたりまで計算量を落とさないといけないので、考察で殴る必要があります。
ということで考察をすると、まず一回目に例えば横と平行に切断するとしたとき、
ケーキはまず上下に分かれます。
3つに分けるには、上下に分かれたうちどちらかをもう一度切断する必要があります。が、残った片方はもう切断することはありません。
ということで、残る方を上側とすると、それは与えられた3つの大きさのうちのどれかにすでになっていなければなりません。
上側の面積が例えばMに一致するように切るとき、横の長さは一定なので、縦の長さは一意に決まってしまいます(MがCで割り切れなかったとき、条件をみたす切り方は存在しません)。
このように切断したとき、のこる下側の、縦の長さはR-M/Cとなります。
次は、残ったケーキを縦、または横に切断して、それぞれ面積がJ,およびKとなるかどうかを判定します。これも同様に調べることができます。
例えば再び横と平行に切断するとしたとき、
J、K両方がCで割り切れて、かつJ/CとK/Cの和がR-M/Cになれば、条件を満たす切断方法が存在します。
これを、必要な回数調べればよいです。
具体的には、RとCは交換可能なので2通り、最初に切り分けられた時点で決まるもの(先ほどの例でいうMです）を3つのうち1つ選ばなければならないので3とおり、最後に二回目の切断を縦できるか横できるかの2通りです。
全部で12通りほど調べて、それでも条件を満たす切断方法が存在しなければNo,すればYesになります。

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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void prians(bool answer) {
  if(answer)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}
ll t, r, c, mjk[3];

bool binary(ll x, ll y, ll z);

int main() {
  int i, k;
  bool ans = 0;
  cin >> t;
  while(t) {
    ans = 0;
    cin >> r >> c >> mjk[0] >> mjk[1] >> mjk[2];
    for(k = 0; k < 2; ++k) {
      for(i = 0; i < 3; ++i) {
        ans = binary(mjk[i], mjk[(i + 1) % 3],
                     mjk[(i + 2) % 3]);
        if(ans) break;
      }
      if(ans) break;
      swap(r, c);
    }
    prians(ans);
    --t;
  }
  return 0;
}

bool binary(ll x, ll y, ll z) {
  if(x % c != 0) return 0;
  ll now = r - x / c;
  if(now == 0) return 0;
  if(y % now == 0 && z % now == 0 &&
     (y / now + z / now) == c)
    return 1;
  if(y % c == 0 && z % c == 0 && (y / c + z / c) == now)
    return 1;
  return 0;
}

2018-09-12

AOJ 2372 - IkaNumber

行列数え上げ二分探索 mod N 考察系実装系バイナリ法

問題

 提出コード
自力でなんとか解けました！時間は4時間くらいかかりました…
くコ:彡　くコ:彡　くコ:彡　くコ:彡

解法

問題を読んだだけではかなり自由度が高いので、一つ一つ見ていくことにします。
まず、Taroの家の位置を固定します。
Taroの家、にんじん、Hanakoの家の3つすべてを好きな場所に置くことができますが、Taroの家とにんじん、にんじんとHanakoの家の距離がすべて同じだった場合はイカ数が必ず等しくなります。なので、わかりやすくするためにTaroの家を原点に固定します。
次に、小さなケースで実験をしていきます。
(にんじんの座標,Hanakoの家の座標)としたとき、(1,2),(1,3),(2,3),(1,4),(2,4),(3,4)...というパターンが考えられるので、その場合のイカ数をそれぞれ計算していくと、1,1,1,2,1,2...となっています。
この実験をするとわかるのが、

にんじんの前後のマスは必ず止まらないといけない

ということです。
にんじんの2マス前に止まったとき、1マスすすむことはできますが、2マスすすむとにんじんのマスに止まってしまうので、にんじんの1マス前に止まることしかできません(それ以上前のマスの場合もにんじんを超えた先に行くことはできません)。同様に、にんじんの1マス前に止まったとき、1マスすすむとにんじんのマスに止まってしまうので、にんじんの1マス先に止まることしかできません。よって、にんじんの前後のマスには必ず止まることになります。
そこで、イカ数は次のように書き換えることができます。
(原点からにんじんの1マス前にいく場合の数)×(にんじんの1マス先からHanakoの家にいく場合の数)
こうすることで、単純な場合の数を書き出していけば見通しがたつようになります。

では、原点から座標 $x$ にいくような場合の数を考えます。
これも1~6あたりまで実験をすると、法則性が見えてきます。
実は、以下の式のようになっています。
$\sum{_{i=0}^{x/2}} _{(x-i)}C_i$
そしてこの数式を $x=0$ から列挙してみると、
1,1,2,3,5,8,13,21,34,55,89...
となっていて、実はフィボナッチ数列になっています。
$i$ 番目のフィボナッチ数を $f[i]$ としたとき、問題の答えは以下のように言い換えることができます。

$f[i]×f[j]$ のなかで $k$ 番目に小さいもの

ここで、被っているものを排除するため、 $i=1$ のときは $f[i]=1$ 、 $i=2$ のときは $f[i]=2$ とします。それ以降はいつものフィボナッチ数列になります。
あとは、 $k$ を入力したときに、 $i$ と $j$ が何かがわかれば、答えを求めることができます。
ここも実験をしてみます。
$i$ と $j$ を探索してひたすら試します。
プログラムを組み、 $i$ と $j$ の範囲を1~15あたりにして実験すると見えてきます。
まず、以下のことがわかります。

$i \neq a,j \neq b$ のとき、 $f[i]×f[j] = f[a]×f[b]$ となるのは $i=b$ かつ $j=a$ の場合のみ

つまり、被りが存在しないということです。

そして、肝心の順番はこうなっています。

$f[i]×f[j]$ は、 $i+j$ が小さい順に並んでいる。
$i+j$ が等しい中では、 $i \leqq j$ としたときに、 $i:1,3,5,7,9...8,6,4,2$ という順番で出てくる。

例えば、 $10 \leqq k \leqq 12$ のとき、 $i+j=7$ になっているのですが、
順番に $(i,j)= (1,6),(3,4),(2,5)$ と並んでいます。
あとは、この法則をうまくプログラムに落とし込み、計算をします。
$i+j$ は二分探索で調べます。 $2$ ～ $10^{9}$ ぐらいまでの範囲をとっていれば十分です。
$(i+j) \leqq \frac{p}{2}×\frac{(p+1)}{2}$
を満たすような最小の $p$ が $i+j$ の答えになります。
次に、 $i$ の数字を特定します。これができれば、 $j=p-i$ で $j$ も求めることができます。
$i+j=p$ のときの $i$ のパターン数は、 $\frac{p}{2}$ となっています。また、それまでの総和が

$\frac{(p-1)}{2}×\frac{p}{2}$ なので、 $i+j=p$ の $\{k - \frac{(p-1)}{2}×\frac{p}{2}\}$ 番目が求めるものになります。長いので、これを $q$ と置きます。
$q$ が $\frac{p}{2}$ の半分を超えているかどうかで $i$ の偶奇を判定します。超えていなければ奇数、超えていれば偶数になります。
奇数のときは、そのまま $i=2×q - 1$ とすれば完了です。
偶数のときは、 $i=2×(\frac{p}{2}-q+1)$ となります。
$i$ が求まったので、 $j=p-i$ で $j$ を求めます。あとは、
$f[i]×f[j]$ を $10^{9}+7$ で割って余りを求めれば完了です。
これを求めるのは行列式を活用します。