ARC 032 B
今回はこの問題です。
n個の町とm本の道路があります。それぞれの道路はa[i]とb[i]の町をつないでいます。
現在の状況に対して新たに道路を加えることで任意の町同士を行き来できるようにしたいです。
このとき新たに作らないといけない道路の本数の最小値を求めましょう、という問題です。
回答はこちら。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define mod 1000000007 vector<int> uf(100001, -1); int getparent(int n) { if(uf[n] == -1){ return n; } else { return uf[n] = getparent(uf[n]); } } int main() { int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int a, b; cin >> a >> b; a = getparent(a); b = getparent(b); if(a == b) continue; if(a > b) swap(a, b); uf[b] = getparent(a); } int ans = -1; for(int i = 1; i <= n; i++){ if(uf[i] == -1) ans++; } cout << ans << endl; return 0; }
union-findっぽいものを使いました。親になっているものの数から1引いたものが答えになります。
道が増えるごとに、aとbが属しているグループの親同士をつないでいきます。uf[i]には頂点iの親を記録していきます。
親になっているものは、ufの値が-1となっているのでそれを数えていけばオッケーです。
親同士をつなげる、というのを忘れてaとb同士をつなげていたので何回もWAしました。気をつけましょう。
ARC 052 B
今回はこの問題。
xyz空間上にn個の円錐が互いに重なり合わないように浮いています。どの円錐も底面がyz平面と平行で、x軸の正の方向にとがっています。i番目の円錐の底面の中心のx座標の値はx[i]、半径はr[i]、高さはh[i]です。2つの整数aとbが与えられるのでa<=x<=bとなる空間の内いずれかの円錐の内側にある部分の体積をもとめよ、というクエリがq個与えられるのでそれぞれ答えてください、という問題です。
回答はこちら。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define mod 1000000007 double pai = 4 * atan(1); double gettaiseki(double r, double h) { return pai * r * r * h / 3; } int main() { int n, q; cin >> n >> q; double x[101], r[101], h[101]; double taiseki[20001]; for(int i = 0; i < n; i++){ cin >> x[i] >> r[i] >> h[i]; taiseki[i] = gettaiseki(r[i], h[i]); } double result[20001] = {}; // result[j] : 0 <= x <= jに含まれる部分の体積の和 for(int ii = 1; ii <= 20000; ii++){ for(int j = 0; j < n; j++){ double i = ii + 0.0; if(x[j] >= i) continue; if(i >= h[j] + x[j]) result[ii] += taiseki[j]; else result[ii] += (1 - pow((h[j] - i + x[j]) / h[j], 3.0)) * taiseki[j]; } } for(int i = 0; i < q; i++){ int a, b; cin >> a >> b; printf("%.10f\n", result[b] - result[a]); } return 0; }
さきに、0<=x<=i(i = 1, 2, ... 2 * 10^4)の範囲にある部分の体積の和を求めておきます。iが底面に達しないときと、頂点よりも上に来ているとき、そうでないときの3パターンに分けます。iが底面に達しなければ足さなければいいし、頂点よりも上であれば円錐全体の体積を足せばいいです。そうでないときは、(円錐全体の体積)-(含まれていないところの体積)を求めて足せばいいです。
ARC 054 B
今回はこの問題。
現在のコンピュータで解くとP年かかる問題があります。ムーアの法則により、いまからx年後のコンピュータの能力は2^(x/1.5)になり、解く時間もP/(2^(x/1.5))になります。計算時間は(今から計算を始めるまでの時間)+(計算にかかった時間)になります。最短計算時間を求めなさい、という問題です。
数学の問題です。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 double f(double x, double p) { return x + p / pow(2, x / 1.5); } double dfdk(double k, double p) { return 1 - (2 * log(2) * p) / (3 * pow(2, 2 * k / 3)); } double mink(double p) { double left = 0.0, right = 1000.0; for(int i = 0; i < 10000; i++){ double mid = (left + right) / 2; if(dfdk(mid, p) > 0) right = mid; else left = mid; } return left; } int main() { double p; cin >> p; printf("%.10f\n", f(mink(p), p)); return 0; }
k年後に計算を開始するとすると、計算時間はk + P(2^(k/1.5))になります。これをkについて微分して0になるところを2分探索で求めます(微分した結果は単調増加になるので正しく求められます)。最後に計算時間を求めればよいです。
ARC 044 B
解いたもののここに載せてないぶんがたまってきました。
今回はこの問題。
頂点数n個のグラフがあります。それぞれ1~nまで番号が振られており、頂点1からの距離が与えられます。
条件を満たすようなグラフは何通りあるでしょうか、という問題です。
回答はこちら。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 long long int pow2result[41]; // pow2result[i] : (2^(2^i)) % mod void getpow2result() { pow2result[0] = 2; for(int j = 1; j <= 40; j++){ pow2result[j] = (pow2result[j - 1] * pow2result[j - 1]) % mod; } return; } long long int getpow(long long int a, long long int b) { // a^b % mod を求める long long int ans = 1; if(a == 0){ ans = 0; } else if(a == 1){ ans = 1; } else if(a == 2){ for(int i = 40; i >= 0; i--){ if(b >= (long long int)pow(2, i)){ ans = (ans * pow2result[i]) % mod; b -= (long long int)pow(2, i); } } } else { long long int result[41]; result[0] = a; for(int j = 1; j <= 40; j++){ result[j] = (result[j - 1] * result[j - 1]) % mod; } for(int i = 40; i >= 0; i--){ if(b >= (long long int)pow(2, i)){ ans = (ans * result[i]) % mod; b -= (long long int)pow(2, i); } } } return ans; } int main() { long long int n; long long int a[100001] = {}; long long int ans = 1; cin >> n; for(int i = 0; i < n; i++){ int tmp; cin >> tmp; if(i == 0 && tmp != 0) ans = 0; a[tmp]++; } if(a[0] != 1) ans = 0; getpow2result(); for(int i = 1; i <= n - 1; i++){ // 頂点1から距離iのノードについて考える if(a[i] == 0) continue; // if(a[i - 1] == 0 && a[i] > 0){ // ans = 0; // break; // } long long int tmp = (getpow(getpow(2, a[i - 1]) - 1, a[i]) * getpow(2, (a[i] * (a[i] - 1)) / 2)) % mod; ans = (ans * tmp) % mod; } cout << ans << endl; return 0; }
a[i]は頂点1からの距離がiになる頂点数を表します。頂点1の距離は0になるはずなので、そうでない場合はansの値を0にしておきます。また頂点1からの距離が0になるのは頂点1ただ一つのはずなので、そうでない場合ansの値を0にしておきます。このあとansは乗算することで更新されていくので、このとき最終的な答えも0となり正しくなります。
次に頂点1からの距離が1, 2, 3, ...の順に考えていきます。条件を満たすためには、頂点1からの距離がi-1の頂点のうちの少なくとも一つ以上の頂点との間に辺があることが必要です。距離がi-1の頂点はa[i-1]個あります。これらのうちそれぞれ辺がある/ないの2通りがあるので、2^(a[i-1]) - 1通りあります。1除いているのは、すべての頂点の間に辺がないという場合を除くためです。距離がiとなる頂点はa[i]個ありこれをそれぞれに対して考えないといけないので、a[i]乗します。また、同じ距離になるような頂点の間には辺があっても大丈夫です。辺の取り方はa[i]個から2つえらぶ方法の数と一致します。2つの頂点は繋がっている/いないの2通りあるので全部で2^(a[i] * (a[i]-1))となります。先ほどとは異なり、すべての辺がなくても構わないので1引いたりしません。
これを繰り返せば答えを求められます。2のなんたら乗は何度も何度も使うので先に求めておきます。pow2result[i] : (2^(2^i)) % mod となっていますが、これは2のなんたら乗の「なんたら」が非常に大きな値になる可能性があるからです。たとえば2^(156)は2^(2^7) * 2^(2^4) * 2^(2^3) * 2^(2^2)に変換して計算するって感じです。底が2以外の時はその都度求めるようにします。
この問題について、2のなんたら乗のみ先に求めるようにしていますが、もともとは
long long int powresult[100010][41] = {};
// powresult[i][j] : i^(2^j) % mod
という配列を求めて必要そうなものを先に求めていました。こうするとREになりました。
このブログを書いてる途中に気づいたんですけど、max100010じゃ全然範囲が足りませんでしたね。
無駄にREやらWAやら重ねてしまった。
ARC 043 B
今回はこの問題です。
n個の問題があります。i番目の問題の難易度はd[i]です。
n個のうち、次の条件を満たすように問題を4つ選びます。
- i + 1番目の問題の難易度はi問目の問題の難易度の2倍以上になる。(i = 1, 2, 3)
このとき、問題の選び方は何通りあるでしょうか、という問題です。数が大きくなるらしいので10^9 + 7でわったあまりを求めろ、とのことです。
わからなかったので解説を見ました。
1,2問目と3,4問目に分けて考えるのがキモ(っぽい)。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 int main() { int n; int d[100001]; long long int a[100001] = {}, b[100001] = {}; cin >> n; for(int i = 1; i <= n; i++){ cin >> d[i]; } sort(d + 1, d + n + 1); // a[i] : 難易度が2 * d[i]以上となる問題の個数 つまり3番目の問題の難易度をd[i]としたとき4番目として選べる問題の数 for(int i = 1; i <= n; i++){ int left = i, right = n; if(d[i] * 2 > d[n]) continue; while(right - left > 1){ int mid = (left + right) / 2; if(d[mid] >= 2 * d[i]) right = mid; else left = mid; } a[i] = n - left; // cout << i << " " << a[i] << endl; } // b[i] : 難易度がd[i] / 2以下となる問題の個数 つまり2番目の問題の難易度をd[i]としたとき1番目のとして選べる問題の数 for(int i = 1; i <= n; i++){ int left = 1, right = i; if(d[i] / 2 < d[1]) continue; while(right - left > 1){ int mid = (left + right) / 2; if(2 * d[mid] <= d[i]) left = mid; else right = mid; } b[i] = right - 1; // cout << i << " " << b[i] << endl; } // ここからaの値を更新 // a[i] : 3番目の問題の難易度がd[i]以上のときの3問目と4問目の組み合わせの数 for(int i = n - 1; i >= 1; i--){ a[i] += a[i + 1]; a[i] = a[i] % mod; } int cnt = 1; long long int ans = 0; for(int i = 1; i <= n; i++){ // 2番目の問題の難易度がd[i]であるとする while(cnt <= n && d[cnt] < 2 * d[i]) cnt++; // cout << d[i] << " " << d[cnt] << endl; // cout << b[i] << " " << a[cnt] << endl; ans += (b[i] * a[cnt]) % mod; ans = ans % mod; } cout << ans << endl; return 0; }
コメント通り、まず
a[i] : 難易度が2 * d[i]以上となる問題の個数 つまり3番目の問題の難易度をd[i]としたとき4番目として選べる問題の数
b[i] : 難易度がd[i] / 2以下となる問題の個数 つまり2番目の問題の難易度をd[i]としたとき1番目のとして選べる問題の数
としてそれぞれ二分探索で求めます。
さらに、
a[i] : 3番目の問題の難易度がd[i]以上のときの3問目と4問目の組み合わせの数
に更新します。後ろから順番に足せばオッケーです。
あとは、2番目の問題の難易度をd[i]である場合を順番に足していきます。d[cnt] >= 2 * d[i]となるようにcntを求めています。3問目の難易度がd[cnt]以上のときの3問目と4問目の組み合わせの数 * 2問目の難易度がd[i]で1問目の難易度がd[i] / 2以下になるような組み合わせの数を計算すればオッケーです。
AGC 004に参加しました
昨日の夜AGCに参加していました。
AのみACと惨敗でした。しかもAはlong long つけ忘れて一回WAしました。
B問題についてメモしておきます。解説見たらスッとわかりました。
n色のスライムがいます。高橋君は全色のスライムを飼いたいです。高橋君は以下の二つの操作を行えます。
- i番目の色のスライムを一匹捕まえて飼う。このときa[i]時間かかる。
- 魔法を唱えて、今飼っているスライムの色をひとつ後ろにずらす。つまりi番目の色のスライムがi + 1番目の色のスライムになる。ただしn番目の色のスライムは1番目の色のスライムになる。このときx時間かかる。
このとき、全色のスライムを飼うのに最短で何時間かかるか求めなさい、という問題です。
回答はこんな感じです。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 long long int b[2001][2001]; int main() { long long int n, x; cin >> n >> x; long long int a[2001]; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ b[i][0] = a[i]; } for(int i = 1; i <= n; i++){ for(int j = 1; j < n; j++){ int moto = i - j; if(moto < 1) moto += n; b[i][j] = min(b[i][j - 1], a[moto]); } } // b[i][j]は魔法j回以下つかったときにスライムiを得るためのスライムを捕まえるのにかかる最短時間 long long int ans = (long long int)pow(mod, 2); for(int i = 0; i < n; i++){ // iは魔法を使う回数 long long int result = x * i; for(int j = 1; j <= n; j++){ result += b[j][i]; } ans = min(ans, result); } cout << ans << endl; return 0; }
全体で魔法を使う回数をk回としたとき、i番目のスライムを得る最短時間は、{a[i], a[i - 1], ... a[i - k]}の最小値になります。たとえば、a[i - j]が最小値であるとします。i - j番目のスライムは魔法をj回使うとi番目のスライムになります。したがって、魔法をk - j回使ったのちにi - j番目のスライムを捕まえ、その後j回魔法を使えばいいわけです。スライムを捕まえる行為と魔法を唱える行為の順番はどうでもいいので、このように考えることができます。
コメント通り、b[i][j]は魔法j回以下つかったときにスライムiを得るためのスライムを捕まえるのにかかる最短時間になります。motoというのが捕まえるべきスライムの番号になっています。
あとは魔法を使う回数を固定、そのときの最短時間を求め、さらにそのうちの最小値を求めれば答えが出ます。
bの大きさは2000 * 2000ということで、main内で宣言するとセグフォ起こすんですよね…問題を解くときにセグフォを起こすような配列は使わなくてもいいはずだ、と思い込んでいたのでこの方法を思いつけませんでした…今度から気をつけたいです。
ARC 022 B
今回はこの問題を解きました。
Ncmの細長いお菓子があります。このお菓子は1cmごとにブロックで分けられていて、i番目のブロックはAi番目の味がします。同じ味のブロックを二つ以上含まないひとつながりになった部分のうち、最も長いものの長さを求めましょう、という問題です。
わからなかったので解説を見ました。しゃくとり法で解きました。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <cstdlib> #include <map> #include <queue> #include <utility> #include <vector> #include <set> #include <memory.h> #include <iomanip> #include <bitset> #include <list> #include <stack> using namespace std; #define pai 3.14159265359 #define mod 1000000007 int main() { int n; cin >> n; vector<int> result(n + 1, 0); int a[100001]; for(int i = 1; i <= n; i++){ cin >> a[i]; } vector<int> lastappear(100001, 0); result[0] = 1; for(int i = 1; i <= n; i++){ // cout << i << endl; // resultは一つ前のものより1減る result[i] = result[i - 1] - 1; // 今からa[i + result[i]]番目のをつける while(i + result[i] <= n){ int nextcolor = a[i + result[i]]; if(lastappear[nextcolor] >= i) break; lastappear[nextcolor] = i + result[i]; result[i]++; } } int ans = 0; for(int i = 1; i <= n; i++){ // cout << result[i] << endl; ans = max(ans, result[i]); } cout << ans << endl; }
1番目のブロックから、どこまで長くのばせるかを見ていきます。その結果がresultに記録されていきます。lastappear[i]はi番目の味がするブロックが最後に現れたのが何番目かを表しています。
i番目のブロックをどこまでのばせるか考えます。i-1番目がのばせたところまではのばすことができるので、とりあえずresult[i]=result[i-1]-1にします(1減らしたのはi番目のブロックの分)。そこから、順番に追加できるか判別していきます。nextcolorが次に追加しようとしているブロックの味です。味じゃなくて色と勘違いしてたのでcolorになってます。で、この味が最後に出てきたのがi番目のブロックより左側であったら追加できるのでlastappearとresultを更新します。これを右端にたどり着くまで、もしくは追加できなくなるまで繰り返します。
あとはresultのうち最大のものを出力すればオッケーです。
