SRM600div2 Med ORSolitaireDiv2
今日からSRMdiv2med埋め開始(atcoderレート1469)
TopCoder Statistics - Match Overview
例えばgoal = 00101110の時、goalのbitが0となっている桁が1になっている数字は取り除く必要はない。 10001111は取り除く必要なし。00101000は取り除く可能性がある。 取り除く可能性がある数字の集合からgoalを作れないようにするには最小で何個の数字を取り除けば良いかという問題。
集合の数字にについて、桁ごとに1が立っている数字が何個あるか調べて、その最小値を答えれば良い。
class ORSolitaireDiv2{ public: int getMinimum(vector <int> numbers, int goal) { int n = numbers.size(); int ret = 1e9; int bit[30]; CLR(bit); FOR(i,0,n) { bool ok = true; FOR(j,0,30) { if((numbers[i]>>j)&1 && !((goal>>j)&1)) ok = false; } if(!ok) continue; FOR(j,0,30) { if((numbers[i]>>j)&1) bit[j]++; } } FOR(j,0,30) if((goal>>j)&1) ret = min(ret, bit[j]); return ret; }
ディスカバリーチャンネルコードコンテスト2016 C - ロト2
できなかったのでやり直し。
C: ロト2 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder
x * y が kの倍数 <=> gcd(x, k) * gcd(y, k) が kの倍数という性質を用いる。
計算量はO(N2) -> O(Kの約数の個数2)になる。
今回Kの約数は1344個らしい。
gcd(Ai, K)の値をmapに保存しておいて、Kの倍数になるか2重ループで調べる。 gcd(Ai, K) * gcd(Aj, K) % K == 0となる時、 map[gcd(Ai, K)] == map[gcd(Aj, K)] の時はmap[gcd(Ai, K)]個から2個選ぶ選び方の数、 そうでない時はmap[gcd(Ai, K)] * map[gcd(Aj, K)]。 ただし、二重ループで重複して数えてしまうので最後に2で割って足した 。
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> #include <bitset> #include <cstring> using namespace std; #define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; //最大公約数 ll gcd(ll a, ll b) { while (a && b) { if (a >= b) a %= b; else b %= a; } return a + b; } int main() { ios::sync_with_stdio(false); cin.tie(0); ll N, K; cin >> N >> K; map<ll, ll> MAP; FOR(i,0,N) { ll in; cin >> in; MAP[gcd(K, in)]++; } ll ans = 0; ll ans2 = 0; for(auto m1 : MAP) { for(auto m2 : MAP) { if((m1.first * m2.first) % K == 0) { if(m1.first != m2.first) { ans2 += m1.second * m2.second; } else { ans += m1.second * (m2.second - 1) / 2; } } } } cout << ans + ans2 / 2 << endl; return 0; }
ABC070 参加記録
ABCしかなかったのでABC070に参加しました。
100-200-300-400なので全完できた。
A - Palindromic Number
やるだけ。
int main() { string s; cin >> s; if(s[0] == s[2]) { puts("Yes"); } else { puts("No"); } return 0; }
B - Two Switches
場合分けしまくればO(1)でできるんだろうけどめんどくさいのでいもす法ぽくやった0(N)。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) int main() { int a,b,c,d; cin >> a >> b >> c >> d; int sw[111]; FOR(i,0,111) sw[i] = 0; sw[a]++;sw[b]--;sw[c]++;sw[d]--; FOR(i,1,111) sw[i] += sw[i-1]; int ans = 0; FOR(i,0,111) if(sw[i] == 2) ans++; cout << ans << endl; return 0; }
C - Multiple Clocks
次に全ての針が上むきで揃うのは全ての針の周期の最小公倍数秒後になる。
最小公倍数求めるライブラリ作っておくと良い。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) typedef long long ll; //最大公約数 ll gcd(ll a, ll b) { while (a && b) { if (a >= b) a %= b; else b %= a; } return a + b; } //最小公倍数 ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b;} int main() { int N; cin >> N; ll ans = 1; FOR(i,0,N) { ll in; cin >> in; ans = lcm(ans, in); } cout << ans << endl; return 0; }
D - Transit Tree Path
絶対にKを経由するのでKからそれぞれの頂点iまでの最短距離d[i]を求めておいてd[x]+d[y]を出力すればOK。
今回のグラフは木なので最短距離を求めるのはdfsでもダイクストラでもどっちでも良さそう。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) typedef long long ll; typedef pair<ll, ll> P; const ll inf = 1e15; struct edge{ ll to, cost; edge(ll t, ll c) { to = t, cost = c; } }; // Kからの距離を求めておく int N; vector<edge> G[100005]; ll d[100005]; void dijkstra(int s){ priority_queue<P, vector<P>, greater<P> >que; FOR(i,1,N+1) d[i] = inf; d[s] = 0; que.push(P(0, s)); while(!que.empty()){ P p = que.top(); que.pop(); int v = p.second; if(d[v] < p.first) continue; for(auto &e : G[v]){ if(d[e.to] > d[v] + e.cost){ d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } } } int main() { cin >> N; FOR(i,0,N-1) { ll a, b, c; cin >> a >> b >> c; G[a].push_back(edge(b, c)); G[b].push_back(edge(a, c)); } int Q, K; cin >> Q >> K; // Kからの距離 dijkstra(K); FOR(i,0,Q) { int x, y; cin >> x >> y; cout << d[x] + d[y] << endl; } return 0; }
yukicoder 171 参加記録
yukicoder 171に参加しました。
5/6完で45位でした。
星3のDPが解けなかった。
No.552 十分簡単な星1の問題
long long でもオーバーフローするのでstringで受け取って+“0"する。
ただし、0が入力される場合はそのまま出力することに注意。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { string s; cin >> s; if(s.length() == 1 && s[0] == '0') cout << 0 << endl; else cout << s << 0 << endl; return 0; }
No.553 AlphaCoder Rating
やるだけだけど数式が複雑でめんどくさそうなので後回しにした。
誤差±1までOKなので誤差を気にせず実装して大丈夫だった。
逆関数の知識が必要。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { int N; cin >> N; double r[N]; FOR(i,0,N) cin >> r[i]; double Fn, fn, f1, finf; FOR(i,1,N+1) Fn += pow(0.81, i); Fn = sqrt(Fn); double tmp = 0; FOR(i,1,N+1) tmp += pow(0.9, i); Fn /= tmp; f1 = sqrt(0.81) / 0.9; finf = sqrt(0.81 / 0.19) / (0.9 / 0.1); fn = (Fn - finf) / (f1 - finf) * 1200; double ans = 0; FOR(i,1,N+1) { ans += pow(2, r[i-1] / 800.0) * pow(0.9, i); } ans /= tmp; ans = 800 * log(ans) / log(2); ans -= fn; cout << int(ans) << endl; return 0; }
No.554 recurrence formula
第2項から順に求めていく。
和の部分を毎回求めていたらO(n2)となるのでTLE。
累積和を保存しておけばO(n)となってAC。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; const ll mod = 1e9 + 7; int main() { int n; cin >> n; ll oddsum = 1, evensum = 0; ll a = 1; FOR(i,2,n+1) { if(i % 2 == 0) { a = i * oddsum; a %= mod; evensum += a; evensum %= mod; } else { a = i * evensum; a %= mod; oddsum += a; oddsum %= mod; } } cout << a % mod << endl; return 0; }
No.555 世界史のレポート
DPぽいなと思ったけどできなかった問題。
dp[i] := 長さをi以上にするのに必要な最小コストとしてしまうとO(n2)となりTLE。
dp[i] := 長さをちょうどiにするのに必要な最小コストとする。 長さをiにするには、長さがiの約数dになった時にコピーしてペーストを(i - d) / d回する。 iの約数の個数は高々 らしいのでO()となりAC。
長さがn-1の時にコピーしてペースとしたら2n-2になるので、dp[2n-2]まで計算する。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; int main() { int N, C, V; cin >> N >> C >> V; ll dp[2*N]; FOR(i,0,2*N) dp[i] = 1e9; dp[0] = dp[1] = 0; // ちょうどiにする FOR(i, 1, 2*N) { // Aの個数がiの約数dになったらコピーしてそのあとペースト // (i / d - 1) 回足せばちょうどiになる for(int d = 1; d * d <= i; d++) { if(i % d == 0) { dp[i] = min(dp[i], dp[d] + C + V * (i / d - 1)); dp[i] = min(dp[i], dp[i/d] + C + V * (d - 1)); } } } ll ans = dp[N]; FOR(i, N, 2 * N) ans = min(ans, dp[i]); cout << ans << endl; return 0; }
No.556 仁義なきサルたち
Union-Findを使う。子分の数を保存しておく。
xとyが喧嘩したらxとyを同じグループにする。この時子分の数が多い方を親とする。 子分の数が同じ時はx<yならxを親にする。x>yならyを親にする。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; // union - find tree !!!!!!!!!!!!!!!!!!!!!!!!! vector<int> par; //oya vector<int> rnk; //子分の数 // n要素で初期化 void init(int n){ par.resize(n);rnk.resize(n); FOR(i, 0, n){par[i] = i;rnk[i] = 1;} } //木の根を求める int find(int x){ if(par[x] == x) return x; else return par[x] = find(par[x]); } //xとyの属する集合を併合 void unite(int x, int y){ x = find(x);y = find(y); if(x == y) return; if(rnk[x] < rnk[y]) swap(x, y); if(rnk[x] == rnk[y] && x > y) swap(x, y); par[y] = x; rnk[x] += rnk[y]; rnk[y] = 0; return; } int main() { int N, M; cin >> N >> M; init(N+1); FOR(i,0,M) { int a, b; cin >> a >> b; unite(a, b); } FOR(i,1,N+1) { cout << find(i) << endl; } return 0; }
No.557 点対称
それぞれの桁に何通りの数字がありえるのか考える。
そして全てかける。
ただし、最大でくらいの計算をする必要が出てくるのでTLEに注意。
高速に(O(log n))累乗を計算するテクニックを使う必要がある。
例えば、aの8乗を計算する時はaを8回かけるよりa->a×a->(a2)×(a2)->(a4)×(a4)というように掛け算した結果を使用した方が早い。a ×= aを3回計算すれば終わる。 100乗の場合100 = 64(26) + 32(25) + 4(22)であり、a ×= aを5回計算すれば終わる。100を2進数にした時に右のbitから調べていき1になっている時にaを足せば良い。
#define FOR(I,A,B) for(int I = (A); I < (B); ++I) #define CLR(mat) memset(mat, 0, sizeof(mat)) typedef long long ll; const int mod = 1e9 + 7; int main() { ll N; cin >> N; if(N == 1) { cout << 2 << endl; return 0; } ll ans; if(N % 2 == 1) ans = 3; else ans = 1; // 5^(N/2-1)を高速に計算 ll j = 0; ll fi = 5; ll p = N / 2 - 1; while((1LL<<j) <= p) { if((p>>j)&1) { ans *= fi; ans %= mod; } fi *= fi; fi %= mod; j++; } ans *= 4; cout << ans % mod << endl; }
問題集(随時更新)
雑なので時間があったらまとめていこう...
全探索(工夫して全探索も)
http://arc020.contest.atcoder.jp/tasks/arc020_2
https://www.hackerrank.com/challenges/two-characters
http://poj.org/problem?id=3279
http://abc002.contest.atcoder.jp/tasks/abc002_4
http://arc074.contest.atcoder.jp/tasks/arc074_b
深さ優先全探索dfs
http://arc001.contest.atcoder.jp/tasks/arc001_3
http://arc009.contest.atcoder.jp/tasks/arc009_3
メモ化再帰
http://tenka1-2012-final.contest.atcoder.jp/tasks/tenka1_2012_final_a
http://wupc2nd.contest.atcoder.jp/tasks/wupc_02
幅優先全探索
http://arc005.contest.atcoder.jp/tasks/arc005_3
http://arc001.contest.atcoder.jp/tasks/arc001_2
https://www.hackerrank.com/contests/w32/challenges/circular-walk
動的計画法dp
http://wupc2nd.contest.atcoder.jp/tasks/wupc_02
http://abc054.contest.atcoder.jp/tasks/abc054_d
https://www.hackerrank.com/contests/world-codesprint-10/challenges/permutation-happiness
bit
http://arc007.contest.atcoder.jp/tasks/arc007_3
bit , nCrの計算
https://www.hackerrank.com/contests/world-codesprint-10/challenges/maximal-and-subsequences
bit+dp
http://arc010.contest.atcoder.jp/tasks/arc010_3
メモ化再帰+dp+bit???!!! - > 再帰関数の中にdp...
https://www.hackerrank.com/contests/rookierank-3/challenges/max-score
貪欲法
http://arc006.contest.atcoder.jp/tasks/arc006_3
http://abc003.contest.atcoder.jp/tasks/abc003_3
ベルマンフォード法
http://abc061.contest.atcoder.jp/tasks/abc061_d
Union-Find tree
http://poj.org/problem?id=1182
クラスカル法
http://poj.org/problem?id=3723
しゃくとり法
http://abc038.contest.atcoder.jp/tasks/abc038_c
http://abc032.contest.atcoder.jp/tasks/abc032_c
http://poj.org/problem?id=3061
累積和
http://abc037.contest.atcoder.jp/tasks/abc037_c
二次元累積和
http://agc015.contest.atcoder.jp/tasks/agc015_c
クラスカル法, 自作の評価関数でsort, 最小公倍数, 平均最大化with二分探索
https://www.hackerrank.com/contests/w31/challenges/spanning-tree-fraction
関数の最大化最小化with二分探索
http://poj.org/problem?id=1064
http://poj.org/problem?id=2456
https://www.codechef.com/SNCKPA17/problems/CONSESNK
http://arc075.contest.atcoder.jp/tasks/arc075_b
stack (使う必要ないやつもある)
https://www.hackerrank.com/challenges/reduced-string
https://www.hackerrank.com/challenges/counting-valleys
いもす法
http://abc001.contest.atcoder.jp/tasks/abc001_4
半分全列挙
http://poj.org/problem?id=2785
強連結成分分解, トポロジーソート??!!, bitset
https://www.hackerrank.com/contests/world-codesprint-11/challenges/hackerland
BIT
+圧縮
http://arc075.contest.atcoder.jp/tasks/arc075_c
桁DP
http://abc007.contest.atcoder.jp/tasks/abc007_4
http://abc029.contest.atcoder.jp/tasks/abc029_d
https://yukicoder.me/problems/no/220
https://yukicoder.me/problems/no/189
行列累乗
木DP
https://arena.topcoder.com/#/u/practiceCode/17090/60726/14812/2/331054
最小カット
グラフ
http://abc040.contest.atcoder.jp/tasks/abc040_d
ゲーム(3ターン目以降でいい点取れないので実質1ターンで終わる問題)
https://community.topcoder.com/tc?module=ProblemDetail&rd=15836&pm=12946 https://beta.atcoder.jp/contests/arc085/tasks/arc085_b
【AtCoder】ABC038 C. 単調増加
AtCoderの問題
C: 単調増加 - AtCoder Beginner Contest 038 | AtCoder
参考書
難しさ(初心者目線)
・考え方***
・実装**
・面白さ***
問題概要
・N個の数からなる数列が与えられる.
・が単調増加、すなわち l≦r であってa_i<a_i+1がl≦i<r を満たす全てのiに対して成り立つような(l,r)の数を求めよ.
制約
1 ≦ N ≦ 105
方針
・普通にあるlに対して最大のrを求める方法だと最悪O(N2).
・あるlに対して最大のrを求めたら、l+1<rの時l+1に対しても同じrとなる.
・l+1=rとなったら再び最大のrを求める.
・よって全てのlの合計でrを探すのにN回しかループしないのでO(N)となり間に合う.
コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) //答え見た int main(){ int N; cin >> N; int a[N+1]; FOR(i, 0, N) cin>>a[i]; a[N] = 0; int l = 0, r = 0; ll ans = 0; while(l < N){ while(a[r+1] > a[r]) r++; ans += r - l + 1; l++; if(l==r+1) r++; } cout << ans << endl; }
【AtCoder】ABC040 C. 柱柱柱柱柱
AtCoderの問題
C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder
参考書
難しさ(初心者目線)
・考え方**
・実装***
・面白さ**
問題概要
・柱が1列にN本並んでいる.
・それぞれの柱の高さはである.
・1本目からN本目まで飛び移りながら移動したい.
・飛び移るには飛び移る前と後の柱の高さの差の絶対値の体力を消耗する.
・最大1本飛ばしできる.
・消費する体力を最小にしたい、最小値を求めよ.
方針
動的計画法か深さ優先全探索(メモ化再帰)で解くことができる.好みだと思う.
動的計画法の場合
dp[i]:=i番目の柱に行くために消費する体力の最小値とする.
これは1個前から来た方が良いのか2個前から来た方が良いのかの二択である(1個前と2個前の柱に行くために消費する体力はすでに最小値を求めているので).
つまり
dp[i] = min(dp[i-1]+1個前の柱との差の絶対値, dp[i-2]+2個前の柱との差の絶対値)
2本目の柱は1本目の柱からしか来れないことに注意.
深さ優先全探索の場合
メモ化再帰を用いてとく.
動的計画法コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) //動的計画法 //dp[i]:=i番目の柱に行く最小値 int a[100000]; int N; ll dp[100001]; int main(){ cin>>N; FOR(i, 0, 100000) a[i] = 0; FOR(i, 0, N) cin>>a[i]; FOR(i, 0, 100001) dp[i] = 999999999999; dp[0] = 0; dp[1] = 0;//1番目の柱に行く最小値はもちろん0 dp[2] = abs(a[1] - a[0]);//2番目の柱には1番目からくるしかない FOR(i, 3, N+1){ //1個前と2個前どっちからきた方がi番目は最小値になるか dp[i] = min(dp[i-2]+abs(a[i-1]-a[i-3]), dp[i-1]+abs(a[i-1]-a[i-2])); } cout << dp[N] << endl; }
メモ化再帰コード
#include <algorithm> #include <cstdio> #include <iostream> #include <map> #include <cmath> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <vector> #include <stdlib.h> #include <stdio.h> using namespace std; #define ll long long #define PI acos(-1.0) #define FOR(I,A,B) for(int I = (A); I < (B); ++I) int a[100000]; int N; ll INF = -1; //再帰関数+メモ化 //位置は0~N-1 ll dp[100000][2]; ll dfs(int n, int bef){ //N本目についたらおしまい if(n == N-1) return abs(a[N-1] - a[n-bef]); //N本目を超えてしまう場合注意 if(n == N) return abs(a[N-1] - a[N-2]); //すでに計算済みならそれを返す if(dp[n][bef-1]!=INF) return dp[n][bef-1]; ll ret = abs(a[n] - a[n-bef]); ret += min(dfs(n+1, 1), dfs(n+2, 2)); return dp[n][bef-1] = ret; } int main(){ cin>>N; FOR(i, 0, 100000) a[i] = 0; FOR(i, 0, N) cin>>a[i]; FOR(i, 0, 100000) FOR(j, 0, 2) dp[i][j] = INF; cout << min(dfs(1, 1), dfs(2, 2)) << endl; }