CADDi 2018 for Beginners

A:12/22

解法：

各桁毎にチェックしていく。

整数Ｎの１桁目はＮ％１０に等しい。

２桁目は（Ｎ／１０）％１０に等しい。以下同様

whileで実装する。

（わからない場合は確かめてみると良い）

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

signed main() {
  int n;
  cin >> n;

  int cont = 0;
  while (n > 0) {
    int tmp = n % 10;
    if (tmp == 2) cont++;
    n /= 10;
  }

  cout << cont << endl;
  return 0;
}

B:AtCoder Alloy

解法：

ある金属板(縦a横b)から縦Ｈ横Ｗの板を取り出せる条件は、

a>=H && b>=W　に他ならない。

この条件をみたすとき、回数を１増やせばよい。

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

int N, H, W;

signed main() {
  cin >> N >> H >> W;

  int cont = 0;
  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;

    if (a >= H && b >= W) cont++;
  }

  cout << cont << endl;
  return 0;
}

C:Product and GCD

考えたこと：

・まずPを素因数分解しないと話が始まらない。

ー＞ライブラリを貼る。

（持っていない場合はどんどん増やしていくと良いと思います。）

・P<=10^12といえども、素因数分解をして出てくる素因数の個数は高々４０個

ー＞理由：１０＾１２＜２＾４０

・前から順に公約数を取りながら回せばいいのだけれど、a[n]の全探索は無理そう。

解法：

求める最大個約数を「最大公約数」と呼ぶ。（厳密には最大の最大公約数なのだけれども）

・a[0~n-1]の最大公約数の素因数にXが含まれるための条件はなにか？

それは、Pが素因数Xをｎ個持っていること！

Pの素因数になりうる候補は、１から√Pまで。

なので、前から全探索をして、素因数の個数がｎ個以上であれば最大公約数はXを素因数にもつ！

といいたいところなのだけれども！

注意すべき点が二つある！

一つ目：Pの素因数の候補にPも含まれるということ！

（この場合はN=１の場合だけ見てあげればいい）

二つ目：素因数の個数がｎ＊ｋ個（ｋは１以上の整数）ある場合、最大公約数の素因数もXをｋ個含めてあげられるということ。すなわち最大公約数はX＾ｋを素因数にもつ。

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

int N, p;

//Ｏ(√n)
//素因数分解
map<int, int> prime_factor(int n) {
  map<int, int> res; // map[i]:=ｎを素因数分解したときiは何乗か。
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      while (n % i == 0) {
        res[i]++;
        n /= i;
      }
    }
  }
  if (n != 1)
    res[n] = 1;
  return res;
}

signed main() {
  cin >> N >> p;
  if (N == 1) {
    cout << p << endl;
    return 0;
  }

  map<int, int> mp = prime_factor(p);

  int ans = 1;
  for (int i = 2; i * i <= p; i++) {
    if (mp[i] / N > 0) ans *= pow(i, mp[i] / N);
  }

  cout << ans << endl;
  retu

D:Harlequin

・本番では嘘解法で通した。（下に載せています）

・実験をして規則をみるタイプの問題でした。

問題のキモとしては、

・すべてのa[i]が偶数の時。

ー＞どのように食べても、奇数個のリンゴが１つ以上出来る。

・１つ以上、奇数のa[i]があるとき。

ー＞奇数のa[i]をすべて１つずつ食べるようにすれば、相手に渡せるリンゴの個数a[i]は全て偶数となる。

なので、初めの状態で少なくとも１つ奇数のa[i]があるとき、先手は常に、後手に「すべてのリンゴの個数a[i]を偶数にした状態」で手番を渡せます。

リンゴの個数は毎ターン単調減少するので、いつかこのゲームは終わります。

ゲーム終了の合図はa[i]が全て０になることですが、これは全て偶数の状態です。

以上から、少なくとも１つ奇数があるとき、先手は全偶数状態を押し付け続けることができるので先手が勝ちます。

逆にすべて偶数の時は、先手は後手に奇数が少なくとも１つある状態で手番を渡してしまうので、同様に考えると（この瞬間からゲームが始まったと考えると）後手が勝ちます。

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

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

  for (int i = 0; i < N; i++) {
    int a;
    cin >> a;
    if (a % 2 == 1) {
      cout << "first" << endl;
      return 0;
    }
  }

  cout << "second" << endl;
  return 0;
}

 すみません！！！！！

