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

naoya_t@hatenablog

いわゆるチラシノウラであります

Google Code Jam 2016 - Qualification Round

4/9 8am〜4/10 11am
hackercup以来のプロコン参加。

QRは27時間で、30点以上獲得すれば本選に進出。
QRに限っては、相談しながらやってもよくて、公開されていない謎言語で解いてもいい。
Project Eulerみたいに紙と鉛筆でもいいのかは分からない)

とりあえず(いつも通り)、予選通過確定のためにsmallから押さえる。
珍しくwrong tries無しでA (small 7pt) - A (large 8pt) - B (small 10pt) - C (small 10pt) - D (small 10pt) と進む。
smallはその場でAC/WA判定されるのだけれど、largeの判定は終了後なので、この時点で37点は確実なので予選通過確定。

その後、B (large 10pt) - C (large 20pt) - D (large 25pt) と解いて全完。
無事全問ACで100点通過しました

A. Counting Sheep

整数Nが与えられて、N,2N,3N,4N,...と唱えていって、0〜9の数字が全部出揃ったところで眠れる。
(N=3なら、3,6,9,12,15,18,21,24,27,30 でようやく0〜9が出揃って眠りに落ちる)
0で眠れないのは自明(Sampleに0があってよかったと内心思ってる)だけど、
この方法で眠れないなんてことがあるのか?Large制約の1e6までシミュレーションしてみる。
どんな数でも、いつかは眠れることを確認した上でコードを書く。
この制約ならSmall, Large共通コードで行ける。

(Small 7pt, Large 8pt)
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
#define rep(var,n)  for(int var=0;var<(n);var++)

ll solve(int N) {
  int f = 0;
  ll iN=0, i=0;
  for (i=1,iN=N; i<1e9; ++i,iN+=N) {
    for (ll x=iN; x>0; x/=10) {
      f |= (1 << (x%10));
      if (f == 0x3ff) return iN;
    }
  }
  return -1;
}

int main(){
  // 確認用コード
  //  for (int n=0; n<=1000000; ++n) {
  //     ll a = solve(n);
  //     printf("%d\t%lld\n", n, a);
  //  }

  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cout << "Case #" << (1+_t) << ": ";
    int N; cin >>N; // 0-1e6
    ll ans = solve(N);
    if (ans >= 0) {
      cout << ans << endl;
    } else {
      cout << "INSOMNIA" << endl;
    }
  }
  return 0;
}

B. Revenge of the Pancakes

表側(笑顔が描かれた面)が上向き下向きごっちゃになってるパンケーキを上からn枚ひっくり返す的な操作で、最小の操作数で全部上向きにする話。

(Small, 10pt)

とりあえず、smallの制約 (S≦10) なら全状態数 2^10=1024、各状態からの操作数10だし、何も考えずに全ての操作の結果を求めてゴールまでDijkstra法しちゃおうと。

// (略)
#include "dijkstra.cc"

void make_mp(vector<vector<int> >&mp, int L) {
  int S = 1 << L;

  for (int p=0; p<S; ++p) { // 1024
    for (int t=1; t<=L; ++t) { // 10
      int m = (1<<t)-1;
      int q = p - (p & m);
      for (int i=0,m0=1,m1=1<<(t-1); i<t; ++i,m0<<=1,m1>>=1) { // t
        if ((p & m0) == 0) q |= m1;
      }
      if (p != q) {
        mp[p][q] = 1;
      }
    }
  }
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
  	string s; cin >> s;

  	int L = s.size();
  	int p = 0;
  	for (int i=0,m=1; i<L; ++i,m<<=1) {
  	  if (s[i] == '-') p |= m;
  	}

  	int S = 1 << L;
  	vector<vector<int> > mp(S, vector<int>(S, INT_MAX));
  	make_mp(mp, L);

  	pair<list<int>, int> res = dijkstra1(mp, p, 0);

 answer:
    cout << "Case #" << (1+_t) << ": " << res.second << endl;
  }
}

Dijkstraの実装 (dikjstra.cc) は略。
当然これでSmallは通るんだけど、同じ戦略でLargeを通すのは無理なのでとりあえず先にC,Dへ。

(Large, 10pt)

