Topcoder SRM 711 Div.1 Easy - ConsecutiveOnes

問題概要

整数n, kが与えられる。n以上の整数のうち、2進表現で1がk個続く部分を持つような数で最小のものを求めよ。

  • 0 <= n < 250
  • k <= 50

解法

1がk個続く箇所を全探索する。1が続く箇所より上位の桁はnと同じになるよう埋めるのが最善。より下位の桁は、場合分けする。(1) k個の1で埋めた箇所が、元のnでも全部1である場合→上位の桁同様、下位の桁もnと同じ数で埋める(こうしないとnを下回ってしまう) (2) そうでない場合→下位の桁は全部0で埋めてOK (こうしてもnを下回らない)

感想

地味にややこしく見えるがビット操作に慣れてきて結構簡潔に書けた

コード (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)

class ConsecutiveOnes {
public:
    ll get(ll n, int k) {
        ll ans = 1LL << 59;
        ll a = (1LL << k) - 1;
        
        for (int i = 0; i <= 60-k; ++i) {
            ll tmp = n | (a << i);
            if (tmp != n)
                for (int j = 0; j < i; ++j)
                    tmp &= ~(1LL << j);
            ans = min(ans, tmp);
        }

        return ans;
    }
};

Topcoder SRM 712 Div.1 Easy - LR

問題概要

N要素の数列S, Tが与えられる。Sに対してLとRという2種類の操作を行うことができる。操作の結果SをTに等しくできるか判定せよ。できるならば具体的に操作の列をひとつ示せ。なおTに等しくできる場合、操作の回数は100回以下になることが証明できる。

  • 操作L: S[i]の値をS[i]+S[i-1]とする。ただしi=0のときはS[i]+S[N-1]
  • 操作R: S[i]の値をS[i]+S[i+1]とする。ただしi=N-1のときはS[i]+S[0]

N <= 50, 0 <= S[i], T[i] <= 1015

解法

最終的にそれぞれの回数が同じであるならば、L, Rを行う順番は結果に影響しない。つまりLLLRRRもRRRLLLもRLRLRLも結果として出てくる数列は同じである。ゆえにまず操作を行う全体回数を決め打ちし、その中でまたLを行う回数を決め打ちするという全探索を行えばよい。操作の全体回数はO(log(max(T[i])))で抑えられそうだが、問題文で100回でOKといっているのでこれを素直に使えばいい。オーバーフローには注意が必要で、足し算を行うたび毎回Sの各要素がTを超えていないかチェックするとこれを避けることができる。

感想

オーバーフローが罠い

コード (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)

int N;
ll A[55];
ll B[55];
ll C[2][55];
const ll MAX = 1000000000000000;

class LR {
public:
    bool check(int L, int R) {
        REP(i, N) C[0][i] = A[i];
        int cur = 0, tar = 1;
        
        REP(l, L) {
            REP(i, N) C[tar][i] = C[cur][i] + C[cur][(i-1+N)%N];
            REP(i, N) if (C[tar][i] > MAX) return false;
            cur ^= 1;
            tar ^= 1;
        }
        
        REP(r, R) {
            REP(i, N) C[tar][i] = C[cur][i] + C[cur][(i+1)%N];
            REP(i, N) if (C[tar][i] > MAX) return false;
            cur ^= 1;
            tar ^= 1;
        }

        REP(i, N) if (B[i] != C[cur][i])
            return false;

        return true;
    }
    
    string construct(vector<ll> s, vector<ll> t) {
        N = s.size();
        REP(i, N) A[i] = s[i];
        REP(i, N) B[i] = t[i];

        REP(i, 101) REP(L, i+1) {
            int R = i - L;
            if (check(L, R)) {
                string ans = "";
                REP(_, L) ans += "L";
                REP(_, R) ans += "R";
                return ans;
            }
        }

        return "No solution";
    }
};

yukicoder No.109 N! mod M

https://yukicoder.me/problems/no/109

問題概要

T個の数の組(N, M)が与えられるので、それぞれでN! mod Mを求めよ

  • 1 <= T <= 100
  • 1 <= M <= 109
  • max(0,M−105) <= N <= 109

解法

まず自明なケースとして、NがMより大きい場合答えは0である(N!で掛ける数の中に必ずMが登場するため)。以下では N < Mとして考える。

