ABC009 - D 漸化式
問題概要
二つの数列 と
が入力で与えられる。
数列 A は以下の式によって計算できる。
数列 A の M 番目の値を求めよ。
解き方
漸化式を計算するには、DPを使えば良いです。しかし、制約が大きく、DPでは解けません。
別の方法を使って漸化式を解く必要があります。
そこで、行列累乗を使います（あり本 P.180参照）。
行列累乗に and や xor が使えるのかですが、それは atcoder の公式解説を参照してください。
あり本を見ながらやれば実装できます。ほとんどあり本のプログラムそのままです。
正しい順番で値を入れて、正しい値で初期化して、演算子を変えましょう。
ただ、割と引っかかるポイントが多かったです。
気をつけるところ
and は論理積
bit の and が取りたい時は、 bitand か & を使いましょう。
各項の順番
行列に値を入れる際、右から左に並べるのか、左から右に並べるのか（もちろん上下も）。
and 演算子の単位元
普通に掛け算をするのであれば、単位元は 1 です。
あり本にあるプログラムや式は、行列の掛け算を行うため、 単位元に 1 が使われています。
しかし、この問題では and 演算子を使うため、単位元は全 bit が 1 の値です。
初期化ミスに気をつけましょう。
m ≤ k の時の処理
m ≤ k の時は、与えらえれた入力をそのまま返せば良いです。
入力を行列累乗のために逆順に持っていたことを忘れるとWAです（2敗）。
実装
#define int long long なので、単位元は -1 を使っています。
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; //const int INF = 1e8; using namespace std; #define int long long typedef vector<vector<int>> mat; mat mul(mat &a, mat &b){ mat c(a.size(), vector<int>(b[0].size())); rep(i,a.size()){ rep(k,b.size()){ rep(j,b[0].size()){ c[i][j] = (c[i][j] xor (a[i][k] bitand b[k][j])); } } } return c; } mat pow(mat a, int n){ mat b(a.size(), vector<int>(a.size(),0)); rep(i,b.size()) b[i][i] = -1; while(n > 0){ if(n & 1) b = mul(b,a); a = mul(a, a); n >>= 1; } return b; } int solve(int n, mat A, vector<int> c){ mat a(A.size(), vector<int>(A.size(), 0)); for(int i = c.size() - 1; i >= 0; i--){ //a[0][i] = c[A.size() - 1 - i]; ここの順番が逆だった。 a[0][i] = c[i]; } rep(i,c.size() - 1){ a[i + 1][i] = -1; } a = pow(a,n); //行列Aのn乗。 mat res = mul(a, A); return res[0][0]; } signed main(){ int k, m; cin >> k >> m; mat a(k, vector<int>(1)); vector<int> c(k); rep(i,k) cin >> a[k - i - 1][0]; rep(i,k) cin >> c[i]; if(m <= k){ cout << a[k - m][0] << endl; }else{ cout << solve(m - k,a,c) << endl; //-kを忘れずに } }
ABC025D - 25個の整数
D - 25個の整数
解説を見て実装を放置していたため、考察要素はないです。
問題概要
5 * 5 のマスがあります。 1 ~ 25 までの数値を、各マスに一つずつ書きます。
ただし、以下の条件を満たすように書かなければいけません。
縦、あるいは横に 3 つ並んだどのマスの数値も、単調減少、あるいは単調増加してはいけない。
あらかじめいくつかのマスはすでに数値が書かれています。
条件に従い全ての全てのマスを埋めるとき、何通りの埋め方がありますか。
考えたこと
制約は N ≤ 20 だけど、2^25のdpテーブル持ちたい…
2^25のdpテーブルをギリギリ持てた。
マスに何も書かれていない状態から考える。
dfsで 1 から順番に書いていき、全部埋められたら 1 を返す。
また、メモ化して無駄な部分を減らす。
元々数値が書いてあるということは、数値が書ける場所が 1 箇所しかないと考えられる。
bit と 2 次元の盤面を行き来する必要がある。
(x, y)は、bit の (x + y * 5) 番目と考えればよい。
実装
check関数で書けるかどうかの判定をしています。
atcoder公式の解説にある通り、数値を書く時のマスの状況が 4 種類に分けられます。
1. 端のマスに書き込む。
2. 書き込むマスの両側がすでに書き込まれている。
3. 書き込むマスの片方がすでに書き込まれている。
4. 書き込むマスの両方が書き込まれていない。
そして、書き込めないパターンは 3 番のみです。
書き込むマスの前後の bit の xor を取り、反転させれば条件を満たすかを判定できます。
それを縦横両方確かめ、and を取れば、書き込めるかわかります。
1 から順番に埋めていくため、実際に値の大小を比べる必要はありません。
dfs関数では、 num を書き込むマスを全通り試しています。
書き込める場所は、 "入力で 0 が与えられている" かつ "集合 s に含まれていない" 場所です。
1 から順番に書き込んでいくとはいえ、元々書き込まれている部分に書き込むことはできません。
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; using namespace std; const int M = 1000000007; int dp[1 << 25]; vector<bool> used_number(25,0); vector<bool> vacant_space(25,0); pair<int, int> p[25]; bool getBit(int num, int i){ return ((num & (1 << i)) != 0); } int setBit(int num, int i){ return num | (1 << i); } bool check(pair<int, int> p, int s){ int y = p.first; int x = p.second; bool xf, yf; if(x == 0 || x == 4){ //端に置くケース xf = true; }else{ bool left_bit = getBit(s, (x - 1) + y * 5); bool right_bit = getBit(s, (x + 1) + y * 5); xf = not (left_bit xor right_bit); } if(y == 0 || y == 4){ yf = true; }else{ bool up_bit = getBit(s, x + (y - 1) * 5); bool down_bit = getBit(s, x + (y + 1) * 5); yf = not (up_bit xor down_bit); } return xf and yf; } int dfs(int s, int num){ //s = 埋められた場所の集合 if(dp[s] != -1) return dp[s]; if(used_number[num]){ //あらかじめ数字が置かれている場合 int y = p[num].first; int x = p[num].second; int next = setBit(s, x + y * 5); if(check(p[num],s)){ return dfs(next, num + 1); }else{ return dp[next] = 0; } } int res = 0; rep(i,25){ // num を置ける場所を探す if(not getBit(s,i) && vacant_space[i]){ if(check(make_pair(i / 5, i % 5), s)){ res += dfs(setBit(s,i), num + 1); res %= M; } } } return dp[s] = res; } signed main(){ memset(dp, -1, sizeof(dp)); dp[(1 << 25) - 1] = 1; //全部埋まったら1通り rep(i,5) rep(j,5){ int a; cin >> a; if(a == 0) vacant_space[i * 5 + j] = true; else used_number[a - 1] = true; p[a - 1] = make_pair(i,j); } cout << dfs(0,0) << endl; }
AOJ 0553 ダンジョンの解説
AOJ 0553 ダンジョン
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0553
考察
問題点
あり本にある優先度キューを用いたガソリン問題と似ています。
ただし、こちらの問題では、ガソリンを入れられる量の上限があります。
体力が0以下になる前に、どこかで回復しなければいけない
->どうせ回復するなら一番回復量が多い泉を使いたい
->体力が0以下になった時に、最も回復量が高い泉を使ったことにすれば良い
これは優先度キューを用いれば実現できそうです。
やっかいなのは体力の上限で、「泉の回復量は多いが、体力が減っていないため、実際の回復量が小さくなる」ということが起きるため、優先度キューだけを用いてもうまくいきません。
「泉の回復量が多い順」ではなく、「実際の回復量が多い順」に並べなければいけません。
実際の回復量は、体力と泉の回復量がわかれば求めることができそうです。
そこで、各階を訪れた際の体力を持っておき、それを元に「実際の回復量」を決めましょう。
実際の回復量を求める
体力の更新方法をまずは考えます。
地下 i 階で体力が0になったので、地下 j 階で泉を使ったことにする（ i > j ）。
すると、当然地下 j 階〜 i 階の体力は増えます。つまり、区間に対する加算を行う必要があります。
また、加算した際に、体力が上限を超えてはいけません。
つまり、地下 j 階で体力を回復する場合、地下 j 階〜 i 階の区間のすべての体力は、（体力の上限 - j 階の回復量）以下である必要があります。
裏を返せば、地下 j 階の回復量は、（体力の上限 - 地下 j 階〜 i 階の区間で最大の体力）以下になります。
よって、実際の回復量を求めるためには、区間の最大値を求める必要があることがわかります。
方針
使うもの
優先度キュー、 セグメントツリー（区間に対する加算、 区間の最小値を求める）
１）体力をセグメントツリーに記録する
２）泉の情報をキューに入れる
３）体力を消費する
４）体力が0以下になったとき
１）最も回復量が多いものを取り出す
２）区間[回復する場所、現在地]の最大値を求める
３）体力の最大値 + 回復量 <= 体力の上限 のとき、その泉を使えるだけ使う。
使えないとき、実際の回復量を更新してキューに戻す。その後、1に戻る
４）泉を使って回復したことにし、区間に加算する。
実装
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; //const int INF = 1e8; using namespace std; #define int long long const int MAX_N = 100010; class segTree{ public: int n, dat[4 * MAX_N]; void init(int n_, int value, int dat_b[4 * MAX_N] = NULL){ n = 1; while(n < n_) n *= 2; rep(i,2 * n){ dat[i] = value; if(dat_b != NULL) dat_b[i] = value; } } void output(int a[4 * MAX_N]){ show("print"); range(i,1,n * 2) cout << (a[i] == INT_MAX ? 0 : a[i]) << ' '; cout << endl; } }; class starrySky : public segTree{ private: int query(int a, int b, int k, int l, int r){ if(b <= l || r <= a) return 0; if(a <= l && r <= b) return dat[k] + dat_add[k]; int vl = query(a, b, k * 2, l, (l + r) / 2); int vr = query(a, b, k * 2 + 1, (l + r) / 2, r); return max(vl, vr) + dat_add[k]; } void add(int a, int b, int k, int l, int r, int x){ if(b <= l || r <= a) return; if(a <= l && r <= b){ dat_add[k] += x; }else{ add(a, b, k * 2, l, (l + r) / 2, x); add(a, b, k * 2 + 1, (l + r) / 2, r, x); dat[k] = max(dat[k * 2] + dat_add[k * 2], dat[k * 2 + 1] + dat_add[k * 2 + 1]); } } void init(int n_){ segTree::init(n_,0,dat_add); } public: int dat_add[4 * MAX_N]; starrySky(int n){ init(n); } int query(int a, int b){ return query(a, b, 1, 0, n); } void add(int s, int t, int x){ add(s, t, 1, 0, n, x); } void add(int i, int x){ add(i, i + 1, 1, 0, n, x); } }; signed main(){ long long n, h; cin >> n >> h; //1-indexのセグ木 starrySky seg(n); //体力を保持する priority_queue<pair<long long, int>> q; //泉の回復量、pos long long cur = h, ans = 0; rep(i,n - 1){ long long damage, heal; cin >> damage >> heal; q.push(make_pair(heal, i)); seg.add(i + 1, cur); cur -= damage; while(cur <= 0){ pair<long long, int> use = q.top(); q.pop(); long long maxHP = seg.query(use.second + 1, i + 2); //回復地点から現在地までの体力の最大 if(maxHP + use.first > h){ //回復量が上限を超えるので、実際の回復量に変更 q.push(make_pair(h - maxHP, use.second)); continue; } long long can_use = (h - maxHP) / use.first; long long require = ceil((-1.0 * cur + 1) / use.first); long long used = min(can_use, require); ans += used; cur += used * use.first; seg.add(use.second + 1, i + 2, used * use.first); q.push(use); } } cout << ans << endl; }
構文解析初心者でも解ける問題を集めた＋解説
水色コーダーが構文解析の問題を解きました。その記録です。
問題の難易度は、AOJ−ICPC基準で300点前後だと思います。
- 構文解析とは
- 問題
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109&lang=jp
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2613
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1012
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155
- http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2570
- まとめ
構文解析とは
構文解析とは、やるだけ問題です。
ここ構文解析 Howto · GitHubにもそう書いてあります。
構文解析初心者の方は、まずはこれを読みましょう。
読みましょう。
ここを読めば、この記事で解説している問題に挑めるはずです。
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0109&lang=jp
四則演算の問題です。
テンプレを間違いなく写しましょう。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2613
問題概要
四則演算の優先順位を自由に入れ替えて、解を最大化しましょう。
ただし、割り算は使いません。
解法
全ての優先順位を全通り試せば良いです。
テンプレを見ると分かりますが、同じ関数にある演算子は優先順位が同じで、先に処理される演算子ほど優先度が高いです。
例えば、全ての演算子の優先順位を同じにしたければ、expr関数に全ての演算子を書けばいいです。
long long expr(State &begin) { long long ret = term(begin); for (;;) { if (*begin == '+') { begin++; ret += term(begin); } else if (*begin == '-') { begin++; ret -= term(begin); } else if (*begin == '*'){ begin++; ret *= term(begin); } else { break; } } return ret; }
とりあえず全部書けば通りますが、面倒なのでどうにかして楽に書きましょう。
4つのparserを書いたり*1、bitを使って全通り試したりしましょう。
ACされたコード
AIZU ONLINE JUDGE: Code Review
注意点
解の初期化に注意する
解のmaxを取っていくのなら、解を入れる変数を小さい数値で初期化しなければいけません。
ここでは最小値で初期化しましょう。雑に小さい数値を入れるとWAです。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1012
問題概要
集合の演算を行う構文解析です。
演算子は u, i, d, s, c の5つあり、式はセット名、演算子、括弧からなります。
この問題の式は、以下のように与えられます。
<expr> ::= <term> <op> <term> <term> ::= c <factor> | <factor> <factor> ::= ( <expr> ) | <set> <set> ::= A | B | C | D | E <op> ::= u | i | d | s
見様見真似なので、正しいか全く自信がないです。
解法
まさに構文解析という問題です。
形は変われどやっていることは同じです。
集合の計算は関数があるので、演算子の処理を考える必要はありません。
順番にテンプレを書き換えていきましょう。
number関数
集合を返すだけです。
文字列を数値に変換するなどの操作がないので、number関数を使わなくても問題ありません。
factor関数
括弧を処理するか数を返すかのどちらかなので、そのままで問題がなさそうです。
term関数
ここで行う演算は 'c' のみです。今見ている文字が'c'のとき、factor関数の戻り値を補集合にすればよいです。
'c'ではなかったら、戻り値をそのまま返します。
expr関数
四則演算で言うところの + や - にあたる部分を u, i, d, s を変えます。
条件分岐させて演算するようにします。
ACされたコード
AIZU ONLINE JUDGE: Code Review
構文解析部分は50行と短いです。
注意点
集合は始めにソートする。
set_unionやset_intersectionは、ソートされていないと正しい集合を返しません。
NULLを出力する。
解が空集合の場合、NULLを出力しなければなりません。
ここでいうNULLはテキストの "NULL" です。 '¥0' ではないです。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155
問題概要
0, 1, 2, P, Q, R, -, *, +, (, ) からなる式が与えられます。
P, Q, R は、それぞれ 0 ~ 2 までの数値へ置き換えることができます。
このとき、式の解が 2 であるような P, Q, R の組み合わせは何通りあるでしょうか。
解法
P, Q, R の組み合わせは 27 通りしかないので、全部試して解が 2 になる回数を数えればよさそうです。
次に、式をどのようにして演算すれば良いのかを考えます。
演算子 +, * は、与えられた数値のmax, minを取ればよいです。
- 演算子は、http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1012の c 演算子のように処理すればよさそうです。
つまり、expr→term（ここで - 演算子を処理）→factor→numberとすれば計算できます。
ただ、 - 演算子は連続することもあります。
ですので、もし - 演算子があれば、term関数を呼ぶ。
それ以外はfactor関数を呼ぶようにして、連続した - 演算子を処理します。
int term(State &begin){ if (*begin == '-') { begin++; //inverted(x) = xを反転した値 return inverted(term(begin)); } else { return factor(begin); } }
ACされたコード
AIZU ONLINE JUDGE: Code Review
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2570
問題概要
>>、S<>、数値からなる式を計算する。
解法
まず、空白はあってもなくても変わらないので全部消します。
次に、>> 、S<>について考えます。
>>はexprで処理し、S<>はfactorの括弧の処理を少し書き換えて実装します。
>>を素直に実装すると、
if(*being == '>' && *(begin + 1) == '>'){ begin++; begin++; ret = ret >> term(begin); }
とやってしまいそうですが、少しまずいです。
まず、この条件では、”S< S< S< 1 > > >” このようなケースのときに、シフトを行ってしまいます。
３ つ '>' が並んでいるときは、シフト演算子ではありません。
if(*begin == '>' && *(begin + 1) == '>' && *(begin + 2) != '>')
２ つのみ並んでいるときだけ、シフトしましょう。
次に、 "ret >> term(begin)" の部分に注目します。
上記の実装では、"1 >> 20000" という計算を行うこともあります。
これだとオーバーフローを起こして 0 ではない値になるので、シフト演算子の右辺は小さめに抑えたほうがよいです。
ACされたコード
AIZU ONLINE JUDGE: Code Review
注意点
2 乗でオーバーフロー
int型だとS<>を処理するときにオーバーフローします。
まとめ
- 処理を関数にまとめて、順番を決めて、終わり。
- バグらせると辛い。
vimに構文チェックのプラグインを入れた（C++）
syntastic
このようになりました。
導入の流れ
GitHub - vim-syntastic/syntastic: Syntax checking hacks for vim
丁寧に書いてあるので、特に迷うこともないと思います。
インストールの手順に沿って、上から順番にコマンドを実行していきましょう。
しかし、その状態ではエラーチェックが行われなかったので、正しく動作しているかを確かめるため以下のコマンドを入力しました。
:SyntasticInfo
明らかに動いていなさそう。
Q&Aによれば、構文チェッカーが有効になっていない可能性があるのこと。
以下を.vimrcに書き込みました。
let g:syntastic_cpp_checkers = ['gcc']
できまし……ん？
errorやwarningが出ます。
構文チェックがc++11に対応していません。
そこで、
let g:syntastic_cpp_compiler="gcc" let g:syntastic_cpp_compiler_options=" -std=c++11"
ちゃんとオプションをつけてあげましょう*1。
これで正しくチェックしてくれるようになりました。
w0rp/ale Asynchronous Lint Engine
こちら 脱VimしようとしてAtomを触ってたけど、やっぱりVimを使うことにした - console.lealog(); で速いとの情報を得たので、早速インストール
GitHub - dense-analysis/ale: Check syntax in Vim asynchronously and fix files, with Language Server Protocol (LSP) support
同じようにインストール。
syntasticがあると衝突するのでアンインストールしておきます。
導入してわかったこと
syntasticと比べて速い
確かに速い。スムーズに動きます。
ただ、エラー箇所を示す矢印（>>）の表示がやや遅いです。
結論
- ファイルが小さいなら、syntasticが極端に遅くなることはない。
- Asynchronous Lint Engineの方が速い。
- 適当にコマンドをコピペするだけでインストールできる
AOJ - 2170 Marked Ancestor
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2170
問題概要
木が与えられる。
以下の２つのクエリを処理し、出力された番号の合計を求める。
- 頂点aをマークする
- 頂点aから最も近いマークされた祖先の番号を出力する
解法
union-find
このスライドにある解法をそのまま実装した。
http://acm-icpc.aitea.net/index.php?plugin=attach&refer=2009%2FPractice%2F夏合宿%2F講評&openfile=3f.pdf
入力を隣接リストで受け取った後、クエリ ’M' だけを処理する。
マークされた頂点を記録する。このとき、同じ部分にマークされた場合、処理せずなかったものとして扱う。
その後、与えられた木を構築するためdfsを行う。このとき、depthに木の深さを記録した。
深さの情報をもとに、マークされなかった頂点と、その頂点の親をuniteした。
常に根に近い部分を親としてuniteしなければいけないため、深さを利用した。
後はクエリを逆順に処理していく。
’Q' クエリはfindし、値を足す。
'M' クエリは、自分の親とuniteする。
木を構築する、各頂点の親を持つ、uniteするときに根に近い頂点を親にする、などやることが多く実装に時間がかかった。
コード
#include<bits/stdc++.h> #define range(i,a,b) for(int i = (a); i < (b); i++) #define rep(i,b) for(int i = 0; i < (b); i++) #define all(a) (a).begin(), (a).end() #define show(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; const int INF = 2000000000; using namespace std; const int gmax_n = 100005; int par[gmax_n]; //親 int depth[gmax_n];//木の深さ void init(int n){ rep(i,n){ par[i] = i; depth[i] = 0; } } int find(int x){ if(par[x] == x){ return x; }else { return par[x] = find(par[x]); } } void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return; if(depth[x] > depth[y]){ par[x] = y; }else{ par[y] = x; } } bool same(int x, int y){ return find(x) == find(y); } void dfs(vector<int> t[gmax_n], int g[gmax_n], int cur){ rep(i,t[cur].size()){ int next = t[cur][i]; if(g[next] != -1) continue; depth[next] = depth[cur] + 1; g[next] = cur; dfs(t,g,next); } } int main(){ int n, m; while(cin >> n >> m, n||m){ vector<int> tree[gmax_n]; init(n); rep(i,n - 1){ //木の構築 int a; cin >> a; a--; tree[i + 1].emplace_back(a); tree[a].emplace_back(i + 1); } bool marked[gmax_n] = {false};//マークされるノードを記録 marked[0] = true; vector<pair<char, int>> q; rep(i,m){ char a; int b; cin >> a >> b; b--; if(a == 'M'){ if(marked[b]) continue; //同じ部分にマークした場合は、初回以外を無視。 else{ marked[b] = true; q.emplace_back(make_pair(a, b)); } }else{ q.emplace_back(make_pair(a,b)); } } int g[gmax_n] = {0}; range(i,1,gmax_n) g[i] = -1; dfs(tree, g, 0); rep(i,n){ if(not marked[i]) unite(g[i], i); } //rep(i,n) show(g[i]) //rep(i,n){ show(find(i)) } //rep(i,n){ show(depth[i]) } long long ans = 0; for(int i = q.size() - 1; i >= 0; i--){ //クエリを逆順に処理 if(q[i].first == 'Q') ans += find(q[i].second) + 1; else{ unite(g[q[i].second], q[i].second); } } cout << ans << endl; } }
ネットワークインターフェイスの名前
MacBook Air でifconfigして表示されたネットワークインターフェイス一覧。
lo0
ループバックアドレス
gif0
トンネリングを行う
en0
Ethernet
en1
有線のEthernet
stf0
IPv6パケットをIPv4ネットワークにルーティングする
awdl0
Handoffの機能用
bridge0
仮想インターフェイスを外部ネットワークに接続する
