#include <vector>
using namespace std;

vector<int> next_comb(int n, int k, vector<int> v){

    for(int i = k-1; i >= 0; --i){
        if (v[i] != i+n-k){
            int t = ++v[i];
            for (int j = i+1; j < k; ++j){
                v[j] = ++t;
            }
            return v;
        }
    }

    for (int i = 0; i < k; ++i){
        v[i] = i;
    }
    return v;
}

vector<int> v = {0, 1, 2};
for (int i = 0; i < 10; ++i){
    for (int j = 0; j < 3; ++j){
        cout << v[j];
    }
    cout << endl;
    v = next_comb(5, 3, v);
}

/*
012
013
014
023
...
234
*/

2019-11-01

私のためのMacキーボード設定

最近バイトの関係でMacを使うようになったのだが、キーボード入力の文化が違いがストレスだったので、MacをWindowsっぽいキーボード入力に設定したときの覚書

システム環境設定 > キーボード > 入力ソース

で以下３点を変える

ライブ変換をオフ
Macでは入力中にスペースを押さなくても予測変換の第一候補に変換してくれる。私は変換したくない時に変換されるのが不便だったので外してある。
Windows風のキー操作をオン
returnキー1回で確定されるようになる。
Caps LockキーでABC入力モードと切り替えるをオン
Macでは入力ソースの切替ショートカットがデフォルトで(ctrl + space)になっているのだがとにかく素早く切り替えたいのでCaps Lock一発の方が私は馴染んだ。

f:id:urashima0429:20191101130021p:plain )

2019-06-02

E - Cell Distance

競プロ C++

atcoder.jp

考えたこと

$M * N$ マスのうち任意に2マス選ぶと、その2マスの選び方は残りの $M * N-2$ マスの中から $K - 2$ マス選ぶ選び方の個数回使われるということに気づけなかった。

#include <iostream>
using namespace std;

const long long mod  = 1e9 + 7;