Smallで求めた手順(Dijkstraの経路を+-のパターンに直したやつ)を眺めていて
これって何なの?DPか何か?と思って見てたんだけど
ふと、どの手でも、+と-の切り替わる箇所が確実に1つずつ減ってることに気づいて。
とすると、最初のパターンの+と-の切り替わり回数が答え?
違うな、最後に-----だともう1手使って+++++に直してるから。
// 元パターンの末尾に '+' をくっつけた文字列で、+と-の切り替わり回数を数えればいいってことでもあるね

#include <iostream>
#include <string>
using namespace std;
#define rep(var,n)  for(int var=0;var<(n);var++)

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
  	string s; cin >> s;

  	int L = s.size();
    char last = s[0];
    int sw = 0;
    for (int i=1; i<L; ++i) {
      if (s[i] != last) {
        ++sw;
        last = s[i];
      }
    }
    if (s[L-1] == '-') ++sw;

 answer:
    cout << "Case #" << (1+_t) << ": " << sw << endl;
  }
}

試しにこれでB-smallを再計算したら提出解と一致したので、B-largeもこれで投げてみた。

C. Coin Jam

0と1だけで表される長さNの "1[01]*1" な文字列を2進法から10進法で読んだ時にいずれも素数にならないものを、それぞれの記数法での値xの自明でない(1とxそのものを除く)約数1つずつとともにJ件列挙する。

(Small, 10pt)

SmallはN=16,J=50決め打ち。ってことは2進数で1000000000000001〜1111111111111111すなわち32769〜65535だけど、これなら全てを調べても大した計算量にはならなさそう。
10進でも16桁ならlong longに収まるし、C++でMiller-Rabin法書いたやつあるからそれ使って素数判定していけばいい。自明でない約数は、適当に1〜1000000ぐらいの素数リストを持っておいて、その中の数で割り切れなければ諦める、でJ=50件ぐらいなら出るんじゃないか(と予想)。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>

using namespace std;
typedef long long ll;
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

vector<int> primes;
char *is_prime = NULL;

void dealloc_sieve() {
  if (is_prime) { free((void*)is_prime); is_prime = NULL; }
}

int prepare_primes_until(int till) {
  is_prime = (char *)malloc(1+till);
  if (!is_prime) return -1;
  memset((void*)is_prime, 1, 1+till);
  primes.clear();

  for (int i=2; i<=till; i++){
    if (is_prime[i]) {
      primes.push_back(i);
      for (int j=i*2; j<=till; j+=i) is_prime[j] = false;
    }
  }
  return primes.size();
}

long long random(long long n)
{
  return (long long)rand() % n;
}

long long check_nontrivial_sqrt_1(long long m, long long a)
{
  long long r = (a * a) % m;
  return (1LL < a && a < m-1 && r == 1)? 0LL : r;
}

long long expmod(long long base, long long exp, long long m)
{
  if (exp == 0)
    return 1LL;
  else if (!(exp & 1))
    return check_nontrivial_sqrt_1(m,expmod(base,exp/2,m));
  else
    return (base*expmod(base,exp-1,m)) % m;
}

bool miller_rabin_test(long long n)
{
  return expmod((1LL+random(n-1)),n-1,n) == 1LL;
}

bool fast_prime(long long n, int times=3)
{
  if (n == 1) return false;
  if (n == 2) return true;
  else if (!(n & 1)) return false;

  for (int i=times; i>0; i--)
        if (!miller_rabin_test(n)) return false;
  return true;
}

ll nontrivial_divisor(ll n) {
  if ((n & 1LL) == 0LL) return 2LL;

  for (int i=1,c=primes.size(); i<c; ++i) {
    int prime = primes[i];
    if (prime >= n) return -1LL;
    if (n % primes[i] == 0) return primes[i];
  }
  // あきらめた
  return -1LL;
}

ll check(int N, int pat, vector<ll>& divisors) {
  for (int b=2; b<=10; ++b) divisors[b] = -1;

  ll n = 0, x;
  for (int b=2; b<=10; ++b) {
    n = 0; x = 1;
    for (int i=0,m=1; i<N; ++i,m<<=1) {
      if (pat & m) n += x;
      x *= b;
    }
    bool p = fast_prime(n, 4);
    if (p) {
      return -1;
    }

    divisors[b] = nontrivial_divisor(n); // bad
    if (divisors[b] == -1) return -1;
  }
  return n;
}

