AtCoder Beginner Contest #008 D- 金塊ゲーム
感想
AtCoder Beginner Contest 008 解説
解説スライドを見ながら解きました。
#include <bits/stdc++.h> using namespace std; int w,h; vector<int> x,y; map<tuple<int,int,int,int>,int> memo; int dfs(int l,int r,int u,int d){ int res = 0; //枠内に回収機があるか bool f = false; tuple<int,int,int,int> tp = make_tuple(l,r,u,d); if(memo.count(tp) != 0)return memo[tp]; for(int i=0;i<x.size();i++){ int ret = 0; //枠内に回収機がある if(l <= x[i] && x[i] <= r && u <= y[i] && y[i] <= d){ //回収機が枠の端以外にある時は、次の範囲を探索 if(x[i] != l){ if(y[i] != u) ret += dfs(l,x[i]-1,u,y[i]-1); if(y[i] != d) ret += dfs(l,x[i]-1,y[i]+1,d); } if(x[i] != r){ if(y[i] != u) ret += dfs(x[i]+1,r,u,y[i]-1); if(y[i] != d) ret += dfs(x[i]+1,r,y[i]+1,d); } f = true; } res = max(res,ret); } //枠内に1個も回収機がない if(!f)return 0; //回収機があれば、(幅+高さ-1)個の金塊が回収できる return memo[tp] = res + (r-l+1)+(d-u+1)-1; } int main(void) { cin >> w >> h; int n; cin >> n; x.resize(n);y.resize(n); for(int i=0;i<n;i++){ cin >> x[i] >> y[i]; } cout << dfs(1,w,1,h) << endl; return 0; }
当時は解説スライド見ても解けなかったし成長を僅かながら感じられた。
yukicoder No.164 ちっちゃくないよ！！
感想
それぞれ、(含まれている数字の最大値+1)進数で最小。
str.to_i(n)で文字列をn進数にできてruby凄い。
n = gets.to_i a = [] for i in 1..n a.push(gets.to_s) end t = 0 dic = {} for s in "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".chars dic[s] = t t += 1 end ar = [] for i in 0..n-1 ar.push(a[i].to_i(dic[a[i].chars.max]+1)) end puts ar.min
yukicoder No.163 cAPSlOCK
問題
文字列の小文字は大文字に大文字は小文字にする。
感想
それぞれのxor 32をとると大文字・小文字が反対になる。
#include <bits/stdc++.h> using namespace std; int main(void) { string s; cin >> s; for(int i=0;i<s.size();i++){ s[i] = s[i]^32; } cout << s << endl; return 0; }
Twitterで見た
【今日の競プロ】
今日は3/2ですね。32といえば2^5と思う方が大半でしょう。実はアスキーコード表において、アルファベットの大文字と小文字のバイト値のXORを取ると32になります。全て大文字にせよ、などの簡単な文字列処理の問題でコード長を短縮するのに役立つかもしれません。
— 双葉 純 (@catupper) 2015, 3月 2yukicoder No.67 よくある棒を切る問題(1)
感想
長さを二分探索したけど、で回すと大きい数の時、無限ループしてしまいました。
なので適当に100回ぐらいで打ち切った。
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<int,pair<int,int>> PP; typedef long long ll; const double EPS = 1e-10; const int INF = 1e9; const int MOD = 1e9+7; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; struct edge{int to,cost,tm;}; bool func(double len,ll K,vector<int>&L){ ll cnt = 0; for(int i=0;i<L.size();i++){ cnt += L[i]/len; if(cnt >= K)return true; } return false; } int main(void) { ll N,K; cin >> N; vector<int> L(N); for(int i=0;i<N;i++){ cin >> L[i]; } cin >> K; double low=0,hi=1e9,mid=0; int t = 0; while(hi > low+EPS && t < 100){ mid = (low + hi)/2; if(func(mid,K,L)){ low = mid; }else{ hi = mid; } t++; } cout << fixed << setprecision(11) << low << endl; return 0; }
double値の二分探索初めてした気がする。
無限ループに陥らないように気をつけていきたいです。
yukicoder No.27 板の準備
感想
制約が小さいので全探索できそう。
A,B,Cのそれぞれの長さ、それぞれの使う枚数について回して30^6ぐらいだけど実際はもう少し小さいから間に合った。
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; typedef pair<int,pair<int,int>> PP; typedef long long ll; const double EPS = 1e-8; const int INF = 1e9; const int MOD = 1e9+7; int dy[] = {0,1,0,-1}; int dx[] = {1,0,-1,0}; int sub(int a,int b,int c,int n){ int ret = INF/2; for(int i=n/c;i>=0;i--){ for(int j=n/b;j>=0;j--){ for(int k=n/a;k>=0;k--){ if(c*i+b*j+a*k == n){ ret = min(ret,i+j+k); } } } } return ret; } int func(int a,int b,int c,vector<int>& v){ int ret = 0; for(int l=0;l<4;l++){ ret += sub(a,b,c,v[l]); } return ret; } int main(void) { vector<int> v(4); cin >> v[0] >> v[1] >> v[2] >> v[3]; sort(begin(v),end(v)); int ret = INF; for(int a=1;a<=30;a++){ for(int b=a+1;b<=30;b++){ for(int c=b+1;c<=30;c++){ ret = min(ret,func(a,b,c,v)); } } } cout << ret << endl; return 0; }
★3なのに全探索で通ってしまい不安。
DPで縮められるらしいので調べておきたい。
Codeforces #294(Div.2)
1575->1516(-59)
レートは下がっちゃったけど人が多いのは楽しいですね。
A,B:手間取った。
C:よくわからないので二分探索しようとしたけど、二分探索が書けなくて焦った。
D:累積和してどうするんだろう・・・
E:読めてない
二分探索きっちり書くの難しい。
int low=min,hi=max,mid=0; while(hi > low+1){ mid = (low + hi)/2; if(/*条件*/){ low = mid; }else{ hi = mid; } } cout << low << endl;