long long modpow(long long a, long long n) {
    long long r = 1;
    // a^n = (n%2) ? (a^2)^(n/2) : a*(a^2)^(n/2)
    while(n) {
        r = r * ( (n%2) ? a : 1) % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return r;
}

long long modcomb(int n, int k) {
    if ( n < 0 || k < 0 || k > n) return 0;
    k = min(k, n - k); //nCk = nC(n-k)
    long long p = 1, q = 1;
    while ( k > 0 ) {
        p = p * n-- % mod; // p = n*(n-1)*(n-2)...(n-k+1)
        q = q * k-- % mod; // q = k*(k-1)*(k-2)...1
    }
    // 1/q = q^(p-2) (mod p)
    return p * modpow(q, mod - 2) % mod;
}

int main(){
    int N, M, K;
    cin >> N >> M >> K;
    long long x = 0, y = 0;
    for (int d = 1; d < N; ++d){
        x += 1LL * d * (N-d) % mod;
    }
    x = x * M % mod * M % mod;
    for (int d = 1; d < M; ++d){
        y += 1LL * d * (M-d) % mod;
    }
    y = y * N % mod * N % mod;
    cout << (x + y) % mod * modcomb(N * M - 2, K - 2) % mod << endl;
}

2019-05-23

ABC126E 1 or 2

C++ 競プロ

atcoder.jp

考えたこと

条件は

$M$ 個の $X_i, Y_i, Z_i$ が与えられ、 $A_Xi + A_Yi + Zi$ は偶数である。

なので、 $A_Xi$ の偶奇が分かれば $A_Yi$ の偶奇が一意に定まる。そこで枝 $(A_Xi, A_Yi)$ によって作られるグラフを考えると連結部分のうち一か所が分かれば、連結部分は一意に定まる。　　よって枝 $(A_Xi, A_Yi)$ によって作られるグラフの連結成分の個数を調べれば、その回数分の魔法だけで各連結部分の偶奇が一意に定まることとなる。実際にやることとしては、枝で繋がれている頂点同士を同一グループに分けて、そのグループの個数を調べればいいので、union-find木でAC。

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

const int MAX_N = 1e5;
int par[MAX_N + 10];
int size[MAX_N + 10];
int rankrank[MAX_N + 10];

void init(int n){
    for (int i = 0; i < n; i++){
        par[i] = i;
        size[i] = 1;
        rankrank[i] = 0;
    }
}

int getRoot(int x){
    if (par[x] == x){
        return x;
    }else{
        return par[x] = getRoot(par[x]);
    }
}

void unite(int x, int y){
    x = getRoot(x);
    y = getRoot(y);
    if (x == y) return;
    if (rankrank[x] == rankrank[y]) {
        par[y] = x;
        size[x] = size[x] + size[y];
        rankrank[x]++;  
    }else if (rankrank[x] < rankrank[y]) {
        par[x] = y;
        size[y] = size[x] + size[y];
    }else if (rankrank[x] > rankrank[y]) {
        par[y] = x;
        size[x] = size[x] + size[y];
    }
}

int getSize(int x){
    return size[getRoot(x)];
}

bool isSame(int x, int y){
    return getRoot(x) == getRoot(y);
}

int main(){
    int N, M;
    cin >> N >> M;
    init(N);
    for (int i = 0; i < M; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        --x; --y;
        unite(x,y);
    }

    set<int> s;
    int ans = 0;
    for (int i = 0; i < N; ++i){
        s.insert(getRoot(i));
    }
    for (auto ite = s.begin(); ite != s.end(); ++ite){
        ans++;
    }
    cout << ans <<endl;

}

2019-05-23

ABC126D Even Relation

C++ 競プロ

atcoder.jp

考えたこと

求めるグラフの条件は

同じ色に塗られた 任意の 2 頂点について、その距離が偶数である。

であるが、任意の2頂点間の距離を求めて、すべてが偶数かを確認する必要はない。なぜなら考えるグラフは木なので、閉路を持たず、各頂点間の距離は適当に選んだある根からの距離で一意に表現できるからだ。（実際、(1)を見れば一意に表せることがわかる。）

f:id:urashima0429:20190522111847p:plain — 図

そこで頂点iと頂点jの距離を $d(i,j)$ 、根を $r$ とすると $(1) : d(i, j) = d(r, i) + d(r, j) - 2d(r, w)$

と表せる。 $d(i,j)$ が偶数であるという条件について考えると(1)より $d(i,j) = 2n (n \in \mathcal{N})$
$\Leftrightarrow$ $d(r, i) + d(r, j) - 2d(r, w) = 2n$
$\Leftrightarrow$ $d(r, i) + d(r, j) = 2(n + d(r, w))$
すなわち $d(i, j)$ が偶数であることは $d(r, i)$ と $d(r, j)$ の偶奇が一致することと同値であることが分かる。

よってやることは
根 $r$ と各頂点 $i$ との距離 $d(r,i)$ を求めて( $O(N)$ )、 $d(r,i)$ の偶奇で01を出力すればよい。

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

const int MAX_N = 1e5;
struct edge{ int to, weight; };
vector<edge> Edges[MAX_N + 10];

int dir[MAX_N];

void dfs(int vertex, int parent, int distance){
    dir[vertex] = distance;
    for (auto e : Edges[vertex]){
        if (e.to == parent) continue;
        dfs(e.to, vertex, distance + e.weight);
    }
}

int main(){
    int N;
    cin >> N;
    for (int i = 0; i < N-1; ++i){
        int u, v, w;
        cin >> u >> v >> w;
        --u; --v;
        Edges[u].push_back(edge{v, w});
        Edges[v].push_back(edge{u, w});
    }

    dfs(0, -1, 0);
    for (int i = 0; i < N; ++i){
        if (dir[i] & 1){
            cout << 1 << endl;
        }else{
            cout << 0 << endl;
        }
    }
}

2019-05-21

ABC126C Dice and Coin

C++ 競プロ

atcoder.jp

考えたこと

愚直に各 $N$ の確率を求めればよい。以下のコードだと $O(min(N, M))$ だが、テストケースの 14.txt だけどうしても通らず…。なにか間違っているのか、それとも精度が足りないのか…。

#include <iostream>
#include <math.h>
#include <iomanip>
#include <algorithm>
using namespace std;
 
int main(){
    double N, K;
    cin >> N >> K;
    double ans = max( 0.0, 1.0-(K/N) );
    for (long long i = 1; i <= min(K, N); ++i){
        ans += 1.0 / ( N * pow(2.0, ceil( ( log(K) - log(i) ) / log(2) )));
    }
    cout << setprecision(15) << ans << endl;
}

そこで、制約を確認すると
$1 \leq N \leq 10^ 5, 1 \leq K \leq 10^ 5$
であるので計算量のはなし - Hello Wor.log 等を参考にすると $O(NlogK)$ か $O(Nlog^ 2K)$ 程度であることが予想できる。各Nに対して、何回2をかければKを超えるかは $O(log_ 2K)$ で求まるので、結局以下のコードで $O(NlogK)$ で求められてAC。

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

int main(){
    int N, K;
    cin >> N >> K;
    double ans = 0;
    for (int i = 1; i <= N; ++i){
        int num = i;
        int counter = 0;
        while (num < K){
            num*=2;
            counter++;
        }
        ans += 1/(double)(1<<counter);
    }

    cout << setprecision(15) << ans/(double)N << endl;
    return 0;
}

ついでに

入出力ストリームで浮動小数点型の桁数を指定しないと、勝手に丸められるので注意。デフォルトは6桁

#include <iomanip>
...
// 少数点以下2桁に固定
cout << fixed << setprecision(2) << 3.1415 << endl; // "3.14"