JOIss2013
参加記です.
JOIssは8/26~30に準山奥で開催されました.
怖い本ばかりに見えて怯えながらコンピュータ・ジオメトリを選択しました.
(指圧マットさんとhogloidさんと同じ班, チューターは藤原さんでした)
講義寝まくってすみませんでした..
セミナーも楽しかったですが普段なかなか会えない人達と交流出来たのが何より良かったです.
それから変な用語が生まれる感じが面白かったです.
最終日にはみんな疲れてきて, snukeさんとDEGwerさんが添い寝したりしていました.
添い寝する人多すぎると思いました.
発表会の間Twitterで実況しまくって規制垢をたくさん作っているチューターとかがいてやばかっｙった(tozanさんプロ)
最終日kagamiz先生と遊んで帰ろうとしたら新幹線の終電がかなり危ない感じになって走って乗るとrefuteさんとcubicさんがいて驚いた.
参加権がまだある人は積極的に行くといいと思います.
内輪感が強くて初めは大変かもしれませんが慣れると快適です!
夏休みの宿題の進捗ダメです！
agypo3したい...
関係ないですがソースを載せておきます.
PKU 3274 Gold Balanced Lineup
N個の数列が与えられて, ある区間に含まれる数の各bitについて立っている個数が等しいような区間をバランスの良い区間と定義した時, 最長のバランスの良い区間の長さを出力せよ.
(N <= 10^5, ai <= 2^30)
少し考えると, 上から順番に見ていって, 各bit間の差が等しいようになる場所が2つあればその間がバランスの良い区間になることがわかるので, 適当に計算する(差を変なハッシュにしてやるとNlogNになる)
//include //------------------------------------------ #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <queue> #include <climits> using namespace std; //conversion //------------------------------------------ inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;} template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();} //math //------------------------------------------- template<class T> inline T sqr(T x) {return x*x;} //typedef //------------------------------------------ typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef pair<int, int> P; typedef long long ll; //container util //------------------------------------------ #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() #define pb push_back #define mp make_pair #define SZ(a) int((a).size()) #define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define SORT(c) sort((c).begin(),(c).end()) #define fi first #define se second //repetition //------------------------------------------ #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) //constant //-------------------------------------------- const double EPS = 1e-10; const double PI = acos(-1.0); const int dx[] = {-1,1,0,0}; const int dy[] = {0,0,1,-1}; //clear memory #define CLR(a) memset((a), 0 ,sizeof(a)) //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; int n, k, ans; int a[100010]; map<ll, int> zan; int z[40]; int main(){ scanf("%d %d", &n, &k); zan[0] = 0; rep(i, n){ scanf("%d", &a[i]); int x = a[i]; rep(j, k){ z[j] += (x & 1); x /= 2; } int mi = 2; rep(j, k) mi = min(mi, z[j]); ll cur = 0; rep(j, k){ cur *= ll(n + 1); z[j] -= mi; cur += z[j]; } if(zan.count(cur)) ans = max(ans, i + 1 - zan[cur]); else zan[cur] = i + 1; } printf("%d\n", ans); return 0; }
PKU 3613 Cow Relays
辺の数が100以下のグラフが与えられる.
点sからtにちょうど辺をN本経由して行く時の最短距離を求めよ(N<=10^6)
各点の次数が2以上という条件から表れる点が高々100個であることがわかる.
行列累乗みたいな感じのことをすると通る. O(V^3*logN)
//include //------------------------------------------ #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <queue> #include <climits> using namespace std; //conversion //------------------------------------------ inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;} template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();} //math //------------------------------------------- template<class T> inline T sqr(T x) {return x*x;} //typedef //------------------------------------------ typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<string> VS; typedef pair<int, int> P; typedef long long ll; //container util //------------------------------------------ #define ALL(a) (a).begin(),(a).end() #define RALL(a) (a).rbegin(), (a).rend() #define pb push_back #define mp make_pair #define SZ(a) int((a).size()) #define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define SORT(c) sort((c).begin(),(c).end()) #define fi first #define se second //repetition //------------------------------------------ #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) #define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++) //constant //-------------------------------------------- const double EPS = 1e-10; const double PI = acos(-1.0); const int dx[] = {-1,1,0,0}; const int dy[] = {0,0,1,-1}; //clear memory #define CLR(a) memset((a), 0 ,sizeof(a)) //debug #define dump(x) cerr << #x << " = " << (x) << endl; #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; int n, m, st, en; pair<P, int> eg[110]; vector<int> xs; int id[1010]; ll d[110][110]; ll x[110][110]; ll ret[110][110]; int main(){ scanf("%d %d %d %d", &n, &m, &st, &en); rep(i, m){ scanf("%d %d %d", &eg[i].se, &eg[i].fi.fi, &eg[i].fi.se); xs.pb(eg[i].fi.fi); xs.pb(eg[i].fi.se); } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); rep(i, xs.size()) id[xs[i]] = i; rep(i, xs.size()){ rep(j, xs.size()) d[i][j] = x[i][j] = ret[i][j] = INT_MAX; x[i][i] = 0; } rep(i, m){ eg[i].fi.fi = id[eg[i].fi.fi]; eg[i].fi.se = id[eg[i].fi.se]; d[eg[i].fi.fi][eg[i].fi.se] = d[eg[i].fi.se][eg[i].fi.fi] = eg[i].se; } while(n > 0){ if(n & 1){ rep(i, xs.size()) fill(ret[i], ret[i] + xs.size(), INT_MAX); rep(i, xs.size()) rep(j, xs.size()) rep(k, xs.size()) ret[i][k] = min(ret[i][k], x[i][j] + d[j][k]); rep(i, xs.size()) rep(j, xs.size()) x[i][j] = ret[i][j]; } rep(i, xs.size()) fill(ret[i], ret[i] + xs.size(), INT_MAX); rep(i, xs.size()) rep(j, xs.size()) rep(k, xs.size()) ret[i][k] = min(ret[i][k], d[i][j] + d[j][k]); rep(i, xs.size()) rep(j, xs.size()) d[i][j] = ret[i][j]; n /= 2; } printf("%lld\n", x[id[st]][id[en]]); return 0; }
SRM585 Div1
コーナーケース氏死んでくれ〜〜 ちゃんと制約読もう
easy
まあ色んな方法あるが自分は下から取っていくイメージ
#define MOD (1000000007LL) ll p[1000010]; ll r[1000010]; class TrafficCongestion{ public: int theMinCars(int treeHeight){ int h = treeHeight; p[0] = 1LL; p[1] = 2LL; for(int i = 2; i <= 1000000; ++i) p[i] = p[i-1] * 2LL % MOD; if(h == 0) return 1; if(h == 1) return 1; r[0] = 1; r[1] = 1; for(int i = 2; i <= h; ++i) r[i] = (p[i-1] + r[i-2]) % MOD; return (int)r[h]; } };
med
自明にdpだが式が少し難しい。左から見ていって、新しい数をそれまであった列に挿入していくイメージで考えると、strictly increasingな末尾に挿入すればLISnumberがそのままで、そうでない所に挿入すれば+1されることに気付くと、よくある数え上げdpになる。
#define MOD (1000000007LL) int n; ll comb[1310][1310]; ll dp[40][1310]; void pre(){ comb[0][0] = 1LL; comb[1][0] = comb[1][1] = 1; for(int i = 2; i <= 1300; ++i){ comb[i][0] = comb[i][i] = 1; for(int j = 1; j < i; ++j) comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD; } } class LISNumber{ public: int count(vector <int> cardsnum, int K){ vector<int> a = cardsnum; n = (int)a.size(); pre(); int s = a[0]; dp[1][a[0]] = 1; for(int i = 1; i < n; ++i){ s += a[i]; for(int j = 1; j <= s; ++j){ for(int k = max(1, j - a[i]); k <= min(j, s); ++k){ if(a[i] + k - j < 0 || a[i] - j > 1) continue; dp[i+1][j] += (dp[i][k] * comb[k][a[i] + k - j]) % MOD * comb[s - k][j - k]; dp[i+1][j] %= MOD; } } } return (int)dp[n][K]; } };
SRM583 Div1
1331->1501 初めての黄色！Med通せて嬉しみ。(遅いけど)
Easy TravelOnMars
環状な路線での最短距離問題。bfsやるだけ modを取って負の値になることがあるので落ちまくっていたらしい
int n; int d[60]; class TravelOnMars{ public: int minTimes(vector <int> range, int s, int g){ n = range.size(); fill(d, d + n, 110); d[s] = 0; queue<int> q; q.push(s); while(!q.empty()){ int v = q.front(); q.pop(); if(v == g) break; for(int i = v - range[v]; i <= v + range[v]; ++i){ int now = i % n; if(now < 0) now += n; if(d[now] == 110){ d[now] = d[v] + 1; q.push(now); } } } return d[g]; } }
Medium TurnOnLamps
木の上で2点を選んで間にある道のスイッチを切り替えるという操作を最小何回で目的の状態にできるか。
greedyやるだけ。デバッグ力低かった
int n, ans; vector<P> g[60]; int ch[60]; int calc(int v, int p){ int ret = 0; rep(i, g[v].size()) if(g[v][i].fi != p){ int tmp = calc(g[v][i].fi, v); if(~ch[g[v][i].se] && ((tmp & 1) != ch[g[v][i].se])){ if(tmp == 1) ++ans; tmp = ch[g[v][i].se]; } //if(v == 0) printf("%d\n", tmp); ret += tmp; } ans += ret / 2; ret &= 1; //printf("vertex:%d, return:%d, ans:%d\n", v, ret, ans); return ret; } class TurnOnLamps{ public: int minimize(vector <int> roads, string initState, string isImportant){ memset(ch, false, sizeof(false)); rep(i, 60) g[i].clear(); ans = 0; n = (int)roads.size() + 1; rep(i, n - 1){ g[i + 1].pb(mp(roads[i], i)); g[roads[i]].pb(mp(i + 1, i)); } rep(i, n - 1){ if(isImportant[i] == '0') ch[i] = -1; else if(initState[i] == '1') ch[i] = 0; else ch[i] = 1; } if(calc(0, -1) & 1) ++ans; return ans; } };
Codeforces Round #157 (Div. 1) D. Little Elephant and Broken Sorting
1~nを並び替えた数列があって、a番目とb番目を入れ替えるクエリがm個来るが、それぞれのクエリは1/2の確率でしか実行されない
この時クエリをm個処理した後の反転数の期待値を求めよ
p[i][j] : i番目 < j番目という配列を持って、クエリに対して順番に確率を計算していけば、
最後に足し合わせることで期待値が求まる。
Div1Dにしては軽実装
#include <cstdio> using namespace std; #define rep(i, m) for(int i = 0; i < (int)m; ++i) int n, m; int a[1010]; double ret; double p[1010][1010]; int main(){ scanf("%d %d", &n, &m); rep(i, n) scanf("%d", &a[i]); rep(i, n) rep(j, n) if(i != j) p[i][j] = (a[i] > a[j] ? 1.0 : 0.0); while(m--){ int a, b; scanf("%d %d", &a, &b); --a; --b; p[a][b] = p[b][a] = 0.5; rep(i, n) if(i != a && i != b){ p[i][a] = p[i][b] = (p[i][a] + p[i][b]) / 2.0; p[a][i] = p[b][i] = 1.0 - p[i][a]; } } rep(i, n) rep(j, i) ret += p[j][i]; printf("%.8lf\n", ret); return 0; }
SRM578 GooseInZooDivOne
マンハッタン距離がdist以下のやつをunionfindでくっつけてから偶奇を見るだけ。
偶数のやつは何個使っても良くて、奇数のやつは偶数個使わなければいけないけど、
偶数のやつをP個, 奇数のやつをQ個とすれば
Q >= 1の時 2 ^ (P + Q - 1) - 1, Q = 0の時 2 ^ P - 1が答えとなる
(奇数のやつをQ - 1個目まで使うかどうか決めれば最後のやつ使うかどうかは勝手に決まるから)
#include <vector> #include <cstdio> #include <string> using namespace std; typedef long long ll; #define rep(i, n) for(int i = 0; i < (int)n; ++i) #define MOD (1000000007LL) int cnt[5010]; int gu, ki; ll r[5020]; struct unionfind{ int par[5010], rank[5010]; unionfind(){ rep(i, 5010){ par[i] = i; rank[i] = 0; } } inline int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } inline void unite(int x, int y){ x = find(x); y = find(y); if(x == y) return ; if(rank[x] < rank[y]) par[x] = y; else{ par[y] = x; if(rank[x] == rank[y]) rank[x]++; } } }uf; class GooseInZooDivOne{ public: int count(vector <string> f, int d){ int h = f.size(), w = f[0].size(); rep(i, h){ rep(j, w){ if(f[i][j] == 'v'){ rep(k, h){ rep(l, w){ if((i == k && j == l) || f[k][l] == '.') continue; int de = abs(i - k) + abs(j - l); if(de <= d) uf.unite(i * 60 + j, k * 60 + l); } } } } } rep(i, h) rep(j, w) if(f[i][j] == 'v') ++cnt[uf.find(i * 60 + j)]; rep(i, h) rep(j, w) if(cnt[i * 60 + j] > 0){ if(cnt[i * 60 + j] & 1) ki++; else gu++; } if(gu == 0 && ki < 2) return 0; r[0] = 1LL; rep(i, 5010) r[i + 1] = r[i] * 2 % MOD; if(ki) --ki; return r[ki + gu] - 1; } };
連結リスト
ポインタ難しいけどこの際listぐらいは実装できるようになろうと思ったら簡単だった(小並)
こんな感じでいいのかな？
#include <cstdio> #include <cstdlib> using namespace std; struct Node{ Node *prev, *next; int val; }; Node *head, *tail; void init(){ head = tail = NULL; } void make_node(int x){ Node *cur = new Node; cur->val = x; cur->next = NULL; if(tail == NULL){ head = tail = cur; cur->prev = NULL; }else{ tail->next = cur; cur->prev = tail; tail = cur; } } void dest(){ for(Node *now = head; now != NULL;){ Node *rem = now; now = now->next; delete rem; } } int calc_sum(){ int s = 0; for(Node *now = head; now != NULL; now = now->next) s += now->val; return s; }
Croc Champ 2013 - Round 2 (Div. 2 Edition)
Div2だけど1位とれて嬉しい(小並感)
Div2E本番中に通せたの初めてな気が。mathのおかげ
A. やるだけ __gcd()使おう
int n; int a[100010]; int g; int main(){ cin >> n; rep(i, n){ cin >> a[i]; if(!i) g = a[i]; else g = __gcd(g, a[i]); } rep(i, n){ if(g % a[i] == 0){ cout << a[i] << endl; return 0; } } cout << "-1" << endl; return 0; }
B. 連続したものを数える
int n, k; string s; vector<int> inv; int main(){ cin >> n >> k >> s; int crt = 0; rep(i, n){ if(s[i] == '.'){ if(crt) inv.pb(crt); crt = 0; }else{ crt++; } } if(crt) inv.pb(crt); rep(i, inv.size()){ if(inv[i] >= k){ cout << "NO" << endl; return 0; } } cout << "YES" << endl; return 0; }
C.
自分 相手
1 1
1 0
0 1
0 0
となる所がこの順に有効なのでgreedyする
int n; string s, t; int a, b, c; int p, q, now; string win(){ if(p > q) return "First"; else if(p < q) return "Second"; else return "Draw"; } int main(){ cin >> n >> s >> t; rep(i, n * 2){ if(s[i] == '1' && t[i] == '1') ++a; else if(s[i] == '1' && t[i] == '0') ++b; else if(s[i] == '0' && t[i] == '1') ++c; } p = (a + 1) / 2; q = a - p; now = a; if(now & 1){ if(c){ --c; ++q; ++now; } else if(b){ --b; ++now; }else{ cout << win() << endl; return 0; } } while(now < n * 2){ rep(i, 2){ if(i == 0){ if(b){ --b; ++p; ++now; } else if(c){ --c; ++now; }else{ cout << win() << endl; return 0; } }else{ if(c){ --c; ++q; ++now; } else if(b){ --b; ++now; }else{ cout << win() << endl; return 0; } } } } cout << win() << endl; return 0; }
D. DP? うまくできるらしいけどわからない。
E. math
n = (a + b + c) ^ 3 - a ^ 3 - b ^ 3 - c ^ 3 = 3(a + b)(b + c)(c + a)より、
p = a + b, q = b + c, r = c + aと置けば
pqr = n / 3かつ、(p + q + r) / 2 = a + b + cよりp, q, rの組にa, b, cが一意に対応。
a, b, c > 0に注意すればp, q, rが三角形を成すことがわかる。
ll ans; ll n; vector<ll> vec; void pr(){ for(ll i = 1; i * i <= n; ++i) if(n % i == 0) vec.pb(i); } int main(){ cin >> n; if(n % 3){ cout << "0\n"; return 0; } n /= 3; pr(); rep(i, vec.size()){ ll v = vec[i]; ll d = n / v; for(int j = vec.size() - 1; j >= 0; --j){ if(d % vec[j]) continue; ll p = d / vec[j]; if(v + vec[j] <= p) break; if((v + vec[j] + p) % 2 == 0 && v + p > vec[j] && vec[j] + p > v){ ans++; } } } cout << ans << endl; return 0; }
