TopCoder(delta2323) / Codeforces(delta) / twitter
2011-03-25
■ [練習][SRM][Div1][Level2] SRM473 Div1 Level2 600 TwoSidedCards 
問題文
http://www.topcoder.com/stat?c=round_overview&er=5&rd=14154
要約
N 枚のカードが与えられている。それぞれのカードには 1 から N のうちいずれかの数字が裏表に 1 つずつ書かれている。表面合計 N 面に書かれている数字は 1 から N の相違なる数で，裏面も同様である（つまり表面の数をすべて集めると {1, ... , N} の置換）。例えば N = 4 の場合の一例は，
表 １ ４ ３ ２ ー ー ー ー 裏 ３ ２ １ ４
この N 枚のカードを適当に順序入れ替え，さらに何枚かを裏返して横一列に並べる事で，ordered N tuple を作る。作れる tuple の種類を modulo 1,000,000,007 で答えよ。
N は 1 以上 50 以下
方針
あるカードの裏の数とその次のカードの表の数が等しいという関係でカードを数珠つなぎにすると，カードをいくつかのグループに分ける事ができる。数珠つなぎの一例は
表 １ ３ ７ ２ ４ ー ー ー ー ー 裏 ３ ７ ２ ４ １
のようなもの。tuple の種類の数はグループに含まれるカードの枚数にしかよらない。各々のグループで作れる tuple の種類の数をまず計算する。
グループのカードの枚数を k 枚とする。適当な枚数裏返した結果，表面に 1 つしか現れていない数字の種類を j , 2 つ現れている数字の種類を i とすると（k = j + 2 * i），これの順序を適当に入れ替えて作れる tuple の種類は n! / 2^i 。さらに i は「裏返したカード達の連結成分の数」に等しい。例えば○は表面を向いたカード，×を裏返したカードとして，カード達が
○○××○○×○
という状態の場合，連結成分の数は××と×で 2 個と数える。また，両端同士はつながっているとみなして，
×○××○×××
の場合も連結成分は 2 個とカウントする。上の i はこの裏返したカードの連結成分の数に等しい。i 個の × - 連結成分を決めることと ○ と × の境界点を 2 * i 個決める事と同義なので，上の (i, j) を達成できる組み合わせの数は kC2*i 通り。また，全て表向きの場合を除いて，ある並べ方とそれを裏表を全部入れ替えたものは異なる tuple になるので，結局サイズが k のグループで作れる tuple の数 f(k) は
f(k) = k! + 2 * Σ_{i=1}^{k/2} (k! / 2^i) * kC2*i
最後に，N 枚のカードが k_1, k_2, .. k_p のグループに分かれていたとすると，N 枚のカードを適当に並べかえ， k_1枚，k_2枚，... k_p枚ずつ同一視し，各々のグループで f(k_i) 通りの入れ替えを行うので，求める組み合わせの数は
N! * Πf(k_i) / Π(k_i)!
コード例(c++)
#include <string> #include <vector> #include <iostream> using namespace std; typedef long long ll; class TwoSidedCards { public: vector<int > t; vector<int > h; vector<int > used; int n; ll mod; // mathematical functions (modulo) ll comb(int n,int k){ if(k == 0 || n == k) return 1; return ((comb(n-1, k-1) * n + mod ) % mod * pow(k,mod-2) + mod) % mod; } ll fact(int n){ if(n == 0) return 1; return (fact(n-1) * n + mod) % mod; } ll pow(int a, int r){ if(r == 0) return 1; ll ans = 1; if(r & 1){ ans = (ans * a + mod) % mod; } ll aa = pow(a, r/2); ans = ( ( (ans * aa + mod) % mod ) * aa + mod ) % mod; return ans; } // make loops int check(int head, int now){ used[now] = 1; if(h[now] == head){ return 1; } int next = 0; for(next = 0; next < n; next++){ if(t[next] == h[now]) break; } return 1 + check(head, next); } // calculate f(k) (defined in the explanation above) ll count(int k){ ll ans = 0; for(int i = 0;i<=k/2;i++){ ans = ( ans + ( ( ( (fact(k) * pow ( pow(2, i), mod-2) )+ mod ) % mod) * comb(k, 2*i) + mod) %mod + mod ) % mod ; if(i != 0){ ans = ( ans + ( ( ( (fact(k) * pow ( pow(2, i), mod-2) )+ mod ) % mod) * comb(k, 2*i) + mod) %mod + mod ) % mod ; } } return ans; } int theCount(vector <int> taro, vector <int> hanako) { mod = 1000000007LL; n = taro.size(); used.clear(); used.resize(n); t = taro;h = hanako; vector<int > loops; for(int i = 0; i < n; i++){ if(used[i] == 1) continue; loops.push_back(check(taro[i], i)); } ll ans = fact(n); for(int i = 0; i < loops.size(); i++){ ll a = fact(loops[i]); ans = ( ans * pow(a, mod-2) + mod) % mod; } for(size_t i = 0; i < loops.size(); i++){ ans = (ans * count(loops[i]) + mod) % mod; } return ans; } };
分析
自力では連結成分の数を境界点の数に翻訳する部分ができずにギブアップ。残りの部分は kusano_prog さんの解説を参考にしました。ありがとうございました
*1。この問題の場合剰余を取った状態で (k_i)! で割り算しなければならない。これを先日のエントリーで計算したように逆元を全探索で調べると到底時間内に終わらないので，ここでは a の Z/pZ 内での逆元は a^{p-2}である事を用いています。
するとあらゆる所で悉く mod 計算が現れました。実際剰余を取る所でサボると，いくつかのケースで落ちました。
2011-03-22
■ [練習][SRM][Div1][Level2] SRM473 Div1 Level2 500 RightTriangle 
問題文
http://www.topcoder.com/stat?c=round_overview&er=5&rd=14155
要約
円周上に等間隔に places 個の点が置かれ，時計回りに 0 から places-1 まで番号が振られている。整数 a, b, c が与えられていて，次のルールで points 個の点に赤いマークを付ける。N = 0,1, ... , points-1に対して
- P(N) = (a * n * n + b * n + c) % places を計算する
- P(N)の番号を振られた点から時計回りに点を巡り，赤くマークされていない最初の点を見つける（P(N)がマークされていなければP(N)自身を選ぶ）
- その点に赤いマークを付ける
円に内接するの直角三角形で頂点 3 つともに赤いマークがついているものの数を答えよ。
places は 1 以上 1000000以下，pointsは 1 以上 100000 以下でplacesより大きくはない，a, b, cは 0 以上 1000000 以下
方針
直角三角形の数を数えるのは，ある点とその反対側の点が両方マークされているという条件で探せば O(places) でできる。問題は赤いマークを付ける部分で，問題文の方法（特にマークされていない点を見つける所）をそのまま実装してしまうと最悪 O(points^2) のアルゴリズムになってしまう。
n を log nにしようということで 2 分探索を考える。今回の場合，条件 C(n):「 P(N) から n 個先まですべてマークされている」を考えると，C(n) が正しいならば k <= n となるすべての k に対し C(k) が正しいので，2 分探索が用いられる。ただ，P(N) から k 個先までにあるマークの数を 1 つずつ数えていると，O(points) のアルゴリズムになり，全てマークするのにやっぱり O(points^2) かかってしまう。
そこで，Binary Index Tree を用いマークの数を管理すれば数えるのが O(log (points) ) に減り，結局合計で O(points * log^2 (points) )で間に合う。
コード例
#include <vector> #include <cmath> using namespace std; class RightTriangle { public: template<typename T> class BIT{ private: /** * val : n * the number of underlying sequence */ int n; /** * val : nn * nn is the minimum value which satisfies the following conditions * (1) nn is some power of 2 * (2) n <= nn; */ int nn; vector<T> val; public: BIT(int _n) : n(_n){ nn = 1; while(n > nn) nn *= 2; val.resize(nn); for(size_t i = 0;i<val.size();i++){ val[i] = 0; } } BIT(size_t _n){BIT((int) _n);} BIT(){BIT(0);} inline size_t size(){return n;} /** * return the partial sum in [0, i) of a * Note that internal data is 1-indexed, * whereas access from outside is required to be 0-indexed */ T sum(int i){ T s = (T) 0; while(i > 0){ s += val[i]; i -= i&-i; } return s; } /** * add x to a[i] where a[i] is considering sequence * note that internal data is 1-index, * whereas access from outside is required to be 0-indexed */ void add(int i, T x){ i++; while(i <= n){ val[i] += x; i += i & -i; } } }; long long triangleCount(int places, int points, int a, int b, int c) { long long A = a; long long B = b; if(places % 2 == 1) return 0; vector<int> isred(places, 0); BIT<int> bit(places); for(long long n = 0; n < points;n++){ long long pos = (A * n * n + B * n) % places; if(isred[pos] == 0 ){ bit.add(pos, 1); isred[pos] = 1; continue; } int low = 0; int high = places; int mid = 0; while(high - low > 1){ mid = (low + high) /2; int h = 0,l = 0; if(mid + pos < places){ h = bit.sum(mid + pos); l = bit.sum(pos); }else{ h = bit.sum(pos + mid-places) + n; l = bit.sum(pos); } if(h-l < mid){ high = mid; }else{ low = mid; } } bit.add((low+ pos) % places, 1); isred[(low + pos) % places]= 1; } long long ans = 0; for(int i = 0;i<places/2;i++){ if(isred[i] == 1 && isred[i+places/2] == 1) ans+= (points-2); } return ans; }
提出する時にこんな警告が
Your submission may contain more than 30% unused code which would violate the Unused Code Rule. Are you sure you want to submit this code?
そんなルールがあったんだ・・・
2011-03-19
■ [練習][SRM][Level2][Div1] SRM474 Div1 Level2 500 TreeCount 
テーマ：試行錯誤，実験の重要性
問題（要ログイン）
http://www.topcoder.com/stat?c=problem_statement&pm=10805&rd=14185
要約
連結無向グラフ G = (E, V) が与えられていて，頂点に 0 から N-1 まで番号が振られている。G に含まれる木で，0 から各点の最短距離が変化しないものの数を modulo 1000000009 で答えよ。つまり数えるのは次の条件を満たす G の部分グラフ
- G' は木
- V' = V
- E' ⊂ E
- 任意の頂点 i に対し，G' と G で 0 と i の最短距離は同じ
コード(c++)
#include <string> #include <vector> #include <cmath> #include <climits> using namespace std; typedef long long ll; class TreesCount { public: int count(vector <string> graph) { ll ans = 1; ll mod = 1000000007; int n = (int )graph.size(); int dist[51][51]; // 最短距離 int graph1 [51][51] = {}; ll count[51] = {}; // 初期化 for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if( i!= j && graph[i][j] == '0'){ graph1[i][j] = INT_MAX/3; // つながっていない所が 0 はいやだ！ dist[i][j] = INT_MAX/3; }else{ graph1[i][j] = graph[i][j] - '0'; dist[i][j] = graph[i][j] - '0'; } } } // ワーシャル・フロイド for(int k = 0;k<n;k++){ for(int i = 0;i<n;i++){ for(int j = 0;j<n;j++){ dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } // 最短経路の種類のカウント for(int i = 0;i<n;i++){ for(int j = 0;j<n;j++){ if(i == j) continue; if(dist[0][i] == dist[0][j] + graph1[i][j]){ count[i] ++; } } } for(int i = 0;i<n;i++){ ans = (ans * count[i]) % mod; } return (int) ans; } };
分析
サンプルケースで色々実験してみると，どうも各点ごとに最短経路の数（実際には違う）を独立に計算して，掛け算すると良さそうだと予想しました。組み合わせだから答えが大きくなる事が予想され，剰余を取る事とも compatible です。でも，最短経路の数ってどうやって数えるのだろう。思いつくのはよくある長方形の場合で「左下から右上にいく最短経路の数」を数える時，一番最後に上に進む場合の数と左に進む場合を足し算するというもの。これと同様に考えると，
（頂点 i への最短経路の数）= Σ( i の直前に通った頂点への最短経路の数)
となるのだろうか。Σを取る範囲は？ i に繋がっている頂点全部を計算するのは明らかに違う。「そこを通れば最短経路になる」という条件を考えるので定式化すると
dist[0][i] == dist[0][j] + (graph1[i][j]))
となりそう。頂点の数が小さいのでワーシャルフロイドで最短距離を計算しても十分間に合う。さらに，お互いにお互いを足しあわせて無限大にならないように，最短経路の数が確定した頂点にはマークをつけてマークをついているものだけ数え上げれば良さそう。
以上の考察のもと書いたのが下のコード。上のコードとの違いは変数 used[i] で確定した点をマーク付けしている所と，count[i] で数えているのが頂点 0 から頂点 i への最短経路の種類である点。
（このコードは正しくありません） #include <string> #include <vector> #include <iostream> #include <cmath> #include <climits> using namespace std; typedef long long ll; class TreesCount { public: int count(vector <string> graph) { ll ans = 1; ll mod = 1000000007; int n = (int )graph.size(); int dist[51][51]; int graph1 [51][51] = {}; int used[51]; ll count[51] = {}; // 初期化 for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if( i!= j && graph[i][j] == '0'){ graph1[i][j] = INT_MAX/3; dist[i][j] = INT_MAX/3; }else{ graph1[i][j] = graph[i][j] - '0'; dist[i][j] = graph[i][j] - '0'; } } } for(int i = 0;i<n;i++){ used[i] = -1; } // ワーシャル・フロイド for(int k = 0; k < n; k++){ for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } count[0] = 1; used[0] = 1; for(int k = 0; k < n; k++){ for(int i = 0; i < n; i++){ if(used[i] == 1 ) continue; bool flag = true; for(int j = 0; j < n; j++){ if(i == j) continue; if(used[j] == -1 && dist[0][i] == dist[0][j] +( graph1[i][j])){ flag = false; } } if(flag){ for(int j = 0;j<n;j++){ if(used[j] == 1 && dist[0][i] == dist[0][j] +( graph1[i][j])){ count[i] += count[j]; } } used[i] = 1; } } } for(int i = 0; i < n; i++){ ans = (ans * count[i]) % mod; } return (int) ans; } };
ケースを試してみると，答えとあわない・・・。EXAMPLE 3を見ると，頂点 2 への最短経路の種類は 4 種類だけど，ここは 3 であってほしい。ということは最短経路の種類ではなく，最短経路として最後に通る頂点の数の方が正しそう。つまり，
count[i] += count[j]; → count[i] ++;
こう書き換えて提出した所，それであっていました。そうすると，変数 count[i] 達がお互いにお互いを足しあわせるという状態にならないので，マークをつける必要がなくなりました。それを修正したのが上のコードです。試行錯誤って重要なんだなと感じた 1 題でした
2011-03-17
■ [Div1][Level2][SRM][練習] SRM475 Div1 Level2 600 RabbitIncreasing 
テーマ：pが素数ならZ/pZは体，Z/p^{k} Z → Z/p^{k-1} Zの標準的全射
問題（要ログイン）
http://www.topcoder.com/stat?c=problem_statement&pm=10879&rd=14156
要約
最初の年 (year 1) の 7 月にオスメスが 1 羽ずつ産まれ，その後次のサイクルをyear kまで繰り返す
- 3 月に 1 歳を越えるつがい 1 組からオスメス 1 羽ずつが産まれる（ 1 歳は含まない）
- 4 月に同じ年齢のオスメスがつがいを作る
1 から k の整数の部分集合が与えられ，その年が部分集合にあるならば，
- 7 月に年齢の高い順に半分（小数点切り上げ）のつがいがいなくなる。
year k の 12 月にいるウサギのつがいの数を mod 1,000,000,009で答えよ。k は 1 以上 10,000,000以下，部分集合の元の数は 1 以上 50 以下
方針
最初に産まれたつがいも 3 月に産まれたと考える。3 月時点で 2 歳以上のつがい達は区別する必要がないので，
- c[0] : 3月時点で2歳以上のつがいの数
- c[1] : 3月で1歳になるつがいの数
- c[2] : その年の3月に産まれたつがいの数
として漸化式を立てればよい（これをせず年齢事に分けるとO(k^2)かかるアルゴリズムになってしまう上に複雑になる）。mod を気にしなければ
c[0]' = c[0] + c[1] c[1]' = c[2] c[2]' = c[0] + c[1]
と更新し，7月に leaving イベントが発生するならば，
c[0]'' = 0
c[1]'' = c[1]' / 2 ( c[1]' が偶数の場合)
(c[1]' + 1) / 2 ( c[1]' が奇数の場合)
c[2]'' = c[2]'
とさらに更新すれば良い。しかし，今 c は剰余で考えるので，2 で割る操作と偶奇の判定を c[1]' そのものに対して行う事が出来ない。その部分に修正が必要となる。
2 で割る代わりに 500000005 (Z/modZ 内での 2 の逆元)をかければ良い。
この問題では最大 50 回 2 で割るので，2^0, 2^1, .., 2^50 で割った余りが必要になる。そこで，下のコードでは mod 2^55 の余りを管理し，これの偶奇で本来の数の偶奇を判定している。
コード(c++)
#include <string> #include <vector> using namespace std; typedef long long ll; class RabbitIncreasing { public: int getNumber(vector <int> leaving, int k) { if(leaving.size() >= 1 && leaving[0] == 1) return 0; ll mod = 1000000009; ll div2 = 500000005; ll mod2 = 1; for(int i= 0;i < 55;i++){ mod2*= 2; } vector<ll > c(3,0); vector<ll > e(3,0); c[2] = 1; e[2] = 1; for(int i = 2; i <= k; i++){ c[0] = (c[0] + c[1] + mod) % mod; c[1] = c[2]; c[2] = c[0]; e[0] = (e[0] + e[1] + mod2) % mod2; e[1] = e[2]; e[2] = e[0]; if(find(leaving.begin(), leaving.end(), i) != leaving.end()){ c[0]= e[0] = 0; if(e[1] % 2 == 0){ c[1] = (c[1] * div2) % mod; e[1] = e[1]/2; } else{ c[1] = ((c[1] - 1) * div2) % mod; e[1] = (e[1] - 1) / 2; } } } return ( ( (c[0]% mod ) + (c[1] % mod) + mod ) + (c[2] % mod) + mod ) % mod; } };
分析
leaving イベントが起こらなければc[0] と c[2] は等しいので変数を 2 つ用意する必要はないかもしれないですが，leavingイベントが起こった直後の値の管理をどうすれば良いかが思いつかなかったです。始め元の数の偶奇だけが分かればよいかと思いましたが，2 で割った後の 偶奇が分からなくなるので，higher order まで管理する必要があります。
答えを剰余で答えるせいでプログラムを根本的に変えなければならないというのは新鮮でした。