void solve(int N, int J) {
  int cnt = 0;

  vector<ll> divisors(11);

  ll pat_begin = (1LL << (N-1)) + 1, pat_end = (1LL << N) - 1;
  for (ll pat=pat_begin; pat<=pat_end; pat+=2) { // from 100..001 to 111..111
    ll n10 = check(N, pat, divisors);
    if (n10 > 0) {
      cout << n10;
      for (int b=2; b<=10; ++b) {
        cout << " " << divisors[b];
      }
      cout << endl;

      ++cnt;
      if (cnt == J) return;
    }
  }
}

int main(){
  prepare_primes_until(1000000);

  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cout << "Case #" << (1+_t) << ":" << endl;
    int N, J; cin >> N >> J;
    solve(N, J);
  }
}
(Large, 20pt)

LargeはN=32,J=500なので、long longでは無理だけど、計算量的には同じ方法で行けると思ったので、愚直にこのコードをpythonに翻訳してみた。

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
import random

primes = []
is_prime = []

def prepare_primes_until(till):
    global primes, is_prime
    is_prime = [True] * (till + 1)

    i = 2
    while i < till:
        if is_prime[i]:
            primes.append(i)
            j = i * 2
            while j < till:
                is_prime[j] = False
                j += i
        i += 1


def check_nontrivial_sqrt_1(m, a):
    r = (a * a) % m;
    if 1 < a < m-1 and r == 1:
        return 0
    else:
        return r


def expmod(base, exp, m):
    if exp == 0:
        return 1
    elif (exp & 1) == 0:
        return check_nontrivial_sqrt_1(m, expmod(base, exp/2, m))
    else:
        return (base * expmod(base, exp-1, m)) % m


def miller_rabin_test(n):
    return expmod((1 + random.randint(0, n-1)), n-1, n) == 1


def fast_prime(n, times=3):
    if n == 1: return False
    if n == 2: return True
    elif (n & 1) == 0: return False

    i = times
    while i > 0:
        if not miller_rabin_test(n): return False
        i -= 1

    return True


def nontrivial_divisor(n):
    if (n & 1) == 0: return 2

    i = 1
    c = len(primes)
    while i < c:
        prime = primes[i]
        if prime >= n: return -1
        if n % prime == 0: return prime
        i += 1

    return -1  # give up


def check(N, pat):
    divisors = [-1] * 11

    n = 0
    for b in range(2, 10+1):
        n = 0
        x = 1
        i = 0
        m = 1
        while i < N:
            if pat & m: n += x
            x *= b
            i += 1
            m *= 2
        p = fast_prime(n, 4)
        if p:
            return None

        divisors[b] = nontrivial_divisor(n)
        if divisors[b] == -1: return None

    return (n, divisors)


def solve(N, J):
    cnt = 0

    pat_begin = (2 ** (N-1)) + 1
    pat_end = (2 ** N) - 1
    pat = pat_begin
    while pat <= pat_end:
        res = check(N, pat)
        if res:
            n10, divisors = res
            print n10, ' '.join(map(str, divisors[2:11]))

            cnt += 1
            if cnt == J: return

        pat += 2


def main():
    prepare_primes_until(1000000)

    T = int(input())
    for t in range(1, 1+T):
        print 'Case #%d:' % t
        N, J = map(int, raw_input().split())
        solve(N, J)


if __name__ == '__main__':
    main()

D. Fractiles

古代文明の、鉛(L)と金(G)のタイルで組まれたフラクタルなタイル。
第c-1世代のパターンから第c世代のパターンを生成するルールが

  • L → 第1世代そのもの
  • G → 第1世代の長さ分のG

というもの。第1世代のパターンの長さをKとすると第C世代の長さはK^Cになる。
金が入っているなら欲しいのだけれど、汚れていてLなのかGなのか分からない。
院生バイトをS人雇って、1人につき1枚汚れを落としてLなのかGなのか判別することができる。
第1世代のパターンにGが入っているかどうかをS人のバイトで知ることができるだろうか。
できるとしたら、どの位置のタイルの汚れを落としてもらえば良いか。

(Small, 10pt)

