ARC#008
今回のAtCoderのwriterやってました。
A
まず10個ずつ纏めて全部パックで買う。そして、残りのたこ焼きを1パックで買った場合とバラで買った場合でかかる費用の小さい方を選ぶ。たこ焼きn個のときの最小費用は、100[n/10]+min{15(n%10),100}円となる。
#include <stdio.h> int main(void) { int price[10]={0, 15, 30, 45, 60, 75, 90, 100, 100, 100}; int n, pack, sole; scanf ("%d", &n); pack = n / 10; sole = n % 10; printf("%d\n", pack * 100 + price[sole]); return 0; }
#include <iostream> #include <algorithm> using namespace std; int main(void) { int n, pack, sole, price; cin >> n; pack = n / 10; sole = n % 10; price = pack * 100 + min(sole * 15, 100); cout << price << endl; return 0; }
B
各文字について、その文字を揃えるのに何袋必要になるかを考え、その最大値を答えとする。零除算に注意。
もとは英字ビスケットでケーキの飾り付けをする問題。chokduaiさんは誕生日ケーキにたこ焼き乗せてソースで「24歳」とか書いたりしてそうだなあ。
#include <stdio.h> int main(void) { int i; int n, m; int ans = 0, pack; int nameNum[32], cookieNum[32]; char name[64], cookie[64]; scanf ("%d%d", &n, &m); scanf ("%s", name); scanf ("%s", cookie); for (i = 0; i < 32; i++) { nameNum[i] = 0; cookieNum[i] = 0; } for (i = 0; i < n; i++) { nameNum[name[i] - 'A']++; } for (i = 0; i < m; i++) { cookieNum[cookie[i] - 'A']++; } for (i = 0; i < 26; i++) { if (cookieNum[i] == 0) { if (nameNum[i] > 0) { ans = 999; } } else { pack = (nameNum[i] + cookieNum[i] - 1) / cookieNum[i]; if (ans < pack) { ans = pack; } } } if (ans == 999) ans = -1; printf("%d\n", ans); return 0; }
#include <iostream> #include <string> #include <algorithm> using namespace std; int main(void) { int n, m; int ans = 0; int nameNum[32], cookieNum[32]; string name, cookie; cin >> n >> m; cin >> name; cin >> cookie; for (int i = 0; i < 32; i++) nameNum[i] = cookieNum[i] = 0; for (int i = 0; i < n; i++) nameNum[name[i] - 'A']++; for (int i = 0; i < m; i++) cookieNum[cookie[i] - 'A']++; for (int i = 0; i < 26; i++) { if (cookieNum[i] == 0) { if (nameNum[i] > 0) ans = 999; } else { ans = max (ans, (nameNum[i] + cookieNum[i] - 1) / cookieNum[i]); } } if (ans == 999) ans = -1; cout << ans << endl; return 0; }
C
ダイクストラで1番の人から各人に何秒でたこ焼きを届けられるかを計算して、時間のかかる人から順にたこ焼きを届ける。O(V^2)のダイクストラなので、慣れてなくても比較的簡単に組める。自分にたこ焼きを投げないように注意。たこ焼き投げたい。
#include <iostream> #include <cmath> #include <algorithm> #define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i) #define REP(i,n) FOR(i,0,n) using namespace std; double x[1024], y[1024], p[1024], r[1024]; double mat[1024][1024], t[1024]; bool flag[1024]; double dist(double x1, double y1, double x2, double y2) { return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); } int main(void) { int n; double ans = 0; cin >> n; REP(i,n) cin >> x[i] >> y[i] >> p[i] >> r[i]; REP(i,n) REP(j,n) mat[i][j] = dist(x[i], y[i], x[j], y[j]) / min(p[i], r[j]); REP(i,n) t[i] = 99999999, flag[i] = true; t[0] = 0; REP(i,n) { double minTime = 99999999; int num; REP(j,n) if (flag[j] && t[j] < minTime) { minTime = t[j]; num = j; } REP(j,n) t[j] = min (t[j], t[num] + mat[num][j]); flag[num] = false; } sort (t, t + n); FOR(i,1,n) ans = max (ans, t[i] + n - i - 1); cout.precision(20); cout << ans << endl; return 0; }
D
SegmentTreeを使うシンプルな問題。セグ木周りには何のひねりも無いので割と簡単。平方分割を使っても解ける。タコヤキオイシクナールなんて胡散臭いｷﾁｶﾞｲﾏｼーﾝを一兆個も買うなんて、高橋社長はどうかしてるZE☆
SegmentTree
#include <cstdio> #include <vector> #include <utility> #include <algorithm> #define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i) #define REP(i,n) FOR(i,0,n) using namespace std; typedef pair<long long,int> P; long long p[128000]; double a[128000], b[128000]; P v[128000]; const int STsize = 1 << 18; class SegTree { public: int n; double datA[STsize], datB[STsize]; SegTree(void) { n = STsize / 2; REP(i, STsize) datA[i]=1,datB[i]=0; } void update(int pos, double a, double b) { datA[pos] = a; datB[pos] = b; while (pos < 2*n-1) { int lpos = pos/2*2, rpos = pos/2*2+1; datA[pos/2+n] = datA[lpos] * datA[rpos]; datB[pos/2+n] = datA[rpos] * datB[lpos] + datB[rpos]; pos = pos/2 + n; } } double query(void) { return datA[2*n-2] + datB[2*n-2]; } }; int main(void) { long long n; int m; double ansMin = 1, ansMax = 1; scanf ("%lld%d", &n, &m); REP(i,m) { scanf("%lld%lf%lf", &p[i], &a[i], &b[i]); v[i] = make_pair(p[i], i); } sort(v, v + m); REP(i,m) { if (i == 0) p[v[0].second] = 0; else if (v[i-1].first == v[i].first) p[v[i].second] = p[v[i-1].second]; else p[v[i].second] = p[v[i-1].second] + 1; } SegTree seg; REP(i,m){ seg.update(p[i], a[i], b[i]); double ret = seg.query(); ansMin = min (ansMin, ret); ansMax = max (ansMax, ret); } printf("%.14lf\n%.14lf\n", ansMin, ansMax); return 0; }
平方分割
#include <cstdio> #include <vector> #include <utility> #include <algorithm> #define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i) #define REP(i,n) FOR(i,0,n) using namespace std; typedef pair<long long,int> P; long long p[128000]; double a[128000], b[128000]; P v[128000]; class SQRT { public: int n; double datA[102400], datB[102400]; double datC[320], datD[320]; SQRT(int m) { n = m; REP(i,n*n) datA[i]=1,datB[i]=0; REP(i,n) datC[i]=1,datD[i]=0; } void update(int pos, double a, double b) { datA[pos] = a; datB[pos] = b; datC[pos/n] = 1; datD[pos/n] = 0; REP(i,n) { datC[pos/n] *= datA[pos/n*n+i]; datD[pos/n] = datD[pos/n] * datA[pos/n*n+i] + datB[pos/n*n+i]; } } double query(void) { double ans = 1; REP(i,n) ans = ans * datC[i] + datD[i]; return ans; } }; int main(void) { long long n; int m; double ansMin = 1, ansMax = 1; scanf ("%lld%d", &n, &m); REP(i,m) { scanf("%lld%lf%lf", &p[i], &a[i], &b[i]); v[i] = make_pair(p[i], i); } sort(v, v + m); REP(i,m) { if (i == 0) p[v[0].second] = 0; else if (v[i-1].first == v[i].first) p[v[i].second] = p[v[i-1].second]; else p[v[i].second] = p[v[i-1].second] + 1; } SQRT sq(320); REP(i,m){ sq.update(p[i], a[i], b[i]); double ret = sq.query(); ansMin = min (ansMin, ret); ansMax = max (ansMax, ret); } printf("%.14lf\n%.14lf\n", ansMin, ansMax); return 0; }
50点解法
#include <iostream> #include <vector> #include <utility> #include <algorithm> #define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i) #define REP(i,n) FOR(i,0,n) using namespace std; double a[1024], b[1024]; int main(void) { int n, m; double ansMin = 1, ansMax = 1; cin >> n >> m; REP(i,1024) a[i] = 1, b[i] = 0; REP(i,m) { int pos; double ans = 1; cin >> pos; cin >> a[pos] >> b[pos]; REP(j,1024) ans = ans * a[j] + b[j]; ansMin = min (ansMin, ans); ansMax = max (ansMax, ans); } cout << ansMin << endl << ansMax << endl; return 0; }
AtCoder #007 のtesterやってました
テスターやってました。この時間帯はバイトだから参加できないのよね。
Dのテストケースをつくるときのわくわく感がやばかった。実際のテストケースファイルを作ったのはほとんどちょくだいさんだったけど。
A
前から順にやるだけ。resを用意せず順次出力していって最後に改行してもいい。
#include <iostream> #include <string> #include <algorithm> #define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i) #define REP(i,n) FOR(i,0,n) #define sz size() using namespace std; int main(void) { string s, str, res; cin >> s >> str; REP (i, str.sz) if (str[i] != s[0]) res += str[i]; cout << res << endl; return 0; }
B
同じCDが二度以上使われたり二連続で使われたりするケースがあることに注意。
#include <iostream> #include <algorithm> #define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i) #define REP(i,n) FOR(i,0,n) using namespace std; int a[128]; int main(void) { int n, m; cin >> n >> m; REP (i, 128) a[i] = i; REP (i, m){ int in, num; cin >> in; REP (j, n + 1) if (a[j] == in) num = j; swap (a[0], a[num]); } FOR (i, 1, n + 1) cout << a[i] << endl; return 0; }
C
全探索。ビットを使うとよい。greedyだと落ちる。
割と実装めんどいかなと思ってたけどそうでもなかった。
#include <iostream> #include <string> #include <algorithm> #define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i) #define REP(i,n) FOR(i,0,n) #define sz size() using namespace std; int main(void) { string str; int a = 0, res = 99999; cin >> str; REP (i, str.sz) a = a * 2 + (str[i] == 'o'); a *= (1 << str.sz) + 1; REP (i, 1 << str.sz) { int num = 0, cnt = 0; REP (j, str.sz){ if ((i & (1 << j)) == 0) continue; num |= (a >> j); cnt++; } if ((num + 1) % (1 << str.sz) == 0) res = min (res, cnt); } cout << res << endl; return 0; }
D
初項はたいてい1桁になる。
例えば
3234363840
のケースは初項は32ではない。3である。2項目は234363840。
あとは2項目をどこまで取るかで場合分けしてそれぞれが数列になりうるかどうかを判定する。数列になるもののうち2項目の値が最小となる場合を出力。
"00000"や"0001"や"0002"などのケースに注意。それぞれの出力結果は、"100000 1","1000 1","1000 1000"である。
死者数多数 http://arc007.contest.atcoder.jp/submissions/all?task_screen_name=arc007_4&language_screen_name=&status=
#include <cstdio> #include <iostream> #include <string> #include <algorithm> #define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i) #define REP(i,n) FOR(i,0,n) #define sz size() #define mp make_pair using namespace std; typedef pair<string,string> P; // return true iff a>b bool compare (string &a,string &b){ if(a.sz != b.sz) return a.sz > b.sz; REP(i,a.sz) if(a[i] != b[i])return a[i] > b[i]; return false; } // increase or decrease in digit string clean (string a){ a = "0" + a; for (int i = a.sz-1 ; i >= 0; i--){ if (a[i] > '9') { a[i] -= 10; a[i-1]++; } else if (a[i] < '0') { a[i] += 10; a[i-1] -= 1; } } REP(i,a.sz) if(a[i] > '0') return a.substr(i); return "0"; } // culcurate a + b string aplusb (string a, string b){ if (compare(a,b)) swap(a,b); b = "0" + b; REP(i,a.sz) b[b.sz-1-i] += a[a.sz-1-i] - '0'; return clean(b); } // culcurate a - b string aminusb (string a, string b){ if (compare(a,b)) swap(a,b); REP(i,a.sz) b[b.sz-1-i] -= a[a.sz-1-i] - '0'; return clean(b); } // return true iff it can be a part of a series bool isSeries(string term, string dif, string &series){ string str; int cnt = 0; while (str.sz < series.sz) { term = aplusb(term, dif); str += term; while (cnt < series.sz && cnt < str.sz) { if (series[cnt] != str[cnt]) return false; cnt++; } } return true; } P solve (string str) { // culcurate first term int num = 1; FOR(i,1,str.sz){ if (str[i] != '0') break; num = i + 1; } string firstTerm = str[0]=='0' ? "1" : ""; firstTerm += str.substr(0, num); str = str.substr(num); // cout << firstTerm << " " << str << endl; // culcurate common difference string s; if(isSeries(firstTerm,"1",str)) return mp(firstTerm, "1"); REP(i,10000000){ if(i < str.sz) s += str[i]; else s += "0"; if(compare(s,firstTerm)){ string dif = aminusb(s,firstTerm); if(isSeries(firstTerm, dif, str)) return mp(firstTerm, dif); } } return mp(firstTerm,str); } int main(void) { string str; cin >> str; P ans = solve(str); cout << ans.first << " " << ans.second << endl; return 0; }
ARC004のwriterやってました
「Cは long long と見せかけて実はそれでもオーバーフローするから多倍長を使いました。」と言われた。
でもwriter解では多倍長を使ってない。
Problem C.
#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> #include <vector> #include <string> using namespace std; typedef long long LL; LL func(LL n, LL num, LL den){ LL a = __gcd(n, den); n /= a; den /= a; LL b = __gcd(num, den); num /= b; den /= b; if(den > 1) return -1; return num * n; } int main(void){ LL num, den, n; bool flag = true; scanf ("%lld/%lld", &num, &den); n = (num * 2 + den) / den - 1; LL x = func(n, num, den); if (n > 0 && x != -1){ cout << n << " " << n * (n + 1) / 2 - x << endl; flag = false; } n++; x = func(n, num, den); if (x != -1){ cout << n << " " << n * (n + 1) / 2 - x << endl; flag = false; } if (flag) cout << "Impossible" << endl; return 0; }
ヽ( ･∀･)ﾉ┌┛ｶﾞｯ[謝罪会見会場]
