(gcd・Kの倍数)DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 C問題 – ロト2

問題URL→http://ddcc2016-qual.contest.atcoder.jp/tasks/ddcc_2016_qual_c

分からなかったので解説を読んだ。
知らない重要知識を使っていた。
それは

xyがKの倍数である ⇔ gcd(x,K)*gcd(y,K)がKの倍数である

これを使うとgcd(A,K)の値の種類ごとにカウントしてO(N^2)回せばいい。

またgcd(A,K)は今回の制約K<=10^9くらいだと1400種類未満に抑えられる。 gcdの種類は多くなりづらいことに注意。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <sstream>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

#ifdef LOCAL
#define dump(…)                                         \
    do {                                                  \
        std::ostringstream os;                            \
        os << __LINE__ << “:\t” << #__VA_ARGS__ << ” = “; \
        print_to(os, “, “, “\n”, __VA_ARGS__);            \
        std::cerr << os.str();                            \
    } while (0)
#define dump_(a)                                          \
    do {                                                  \
        std::ostringstream os;                            \
        os << __LINE__ << “:\t” << #a << ” = [“;          \
        print_to_(os, “, “, “]\n”, all(a));               \
        std::cerr << os.str();                            \
    } while (0)
#else
#define dump(…)
#define dump_(…)
#endif

template <typename T>
void print_to(std::ostream &os, const char *, const char *tail, const T &fst) {
    os << fst << tail;
}
template <typename Fst, typename… Rst>
void print_to(std::ostream &os, const char *del, const char *tail, const Fst &fst, const Rst &… rst) {
    os << fst << del;
    print_to(os, del, tail, rst…);
}
template <typename Iter>
void print_to_(std::ostream &os, const char *del, const char *tail, Iter bgn, Iter end) {
    for (Iter it = bgn; it != end;) {
        os << *it;
        if (++it != end) {
            os << del;
        } else {
            os << tail;
        }
    }
}
template <typename Fst, typename… Rst>
void println(const Fst &fst, const Rst &… rst) {
    print_to(std::cout, “\n”, “\n”, fst, rst…);
}
template <typename Fst, typename… Rst>
void print(const Fst &fst, const Rst &… rst) {
    print_to(std::cout, ” “, “\n”, fst, rst…);
}
template <typename Iter>
void println_(Iter bgn, Iter end) {
    print_to_(std::cout, “\n”, “\n”, bgn, end);
}
template <typename Iter>
void print_(Iter bgn, Iter end) {
    print_to_(std::cout, ” “, “\n”, bgn, end);
}

// const int MOD = 1000000007;
namespace trush {
    int _ = (std::cout.precision(10), std::cout.setf(std::ios::fixed), std::cin.tie(0),
             std::ios::sync_with_stdio(0), 0);
}

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

int N, K;
int A;
map<int, int> cnt;

signed main()
{
    cin >> N >> K;
    REP(i,N) {
        cin >> A;
        cnt[gcd(A, K)]++;
    }

    int ans = 0;
    for (auto it=cnt.begin(); it!=cnt.end(); it++) {
        for (auto it2=cnt.begin(); it2!=cnt.end(); it2++) {
            if (it->first * it2->first % K == 0) ans += it->second * it2->second;
        }
        if (it->first * it->first % K == 0) {
            ans -= it->second;
        }
    }

    cout << ans / 2 << endl;
}

(括弧問題・DP)天下一プログラマーコンテスト2016予選B-B

問題URL→http://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_b

よくある括弧だけの文字列の問題。これからこういう問題は括弧問題と言うことにしよう。
今回の解法は他の括弧問題にも応用が利きそう。

DPだということにはすぐ気づいたが実装でバグらせた。
そのバグったコードはコメントアウト部分。
結局解説や他の人のコードを見た。
最終的に納得したのははまやんさんのこのブログを見たとき。

自分のコードではdp[i][j][k]=valをi:今の位置、j:最後に変更した位置、k:変更回数、val:開き括弧の数-閉じ括弧の数
としていたが、それだとだめなようだ。

