AOJ 2442 Convex-Cut
問題概要
N 個の頂点からなる凸多角形が与えられる．このとき，ある点があって，その点を通る任意の直線がこの多角形を二等分することができるだろうか？できる場合は，その点の座標を求めよ．
自分が解いた時の流れ
任意の直線で二等分だからかなり制約がきつそう．点対称とかそんなんじゃないの？（適当）
→なんか通った
多少厳密（？）な証明
仮にそういう点Pがあったとして，Pを通り，それぞれ異なる直線を2本引く．
すると，明らかに，この多角形は4つの領域A, B, C, Dに分割される．
A+B = C+D かつ A+D = B+C より，A = C かつ B = D であることがわかる．つまり，向かい合う領域の面積が等しい．
ここで，向かい合う領域が共に三角形となるように直線を引くことができる（図の右側）．そして，図のように辺の長さを a, b, c, d とおくと，向かい合う領域の面積が等しいことから a * b == c * d が成り立つ．ここで，2本の直線を限りなく近づけていくと，a ≒ b, c ≒ d と近似できるので，a == d と考えることができる．
これはつまり，点Pに直線を一本引いたときに，凸多角形と2点で交わるが，その2点は点Pに関して点対称の位置にあるということ．直線は任意に引けるので，結局，凸多角形の辺上の任意の点は点Pに関して点対称（凸多角形が点対称）であるということ．
よって，Nが奇数のときは点対称にならないのでNA．
Nが偶数のときは，点対称となっているかを調べればよい．これは i 番目の頂点と i + N/2 番目の頂点を調べていけば十分．
計算量は O(N)．
ソースコード
#include <iostream> #include <vector> #include <iomanip> #include <cmath> using namespace std; constexpr double eps = 1e-10; int main() { int N; cin >> N; vector<double> x(N), y(N); for(int i=0; i<N; ++i) { cin >> x[i] >> y[i]; } if(N % 2 == 1) { cout << "NA" << endl; } else { double px = (x[0] + x[N/2]) / 2, py = (y[0] + y[N/2]) / 2; bool ok = true; for(int i=0; i<N; ++i) { double vx = px - x[i], vy = py - y[i]; ok &= fabs(px + vx - x[(i+N/2) % N]) < eps && fabs(py + vy - y[(i+N/2)%N]) < eps; } if(ok) { cout << fixed << setprecision(10) << px << " " << py << endl; } else { cout << "NA"; } } }
AOJ 2303 Marathon Match
問題概要
N 人のランナーがマラソンをする．コースの長さは L で，休憩所が途中に M 箇所存在する．i 人目のランナーは，どの休憩所でも全く同じ Pi パーセントの確率で休憩を取る．一度の休憩で Ti だけ時間を使う．また，それぞれのランナーは速度 Vi （一定）で走り続けるものとする．
このとき，i 人目のランナーが優勝する確率を求めなさい．ただし，複数人が同時に最初のゴール者となった場合，優勝したとはみなさない．
・制約
1 <= N <= 100
0 <= M <= 50
1 <= L <= 100000
0 <= Pi <= 100
0 <= Ti <= 100
0 <= Vi <= 100
解法
N, M が小さいので，愚直に確率を求めに行けばいい．具体的には， i 番目の人が j 回休憩したときに，優勝する確率を求め，それらを足していく．
このとき，j 回休憩する確率を求めないといけないが，これはパスカルの三角形の要領（普通にDP）で求めることができる．これは前計算しておけば良い．
i 番目の人が j 回休憩した時，t := L / Vi + Ti * j だけの時間がかかる．この時，k ( != i ) 番目の人が何回以上休憩すれば i 番目の人より遅くゴールするかを考えて，そのそれぞれの回数休憩する確率を足していけば，k 番目の人が i 番目の人より遅くゴールする確率が求まる．
これを i 番目以外の全てのランナーについて考え，掛け合わせれば，i 番目の人が優勝する確率を求めることができる．
ただし，Vk で割ったり，Tk で割ったりする場合があるので，Vk == 0 や Tk == 0 の場合は特別な処理をしないといけない．
また，同時にゴールした場合を省く必要があることもわすれない．
・反省
（ちゃんと考慮してたのに，最後に述べた点で2回WAくらいました．小数に対する処理が甘かった．そもそも何回以上休憩すればオッケーかを求める必要はなくて，とりあえず全部試してオーバーしてたら無視すれば Tk で割ったりする必要は無い．無駄なことをしてしまった．）
計算量は O(N^2M^2) となる．
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <iomanip> using namespace std; constexpr double eps = 1e-10; int main() { int N, M, L; cin >> N >> M >> L; vector<vector<vector<double>>> cmb(N, vector<vector<double>>(M+1, vector<double>(M+1))); for(int i=0; i<N; ++i) { cmb[i][0][0] = 1; } vector<double> P(N), T(N), V(N); for(int i=0; i<N; ++i) { cin >> P[i] >> T[i] >> V[i]; P[i] /= 100; } for(int i=0; i<N; ++i) { for(int j=1; j<=M; ++j) { for(int k=0; k<=j; ++k) { cmb[i][j][k] = cmb[i][j-1][k] * (1 - P[i]) + (k-1 >= 0 ? cmb[i][j-1][k-1] * P[i] : 0); } } } for(int i=0; i<N; ++i) { if(V[i] == 0) { cout << 0 << endl; continue; } double res = 0; for(int j=0; j<=M; ++j) { double t = L / V[i] + T[i] * j; double p = cmb[i][M][j]; for(int k=0; k<N; ++k) { if(i == k || V[k] == 0) { continue; } double tt = L / V[k]; if(T[k] == 0 && tt - t <= 0) { p = 0; break; } int cnt = (T[k] == 0 ? 0 : ceil(max(0.0, t - tt) / T[k])); if(tt + T[k] * cnt - t < eps) { cnt += 1; } double pp = 0; for(int l=cnt; l<=M; ++l) { pp += cmb[k][M][l]; } p *= pp; } res += p; } cout << fixed << setprecision(10) << res << endl; } }
AOJ 2157 Dial Lock
解法
全探索．前から順番に，数字を合わせて行けば良さそう．
なぜなら，数字をずらしていく操作列を考えたときに，それらの順番を入れ替えても最終的な状態は変化しないから．
しかし，例えば最初の数字を複数回の操作で合わせるような操作を考える必要があるだろうか？
これは考える必要が無いことが分かる．なぜなら，例えば3回の操作（それぞれ，区間 [0, a]，[0, b]，[0, c] を操作する．ただし，a < b < c としてよい．a == b なら無駄だし，最初に述べたように操作順は自由で良いため．）で最初の数字をあわせることを考える．
このとき，それぞれの操作で，x, y, z だけずらすとする．この時，[0, a] は x + y + z だけ，(a, b] は y + z だけ，(b, c] は z だけずれたことになる．これは，[0, a] を x + y + z だけ，(a, b] を y + z だけ， (b, c] を z だけずらす操作と同値であり，これらの操作回数は等しい．
これはつまり，ある桁をあわせることを目標とする時，その桁を一回の操作で合わせることだけ考えればよいことにほかならない．
以上から，前の桁から目的の数字に合わせ，かつ先頭の数字は一回の操作で合わせることを考えればよいことになる．
あとは，注目している区間の先頭の数字を合わせるためにずらす操作を，どの区間で行うかを全探索すれば，最終的な答えが求まる．ずらした後隣の数字を考えるので，DFSで実装すると楽．
計算量は O(k!) である．ただ，以下の実装だと string のコピーが無視できないかもしれない（それでもぎりぎり間に合う）．
ソースコード
#include <iostream> #include <string> using namespace std; int dfs(int i, string s, string const& g, int cnt) { if(i >= s.size()) { return cnt; } if(s[i] == g[i]) { return dfs(i+1, s, g, cnt); } int res = 1e9; int t = (g[i] - s[i] + 10) % 10; for(int j=i; j<s.size(); ++j) { s[j] = '0' + ((s[j] - '0' + t) % 10); res = min(res, dfs(i+1, s, g, cnt+1)); } return res; } int main() { int k; while(cin >> k, k) { string s, g; cin >> s >> g; cout << dfs(0, s, g, 0) << endl; } }
AOJ 2182 Eleven Lover
解法
DP で解くことができる．dp[i][j] := 先頭から i 桁目まで見たときに，11 で割ったあまりが j となるものの総数，と定義する．
ここで，ある整数 n を 11 で割った余りの計算をたとえば 17891 を例にして考えてみる．
先頭から順番に見ていけばよく，まず 1 % 11 = 1 となる．
次に 1 * 10 + 7 % 11 = 6．
6 * 10 + 8 % 11 = 2．
2 * 10 + 9 % 11 = 7．
7 * 10 + 1 % 11 = 5．
となり，あまりは5となる．これを利用して dp で計算する．
つまり，dp[i+1][(j*10+d)%11] += dp[i][j] を計算していけば良い．ただし，d は現在見ている(i 桁目の)数字である．
また，dp[i+1][d] += 1 とすれば，i桁目を左端とした場合を含めることができる．ただし，0から始まるものは省かなければならない．
答えは dp[i][0] の総和である．
ソースコード
#include <iostream> #include <string> #include <vector> using namespace std; int main() { string n; while(cin >> n, n != "0") { vector<vector<int>> dp(n.size()+1, vector<int>(11)); int res = 0; for(int i=0; i<n.size(); ++i) { int m = n[i]-'0'; if(m != 0) { dp[i+1][m] += 1; } for(int j=0; j<11; ++j) { dp[i+1][(j*10+m)%11] += dp[i][j]; } res += dp[i+1][0]; } cout << res << endl; } }
ARC070 D - No Need
解法（証明？）
a[i] を降順にソートする．
今，a[i] が不必要かどうかを判定したいとする．この時，Si := a[1] + a[2] + ... + a_[i] とおく．
また，a[n] から a[i + 1] までの和で表現できる K 未満の数がわかっているとする．（dpで保存）
その中の任意の数 t について，t + Si < K であるならば，それは不必要な数である．
必要条件は明らか．なぜなら，t + Si < K が成り立つならば，a[i] を用いた和で K 以上となるものは，存在しないか，あるいはもともと K 以上であるかのどちらかだからである．
十分条件について示す．これは対偶を取れば良い．つまり，「必要な数ならば t + Si >= K が成り立つ」を示せば良い．
t + a[i] >= K ならば，a[i] を取り除けば K 未満となる和の作り方が存在することになるので，t + a[i] < K であると考えて良い．
ここで，数列 a が降順にソートされていることに注目すると，ある j があって t + (a[j] + ... + a[i]) >= K かつ t + (a[j + 1] + ... + a[i]) < K がなりたつ．この時，a[i] > a[j] だから， t + (a[j] + ... + a[i - 1]) < K が成り立つ．これは a[i] が必要な数であることに他ならない．
以上より，示された．
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <numeric> using namespace std; using ll = long long; int main() { int N, K; cin >> N >> K; vector<int> a(N); for(int i=0; i<N; ++i) { cin >> a[i]; } ll sum = accumulate(a.begin(), a.end(), 0LL); sort(a.rbegin(), a.rend()); int res = 0; vector<bool> dp(K); dp[0] = true; for(int i=0; i<N; ++i) { bool f = false; for(int j=0; j<K; ++j) { f |= dp[j] && j+sum >= K; } if(!f) { res++; } sum -= a[i]; for(int j=K-1-a[i]; j>=0; --j) { dp[j+a[i]] = dp[j+a[i]] | dp[j]; } } cout << res << endl; }
2016年を振り返る
Twitterのハッシュタグで，「#一年の思い出を月別で振り返る」ってのがあったんですが，なんとなく自分でもやってみようと思ったのでブログに書くことにした．
1月
浪人していたので，センター試験の勉強をしていた気がします．してたかな？してなかったかも……．予備校の自習室の近くにネコのたまり場があったので，そこへ行くついでに自習室で勉強してました．
1月下旬は，センター試験で見事にボコボコにされてつらい気持ちになってたような気がします．
2月
さすがに遊べるような身分でもなく，普通に2次試験の勉強をしてました．時々，友人と予備校近くのフードコートで傷を舐め合ったり，傷口に塩を塗り合ったりしてました．
あれ？他の記憶が無い．なんでや．
3月
前期試験の発表前に中期日程の試験を受けたり，なんやかんやで受かってたり（親が喜んでくれてたので良かった）して一息つけた時期．受かってからはほどほどに遊んでました．
入学の手続きがややこしくて結構手こずってたな～．
4月
入学式も終え，これからの生活に（まだ）期待と不安を抱えていたころ．なんとか友人も作れた（そして偶然全員オタクだった．類は友を呼ぶんですねぇ……）し，授業も（微分積分学以外は）なんとかなりそうだったので，すこし安心してました．
入ろうと思っていたサークルの雰囲気もよくて，シュッと参加しました．良かったよかった．
余談ですが，この時期の学食混みすぎ．飯食うってレベルじゃねえぞ．
5月
大学生活に慣れてきてしまった緩みからか，不幸にも講義をぶっちしてしまう学生が目立ち始める．それにつられないように必死で講義に出ていた記憶があります．べつに講義に出ること自体は重要じゃないんですが，なんだかんだいって単位は無いよりあったほうが後々楽なので，頑張ろうと意気込んでました．
サークルでは競プロをやっていて，自分は殆ど初心者だったのでついていくのが大変でしたね．あとはC++の勉強をする読書会があったのでそれにも参加してました．
6月
気が緩み始める．いやね？一限にね？語学入れられたって出られないと思いますよ？僕は頑張ったほうだよ．うん．一限語学は人権侵害．
このころは友人宅で麻雀をうちまくっていた．うちの学科の人間，麻雀打てる人がめちゃんこいてびっくらこいた．しかも上手いし．なにもんだよ．
7月
テスト前で今までサボっていたつけが回ってくる．ちゃんと勉強しておけばよかった．お前は浪人時代に何を学んだんだという感じ．
でもなんとか乗り切る．やればなんとかなるもんですね．
8月
夏休み．何してたか記憶にない．空白の一ヶ月である．
あ，大洗に友人と旅行に行ってたか．楽しかったです（小並感）
9月
大半が免許合宿で埋まる．福井にいったんだけど，いいところだった．福井駅前とか，人は少ないし，でも店はそれなりにあるし，交通アクセスもまぁ良かったしで満足だった．免許も無事取れたしめでたしめでたし．
11月
10月と大差なし．単調な（かといってつまらなくはない）生活が続く．
CODE FESTIVAL 2016の本戦に行けることになる．同回生ではビリの成績だったけど，本戦はコンテンツが充実していてすごくいい経験になった．来年もまた行けたらいいなぁ．
サークルでプロにハラスメントを受ける．ハラスメントダメ，ゼッタイ．はやくプロになりたい．
12月
なんとなく勉強する気になって，地に足の着いた勉強をするようになる．サボれる講義は積極的にサボるようになった（出席をしないという意味）．
サークルでは相変わらずハラスメントの応酬が繰り広げられていたけど，さすがに4月よりは僕も含めてみんな強くなってるなぁという感じはする．
AOJ-ICPCの350までほとんど埋まる（やったー）
最後に
来年のことは来年の僕がそのときどきでうまいことやってくれるでしょうから，あまり考えないことにしました．
それではみなさん，よいお年を．
int とlong long のビット演算でハマった話
#include <iostream> #include <bitset> using namespace std; using ll = long long; int main() { ll a = 0, b = 0, c = 0; for(int i=0; i<32; ++i) { a |= (1 << i); } for(int i=0; i<32; ++i) { b |= (1ll << i); } c |= (1 << 31); cout << bitset<64>(a) << endl; cout << bitset<64>(b) << endl; cout << bitset<64>(c) << endl; }
Output:
1111111111111111111111111111111111111111111111111111111111111111 0000000000000000000000000000000011111111111111111111111111111111 1111111111111111111111111111111110000000000000000000000000000000
つらい．ちゃんと確認しような．
