ドワンゴからの挑戦状 第三回 本戦
コンテストはひどい結果になりました。
懇親会ではなんとミスケンさんが来ていて、ぷよ通で対戦しました。めっちゃ貴重な体験ができて楽しかったです。(はじめ操作が難しかった)
ありがとうございました(dwango作のC問題も割ときれいな問題だったので良かったです) 運営の方々ありがとうございました。
コンテストについて:
今回に関しては反省点は一個だけで、Bでlogを落とす発想が遅れたのはまあ僕が悪いんですけど、それでもこんな問題を作るほうが悪いです(発想自体は面白いんだけど、こんなmoの定数倍もついたようなしかもありうる素因数の個数(6ですよ?)) 倍を改善させたものを区別するのなんて不可能に決まっていて、実際何も考えずにmoをしただけで通ってる人もいて、一方想定解のintを一要素のvectorをなめるふうにしただけでTLEする、マジでなんでこんな設定にしたのか理解不能.
D:
tenka1-2016-qualb.contest.atcoder.jp
典型
A:典型区間DP
C:円の中にあるかどうかになるから,円の内部の点から三方向ににぶたんして境界を3つ見つければ外心が得られる.円の内部の点ははじめに長さ10^5の正方形(をふくむ半径10^5の円)で埋め尽くせば絶対100回で得られる.(ほんとはsqrt(2)倍くらいとれるから8^2=64でとれる)
B:mo+定数倍 sqrtまでの小さい素因数に関しては全て累積和を持っておくことでmoでのmerge次に見る値を1つにすることができる
__int128
は僕の環境だと使えないんですけど、(gccのバージョンではなくハードの問題なんですかね)AtCoderでは使えます(使う問題なんてほぼ出ないだろうけど). Ideoneだと使えないです.
演算はだいたい大丈夫だけどcin,coutは自分で書きましょう.
気づいたんですが負数と0に対応してなかった.ごめん.
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef __int128 ll; istream& operator>>(istream& i, ll& x){ x=0; string s; i>>s; int N=s.size(),it=0; if(s[0]=='-') it++; for(;it<N;it++) x=(x*10+s[it]-'0'); if(s[0]=='-') x=-x; return i; } ostream& operator<<(ostream& o, const ll& x){ ll tmp=x; if(tmp==0) return o<<0; if(tmp<0) o<<'-',tmp=-tmp; vector<int> ds; while(tmp) ds.pb(tmp%10),tmp/=10; reverse(all(ds)); for(int d:ds) o<<d; return o; } int main(){ while(true){ ll x; cin>>x; if(x==114514) break; cout<<x+1<<endl; } }
JOI春
問題一覧 - 情報オリンピック 問題と解説
2012年 日本情報オリンピック春合宿OJ - 2012年 日本情報オリンピック春合宿OJ | AtCoder
2013年 日本情報オリンピック春合宿 1日目 - 2013年 日本情報オリンピック春合宿 1日目 | AtCoder
2014年 日本情報オリンピック春合宿 オンラインジャッジ - 2014年 日本情報オリンピック春合宿 オンラインジャッジ | AtCoder
(2013だけURLが違う)
やります
2012
building2
データ構造をマージする一般的なテク.今となっては典型.マージテクで参照してる場所 をちゃんと持たないとバグります.
fish
まず2倍がどうこう、というのを見てmaximalな区間たちに落とす、次に高次元なので時間軸として一次元処理する、のこりの二次元の面積を求められればいいので、これは階段状の点を持って処理する. P(inf,0)とP(0,inf)を始めに入れとくと楽.
joi_flag
動的segtreeみたいに、非自明な計算が必要なとこだけ計算する.
broadcasting
output only 知らない. こういうのは各outputをvisualizeしてから考えるといいらしい.Kruskalとか,中心集合を適当に取る→貪欲→それらの中心を取る を繰り返すとかかなあ.
constellation
まず適当な例を考えると、どう考えてもDPの状態として持ちようがないつなぎ方をするしかないような例が作れて、まあだから実は簡単な条件で書けるんだろうという察しがつく. 凸包上でoxoxみたいになってたらアウトだなあ→それ以外ならできそう
rotate
とりあえず一次元でreverseだと面倒なクエリごとにlogNの平衡二分木があるけど、そんな感じのが想定解だったらΩ\ζ°)チーンなので,各クエリでO(N^2)よりましなものを考える.縦横がどれにつながってるかだけなら境界のO(N)だけ変えればいいので出来そうという気持ちになる.実際どこにいるかを取得するのが難しい気がしたのでまずはじめに考えたのがクエリ平方分割で、各クエリブロックごとに、「いまXにいるのは誰ですか?をクエリの逆演算をして求める」というのをやった、これをするとO(NQsqrt(N))とかになるんですけど定数倍がかなり重いのでTLEした. 冷静に考えると、つながり方はcyclicな向きを保って持てるので、端っこから調べるとO(N)で境界を見つけられる.全体でO(NQ).
TLEだったけどクエリ平方分割をあまり実装したことがないので練習になった(結局「答えを求める」をB回やって、各ブロックではクエリiにクエリj(<i)が影響を及ぼす というのを全ペアに対して考慮してもO(sqrt(Q)^2)で大丈夫、というのが重要.いやそれはそう.
プログラミングコンテストでのデータ構造 2 ~平衡二分探索木編~に書いてあるように、もとからreverseしたものを複製しておいてswap(つなぎかえる) というのが便利.
fortune_telling
典型遅延評価segtree
kangaroo
数え上げ,簡単だけど面白い(575)
集合から候補を選んで取っていく形で、集合が単調に出来る場合(この例だと,Cand_i = {j|Aj < Bi})はその集合が小さい順に考えると個数しか持たなくていい、っていう一般的なテク.
今回は、操作ができるまで繰り返す という条件を考えると、「最後にbに何も入れなかった時の残り」が何個今残ってるか というのを持てばいいことがわかる. 区間として考えたほうが良かったかもしれない.
sokoban
面倒 of 面倒 二重辺連結成分だとわかりやすく木に分解できるが、二重頂点でも同様のことが出来る.
chinese
自明 実はsetだけでいける
copypaste
invitation
ICPCつくば2016
が10/15,16にあったんですが、参加記を書いていなかったので書きます。
今年もsleep 18000 (sigma,wafrelka,wo) で参加していました
10/14
消費期限切れの牛乳を持ってないことを確認する
10/15
早起きしたけどライブラリ印刷したりしてたらギリギリの時間になって、今年も到着が遅れてしまった、けど今年はチームメイトが外で待たされていなかったのでよかった。
パーティーには色んな人が来ていて懐かしかった(特にI社の人とか)
ARCのwriterをやっていたのでめっちゃ参加を呼びかけたけど結構みんな風呂に入っていて悲C(僕も入ったけど).結構重いセットだったようで全完は少なかった.良問を作るのは難しいね.流石に寝る.
10/16
眠かったがなんとか起きて会場に行く.コンテスト開始まではうろちょろしていた.
コンテスト
つくばは基本難易度順なので,3人の強さの近いsleepは前半から3人がバラバラに解いていく.
A(sigma) やるだけ→WA→は? (この時結構大きい声を出してしまったらしく中心から角まで聞こえたっぽくて申し訳ない(あとでsugimさんに言われた))→AC(ごめん)
B(wo) やるだけ→AC
C(waf) 面倒やるだけ→AC
D(wo) vectorもつとやばいけどhashでいいかなあという話をしてええんちゃうみたいなことを僕が言ったら普通にTLEしそうだったのでもうちょっといい方針を考えることに
E(sigma) やることはすぐわかったのである程度詰めた後Gを読み始める
F(waf) むずいね みたいなことを言っていて,Hを読み始める
G(sigma) どう考えてもEより簡単なのでこっちをやり始める→AC
D(wo) woがいい感じの方針を考えていたっぽく書いてAC
H(waf) どのタイミングか忘れたけど書いていてTLE 冷静に考えてウニで死ぬことに気づいていた
E(sigma) 書き始める→鬱病→AC (1h以上かかっている・・・?(途中Hとか書いていたかも))
ここらへんで後半をだいたい読むと、H:これ全方位木DPでは? I:なんか適当に削れば良さそう J:hoge K:無理そう となっていたが、まだFが残っているので必死に考える
F(wo) TLEしそうな解法を思いつく→TLE
I(sigma) 嘘を書く→WA
H(waf) バグらせる→WA
F(wo) 64で割ったら?と言ったら割っていた、何度かバグらせたがギリギリAC.
コンテスト終了
悲しいね
10/16 つづき
悲しみに明け暮れていた.114514とは3完差だったし、いくらなんでも実力が足りなさすぎるなあ・・・
それはそうとパーティーはいろんな会社がブースを置いていて面白かった.Preferred Networksでiwiさんから話を聞いた,かなり面白そうだった.Indeedの出していた対戦ゲームが普通にSRMとかに出ててもおかしくないくらい良問でおもしろかった.あと5位はいろんな賞にあたっていたらしく色々もらった.
ダベってから帰る.
帰ってからAOJでやったらIのジャッジがなかった
11/17
参加記を書いたのでICPCつくば終了です.(日付が連続しているように見えるがこれは罠で、遅れてごめんなさい)
まとめ
JAGやボランティアやスポンサーの方々ありがとうございました、負けて残念でしたが今年も楽しかったです.
精進したいけどCPU実験が・・・
AGC006
死んだ。
まためっちゃ面白いセットだった。sugim48すごすぎ。
A:流石にやるだけ
B:いきなり難しいconstructive. 実験したらrotate(ans+x-2,ans+x,ans+N) が見つかったのでこれを出力した。D考えてるときに真ん中でa<b<cってなってるなら絶対bが残ることに気づいたのでわざわざこんなことしなくてもよい.
C:期待値なのでそのまま計算していいことには気づいたのに、差分取るのに気づけなかった・・・ Air Pollution という問題がAOJにあるんですけど、それと同じ発想。なんで気づけなかったかなあ・・・
D:全く何もわからなかったんですが、にぶたんと言われたら解ける。こういうのなくしたいなあ(あまりにぶたんして嬉しい形に見えなかったけど、中央値→x以下が2個 みたいな言い換えを考えるとbool値にすると嬉しいことがわかる)
E:二個離れたところのswap+その二個と間の一個が逆向きになる という操作なんだけど、二つの列の転倒数のparityを見ればOKだった.まあなんかflipの場所を変えるのは出来そうだったので多分そうだろうと思ったけどそうなのか。
F:まだなんもわかってない
Cはともかく、D解けないのはダメなので気をつけないと
FunctionalEquation (SRM456hard)
おもしろかった.
問題:整数1≤C≤16 と, x[i],y[i]が与えられる.
f:Z->Zで,f(2f(x)-x+1)=f(x)+C を満たすという条件のもとでsigma |f(x[i])-y[i]| を最小化せよ.
x,yの長さは<=10000.値は10^9.
まずxに2f(x)-x+1を再代入しするとf(x+2C)=f(x)+2Cが得られる.
逆に,
f(x+2C)=f(x)+2C for any x かつ
f(2f(x)-x+1)=f(x)+C for any x in [0,2C)
が成り立てば元の式も成り立つことがわかるので,これを満たすようなものを考える.
f(0)~f(2C-1)を決めれば自動的にすべての値が決まる.
あるf(x)を決めると,xを代入してf(2f(x)-x+1)の値も決まる.そこから更に何か決まるかというと,できることがxに2f(x)-x+1を代入するしかないが,これはさっきやったf(x+2C)=f(x)+2Cになるのでやる意味がない.
冷静に考えると,xと2f(x)-x+1は(mod 2Cで)偶奇が異なるので, 偶数xに対して,f(x)=a と決めると,元の式から,y=2a-x+1として,f(y)=a+Cが決まる.それ以外(mod 2Cで)は決まらない.
偶数xがどの奇数yとペアを組むかはa mod Cに依存することがわかるので,これを固定する.この時,f(x)=aのとき,f(y)=b(=a+C)とすると,f(x)=a+?Cのときはf(y)=b-?Cになることがわかる,?には任意の整数が入れられる.この時関連する部分(つまりx[i]%2Cがxかy)での値を最小化するには,だいたい中央値っぽいところを?Cとして取れば良いので簡単に計算できる.
さいごにbitDPしておわり.
modが16*2で32になって焦るが,xと2f(x)-x+1の偶奇が違う, というところに気づくのが難しかった.
これ非数オリ勢だとはじめのFEパートどのくらいで気づくんだろう
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; bool B(int x,int y){return (x>>y)&1;} typedef long long ll; const int MN=10000; ll inf=1e18; ll xs[MN],ys[MN]; ll cost[16][16]; ll dp[17][1<<16]; class FunctionalEquation{ public: long long minAbsSum(int C, int N, int xzero, int xprod, int xadd, int xmod, int yzero, int yprod, int yadd, int ymod){ xs[0]=xzero,ys[0]=yzero; rep(i,N-1) xs[i+1]=(xs[i]*xprod+xadd)%xmod,ys[i+1]=(ys[i]*yprod+yadd)%ymod; int M=C*2; rep(t,C){ //f(x)=a+?*C,f(y)=b-?*C int x=t*2; rep(a,C){ int yo=2*a-x+1; int y=(yo%M+M)%M; int b=a+C+(y-yo); vector<ll> vc; rep(i,N){ // |?*C - tmp| if(xs[i]%M==x){ ll tmp=ys[i]+x-xs[i]-a; vc.pb(tmp); } if(xs[i]%M==y){ ll tmp=-(ys[i]+y-xs[i]-b); vc.pb(tmp); } } sort(all(vc)); int K=vc.size(); if(K==0){ cost[x/2][y/2]=0; continue; } ll med; if(K%2==0) med=(vc[K/2-1]+vc[K/2])/2; else med=vc[K/2]; ll qo=med/C; ll mn=inf; for(ll q=qo-2;q<=qo+2;q++){ ll sum=0; rep(i,K) sum+=abs(q*C-vc[i]); chmin(mn,sum); } cost[x/2][y/2]=mn; // printf("f(%d)=%d+?C, f(%d)=%d+?C, cost=%lld\n",x,a,y,b,mn); } } // rep(i,C) rep(j,C) printf("cost[%d][%d]=%lld\n",i,j,cost[i][j]); rep(i,C+1) rep(j,1<<C) dp[i][j]=inf; dp[0][0]=0; rep(i,C) rep(b,1<<C) if(dp[i][b]!=inf){ rep(j,C) if(!B(b,j)){ chmin(dp[i+1][b|(1<<j)],dp[i][b]+cost[i][j]); } } return dp[C][(1<<C)-1]; } };
yukicoder No.284 門松と魔法(2)
発想は良問.実装が大変.
問題:数列が与えられる,部分列Bであって,B[i]!=B[i+2] かつ (B[i]<B[i+1]>B[i+2] または B[i]>B[i+1]<B[i+2]) を任意のiに対して満たすようなものの長さの最大値を求めよ.
まずはじめB[i]!=B[i+2]を完全に見落としてたためO(N^2)DPから自然に生えるsegtreeを書いて提出したらWAだったので,問題文を読むと違うことがわかった.
このsegtreeでは最後がbで終わるような列 というのの最大値をsegで持っていたけど,最後から二番目aの情報も持って置かなければいけないことがわかる.でも,条件は,今xを更新しようとしてるとするとx!=a なので,aとしてはでかい方からたかだか2個しか持たなくて良い.
なので,seg[b]に,(mx,a)の組(aは異なる)を2つ持っておけばできる.(mergeはちょっと面倒だけど)
ただ,これを持とうとするとちゃんとqueryの際にどっから最大値が来たか,というのを求めないといけないので,idも持っておく.
しかも更新のためには2番目の最大値も求めなければいけないが,これは冷静に考えるともう一度1番目のとこを除いてクエリを投げれば良い.
実装がしんどかった(2番目がまだないとか,一箇所しか候補がないなら2番目はなしとか,細かい部分が大変).
はじめoperator+でmapを使ってたらTLEしたので,bubble sortにしたら通った.
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";} template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;} struct D{ int segid[2],id[2],mx[2]; //id[i] -> segid[i] -> nxt D(){ segid[0]=segid[1]=-1; id[0]=id[1]=-1; mx[0]=mx[1]=-1; } D(int x){ segid[0]=x; segid[1]=-1; id[0]=-1; id[1]=-1; mx[0]=1; mx[1]=-1; } D(int a,int b,int c,int d,int e,int f){ id[0]=a,segid[0]=b,mx[0]=c,id[1]=d,segid[1]=e,mx[1]=f; } const static D e; /* D operator+(const D& r) const { typedef pair<int,int> P; typedef pair<P,int> PP; map<int,P> mp; rep(i,2) if(mx[i]>=0) chmax(mp[id[i]],P(mx[i],segid[i])); rep(i,2) if(r.mx[i]>=0) chmax(mp[r.id[i]],P(r.mx[i],r.segid[i])); vector<PP> vp; for(auto it:mp) vp.pb(PP(it.sc,it.fs)); sort(all(vp),greater<PP>()); int K=vp.size(); D ret; rep(i,min(2,K)) ret.id[i]=vp[i].sc,ret.mx[i]=vp[i].fs.fs,ret.segid[i]=vp[i].fs.sc; return ret; }*/ D operator+(const D& r) const { int tid[4],tsegid[4],tmx[4],K=0; rep(i,2) if(mx[i]>=0) tid[K]=id[i],tsegid[K]=segid[i],tmx[K]=mx[i],K++; rep(i,2) if(r.mx[i]>=0) tid[K]=r.id[i],tsegid[K]=r.segid[i],tmx[K]=r.mx[i],K++; rep(i,K-1) rep(j,K-1-i) if(tmx[j]<tmx[j+1]) swap(tmx[j],tmx[j+1]),swap(tsegid[j],tsegid[j+1]),swap(tid[j],tid[j+1]); int I=0; D ret; rep(i,K){ bool ok=1; rep(j,i){ if(tid[j]==tid[i]){ ok=0; break; } } if(!ok) continue; ret.id[I]=tid[i],ret.segid[I]=tsegid[i],ret.mx[I]=tmx[i],I++; if(I==2) break; } return ret; } void inc(){ rep(i,2) if(mx[i]>=0) mx[i]++; } friend ostream& operator<<(ostream& o,const D& d){ o<<"d= mx="<<d.mx[0]<<" at ("<<d.id[0]<<","<<d.segid[0]<<")"<<endl; o<<" mx="<<d.mx[1]<<" at ("<<d.id[1]<<","<<d.segid[1]<<")"<<endl; return o; } }; const D D::e = D(); template<class D> struct segtree{ static const int N=1<<17; D e=D::e; vector<D> seg; segtree():seg(N*2,e){} void update(int k,D val){ k+=N; seg[k]=val; k/=2; while(k){ seg[k]=seg[k*2]+seg[k*2+1]; k/=2; } } D calc(int a,int b,int l=0,int r=N,int k=1){ if(b<=a||b<=l||r<=a) return e; if(a<=l&&r<=b) return seg[k]; return calc(a,b,l,(l+r)/2,k*2)+calc(a,b,(l+r)/2,r,k*2+1); } }; segtree<D> up,down; int N; int x[100000]; vector<int> xs; int main(){ cin>>N; rep(i,N){ scanf("%d",x+i); xs.pb(x[i]); } sort(all(xs)); xs.erase(unique(xs.begin(),xs.end()),xs.end()); int K=xs.size(); rep(i,N) x[i]=lower_bound(all(xs),x[i])-xs.begin(); rep(i,N){ // printf("i=%d\n",i); int X=x[i]; D dval,uval; {//go up D dmx=down.calc(0,X); int mx=-2,arg; rep(j,2){ if(dmx.id[j]!=X){ mx=dmx.mx[j]; arg=dmx.segid[j]; break; } } if(mx>=0){ D dmx2 = down.calc(0,arg) + down.calc(arg+1,X); int mx2=-2,arg2; rep(j,2){ if(dmx2.id[j]!=X){ mx2=dmx2.mx[j]; arg2=dmx2.segid[j]; break; } } dval = D(arg,X,mx,arg2,X,mx2); }else{ dval = D(arg,X,mx,-1,-1,-1); } dval.inc(); dval = dval + D(X); } {//go down D umx=up.calc(X+1,K); int mx=-2,arg; rep(j,2){ if(umx.id[j]!=X){ mx=umx.mx[j]; arg=umx.segid[j]; break; } } if(mx>=0){ D umx2 = up.calc(X+1,arg) + up.calc(arg+1,K); int mx2=-2,arg2; rep(j,2){ if(umx2.id[j]!=X){ mx2=umx2.mx[j]; arg2=umx2.segid[j]; break; } } uval = D(arg,X,mx,arg2,X,mx2); }else{ uval = D(arg,X,mx,-1,-1,-1); } uval.inc(); uval = uval + D(X); } // cout<<"dval"<<endl<<dval<<endl; // cout<<"uval"<<endl<<uval<<endl; up.update(X,dval); down.update(X,uval); } int ans=max(up.calc(0,K).mx[0],down.calc(0,K).mx[0]); if(ans<=2) ans=0; cout<<ans<<endl; }