はまやんさんのコードではdp[i][j][k] = i文字目までで最後に変更したのがj文字目で
cnt(そこまでの'(‘の数-‘)’の数)の数がkである最小の変更回数
となっている。

自分のコードでvalを値としたのはマイナスになるかもしれないからだったけど、
よく考えるとマイナスになると多く閉じているのでおかしい。
よってvalはマイナスにはならないので値にする必要は無い。
そもそも求めたいものを値にするべき。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <sstream>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

#ifdef LOCAL
#define dump(...)                                         \
    do {                                                  \
        std::ostringstream os;                            \
        os << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; \
        print_to(os, ", ", "\n", __VA_ARGS__);            \
        std::cerr << os.str();                            \
    } while (0)
#define dump_(a)                                          \
    do {                                                  \
        std::ostringstream os;                            \
        os << __LINE__ << ":\t" << #a << " = [";          \
        print_to_(os, ", ", "]\n", all(a));               \
        std::cerr << os.str();                            \
    } while (0)
#else
#define dump(...)
#define dump_(...)
#endif

template <typename T>
void print_to(std::ostream &os, const char *, const char *tail, const T &fst) {
    os << fst << tail;
}
template <typename Fst, typename... Rst>
void print_to(std::ostream &os, const char *del, const char *tail, const Fst &fst, const Rst &... rst) {
    os << fst << del;
    print_to(os, del, tail, rst...);
}
template <typename Iter>
void print_to_(std::ostream &os, const char *del, const char *tail, Iter bgn, Iter end) {
    for (Iter it = bgn; it != end;) {
        os << *it;
        if (++it != end) {
            os << del;
        } else {
            os << tail;
        }
    }
}
template <typename Fst, typename... Rst>
void println(const Fst &fst, const Rst &... rst) {
    print_to(std::cout, "\n", "\n", fst, rst...);
}
template <typename Fst, typename... Rst>
void print(const Fst &fst, const Rst &... rst) {
    print_to(std::cout, " ", "\n", fst, rst...);
}
template <typename Iter>
void println_(Iter bgn, Iter end) {
    print_to_(std::cout, "\n", "\n", bgn, end);
}
template <typename Iter>
void print_(Iter bgn, Iter end) {
    print_to_(std::cout, " ", "\n", bgn, end);
}

// const int MOD = 1000000007;
namespace trush {
    int _ = (std::cout.precision(10), std::cout.setf(std::ios::fixed), std::cin.tie(0),
             std::ios::sync_with_stdio(0), 0);
}

/*
string S;
int dp[110][110][310];

signed main()
{
    cin >> S;

    REP(i,110) REP(j,110) REP(k,310) dp[i][j][k] = -INF;
    dp[0][0][0] = (S[0] == '(' ? 1 : -1);
    REP(i,S.length()-1) {
        REP(j,110) {
            REP(k,310) {
                if (dp[i][j][k] != -INF) {
                    //変えない
                    if ((dp[i][j][k] + (S[i+1] == '(' ? 1 : -1)) >= 0)
                        dp[i+1][j][k+1] = dp[i][j][k] + (S[i+1] == '(' ? 1 : -1);
                    //変える
                    if ((dp[i][j][k] + (S[i+1] == '(' ? -1 : 1)) >= 0)
                        dp[i+1][i+2][k+2] = dp[i][j][k] + (S[i+1] == '(' ? -1 : 1);
                }
            }
        }
    }

    int ans = INF;
    REP(j,110) REP(k,310) if (dp[S.length()-1][j][k] == 0) {
        dump(k - (S.length() - j));
        ans = min(ans, k - ((int)S.length() - j));
    }

    cout << ans << endl;
}
*/

//dp[i][j][k] = i文字目までで最後に変更したのがj文字目で
//cnt(そこまでの'('の数-')'の数)の数がkである最小の変更回数
int dp[101][101][101];
string S;

signed main()
{
    cin >> S;

    int N = S.length();
    REP(i,N+1) REP(j,N+1) REP(k,N+1) dp[i][j][k] = INF;

    dp[0][0][0] = 0;
    REP(i,N) REP(j,N) REP(k,N+1) if (dp[i][j][k] != INF) {
        if (S[i] == '(') {
            dp[i+1][j][k+1] = min(dp[i+1][j][k+1], dp[i][j][k]);
            if (0 < k) dp[i+1][i][k-1] = min(dp[i+1][i][k-1], dp[i][j][k] + 1);
        } else {
            dp[i+1][i][k+1] = min(dp[i+1][i][k+1], dp[i][j][k] + 1);
            if (0 < k) dp[i+1][j][k-1] = min(dp[i+1][j][k-1], dp[i][j][k]);
        }
    }

    int ans = INF;
    REP(j,N) ans = min(ans, dp[N][j][0] + j);

    cout << ans << endl;
}

(最大流)POJ-3281-Dining

問題URL→http://poj.org/problem?id=3281

蟻本の問題。蟻本の解説が詳しい。
蟻本に書いてあるグラフで、左側の牛と右側の牛を結ぶ間の辺は1つの牛に1つのマッチングを対応させるために必要。

最大流はDinic(ディニッツ)法を使った。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
//#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;
const int dx[9] = {-1, 0, 0, 1, -1, -1, 1, 1, 0};
const int dy[9] = {0, -1, 1, 0, -1, 1, -1, 1, 0};

const int MAX_V = 10101;

//辺を表す構造体(行き先、容量、逆辺)
struct edge
{
    int to, cap, rev;
    edge() {}
    edge(int to, int cap, int rev) : to(to), cap(cap), rev(rev) {}
};

vector<edge> G[MAX_V];  //グラフの隣接リスト表現
int level[MAX_V];       //sからの距離
int iter[MAX_V];        //どこまで調べ終わったか

//fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge(int from, int to, int cap)
{
    G[from].push_back(edge(to, cap, G[to].size()));
    G[to].push_back(edge(from, 0, G[from].size()-1));
}

//sからの最短距離をBFSで計算する
void bfs(int s)
{
    memset(level, -1, sizeof level);
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int v = que.front(); que.pop();
        REP(i,G[v].size()) {
            edge &e = G[v][i];
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[v] + 1;
                que.push(e.to);
            }
        }
    }
}

