C言語 ポインタ同士の引き算
アドレスの差分にはならない.
int main(void){ int a[2]; int k = &a[1] - &a[0]; return 0; }
上のコードを実行したら, kを表示すると結果は1となる. 4ではない. ポインタ同士の引き算は内部でアドレスの値を引いた後にそのポインタが指している変数の型のバイト数(sizeof(変数の型))で割った結果を求めるようにコンパイラは働く.
実際に上のコードをコンパイルしたアセンブラを見ると,
0000000100000f9e <_main>: 100000f9e: 55 push rbp 100000f9f: 48 89 e5 mov rbp,rsp 100000fa2: c7 45 fc 01 00 00 00 mov DWORD PTR [rbp-0x4],0x1 //変数kに1が代入されている 100000fa9: b8 00 00 00 00 mov eax,0x0 100000fae: 5d pop rbp 100000faf: c3 ret
のようになっている. これは最適化を切ってコンパイルした結果である.
連続領域の場合最適化を切っていても, コンパイル時に相対距離が計算できるので, コンパイル時に計算してしまうようだ(下記の結果から推測).
次に, 連続領域に存在しないポインタの引き算を実行してみる.
int main(void){ int a[2], b[2]; int k = &b[0] - &a[0]; return 0; }
上のコードを最適化を切って, コンパイルしたアセンブラは以下のようになる.
0000000100000f90 <_main>: 100000f90: 55 push rbp 100000f91: 48 89 e5 mov rbp,rsp 100000f94: 48 8d 55 e0 lea rdx,[rbp-0x20] // rdx に &b[0]を代入 100000f98: 48 8d 45 f0 lea rax,[rbp-0x10] // rax に &a[0]を代入 100000f9c: 48 29 c2 sub rdx,rax // rdxからraxを引く 100000f9f: 48 89 d0 mov rax,rdx // rdxの値をraxに代入 100000fa2: 48 c1 f8 02 sar rax,0x2 //raxの値を右へシフト2する (rax /= 4) 100000fa6: 89 45 fc mov DWORD PTR [rbp-0x4],eax //変数kに代入する 100000fa9: b8 00 00 00 00 mov eax,0x0 100000fae: 5d pop rbp 100000faf: c3 ret
今回はコンパイル時には計算できないようで, sizeof(int)で割る処理が行なわれている(sar rax,0x2).
double 型でも同様なことをやっておく.
int main(void){ double a, b; int k = &a - &b; //1 int l = &b - &a; //-1 return 0; }
0000000100000f7b <_main>: 100000f7b: 55 push rbp 100000f7c: 48 89 e5 mov rbp,rsp 100000f7f: 48 8d 55 f0 lea rdx,[rbp-0x10] // rdx = &a; 100000f83: 48 8d 45 e8 lea rax,[rbp-0x18] // rax = &b; 100000f87: 48 29 c2 sub rdx,rax // rdx -= rax; 100000f8a: 48 89 d0 mov rax,rdx // rax = rdx; 100000f8d: 48 c1 f8 03 sar rax,0x3 // rax >>= 3; (rax /= sizeof(double)) 100000f91: 89 45 fc mov DWORD PTR [rbp-0x4],eax // k = eax; 100000f94: 48 8d 55 e8 lea rdx,[rbp-0x18] // rdx = &b; 100000f98: 48 8d 45 f0 lea rax,[rbp-0x10] // rax = &a; 100000f9c: 48 29 c2 sub rdx,rax // rdx -= rax; 100000f9f: 48 89 d0 mov rax,rdx // rax = rdx; 100000fa2: 48 c1 f8 03 sar rax,0x3 // rax >>= 3 (rax /= sizeof(double)) 100000fa6: 89 45 f8 mov DWORD PTR [rbp-0x8],eax // l = eax; 100000fa9: b8 00 00 00 00 mov eax,0x0 // return 0;を設定 100000fae: 5d pop rbp 100000faf: c3 ret
上記はコードとそのアセンブラの結果である.
sar rax,0x3
という命令があり, 右へ3シフトする. つまり sizeof(double) で割っているということ.
実際のポインタの値同士の引き算をするには?
int main(void){ int a[2]; int k = (int)&a[1] - (int)&a[0]; return 0; }
上のコードのkには4が代入される. int型にキャストしてから演算すればいい.
Codeforces #197 Div2 D Xenia and Bit Operations
問題概要
奇数回目に数列を左から隣同士を見て, ORを計算し, 偶数回目に数列を左から見て, XORを計算する. それぞれのステップで数列の要素数は半分になる. 数列の要素数が1になるまでこれを繰り返す.
はじめの数列がm回変化するので, m個の数列に対して要素数が1になるときの値を求める.
解法
奇数回目の計算はORで, 偶数回目はXORで計算しなければならないので, updata()関数で場合分けをして計算しなければならない. また, ORとXORの単位元は0なので, 初期値を0にして更新する. さらに, ORとXORは結合法則を満たすのでsegment treeのデータ構造を用いても問題ない. 以上のこと以外は, 通常のsegtreeと同じようにやればよい.
ミス
nは数列の数でないので注意.
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define REP(i,n) for(int i=n-1;i>=(0);i--) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(), (v).rend() #define eall(v) unique(all(v), v.end()) #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) #define OUT(x) cout << #x << " = " << x << endl; const int MOD = 1e9 + 7; const int INF = 1e9; const ll INFF = 1e18; template <class T> //T : dat[]の中身の型 class segtree{ public: int n; vector<T> dat; segtree(int n_): n(n_){ //n_要素数 n = 1; while(n < n_) n *= 2; dat.resize(n * 2, 0); //(1) 単位元 } void update(int k, T val){ // k番目の値(0-indexed)を val に変更 k += n - 1; //葉の節点 dat[k] = val; int cnt = 0; while(k > 0){ k = (k - 1) / 2; if(cnt % 2)dat[k] = dat[k * 2 + 1] ^ dat[k * 2 + 2]; else dat[k] = dat[k * 2 + 1] | dat[k * 2 + 2]; cnt++; } } }; int n, m; int main(void){ cin >> n >> m; segtree<int> seg(pow(2, n)); //大きさに注意 rep(i, pow(2, n)){ int a; cin >> a; seg.update(i, a); } rep(i, m){ int p, b; cin >> p >> b; p--; seg.update(p, b); printf("%d\n", seg.dat[0]); } return 0; }
ABC 009 D - 漸化式
問題概要
与えられた漸化式によって導かれるM番目の値を求めよ.
解法
andとxorの演算は, (G, 和, 積) := ({1,0}, xor, and)とすると, 環をなしている. また, 行列の演算は半環であれば, 成り立つ. これらのことから, 通常の行列ライブラリの和をxorへ, 積をandへ置換しても, 行列演算が行える.
注意する点は, andの単位元は1ではなく, 全ての桁に1を用意しなければならないので, 0xffffffffなどとしている.
ミス
行列計算の単位元を1のままやっていた. andとxorはそれぞれの桁に対して行われる演算なので, すべての桁に1を入れておく必要がある.
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const ll INF = 1e9; const ll INFF = 1e18; // N*N行列Aを作りたい場合 mat A(N, vec(N)); typedef vector<long long> vec; typedef vector<vec> mat; // +->and *->xor mat mul(mat &A,mat &B){ // A * B の計算 mat C(A.size(), vec(B[0].size())); for(int i = 0; i < A.size(); i++){ for(int k = 0; k < B.size(); k++){ for(int j = 0; j < B[0].size(); j++){ C[i][j] = C[i][j] ^ (A[i][k] & B[k][j]); //演算子置き換え } } } return C; } mat pow(mat A, long long n){ // A^n の計算 mat B(A.size(), vec(A.size())); for(int i = 0; i < A.size(); i++){ B[i][i] = 0xffffffffffffffff; //単位元 全ての桁に1が必要 } while(n > 0){ if(n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } int main(void){ int K, M; long long A[110], C[110]; cin >> K >> M; rep(i, K) cin >> A[i]; rep(i, K) cin >> C[i]; if(M <= K) { cout << A[M - 1] << endl; return 0; } mat B(K, vec(K, 0)); rep(i, K) B[0][i] = C[i]; rep(i, K - 1) B[i + 1][i] = 0xffffffffffffffff; //単位元 全ての桁に1が必要 auto Bn = pow(B, M - K); mat A0(K, vec(1)); rep(i, K) A0[i][0] = A[K - 1 - i]; auto ret = mul(Bn, A0); printf("%lld\n", ret[0][0]); return 0; }
ABC 029 D - 1
問題概要
1以上N以下の全ての数字のなかに数字1が全部でいくつ含まれているか?
解法
脳死しているので桁dpをする.
dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる数字の総数
という状態を決めてやればいい. 漸化式の遷移はすでにNより小さいのかどうかで場合分けした後, 今見ている桁が0, 1またはそれ以外で場合分けして丁寧にj, kの値を決めていけば大丈夫.
ミス
dpの状態を決めるのに悩んだ.
求めたいものが数字1の総数なので, dp[i][j]:= (上記)ijの時の1を使った数 という状態としてしまった.
状態数に求めたいものをいれることだってあるので注意. 桁dpは決めた状態を満たす数字の総数をメモっていくと考えておこう.
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define REP(i,n) for(int i=n-1;i>=(0);i--) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define eall(v) unique(all(v), v.end()) #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; const ll INFF = 1e18; string N; ll dp[12][2][12]; // dp[i][j][k] := i桁目まで見て, j==1ならNより小さい, 1を使った数がk回となる 数字の総数 int main(void){ cin >> N; rep(i, 12)rep(j, 2)rep(k, 12) dp[i][j][k] = 0; dp[0][0][0] = 1; rep(i, N.size()){ rep(j, 2)rep(k, 12){ if(dp[i][j][k] == 0) continue; if(j == 1){ // N より小さい dp[i + 1][1][k + 1] += dp[i][j][k]; // 1を選ぶ dp[i + 1][1][k] += dp[i][j][k] * 9; // 0,2, .. 9 を選ぶ }else{ if(N[i] == '1'){ dp[i + 1][0][k + 1] += dp[i][j][k]; //1を選ぶ dp[i + 1][1][k] += dp[i][j][k]; //0を選ぶ }else if(N[i] == '0'){ dp[i + 1][0][k] += dp[i][j][k]; //0を選ぶ }else{//2 <= N[i] <= 9 dp[i + 1][0][k] = dp[i][j][k]; // N[i]を選ぶ dp[i + 1][1][k] = dp[i][j][k] * ((N[i] - '0') - 1); //2 ~ N[i]-1 dp[i + 1][1][k + 1] += dp[i][j][k]; //1を選ぶ } } } } ll ans = 0; rep(j, 2)rep(k, 12){ if(dp[(int)N.size()][j][k]){ ans += k * dp[(int)N.size()][j][k]; } } cout << ans << endl; return 0; }
CODE THANKS FESTIVAL 2015 G - カメレオン
問題概要
頂点1からNまでの最短コストを求めよ. ただし辺のコストtに加えて, 辺を通る時の色が決められているので, 色を変えるのにもコストがかかる. xからyに色を変える場合のコストは, |x-y|である.
解法
拡張ダイクストラをすればいい.
dist[i][j]として 頂点0からiまで, iへ色jで来た時の最小コストとして ダイクストラで計算していけばいい. ただし, 今回の問題で普通に2次元配列を取るとMLEしてしまう. しかし, 頂点iで可能性のある色は, iと隣接する辺で指定される色のみなので, dist[i][j]のjは実際は全種類の色の総数分の空間を用意しなくて良いことになる.
ではどうするかだが, dist[i]を必要な分だけ拡張すればよいかなと考えたが, めんどくさいので, map<int, ll> dist[] とすることで, dist[i][j]のjが必要な分だけ用意できることになる.
ミス
2次元配列が欲しくて, そのままではMLEしてしまうが, 2つめの要素がまばらな時, mapを使えば楽に空間を減らせる.
mapの使い方に注意
dist[v]にkey=ncが登録されていないか, 登録されていたとしても, ncostより大きかを調べる場合に,
if(dist[v][nc] > ncost || dist[v].count(nc) == 0)
ではだめ.
if(dist[v].count(nc) == 0 || dist[v][nc] > ncost)
としなければならない.
std::mapは[]演算子で存在しない要素にアクセスすると自動的に追加されるしまうので, 左側に(先に評価される方)dist[v][nc]とすると, key=ncの要素がないのに作られてしまい, 右側の評価が意味のないものになってしまった.
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define REP(i,n) for(int i=n-1;i>=(0);i--) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define eall(v) unique(all(v), v.end()) #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; const ll INFF = 1e18; int N, M; int a[80010], b[80010], c[80010], t[80010]; using tup = tuple<ll, int, int>; vector<tuple<int, int, int>> G[40010]; // G[i] := i->j color time //dist[i][j] := 頂点iへcolor jでつくときのコストの最小値 map<int, ll> dist[40010]; void dijkstra(int start){ priority_queue<tup, vector<tup>, greater<tup>> que; // コスト 位置 color dist[start][1] = 0; que.push(make_tuple(0, start, 1)); while(!que.empty()){ ll cost; int u, color; tie(cost, u, color) = que.top(); que.pop(); if(dist[u][color] < cost) continue; // これでTLE回避 if(u == N - 1) break; for(auto tm : G[u]){ int v, nc, nt; tie(v, nc, nt) = tm; ll ncost = cost + abs(nc - color) + nt; // if(dist[v][nc] > ncost || dist[v].count(nc) == 0){ // dist[v][nc]の要素ができてしまう if(dist[v].count(nc) == 0 || dist[v][nc] > ncost){ dist[v][nc] = ncost; que.push(make_tuple(ncost, v, nc)); } } } } int main(void){ scanf("%d %d", &N, &M); rep(i, M) scanf("%d %d %d %d", &a[i], &b[i], &c[i], &t[i]); rep(i, M){ a[i]--; b[i]--; G[a[i]].pb(make_tuple(b[i], c[i], t[i])); G[b[i]].pb(make_tuple(a[i], c[i], t[i])); } dijkstra(0); ll ans = INFF; for(auto u : dist[N - 1]){ chmin(ans, u.se); } printf("%lld\n", ans); return 0; }
yukicoder No.492 IOI数列
問題概要
a1 = 1, ai = 100ai-1 + 1という数列がある.
第N項を1000000007と101010101010101010101で割ったあまりを求める.
解法
前半の解
数列の一般項を求めて計算するだけ. ただし, 数が大きくなるため, 逐次modをとったり, powmodでやらないと行けない. また行列を利用して, 第n項を求める方法でもよい. 蟻本p180参照.
後半の解
答えは周期11で回っているので, mod11をしたあとに, 計算すればいい.
サンプルなどから周期はありそうで, 周期の見つけ方は,
mod = 101010101010101010101 d = 0 for i in xrange(1, 30): print d % mod d = d * 100 + 1
1 101 10101 1010101 101010101 10101010101 1010101010101 101010101010101 10101010101010101 1010101010101010101 0 1 101 10101 1010101 101010101 10101010101 1010101010101 101010101010101 10101010101010101 1010101010101010101 0 1 101 10101 1010101 101010101 10101010101 1010101010101
ミス
行列を使った問題初めて.
コード
漸化式を解くパターン
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const ll INF = 1e9; const ll INFF = 1e18; // x^k (mod m) long long powmod(long long x, long long k, long long m){ long long ret = 1; while(k){ if(k & 1) ret = ret * x % m; x = x * x % m; k >>= 1; } return ret; } // 1/a mod(p(素数)) long long invmod(long long a, long long p){ return powmod(a, p - 2, p); } int main(void){ ll n; cin >> n; ll d = powmod(100, n, MOD) + MOD - 1; d %= MOD; d *= invmod(99, MOD); printf("%lld\n", d % MOD); if(n % 11 == 0){ printf("0\n"); return 0; } string s = "1"; n %=11; rep(i, n - 1){ s = "10" + s; } cout << s << endl; return 0; }
行列演算でanを求める.
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const ll INF = 1e9; const ll INFF = 1e18; typedef vector<long long> vec; typedef vector<vec> mat; mat mul(mat &A,mat &B){ // A * B の計算 mat C(A.size(), vec(B[0].size())); for(int i = 0; i < A.size(); i++){ for(int k = 0;k < B.size(); k++){ for(int j = 0; j < B[0].size(); j++){ C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % (ll)MOD; // mod } } } return C; } mat pow(mat A, long long n){ // A^n の計算 mat B(A.size(), vec(A.size())); for(int i = 0; i < A.size(); i++){ B[i][i] = 1; } while(n > 0){ if(n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } int main(void){ ll n; cin >> n; mat A(2, vec(2)); A[0][0] = 100, A[0][1] = 1; A[1][0] = 0, A[1][1] = 1; auto ret = pow(A, n - 1); ll an = (ret[0][0] + ret[0][1]) % MOD; printf("%lld\n", an); int m = n % 11; ll ans = 0; rep(i, m){ ans = ans * 100 + 1; } printf("%lld\n", ans); return 0; }
yukicoder No.491 10^9+1と回文
問題概要
1以上N以下の整数で、109 + 1 の倍数かつ回文の数の個数を求めな
解法
109+1の倍数かつ回文になるには, 109+1に回文をかければ良い. よって,
Nを109+1で割った数以下の整数で, 回文の個数を数えれば良い.
よって, dfsを用いて, その整数の桁数以下の桁数で作れる回文を作成し, その整数以下であるかをしらべてカウントした. 回文なので, 右半分は左半分と一致しているので, 左半分を作ったら, ひっくり返して右側にくっつければよい. 奇数桁の時は真ん中に注意.
もっと単純にできる. N <= 1018よりN/(109+1)は109以下の整数になり, 回文の条件より, 左半分の5桁までを全探索すれば, すべての回文数を列挙できる.
ミス
もっと単純に全探索すればよかった.
int main(void){ ll n; cin >> n; ll cnt = 0; ll m = n / (1000000001); set<ll> se; for (int i = 1; i <= 100000; ++i){ string left = to_string(i); string right = left; reverse(all(right)); string even = left + right; string odd = left + right.substr(1); se.insert(stoll(odd)); se.insert(stoll(even)); } for(auto u : se) if(u <= m) cnt++; printf("%lld\n", cnt); return 0; }
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vint; typedef pair<int,int> pint; typedef vector<pint> vpint; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) #define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++) #define all(v) (v).begin(),(v).end() #define eall(v) unique(all(v), v.end()) #define pb push_back #define mp make_pair #define fi first #define se second #define chmax(a, b) a = (((a)<(b)) ? (b) : (a)) #define chmin(a, b) a = (((a)>(b)) ? (b) : (a)) const int MOD = 1e9 + 7; const int INF = 1e9; const ll INFF = 1e18; set<string> tmp; void dfs(string s, int cnt, int size){ if(cnt == size){ tmp.insert(s); return; } if(cnt < size / 2){ rep(i, 10){ string d = to_string(i); dfs(s + d, cnt + 1, size); } } if(cnt >= size / 2){ auto left = s; auto right = s; reverse(all(right)); if(size % 2 == 1){ rep(i, 10){ string d = to_string(i); tmp.insert(left + d + right); } }else{ tmp.insert(left + right); } } return; } ll solve(ll n){ ll ret = 0; string s = to_string(n); reps(cnt, 1, s.size() + 1){ reps(i, 1, 10){ auto d = to_string(i); dfs(d, 1, cnt); } } for(auto u : tmp){ ll d = stoll(u); if(d <= n) ret++; } return ret; } int main(void){ ll n; cin >> n; n /= (INF + 1); printf("%lld\n", solve(n)); return 0; }
