New Year Contest 2015
rng_58さんのコンテスト。まだあんまり解けてないけど面白かった。
とりあえずコンテスト中に通った分だけ
A : 愚直にやればよい(vectorは比較出来るらしい)
#include <bits/stdc++.h> using namespace std; #define pb push_back int n; vector<int> a,b; int main(){ cin>>n; while(n){ a.pb(n&1); n/=2; } b=a; reverse(b.begin(),b.end()); if(a==b) cout<<"Yes\n"; else cout<<"No\n"; return 0; }
B : sortしてgreedyに拾っていく
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<n;++i) int n,ret; ll a[1010],s; int main(){ cin>>n; rep(i,n) cin>>a[i]; a[n]=LLONG_MAX; sort(a,a+n); s=a[0];ret=1; for(int i=1;i<n;){ int v=upper_bound(a+i,a+n,s)-a; if(v==n) break; i=v; s+=a[v]; ++ret; } printf("%d\n",ret); return 0; }
C : 一見難しそうだけど、少し考えると、元ある文字と文字の間には、1文字目が異なるならなんでも挿入出来ることがわかる。DPしなくても出来るらしい。
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;++i) bool ok[5010][5010]; string s,t; bool ch(){ if(s.size()>t.size()) return 0; ok[0][0]=1; rep(i,s.size()){ int mi=5010; rep(j,t.size()){ if(ok[i][j]&&s[i]==t[j]){ ok[i+1][j+1]=1; if(j+1<t.size()&&t[j]!=t[j+1]){ mi=min(mi,j+1); } } } for(int j=mi;j<=t.size();++j) ok[i+1][j]=1; } return ok[s.size()][t.size()]; } int main(){ cin>>s>>t; if(ch()) cout<<"Yes\n"; else cout<<"No\n"; return 0; }
D : 問題文が親切。x -> a*2 - xに移る。更にb*2 - (a*2 - x) = b*2 - a*2 + xという風に、xに関係なく移動幅が決まるので0から偶奇別にBFSするとなんとかなる。
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; #define mp make_pair #define fi first #define se second #define rep(i,n) for(int i=0;i<n;++i) const int B = 50010; int d[2][100050],n,a[210],q; int main(){ memset(d,-1,sizeof(d)); scanf("%d",&n); rep(i,n){scanf("%d",a+i);a[i]*=2;} queue<pii> que; que.push(mp(0,B)); d[0][B]=0; while(!que.empty()){ pii p=que.front();que.pop(); int f=p.fi,x=p.se-B; rep(i,n){ int nx=a[i]-x; if(nx>=-20000&&nx<=30000&&d[f^1][nx+B]==-1){ d[f^1][nx+B]=d[f][x+B]+1; que.push(mp(f^1,nx+B)); } } } scanf("%d",&q); while(q--){ int s,t; scanf("%d%d",&s,&t); int l=d[0][t-s+B],r=d[1][t+s+B],as; if(l!=-1&&r!=-1) as=min(l,r); else if(l!=-1) as=l; else if(r!=-1) as=r; else as=-1; printf("%d\n",as); } return 0; }
G : JOIでよくありそうな感じ。最短路的なことをすると解けるが適当にやると計算量がダメ。
もう動き出して他にぶつかるのを考えた点を消す&同じ向きのロボットに当たったらそっちを動かすことにして打ち切ると大丈夫。
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; typedef long long ll; #define pb push_back #define mp make_pair #define fi first #define se second #define rep(i,n) for(int i=0;i<n;++i) int dx[]={0,0,-1,1}; int dy[]={1,-1,0,0}; struct ev{ int id;ll tt; ev(int id, ll tt):id(id),tt(tt){} bool operator<(const ev& a) const{ return tt>a.tt; } }; int n; int dir[100010]; ll t,st[100010]; pii po[100010]; vector<int> xs,ys; set<pii> sx[100010],sy[100010]; void rem(int i){ int xx=lower_bound(xs.begin(),xs.end(),po[i].fi)-xs.begin(), yy=lower_bound(ys.begin(),ys.end(),po[i].se)-ys.begin(); sy[xx].erase(mp(po[i].se,i)); sx[yy].erase(mp(po[i].fi,i)); } int main(){ scanf("%d%lld",&n,&t); rep(i,n) st[i]=LLONG_MAX; rep(i,n){ char c[3]; scanf("%d%d%s",&po[i].fi,&po[i].se,c); if(c[0]=='U') dir[i]=0; else if(c[0]=='D') dir[i]=1; else if(c[0]=='L') dir[i]=2; else dir[i]=3; xs.pb(po[i].fi); ys.pb(po[i].se); } sort(xs.begin(),xs.end()); sort(ys.begin(),ys.end()); xs.erase(unique(xs.begin(),xs.end()),xs.end()); ys.erase(unique(ys.begin(),ys.end()),ys.end()); rep(i,n){ int xx=lower_bound(xs.begin(),xs.end(),po[i].fi)-xs.begin(), yy=lower_bound(ys.begin(),ys.end(),po[i].se)-ys.begin(); sx[yy].insert(mp(po[i].fi,i)); sy[xx].insert(mp(po[i].se,i)); } priority_queue<ev> que; que.push(ev(0,0)); while(!que.empty()){ ev e=que.top(); que.pop(); if(st[e.id]<e.tt) continue; int xx=lower_bound(xs.begin(),xs.end(),po[e.id].fi)-xs.begin(), yy=lower_bound(ys.begin(),ys.end(),po[e.id].se)-ys.begin(); st[e.id]=e.tt; rem(e.id); int d=dir[e.id]; if(d==0){ for(auto it=sy[xx].upper_bound(mp(po[e.id].se,-1));it!=sy[xx].end();++it){ int ii=(*it).se; ll nt=e.tt+(*it).fi-po[e.id].se; que.push(ev(ii,nt)); if(dir[ii]==d) break; } }else if(d==1){ for(auto it=sy[xx].lower_bound(mp(po[e.id].se,-1));;){ if(it==sy[xx].begin()) break; --it; int ii=(*it).se; ll nt=e.tt-(*it).fi+po[e.id].se; que.push(ev(ii,nt)); if(dir[ii]==d) break; } }else if(d==3){ for(auto it=sx[yy].upper_bound(mp(po[e.id].fi,-1));it!=sx[yy].end();++it){ int ii=(*it).se; ll nt=e.tt+(*it).fi-po[e.id].fi; que.push(ev(ii,nt)); if(dir[ii]==d) break; } }else{ for(auto it=sx[yy].lower_bound(mp(po[e.id].fi,-1));;){ if(it==sx[yy].begin()) break; --it; int ii=(*it).se; ll nt=e.tt-(*it).fi+po[e.id].fi; que.push(ev(ii,nt)); if(dir[ii]==d) break; } } } rep(i,n){ ll px=po[i].fi,py=po[i].se; if(st[i]<=t){ px+=(t-st[i])*dx[dir[i]]; py+=(t-st[i])*dy[dir[i]]; } printf("%lld %lld\n", px, py); } return 0; }
Pokemon Advent Calendar 2014 11日目
この記事はPokemon Advent Calendar 2014 - Adventarの11日目の記事として書かれたものです。
最近はポケモンから遠ざかっていましたが、主催者のkagamizさんが辛そうだったので書くことになりました。ご確認ください。
エンジョイ勢なので育成論とかは置いておいて(まあ多少はやってたんですがそういうのはガチ勢の方にお願いすることにして)思い出を軽く語ろうと思います。当初はn文字(n<=10)の記事になる予定でしたが先に釘をさされてしまいました(╹◡╹)
直近のポケモンのソフトと言えばオメガルビー/アルファサファイアです(自分は今年受験生なのもあって(まあ主な理由は金欠なのですが)買えていません)
このソフトは2002年11月21日に発売されたゲームボーイアドバンス版のルビー/サファイアのリメイクです。
え....
2002年??????????
現在18歳なので.......(察し)
実は自分が初めてやったポケモン、更には初めてやったゲームがサファイアでした。 なのでこのリメイクはかなり気になっていました。
初めに選んだ御三家はミズゴロウだったかな。可愛さ重視。
因みにそれ以前のゲームボーイ系とかは触ったことがないです。
こういうポケモンを集めたり育てたりといったゲームが自分に合っていたらしくハマって、馬鹿みたいに長時間やっていたら親に怒られてエアコンの上に隠されたりした記憶があります。当時は努力値とかそういったパラメータの存在は全く知らず純粋に好きなポケモンを育てたりして楽しんでしました。小学校とかでもやっている人が多くて盛り上がった記憶。速く殿堂入りする遊びとかもあった気がする。
それ以後のポケモンはX,Yまでは結構プレーして来ましたが(コロシアムとかダンジョン系とかレンジャーとかも)、1番プレーしたのは多分ダイヤモンドとかかな？(忘れた) まあその辺に極大値がありそう。ボックスがたくさん同じポケモンで埋まったりしてました。個人的にコロシアムとか結構楽しかったような。
中高に入ってからは結構他のゲームに流れてしまいました...がたまにポケセンとかに行くと相変わらずぬいぐるみに惹かれてしまいます。
文章力が足りないのでぬいぐるみ情報をお送りします。
最後に...
ポケモンで悶々
一般に受験生は辛いぞい。
AOJ2439 Hakone
箱根駅伝。問題概要は略。
解法が面白かったのでメモ
dp[i][j] : 現在i位まで見てj個unmatchedな場合の数
として、
i番目が-ならそのまま,
Dならi番目をそれまでの空いているところに入れるのでj通り,
またi番目にそれまでのを入れる.... dp[i+1][j-1] += dp[i][j] * j * j
スルー.... dp[i+1][j] += dp[i][j] * j
Uなら
i番目にそれまでのを入れる... dp[i+1][j] += dp[i][j] * j
スルー... dp[i+1][j+1] += dp[i][j]
として更新するとO(n^2)で解ける
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i = 0; i < (int)n; ++i) const int MOD = 1000000007; int n; int dp[210][210]; inline void md(int &x, int y){ x += y; if(x >= MOD) x -= MOD; } int main(){ dp[0][0] = 1; scanf("%d", &n); rep(i, n){ char c[3]; scanf("%s", c); if(c[0] == '-') for(int j = 0; j <= i + 1; ++j) dp[i+1][j] = dp[i][j]; else if(c[0] == 'D'){ for(int j = 1; j <= i + 1; ++j){ md(dp[i+1][j-1], (ll)dp[i][j] * j * j % MOD); md(dp[i+1][j], (ll)dp[i][j] * j % MOD); } }else{ for(int j = 0; j <= i; ++j){ md(dp[i+1][j], (ll)dp[i][j] * j % MOD); md(dp[i+1][j+1], dp[i][j]); } } } printf("%d\n", dp[n][0]); return 0; }
Codeforces #157 Div1 E Little Elephant and Tree
segment treeを使って頑張ると解ける(dfsしながらやると上手く行く系)
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; #define pb push_back #define mp make_pair #define fi first #define se second #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) struct segtree{ int *lazy, *mi, *cnt; int sz; segtree(int n){ for(sz = 1; sz < n; sz *= 2); lazy = new int[sz * 2 - 1]; mi = new int[sz * 2 - 1]; cnt = new int[sz * 2 - 1]; } void init(){ init(0, 0, sz); } void add(int a, int b, int x){ add(a, b, x, 0, 0, sz); } pii query(int a, int b){ return query(a, b, 0, 0, sz); } void init(int k, int l, int r){ lazy[k] = mi[k] = 0; cnt[k] = r - l; if(k < sz - 1){ init(k * 2 + 1, l, (l + r) / 2); init(k * 2 + 2, (l + r) / 2, r); } } inline void spread(int k){ if(lazy[k] == 0) return ; mi[k] += lazy[k]; if(k < sz - 1){ lazy[k * 2 + 1] += lazy[k]; lazy[k * 2 + 2] += lazy[k]; } lazy[k] = 0; } inline void upd(int k){ cnt[k] = 0; mi[k] = min(mi[k * 2 + 1], mi[k * 2 + 2]); if(mi[k * 2 + 1] == mi[k]) cnt[k] += cnt[k * 2 + 1]; if(mi[k * 2 + 2] == mi[k]) cnt[k] += cnt[k * 2 + 2]; } void add(int a, int b, int x, int k, int l, int r){ spread(k); if(r <= a || b <= l) return ; if(a <= l && r <= b){ lazy[k] += x; spread(k); return ; } add(a, b, x, k * 2 + 1, l, (l + r) / 2); add(a, b, x, k * 2 + 2, (l + r) / 2, r); upd(k); } pii query(int a, int b, int k, int l, int r){ spread(k); if(r <= a || b <= l) return mp(0, INT_MAX); if(a <= l && r <= b) return mp(cnt[k], mi[k]); pii lc = query(a, b, k * 2 + 1, l, (l + r) / 2); pii rc = query(a, b, k * 2 + 2, (l + r) / 2, r); pii ret = mp(0, INT_MAX); if(lc.se <= rc.se) ret = lc; if(rc.se <= lc.se){ ret.se = rc.se; ret.fi += rc.fi; } return ret; } }; int n, m; segtree *t; vector<int> g[100010]; vector<int> op[100010]; int in[100010], out[100010]; int ans[100010]; int now; inline void tour(int v, int p){ in[v] = now++; for(int &to : g[v]) if(to != p) tour(to, v); out[v] = now; } void calc(int v, int p){ bool f = false; for(int &x : op[v]){ t->add(in[x], out[x], 1); if(!f){ f = true; t->add(in[v], out[v], 1); } } pii ret = t->query(0, n); if(ret.se > 0) ans[v] = n; else ans[v] = n - ret.fi; if(ans[v]) --ans[v]; for(int &to : g[v]) if(to != p) calc(to, v); for(int &x : op[v]) t->add(in[x], out[x], -1); if(f) t->add(in[v], out[v], -1); } int main(){ scanf("%d %d", &n, &m); rep(i, n - 1){ int a, b; scanf("%d %d", &a, &b); --a; --b; g[a].pb(b); g[b].pb(a); } rep(i, m){ int a, b; scanf("%d %d", &a, &b); --a; --b; op[a].pb(b); op[b].pb(a); } tour(0, -1); t = new segtree(n); t->init(); calc(0, -1); rep(i, n) printf("%d%c", ans[i], i == n - 1 ? '\n' : ' '); return 0; }
gcc4.9 インストール(OS X Yosemite)
珍しくパソコン系かつ問題系でない話題。(メモ)
#include<bits/stdc++.h> は前準備禁止なIOIとかICPCで特に役に立つ気がする（あとはテンプレート使わないで毎回0から書いてる人）
— hogloid (@hogloid) 2014, 11月 12を見てbits/stdc++.hの存在に気付く
昔なにかをした時homebrewやらmac portやらを入れていたので楽勝だと思ったら意外と手こずった
まずhomebrewを用いてgccをインストールを試みたが、意味不明なエラー(検索しても出てこなかった)のせいで時間を溶かしてしまった
某potetisenseiからmac portでやってみたらと言われやると、1回目は失敗したが2回目は特にエラーも出ずスムーズにインストール出来ました。
(参考にしたページ :
mac port で gcc4.8を入れたった - Bye Bye Moore
テンプレートが短くなって嬉しみ
Codeforces #189 Div1. C Kalila and Dimna in the Logging Industry
Convex-Hull Trickを蟻本の形のまま使える問題があったのでメモ。
b[n-1] = 0に気付けると、
dp[0] = 0,
dp[i] = min[j=0, i - 1] (dp[j] + b[j] * a[i]) (i >= 1)
とすればO(N^2)で計算出来ることがわかる。
y = b[j] * x + dp[j]のa[i]での値であって、b[j] : 単調減少, a[i] : 単調増加より蟻本のまま適用できる。
直線の上下判定に超苦戦(long longをあふれるのに気付かなかった。)
#include <algorithm> #include <cstdio> using namespace std; typedef long long ll; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) FOR(i,0,n) int n; ll a[100010], b[100010]; ll dp[100010]; int deq[100010]; int s, t; ll f(int j, int pos){ return b[j] * a[pos] + dp[j]; } bool ng(int t1, int t2, int t3){ double a1 = b[t1], b1 = dp[t1]; double a2 = b[t2], b2 = dp[t2]; double a3 = b[t3], b3 = dp[t3]; return (a2 - a1) * (b3 - b2) >= (b2 - b1) * (a3 - a2); } int main(){ scanf("%d", &n); rep(i, n) scanf("%I64d", &a[i]); rep(i, n) scanf("%I64d", &b[i]); for(int i = 1; i < n; ++i){ while(s + 1 < t && ng(deq[t - 2], deq[t - 1], i - 1)) --t; deq[t++] = i - 1; while(s + 1 < t && f(deq[s], i) >= f(deq[s + 1], i)) ++s; dp[i] = f(deq[s], i); } printf("%I64d\n", dp[n-1]); return 0; }