サンプルを見ると、N=999999936, M=999999937 で答えが 999999936 というのが目につく。もしかしてMが素数ならば (M-1)! ≡ M-1 (mod M) というような法則でも成り立っているのだろうか…と思っていくつかの素数で実験してみると、どうやら当たっているように思える(実際にはウィルソンの定理として知られている)。この仮定に基づくとMが素数の場合にはM-1から始めてどんどん逆元をたどっていけば求めることが可能になる。ここで N >= M-105 という怪しげな制約が生きてきて、この遡りが105ステップ以内に終了することを保証してくれる。これでMが素数の場合は解けた。

次にMが合成数の場合。まずMが十分大きければ答えは必ず0になる。例えば M >= 106 とすると、制約より N >= 106-105 になる。ここでMを2以上の正整数2つ(m1, m2)の積で表すことにすると、その最大値は M/2 である。M > N > M/2 より m1, m2がともにN!の途中に現れることになるので、答えは0になる。一方、Mがそれより小さい場合には普通にmodをとりながら階乗を計算していけば答えを出すことができる。

感想

サンプルが優しいおかげでできた

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

bool is_prime(long n) {
    for (long i = 2; i * i <= n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

long solve() {
    auto s = readln.split.map!(to!long);
    auto N = s[0];
    auto M = s[1];

    if (M == 1)
        return 0;
    if (N == 0)
        return 1;
    if (N >= M)
        return 0;

    if (is_prime(M)) {
        long ret = M - 1;
        for (long cnt = M - 1; cnt > N; --cnt)
            ret = ret * powmod(cnt, M-2, M) % M;
        return ret;
    } else if (M < 10^^6) {
        long ret = 1;
        for (long i = 2; i <= N; ++i)
            ret = ret * i % M;
        return ret;
    } else {
        return 0;
    }
}

void main() {
    auto T = readln.chomp.to!int;
    while (T--)
        solve.writeln;
}

yukicoder No.387 ハンコ

https://yukicoder.me/problems/no/387

問題概要

Nマスが横に連なったハンコがあり、マスiには色Aiのインクがついている。(2N-1)マスの紙に対し、はじめこのハンコを左端が合うように置き、「ハンコを押すor押さない」→「ハンコを右に1マスずらす」という操作をN回繰り返す。各操作においてハンコを押すか押さないかは0/1の数列Bとして与えられる。紙の(2N-1)の各マスにおいて、最終的に押される色数の偶奇を答えよ。

N, A <= 105

解法

  • 同じ色は何回押しても1色とカウントされる → orっぽい
  • 押される色数の偶奇を知りたい → xorっぽい

ということからビット操作に落とせないか考える。

まずハンコ側の視点で考えると、ハンコ側のマスiが紙側のどのマスに押されることになるかは、単純にビット列Bをiだけシフトさせればわかる(B=101のとき、ハンコの0マス目は紙の0マス目、2マス目に押される。ハンコの1マス目は2マス目、4マス目に押される。…)。よって、同じ色のマスについてこのビット列のbitwise orをとれば、最終的にその色が押されるマスを出すことができる。あとはすべての色についてそのビット列を計算し、bitwise xorをとっていけばあるマスに押される色数の偶奇を出すことができる。

ビット列の長さが 2N-1 なので各操作にO(N)かかりO(N2)となるが、ビット操作にC++のbitsetみたいなのを使うとワード長分(?)定数倍高速化がかかって 1010 / 64 ≒ 108 くらいになって間に合うようになる。

感想

AtCoderでは絶対出ないタイプの問題だけど、前にhackerrankか何かでもN=105でO(N2)をbitsetドーンが想定解なのを見たことあるなあ

コード (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)

int N;
int A[101010];
int B[101010];
bitset<202020> bs;
bitset<202020> ans;
bitset<202020> tmp;
vector<int> rev[101010];

int main() {
    cin >> N;
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> B[i];

    REP(i, N) rev[A[i]].push_back(i);
    REP(i, N) bs[i] = B[i] == 1;

    REP(c, 101010) {
        tmp = 0;
        for (auto i: rev[c]) 
            tmp |= (bs << i);
        ans ^= tmp;
    }

    REP(i, 2*N-1) cout << (ans[i] ? "ODD" : "EVEN") << "\n";
}

KaggleのTitanicをやってみたよ

問題概要

Titanic: Machine Learning from Disaster

Kaggleの入門用として位置づけられているコンテスト?で、タイタニック号に乗っていた客のデータ(名前、年齢、客室の等級etc)が与えられるのでその生死を予測してくださいねというもの。実際の正解まで書いてある訓練用のデータと、正解は伏せられてるテスト用のデータが与えられるので、テスト用のデータに予測値を書き込んで提出してね、その正解率でスコアが出るよ、という感じです。

やったこと

1. ランダムフォレストの実装

これまでこの問題をやろうと思ってやめるを数か月繰り返してきたので、ランダムフォレストなる手法が有効であることはぼんやり把握していた。でググっていると診断人さんのブログにたどり着いた。

アルゴリズムの懇切丁寧な説明とC++の実装例が載っており、とりあえず自分でも実装してみて雰囲気を掴もうという気持ちになった。同じ言語で書いてもコピペになってしまいそうだったので競プロでよく使っているD言語で書いてみたが、まあ立ち位置的には似てるので結局割とコピペ感が強くなってしまった。

2. 欠損値の補完

ランダムフォレストができたので早速データをぶちこもうとすると、データ欠損の壁が立ちふさがる。この問題では一部項目でたまにデータがない部分があり、これをどうにかしないとちゃんとアルゴリズムを回すことができない。こういう欠損値への対処に関しては一般的にこれをやっておけば全部OKというようなやり方はないようで、都度アドホックなやり方でいい感じにデータを補完していく必要があるらしい(要出典)。この問題では特に年齢情報の欠損が多かったが、これはなんか名前にくっついてる敬称である程度推測可能らしい、ということを以下の記事を見て知った。

今回はとにかくさっき実装したランダムフォレストがちゃんと回るかを確かめたかったので、上の記事をそのまま参考に敬称内の平均年齢で欠損を埋めることにする。あとこまごました欠損があるが雰囲気で補った。

3. 提出

これでデータの体裁が整ったので、ランダムフォレストに投入する。データ数の少なさゆえに一瞬で終わった。早速提出してみたところ、スコア0.79904で約9000チーム中1500位くらいになった。

f:id:fluffyowl:20171113195521p:plain

自分で生み出したものが何もないのでどういう感情を持てばいいのか微妙だが、とりあえずランダムフォレストがちゃんと動いてるっぽいと言えそうな結果になったのは嬉しかった。

感想

競プロ志向が強いせいか、ランダムフォレストを実装しているときが一番楽しかった。まあ正直kaggleにおいてその辺の作業はかなりどうでもいい部分ではあると思うので、今後参加するときはもっと順位に効くところをちゃんとやっていければな~という感じです。とはいえ何かほんとにたくさんの情報がKernelに書き込まれていて、一体上位陣の優位性はどこから生まれているんだ…という疑問はある。ていうかまずは統計をちゃんと勉強しようね…

コード

以下に置きました。

yukicoder No.511 落ちゲー ~手作業のぬくもり~

https://yukicoder.me/problems/no/511

問題概要

無限行W列のグリッドで、2人ゲームが行われる。このゲームでは2人交互に長方形のブロックを上から落とし、ブロックの各列は一番下か他のブロックにつくまで落下を続ける。ブロックを落とすことである列の高さがHを超えたとき、そのブロックを落としたプレイヤーに1列につき1ポイント入る。すべての列がHを越えたとき多くのポイントを獲得している方が勝者になる。あるゲームでどこにブロックが置かれたかの記録が順番にN個与えられるので、ゲームの勝敗を求めよ。

W, N <= 105

H <= 1015

解法

Binary Indexed Tree で各列の高さを管理しつつ、並列二分探索をする。

まず列の高さをシミュレートするために区間add, 一点取得が高速でできるデータ構造が欲しい。これは区間add, 区間和取得が可能な普通のBITで実現できる。具体的にはimos法のイメージで、[l, r]に一律nを足すときはtable[l]にnを足し、table[r+1]に-nを足す。点xの現在値が知りたいときには[0, x]の区間和を取る。こうすると区間add, 一点取得ともにO(logW)でできるようになる。

次にある1列のみにおいてどちらが得点を得たかを判定してみる。これは前述のBITがあればブロックのクエリを二分探索してO(NlogNlogW)で求めることができる。

この二分探索を全部の列で行うことを考えると、普通にやったらO(NWlogNlogW)になって全く間に合わない。しかし各二分探索で探索する対象は同じであることを考えると、 これを全部並列に行うことで計算量を落とすことができる(並列二分探索)。具体的には以下のような手順で行う。

  • 各列について「今、二分探索のhigh, low, middleはどこか」を覚えておく。
  • BITで普通にブロックの積みをひとつずつシミュレートしていく
  • 途中で「今ここがmiddleである」という列があれば、普通の二分探索のようにhigh, lowの再計算を行う。
  • ブロックを最後まで積み終わったら、また最初に戻って積むことを繰り返す。
  • 全部の二分探索が収束したら終わり

個別の二分探索はlogN回で収束するため、ブロックの積みは高々logN回までしか繰り返されない。各繰り返し内でBITによるブロックのシミュレートはO(NlogW)かかるため、このパートはO(NlogNlogW)になる。また各二分探索の保持を平衡二分木とかでやると一回の処理がO(logW)ででる。そしてW個の二分探索それぞれがlogN回行われることになるので二分探索を捌くのはO(WlogNlogW)になる。2つのパートを合わせてO((N+W)logNlogW)となる。(たぶん)

感想

AGC002Dの解説で並列二分探索を知り、よくわからずにいろいろググってたらこの問題が並列二分探索の例題として挙げられていたのを見つけたので解いてみました。並列二分探索は頭良すぎて理解した瞬間感動しました。実装面の細かい話として最初各にぶたんを溜めておくところで連想配列内の動的配列に入れてたんですが、偏った入力で同じところへのpushがたくさん発生すると動的配列の伸長が起こりまくってクソ遅くなってしまったところ、平衡二分木に切り替えたらまともな速度になりました。そして何気にyukicoderの問題記録を書くのこれが初めての気がします。yukicoderも結構解いてるんですがブログに問題記録を書く習慣をつける前に適正レベルの問題を解きつくしてしまった感じなのであまり書く機会がありませんでした。今後もちょうどいいやつがあれば書いていきたいですね。この記事だけ異常に感想が長いな

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;


void main() {
    auto s = readln.split;
    auto N = s[0].to!int;
    auto W = s[1].to!int;
    auto H = s[2].to!long;

    auto A = new int[](N);
    auto B = new long[](N);
    auto X = new int[](N);

    foreach (i; 0..N) {
        s = readln.split;
        A[i] = s[0].to!int;
        B[i] = s[1].to!long;
        X[i] = s[2].to!int - 1;
    }


    auto ans = new int[](W);
    auto rbt = new RedBlackTree!(Tuple!(int, int, int, int), "a[3] < b[3]", true)();

    foreach (i; 0..W)
        rbt.insert(tuple(i, -1, N-1, (N-2)/2));


    for (int settled = 0; settled < W; ) {
        BIT height = new BIT(W+10);

        foreach (i; 0..N) {
            height.add(X[i], X[i]+A[i], B[i]);
            auto nodes = rbt.equalRange(tuple(0, 0, 0, i)).array;

            foreach (node; nodes) {
                auto col = node[0];
                auto lo = node[1];
                auto hi = node[2];
                rbt.removeKey(node);

                if (hi - lo <= 1) {
                    settled += 1;
                    ans[col] = hi % 2 ? -1 : 1;
                } else {
                    if (height.sum(col) >= H) hi = (hi + lo) / 2;
                    else lo = (hi + lo) / 2;
                    rbt.insert(tuple(col, lo, hi, (hi+lo)/2));
                }
            }
        }
    }

    if (ans.sum > 0) writeln("A");
    else if (ans.sum == 0) writeln("DRAW");
    else writeln("B");
}


class BIT{
    int n;
    long[] table;

    this(int n){
        this.n = n;
        table = new long[](n+1);
    }

    void add(int i, long x){
        i++;
        while (i <= n){
            table[i] += x;
            i += i & -i;
        }
    }

    // [l, r)
    void add(int l, int r, long x) {
        add(l, x);
        add(r, -x);
    }

    // [0, i]
    long sum(int i){
        i++;
        long ret = 0;
        while (i > 0){
            ret += table[i];
            i -= i & -i;
        }
        return ret;
    }

    // [l, r)
    long sum(int l, int r){
        if (l >= r) return 0;
        return sum(r-1) - sum(l-1);
    }
}

AtCoder Grand Contest 002 D - Stamp Rally

http://agc002.contest.atcoder.jp/tasks/agc002_d

問題概要

N頂点M辺の無向グラフがあり、頂点には1~N, 辺には1~Mの番号がついている。またQ個のクエリがあり、ひとつのクエリでは2つの頂点番号x, yと整数zが与えられる。各クエリごとに、x, yの2つを出発点として合計でz個の頂点を訪れるとき、通る辺の最大の番号の最小値を求めよ。

N, M, Q <= 105

解法

まずクエリが1回だけの場合を考える。最初グラフのすべての辺がなくなったものとして、ここに番号の小さい順から辺を追加していくことを考えると、この操作の過程でx, yから訪れることができる頂点数が初めてzを超えるタイミングが答えになることがわかる。具体的にはUnionFindを用いて、(1)もしxとyが同じ連結成分に入っていればその連結成分のサイズ (2)違う連結成分であればそれぞれのサイズの合計 を求めれば「x, yから訪れることができる頂点数」が割り出せるので、UnionFindで辺をつなぐたびこの値を計算すればよい。

この方法はクエリが複数回のときにも通用しそうに見える。つまりUnionFindで辺をつないでいく操作は各クエリの内容に関係なく共通なので、前計算しておけばよさそうな気がする。ただしここで問題があり、普通のUnionFindでは辺をつなぐ操作は非可逆的に行われるため「i番目の辺をつないだときの状態」を取り出すことができない。もちろん愚直には辺を追加した時点でコピーを作って取っておけば後から見ることができるが、これは計算量がかかりすぎる(時間も空間も)。

これを解決するのが (部分)永続UnionFind である。このデータ構造では空間計算量(N+Q)で以下の3つの操作をいずれもO(logN)で行うことができる。

  • unite(u, v): 頂点u, vをつなぐ
  • find(u, t): t回目のuniteを行った時点での頂点uの親
  • size(u, t): t回目のuniteを行った時点での頂点uが属する連結成分のサイズ

(仕組みとか実装に関してはhttps://camypaper.bitbucket.io/2016/12/18/adc2016/ がとてもわかりやすかったのでこちらを見てください)

これで各辺を追加した段階での特定頂点が属する連結成分のサイズをO(logN)で計算できるようになった。あとは各クエリごとに2分探索でzを超える瞬間の辺番号を求めればよい。合わせてO(Q(logN)2)となる。

感想

初めて永続的データ構造の類を使ったけど思ったよりゴテゴテしてなくてよかった(?)想定解はこれじゃなくて並列二分探索なるものらしいので要理解

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
 
const int INF = 1 << 29;
 
void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto uf = new PersistentUnionFind(N);
    foreach (i; 0..M) {
        s = readln.split.map!(to!int);
        uf.unite(s[0]-1, s[1]-1);
    }
 
    auto Q = readln.chomp.to!int;
    while (Q--) {
        s = readln.split.map!(to!int);
        auto x = s[0]-1;
        auto y = s[1]-1;
        auto z = s[2];
        int hi = M;
        int lo = 0;
        while (hi - lo > 1) {
            int size;
            int mid = (hi + lo) / 2;
            if (uf.find(x, mid) == uf.find(y, mid))
                size = uf.size(x, mid);
            else
                size = uf.size(x, mid) + uf.size(y, mid);
            if (size >= z)
                hi = mid;
            else
                lo = mid;
        }
        hi.writeln;
    }
}
 
class PersistentUnionFind {
    int[][] rank;
    int[][] time;
    int[][] parent;
    int n;
    int global_time;
 
    this(int n) {
        this.n = n;
        rank = new int[][](n);
        time = new int[][](n);
        parent = new int[][](n);
        foreach (i; 0..n) {
            rank[i] ~= 1;
            time[i] ~= 0;
            parent[i] ~= i;
        }
        global_time = 0;
    }
 
    void unite(int u, int v) {
        global_time += 1;
        u = find(u, global_time);
        v = find(v, global_time);
        if (u == v) return;
 
        if (rank[u] < rank[v]) swap(u, v);
 
        int r = rank[u].back + rank[v].back;
 
        rank[u] ~= r;
        time[u] ~= global_time;
        parent[u] ~= u;
 
        rank[v] ~= r;
        time[v] ~= global_time;
        parent[v] ~= u;
    }
 
    int find(int u, int t) {
        if (parent[u].back == u) return u;
        if (time[u].back > t) return u;
        return find(parent[u].back, t);
    }
 
    int size(int u, int t) {
        int v = find(u, t);
        int i = time[v].assumeSorted.lowerBound(t+1).length.to!int;
        return rank[v][i-1];
    }
}