ここから下のDの解法は嘘解法です！

このブログはここで終わりになります！！

嘘解法を見たい方のみどうぞ！

D:Harlequin

初めに思ったこと：

・grundy数を使う。

・アドホックな解法がある。

・規則性が存在する。

・前からDPしていく。（前の結果が使える。）

ー＞これはなさそう、a<=10^9,n<=10^5　デカすぎる。

解法：

用いたのはgrundy数を使う方法。

a[i]はsortしておく。（二部探索を使うので）（というか、できるのならばしておいて損はない）

・縦からa[i]の列を縦に並べる。xはリンゴ

　　1234567

a[0]  x

a[1]  xxx

a[2]  xxxxxx

a[3]  xxxxxxx

....

このとき、縦には取れるだけとれるので、縦の石の列をNimの石の山と見た。

具体的には、

・(i=0から順番に）リンゴがa[i]個以上ある縦の列の個数を求める。これをcont[i]とする。

ー＞これはlower_boundで求まる。O（N lon N)

次にgrundy数を求めていく。

a[i]の大きさによってまとめて計算していく。

具体的にはset<int>stにa[i]を挿入していき、すでに挿入されていればcontinueする。

・i=0のとき

リンゴの数がa[0]以上となる列の個数はcont[0]個である、このような列がa[0]個横に並ぶので、for(int i=0;i<a[0];i++)grundy^=cont[0];とすればよいのだが、これだと明らかに間に合わない。

xor演算においてx^x^x=xとなる性質を用いると、a[i]が奇数ならばgrundy^=cont[0]とし、偶数ならばcont[0]同士で打ち消しあうので、何もしなくてよい。

よって、

if(a[i]%2)grundy^=cont[0];

・i>0のとき

上と同様に考えるが、もしもa[i]と同じ値がa[j](i>j)に存在すればcontinue

ー＞何故なら、このような場合の処理は（a[i]個横にならんでいるので・・・）のくだりでまとめてされているから。

・continueされなかった場合。

i=0のときと同じように考えるが、注意すべき点は、cont[i]以上となる列が横に並ぶ個数

はa[i]ではなく、a[i]-a[i-1]個であるということ。その他の点は同じ。

よって、if((a[i]-a[i-1])%2)grundy^=cont[i];

これで値は求まった。

最後にgrundy=0ならばsecont

grundy!=0ならばfirstをする。

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

#define EXIST(s, e) ((s).find(e) != (s).end())

int N;
int a[101010], cont[101010];
set<int> st;

signed main() {
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
  }
  sort(a, a + N);

  for (int i = 0; i < N; i++) {
    cont[i] = (N - (int)(lower_bound(a, a + N, a[i]) - a));
  }

  int grundy = 0;
  for (int i = 0; i < N; i++) {
    if (st.find(a[i]) != st.end()) continue;

    if (i > 0) {
      if ((a[i] - a[i - 1]) % 2) grundy ^= cont[i];
    }
    if (i == 0) {
      if (a[i] % 2) grundy ^= cont[0];
    }

    st.insert(a[i]);
  }

  if (grundy != 0) {
    cout << "first" << endl;
  } else {
    cout << "second" << endl;
  }

  return 0;
}

感想：

C問題を１WA（コーナーケースを見落とした）

D問題を５WAした。（かなしい）

でも全完は全完！次も頑張ります！