//増加パスをDFSで探す
int dfs(int v, int t, int f)
{
    if (v == t) return f;
    for (int &i=iter[v]; i<G[v].size(); i++) {
        edge &e = G[v][i];
        if (e.cap > 0 && level[v] < level[e.to]) {
            int d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

//sからtへの最大流を求める
int max_flow(int s, int t)
{
    int flow = 0;
    for (;;) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof iter);
        int f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
}

const int MAX_N = 110;
const int MAX_F = 110;
const int MAX_D = 110;

int N, F, D;
bool likeF[MAX_N][MAX_F];   //食べ物の好き嫌い
bool likeD[MAX_N][MAX_D];   //飲み物の好き嫌い

signed main()
{
    cin >> N >> F >> D;
    REP(i,N) {
        int Fi, Di, f, d;
        cin >> Fi >> Di;
        REP(j,Fi) {
            cin >> f;
            f--;
            likeF[i][f] = true;
        }
        REP(j,Di) {
            cin >> d;
            d--;
            likeD[i][d] = true;
        }
    }

    int s = N * 2 + F + D, t = s + 1;

    //sと食べ物を結ぶ
    REP(i,F) add_edge(s, N * 2 + i, 1);

    //飲み物とtを結ぶ
    REP(i,D) add_edge(N * 2 + F + i, t, 1);

    REP(i,N) {
        //食べ物側の牛と飲み物側の牛を結ぶ
        add_edge(i, N + i, 1);

        //牛と好きな食べ物、飲み物を結ぶ
        REP(j,F) {
            if (likeF[i][j]) add_edge(N * 2 + j, i, 1);
        }
        REP(j,D) {
            if (likeD[i][j]) add_edge(N + i, N * 2 + F + j, 1);
        }
    }

    cout << max_flow(s, t) << endl;
}

(二部マッチング・最小点カバー)POJ-3041-Asteroids

問題URL→http://poj.org/problem?id=3041

縦の打ち方を左側頂点、横の打ち方を右側頂点とし、各小惑星を破壊できる頂点を結ぶと
問題は最小点カバー問題になる。つまり頂点を選んで全ての辺をカバーする。

最小点カバー問題は一般にはNP困難らしいが、二部グラフの場合は最大マッチングと等しくなるらしい。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

const int MAX_V = 3030;

int V;  //頂点数
vector<int> G[MAX_V];
int match[MAX_V];       //マッチングのペア
bool used[MAX_V];       //DFSですでに調べたかのフラグ

//uとvを結ぶ辺をグラフに追加する
void add_edge(int u, int v)
{
    G[u].push_back(v);
    G[v].push_back(u);
}

//増加パスをDFSで探す
bool dfs(int v)
{
    used[v] = true;
    REP(i,G[v].size()) {
        int u = G[v][i];
        int w = match[u];
        if (w < 0 || !used[w] && dfs(w)) {
            match[v] = u;
            match[u] = v;
            return true;
        }
    }
    return false;
}

//2部グラフの最大マッチングを求める
int bipartite_matching()
{
    int res = 0;
    memset(match, -1, sizeof match);
    REP(v,V) {
        if (match[v] < 0) {
            memset(used, 0, sizeof used);
            if (dfs(v)) {
                res++;
            }
        }
    }
    return res;
}

int N, K;
int R, C;

signed main()
{
    cin >> N >> K;
    V = N * 2;
    REP(i,K) {
        cin >> R >> C;
        R--; C--;
        add_edge(R, N + C);
    }

    cout << bipartite_matching() << endl;
}

(桁和・約数列挙)ARC-060-D-桁和 / Digit Sum

問題URL→http://arc060.contest.atcoder.jp/tasks/arc060_b

まず、制約が10^11や10^12あたりだったらO(√n)あたり主に約数列挙・素因数分解などを注意しよう。

2<=b<=√nと√n#include <iostream> #include <vector> #include <string.h> #include <stack> #include <queue> #include <algorithm> #include <climits> #include <cmath> #include <map> #include <set> #include <assert.h> #define REP(i,n) for(ll i=0;i<(n);i++) #define MOD 1000000007 #define int long long #ifdef int const long long INF = LLONG_MAX / 10; #else const int INF = 1010101010; #endif using namespace std; typedef long long ll; typedef vector<vector<ll>> mat; typedef pair<int, int> P; //typedef pair<double, double> P; //約数の列挙O(√n) vector<int> divisor(int n) { vector<int> res; for (int i=1; i*i<=n; i++) { if (n % i == 0) { res.push_back(i); if (i != n / i) res.push_back(n / i); } } return res; } int n, s; int f(int b, int n) { if (n < b) return n; else return f(b, n / b) + n % b; } signed main() { cin >> n >> s; if (s == n) { cout << n + 1 << endl; return 0; } for (int b=2; b*b<=n; b++) { if (f(b, n) == s) { cout << b << endl; return 0; } } vector<int> divs = divisor(n – s); set<int> ans; for (int div : divs) { int b = div + 1; if (f(b, n) == s) ans.insert(b); } if (ans.size() == 0) { cout << -1 << endl; } else { cout << *ans.begin() << endl; } }

(部分集合の部分集合を列挙・差集合)ARC-056-C-部門分け

問題URL→http://arc056.contest.atcoder.jp/tasks/arc056_c

分からなかったので解説を見たが、まだ良く分かっていない。
結局他の人のコードを見た。

最初、コードの下のほうのビット演算が何を意味しているのか分からなかったが、
どうやら部分集合の部分集合を列挙しているらしい。
蟻本に書いてあった。←これなくしたい

集合の演算でi^jは集合iと集合jの差集合i-jを表す!!(ただしjがiの部分集合のとき)

独立な集合i,j間の辺の重みの総和は全ての部分集合に含まれる辺の総和を前計算しておくと
ある集合iの辺の総和をsouwa(i)として
i,j間の辺の重みの総和は
souwa(i|j) – souwa(i)-souwa(j)で求められる!

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N, K;
int w[20][20];
int clq[1<<17];
int dp[1<<17];

signed main()
{
    cin >> N >> K;
    REP(i,N) REP(j,N) cin >> w[i][j];

    REP(i,1<<N) {
        int s = 0;
        REP(j,N) if (i & (1 << j)) {
            for (int k=j+1; k<N; k++) if (i & (1 << k)) {
                s += w[j][k];
            }
        }
        clq[i] = s;
    }

    dp[0] = 0;
    for (int i=1; i<(1<<N); i++) {
        dp[i] = 0;
        //↓部分集合iの部分集合を列挙する
        for (int j=i; j>0; j=(j-1)&i) {
            dp[i] = max(dp[i], dp[i^j] + clq[j] + K);
        }
    }

    cout << dp[(1<<N)-1] - clq[(1<<N)-1] << endl;
}

(倍々は計算量軽い)ARC-051-C-掛け算

問題URL→http://arc051.contest.atcoder.jp/tasks/arc051_c

ある時点の数列を昇順に並べた時に、a_1 * A >= a_Nとなると以降はa_1,a_2,a_3,・・・a_Nの順で周期的に更新されていくことになる。
よって周期的になるまでは愚直にシミュレーションして、周期に入ったら、その周期で割り算すればいい。

最初の愚直なシミュレーションだが、A=1の場合はコーナーケースでこれを除外すると、
計算量はO(N * log(max(a_i)))くらいになる。

倍々の計算量は軽いと覚えておこう。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

//(x^n)%modを求める
ll mod_pow(ll x, ll n, ll mod = MOD)
{
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

int N, A, B;
int a[55];

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

    sort(a, a + N);
    if (A == 1) {
        REP(i,N) cout << a[i] << endl;
        return 0;
    }

    while (B > 0) {
        if (a[N-1] <= A * a[0]) {
            break;
        }
        a[0] *= A;
        sort(a, a + N);
        B--;
    }

    if (B == 0) {
        REP(i,N) cout << a[i] % MOD << endl;
        return 0;
    }

    int mul = B / N;
    int remain = B % N;
    for (int i=remain; i<N; i++) {
        cout << a[i] * mod_pow(A, mul) % MOD << endl;
    }
    REP(i,remain) {
        cout << a[i] * mod_pow(A, mul + 1) % MOD << endl;
    }
}

(gcdとlcmの関係)ARC-050-C-LCM 111

問題URL→http://arc050.contest.atcoder.jp/tasks/arc050_c

最小公倍数(lcm)とあるので、まず次の公式は考えないといけない。

lcm(x,y) = (xy)/gcd(x,y)

この式が1ステップ目。
よってgcd(x,y)をまず考える。

1をN個ならべてできる整数をone(N)とする。(こういう簡略化定義大事)
よって次の値を考える

gcd(one(A), one(B)) = gcd(one(B), one(A) % one(B))

ここでone(A) % one(B) = one(A % B)

以下略(めんどくなった。公式解説みよう)

ポイントだけ

1001001001001のような数列は

a_1 = 1, a_(k+1) = 10^D ・a_k + 1の第B/D項

あとは解説通り行列累乗する。
今回初めて行列累乗をちゃんと理解して実装した。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#include <sstream>
#include <bitset>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int AA, BB, MM;

//行列A,Bの積ABを返す
mat mul(mat &A, mat &B)
{
    mat C(A.size(), vector<ll>(B[0].size()));
    REP(i,A.size()) {
        REP(j,B[0].size()) {
            REP(k,B.size()) {
                C[i][j] += A[i][k] * B[k][j];
                C[i][j] %= MM;
            }
        }
    }
    return C;
}

//行列AのA^nを返す ※行数列数は同じ
mat ppow(mat &A, ll n)
{
    mat B(A.size(), vector<ll>(A.size()));
    //REP(i,A.size()) B[i][i] = (1LL << 60) - 1;
    REP(i,A.size()) B[i][i] = 1LL;
    while (n) {
        if (n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int gcd(int a, int b)
{
    if (b == 0) return a;
    return gcd(b, a % b);
}

//(x^n)%modを求める
ll mod_pow(ll x, ll n, ll mod)
{
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

signed main()
{
    cin >> AA >> BB >> MM;

    mat A(2, vector<ll>(2));
    A[0][0] = 10LL; A[0][1] = 1LL;
    A[1][0] = 0LL;  A[1][1] = 1LL;
    A = ppow(A, AA - 1);

    int oneA = A[0][0]*1LL + A[0][1]*1LL;
    oneA %= MM;

    int D = gcd(AA, BB);
    mat B(2, vector<ll>(2));
    B[0][0] = mod_pow(10LL, D, MM); B[0][1] = 1LL;
    B[1][0] = 0LL;                            B[1][1] = 1LL;
    B = ppow(B, BB/D - 1);

    int oneBD = B[0][0]*1LL + B[0][1]*1LL;
    oneBD %= MM;

    cout << ((oneA * oneBD) % MM) << endl;
}

(K以下の数)Tenka1 Programmer Contest-D-IntegerotS

問題URL→https://beta.atcoder.jp/contests/tenka1-2017/tasks/tenka1_2017_d

K以下の数は、2進数で見たときにK自信と、ビットが立っている最も右のビットを伏せて、その右のビットは任意のもの。

semiexpさんのコードがすごくきれいだった。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int N, K;
int A[101010], B[101010];

int solve(int lim)
{
    int ret = 0;
    REP(i,N) {
        if ((lim & A[i]) == A[i]) {
            ret += B[i];
        }
    }
    return ret;
}

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

    int ret = solve(K);
    REP(i,30) {
        if (K & (1 << i)) {
            int K2 = (K - (1 << i)) | ((1 << i) - 1);
            ret = max(ret, solve(K2));
        }
    }
    
    cout << ret << endl;
}

(X座標Y座標を独立に考える)ARC-044-C-ビーム

問題URL→http://arc044.contest.atcoder.jp/tasks/arc044_c

全然分からなかったので解説とkmjpさんのブログを見た。

求めるものがマンハッタン距離であり、ビームもX軸方向、Y軸方向に飛んでくるので、
X座標Y座標を独立に考えることができる。
↑これ重要

あとはDPをするのだが、このDPが良く分からなかった。

#include <iostream>
#include <vector>
#include <string.h>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath>
#include <map>
#include <set>
#include <assert.h>
#define REP(i,n) for(ll i=0;i<(n);i++)
#define MOD 1000000007
#define int long long
#ifdef int
const long long INF = LLONG_MAX / 10;
#else
const int INF = 1010101010;
#endif
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
typedef pair<int, int> P;
//typedef pair<double, double> P;

int S[2];   //S[0]:W, S[1]:H
int Q;      //ビームが飛んでくる回数
vector<int> E[2][101010];   //E[方向][時刻]
int dp[101010];

signed main()
{
    cin >> S[0] >> S[1] >> Q;
    REP(i,Q) {
        int j;  //ビームが飛んでくる時刻
        int x;  //方向(0:縦、 1:横)
        int y;  //座標
        cin >> j >> x >> y;
        E[x][j].push_back(y-1);
    }

    ll tot = 0;
    REP(j,2) {
        memset(dp, 0, sizeof(dp));

        REP(i,100100) if (E[j][i].size()) {
            sort(E[j][i].begin(), E[j][i].end());
            if (E[j][i].size() == S[j]) {
                cout << -1 << endl;
                return 0;
            }

            for (int x : E[j][i]) {
                if (x) dp[x-1] = min(dp[x-1], dp[x]+1);
                if (x<S[j]-1) dp[x+1] = min(dp[x+1], dp[x]+1);
            }
            reverse(E[j][i].begin(), E[j][i].end());
            for (int x : E[j][i]) {
                if (x) dp[x-1] = min(dp[x-1], dp[x]+1);
                if (x<S[j]-1) dp[x+1] = min(dp[x+1], dp[x]+1);
            }
            for (int r : E[j][i]) dp[r] = 1 << 30;
        }

        tot += *min_element(dp, dp + S[j]);
    }

    cout << tot << endl;
}