S=Kなら、Kが何億枚だろうが、Cが何億世代だろうが、最初のK枚を調べればいいよね。
第1世代の1枚目がGなら全部Gになるし、Lなら第1世代のパターンがそこに来るはずだから。
でもまあ、それじゃ能がないと思って、1枚目を見なくても良いケースでは1枚目を見ないようにしてみた。

#include <iostream>
#include <vector>
using namespace std;

#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

vector<int> solve_s(int k, int c) {
  vector<int> ans;
  if (k == 1 || c == 1) {
    // all
    for (int i=0; i<k; ++i) ans.push_back(1+i);
  } else {
    for (int i=1; i<k; ++i) ans.push_back(1+i);
  }
  return ans;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cout << "Case #" << (1+_t) << ":";

    int K, C, S; cin >> K >> C >> S;

    vector<int> s = solve_s(K,C);
    if (s.size() <= S) {
      for (int i=0; i<s.size(); ++i) {
        cout << " " << s[i];
      }
    } else {
      cout << " IMPOSSIBLE";
    }
    cout << endl;
  }
}
(Large, 25pt)

さて。院生バイトがK人確保できない場合。
そもそも、何人いれば足りるんだろう。
それぞれの位置のL/Gパターンは、元の第1世代の何を表してる?
例えば、第1世代の長さkを3のとき、第2世代のパターンの全長は3^2=9、第3世代のパターンの全長は3^3=27となる。
それぞれのパターンの位置にk進法で番号を振ってみる
0,1,2
00,01,02,10,11,12,20,21,22
000,001,002,010,011,012,020,021,022,100,101,102,110,111,112,120,121,122,200,201,202,210,211,212,220,221,222
...
それぞれの位置、例えば第3世代の #021 のタイルは、第2世代のタイル#02がGならG、Lなら第1世代のタイル#1と同じものが来る。第2世代の#02は、第1世代の#0がGならG、Lなら第1世代の#2と同じものが来る。
てことは、G=1,L=0と見立てると、#021は第1世代の#0,#2,#1のORを取った値、あるいは3ビットで表現するとビット0,ビット2,ビット1が立った状態か。第1世代のタイルのどれかにGが入ってるならG,入っていないならLだと言えるから、この1枚だけ調べればOKってことになる。
第2世代だと、知りたい#0,#1,#2の真偽(3ビット分の情報)を1枚のタイル(2ビット分の情報しかない)で知ることはできなくて、#00,#01,#02 のように愚直に3枚調べるか(S=Kならそれでもよかった)、あるいは#01,#02 とか、#01,#12 のような2枚の組み合わせで調べることになる。
でも、#0〜#2の真偽を知るのに必要な最小枚数とその組み合わせをどう求める?
無理ゲーじゃない?(諦めムード)
いや、#01,#23,#45,#67,... #012,#345,#678,... みたいに取っていけばいいじゃん!
1枚にc(cは世代番号)ビットの情報があって、重複なく情報を得られるならk/c枚で足りる、いや、余りが出るからceil(k/c)枚で。余ったところは0でpaddingするとして、先の例のk=3,c=2だと #01, #20 みたいな感じで。
この最小枚数解がS以内に収まるならそれを返せばいいし、収まらないなら不可能と言えばいい。
タイル番号 #xyz は回答時には通し番号に変換する必要がある(10進法に直して+1するだけだけど)
※実装では計算の便宜上、#01,#20じゃなくて #10, #02 を求めてる

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

vector<ll> solve_l(int k, int c) {
  vector<ll> ans;
  for (int i=0; i<k; i+=c) {
    ll x = 0;
    for (int j=0; j<c; ++j) {
      if (i+j >= k) break;
      x = x*k + (i+j);  // k^c <= 1e18 < 2e63
    }
    ans.push_back(1+x);
  }
  return ans;
}

int main(){
  int _T; cin>>_T; // 1-100
  rep(_t,_T){
    cout << "Case #" << (1+_t) << ":";

    int K, C, S; cin >> K >> C >> S;

    vector<ll> s = solve_l(K,C);
    if (s.size() <= S) {
      for (int i=0; i<s.size(); ++i) {
        cout << " " << s[i];
      }
    } else {
      cout << " IMPOSSIBLE";
    }
    cout << endl;
  }
}