ARC102: D - All Your Paths are Different Lengths
問題概要
が与えられる。 個の頂点と 個の辺を持ち,かつ頂点から頂点への異なるパスがちょうど個あってそれらのパスがそれぞれであるような有向グラフを構成せよ。
(問題文は https://beta.atcoder.jp/contests/arc102/tasks/arc102_b に記載されている。)
制約
- 辺の重みは以上以下
アイディア
がだいたい であることから 進数を使うことを考える。
まず,もしも となる整数 があるならば,次のようなグラフを構成すればよい(画像は の例)。
次に, の場合について考える。
ここではわかりやすく具体的に考えるために とする。
上の図のグラフで,以上未満のパスはすでに生成されている。
次に, 以上 未満のパスについて考える。
以上のパスは必ず 以上なので, 以上 未満のパスについて考えた上で最後に を足しても問題がない。
ここで,頂点 から頂点 までのすべての行き方がちょうど 以上 未満のすべてのパスに一致していることに注目すると,頂点 から頂点 に の辺を張ることでこのグラフに 以上 未満のパスが生成される(次の図は実際に追加した例です)。
次に, 以上 未満のパスについて考える。
以上のパスは必ず 以上なので, 以上 未満のパスについて考えた上で最後に を足しても問題がない。
ここで,頂点 から頂点 までのすべての行き方がちょうど 以上 未満のすべてのパスに一致していることに注目すると,頂点 から頂点 に の辺を張ることで 以上 未満のパスが生成される(次の図は実際に追加した例です)。
次に, 以上 未満のパスについて考える。
以上のパスは必ず 以上なので, 以上 未満のパスについて考えた上で最後に を足しても問題がない。
ここで,頂点 から頂点 までのすべての行き方がちょうど 以上 未満のすべてのパスに一致していることに注目すると,頂点 から頂点 に の辺を張ることでこのグラフに 以上 未満のパスが生成される(次の図は実際に追加した例です)。
最後に, 以上 未満のパスについて考える。
以上のパスは必ず 以上なので, 以上 未満のパスについて考えた上で最後に を足しても問題がない。
ここで,頂点 から頂点 までのすべての行き方がちょうど 以上 未満のすべてのパスに一致していることに注目すると,頂点 から頂点 に の辺を張ることでこのグラフに 以上 未満のパスが生成される(次の図は実際に追加した例です)。
これを他の についても適用することでこの問題を解くことができる。
また,ここで であることから であり,頂点が 個あれば(ギリギリではあるが)グラフを生成することができることがわかる。そして,各頂点から最大で 個の辺が張られるので,辺の数の条件も満たすことができることがわかる。
実装
まず を入力として受け取り となる整数 を求める。このとき,頂点数 は となる。
次に, となる各 に対して,頂点 から頂点 に と の辺を張る。このとき,辺を つ追加するたびに辺の数をカウントしておく。
そして, として次のようなループを回す。
- が 以上ならループを終了する。
- となる整数 を求める。
- 頂点 から頂点 に の辺を張る。
- に を追加する。
最後に を出力して,そのあと 行でグラフを出力すればよい。
コード
#include <iostream> using namespace std; int N,M=0,u[66],v[66],w[66]; void addedge(int s, int t, int l){ u[M] = s; v[M] = t; w[M] = l; ++M; } int l2(int x){ int l = 0,r = 25,m; while(r - l > 1){ m = (l+r)/2; if(x < (1<<m)){ r = m; }else{ l = m; } } return l; } int main(void){ int L,p,t,i,l; cin >> L; p = l2(L); N = p+1; for(i=0; i<p; ++i){ addedge(i+1,i+2,0); addedge(i+1,i+2,(1<<i)); } l = (1<<p); while(l < L){ t = l2(L-l); addedge(t+1,N,l); l += (1<<t); } cout << N << " " << M << endl; for(i=0; i<M; ++i){ cout << u[i] << " " << v[i] << " " << w[i] << endl; } return 0; }
ABC106: D - AtCoder Express 2
問題概要
の個の数の組が与えられる。を満たすそれぞれのについてかつを満たすの個数を求めよ。
(問題文は https://beta.atcoder.jp/contests/abc106/tasks/abc106_d に記載されている。)
制約
アイディア
の制約がと小さいことに注目する。
とりあえず,次のような表を作ることを考える。
行目の列目にはかつを満たすの個数が入っている。
例えば「入力例 3」を例に取ると,表は以下のようになる。
そして,この表の行目の列目の要素をと表すことにすると,クエリに対する答えはとなる。
例えば「入力例 3」のつ目のクエリに対する答えは,下の表の黒く塗られたセルの値の和になる。
すべての考えられる答えを2次元累積和によって先に求めておくこともできるが,ここではクエリごとにメモ化再帰で求めることを考える。
メモ化再帰をするためにに関する漸化式をたてる。
「入力例 3」のつ目のクエリで考えると以下のようになる。
(配色が悪くてごめんなさい... 紫色の部分は赤色と青色が重なっていると考えてください。)
上の図で,黒色に塗られた部分はである。また,赤色(紫色を含む)部分はとなっていて,青色(紫色を含む)部分はとなっている。さらに,赤色と青色が重なって紫色になっている部分はとなっている。
ここから求めたい部分は赤色(紫色を含む)部分と青色(紫色を含む)部分の和からダブルカウントした紫色部分を引いたところに黒色の部分を足したものであることがわかるので,となることがわかる。
さらに,これを一般化するととなる。なお,ここでまたはのときとしておくと便利である。
実装
最初にすべてのについてとし,のそれぞれについてにを加える。
次にすべてのについてに初期化しておく(理由は後述する)。
そして,次のような関数を考える。
またはのときを返して終了する。
のとき を計算してに格納する。
を返して終了する。
ここで最初にとする理由は「のときにすでにを計算済みである」ようにして,すべてのについてを1回のみ計算し,あとは保存済みの計算結果を返すようにすることで計算量をにするためである。
このような関数を実装した上で,あとはを満たすそれぞれのについてを求めるのみである。
最終的に計算量は。
コード
#include "bits/stdc++.h" using namespace std; int N,ans[555][555],t[555][555]; int solve(int p, int q){ if(p > N || q == 0){ return 0; } if(ans[p][q] == -1){ ans[p][q] = solve(p,q-1) + solve(p+1,q) - solve(p+1,q-1) + t[p][q]; } return ans[p][q]; } int main(void){ int M,Q,i,L,R,p,q; fill(t[0],t[555],0); fill(ans[0],ans[555],-1); cin >> N >> M >> Q; for(i=0; i<M; ++i){ cin >> L >> R; ++t[L][R]; } for(i=0; i<Q; ++i){ cin >> p >> q; cout << (solve(p,q)) << endl; } return 0; }
注意点
Python3で提出した際に(おそらく再帰の深さの上限を超えたせいで)REが出ました。