Misere(正しくはMisère) Game とは,(多分)"最後の一個をとったら負け"みたいなゲームの事で,例えばNimに対して Misere Nimというものが考えられる.
Nimの勝利条件がNimber(Grundy number)であることはwell known factだが,Misere Nimの勝利条件を知らなかったのでメモ.(2014年12月放送の頭脳王という番組に番組独自の問題として出てきた,後述)
実はNimとほとんど同じで基本的に相手にxorが0の状態を渡せばいいのだが,最後までそれをやるとこっちが負けるので,最後はちょっと変える.正確には,その状態で次に動かすプレイヤーの敗北条件は,
となる.
prf(の概略).
後半は自明(残り奇数個なら最後取ってしまうので).
前半はNimと一緒で,あとは前半から後半にうまく移行できるかだが,全て1以下の状態でこっちに帰ってくることがないようにすれば良い.
普通のNimっぽくやって自分に1,..,1(2k-1個(k>=1))が来るような手になった時どう改善すればよいか考える.
その直前の相手の状態は,"1が2k個"または"1が2k-2個,xが1個(x>1)"(以下x>1とする)だが,後者はありえない(xorが0にならないので).
よって更にその直前の自分の状態を考えると,
この時はこの段階で対処をすべき(ちゃんというと,帰納法で示される(前半から後半へ移行出来る状態では必ず対処できる段階があるため)).
xを全て取る
よって必敗を相手に回せることがわかった.
それ以外で負けることは,それ以外の状態で以上の状態のどれかに引き渡せることが(Nim同様に)わかるため言える.■
なんでこの記事を書こうと思ったかというと,2014年12月放送の頭脳王という番組で,番組独自のゲームとしてpileが3個のmisere Nimを出場者にやらせていて(vs コンピュータ),まあそれはまだ百歩譲って許せなくはないのだが,しかも数十手先を見通す力とか的はずれなことを言っていたが(石は数十個もない)(まあいつもの煽りだから許される).許されないのは,それぞれの人に初期状態として別の手が渡されていたのだが,
そのうちいくつかは必敗でいくつかは必勝だったという激ヤバな事実があったからです(先手で(3,9,10)が渡された人と(4,5,9)が渡された人がいた).
しかもコンピュータ側の動きを見ると,ちゃんと必勝の手に従っていたので,多分わざとだと思う.(一応コンピュータは探索をしているだけで,必勝かどうかは出題側は知らなかった(独自のゲームとして紹介しているので)と言い張ることは可能だけれど)
必敗の人かわいそうだった.
50点問題で,その時点での点数が150,110,100,60で2位以上勝ち抜けだったので同点を避けたのかなあ.
n(<=1000)回攻撃される.i回目の攻撃で体力がDi減る.始めの体力はHsで体力の最大値はHmax(<=1000).体力が0以下になると死.
回復薬がP(<=12)個ある.それぞれの攻撃の前に好きな個数だけ回復薬を使える.i個目の回復薬を使うと体力がPi回復する(Hmaxを超えるとHmaxになる).使ったらなくなる.最後まで生きれるならYES,無理ならNOをoutputせよ.
dp[i][j]="i回攻撃受けた時点での回復薬使用状況(bit)がjの時の体力のmax"を持てば良さそう.それぞれの状態からどの回復薬のsubsetを使うか、を考えるとO(n*P*3^P)となり死亡.
よく考えると、回復薬aとbを使いたいときはaを使った状態を(その回の更新時に使う)dpに放り込んでおけばok.ということはdp[i]=回復薬状況iのときのmaxHPをトポロジカル順序で(0から回せば良い)更新していけば良いことがわかる.
ポイント:bit状況からsubsetを増やす,みたいな操作があり,subsetの要素の増やす順によって値が変わらないなら,トポロジカル順に増やせば良い.
上から,反省もこめて
Merry Christmas(2251)☆
transitiveDAGの二部マッチングのアレ
Reverse Sort(2443)
半分探索,知らなかったので勉強になった
ちなみに始め単にdfsという解法に固執しまくっていて2443という数字を覚えてしまい、後日(Code Formula?)snukeのeditorの2443.cppという番号を見てこの問題だと気づいた ということがあった
Dangerous Tower(2293)
割り当てはmin_cosst_flowだよなあ?
縦と横を割り当てようとするんじゃなくて積み木と数字を割り当てようとするのが重要(かぶってはいけないのは数字なので)
Malfatti Circles(1301)
なんだっけ・・・三角形にうまく接する3つの円を入れるんだけど、一個目の円としてでかいのを入れると二個目が小さく、三個目が大きくなるのでC1とC3の距離が近すぎるとなるので、二分探索を二重くらいですれば良い.なんか適当な場合を除いてなくてバグりまくった記憶が・・・
10歳の動的計画(2335)
カタラン数的な話を知っていれば解ける.DPじゃない・・・
Three-way Branch(2397)
[0,W)の範囲で右下か左下に行ける,左上から右下へ行く方法は何通り?という問題.行列累乗の合間に適当に行列を掛けるだけ.ちょっとTLEがつらいかもしれない.
ハコの魔女(2313)☆
ちょっとずつフロー変えてく典型.a->bをつける時は残余グラフで流すだけ,a->bを消す時は残余グラフでa->bに流せればそれでok,流せなければa->s,t->bと押し戻しておく.
辺が増えたり消えたりするので,オーダーに問題がなければ隣接行列でedgeを持ちましょう.非常に書きやすい.
箱根駅伝(2439)☆
最近追加された光り輝く天啓DP.問題設定,解法共に素晴らしい.
今見ているものを左にやったり右にやったりしなければいけないような問題では,"ここまで処理したうちでここに来れるのは何個か"と"ここまでで埋めてない奴は何個か"を持てばいい感じになることがある.更新は"こいつをどこに埋めるか,左から来たやつを使うか"みたいなことを考える必要がある.
"ここまでのunmatchedな個数"という考えはSRM592Div1Medの"LittleElephantAndPermutationDiv1"も参照.
Strange Couple(2171)
溢れ出るICPC臭.掃き出し法を書くだけ.連結成分以外をあらかじめ除くと楽.
Testing Circuits(2348)
自明な構文解析とおもいきやまさかのスタックオーバーフロー.自前stackを書きましょうという激ムズ問題.解説スライドによると問題作成者は構文解析後の自明問を解くのが本質だと思っていたようだが全くそんなことはない.悪問と言いたいけどまあ自前構文解析の練習にはなるのでやりたければやって,どうぞ.
舞台装置の魔女(2318)
かんたんなdp.
スプリング・タイル(2336)
e="バネを踏んだ後の期待値"でにぶたん.eが真の値より小さいとして解くとそれによって出てきたe'はeより大きい.として解いたんだけど何でだっけ・・・.
解説スライドを見ると,よく考えるとバネに向かうかゴールに向かうかの差は整数なのでH*W通りくらいしかなく、全部確かめれば良いという解法でも良かったらしい.
Enumeration(2446)☆
包除だとそれぞれのsubsetに対し,subsetの要素のそれぞれが選ばれるか試してΣ(x∈P(a)) |P(x)|=3^|a|かかる(Pは冪集合).
"iビット目まではsubsetになっていて、iビット目以降は一致している"の総和をdpで計算して、i=nの時の値を見ればok.
Sliding Block Puzzle(1329)
探索.他に言うことはない.
ケーキ分割問題(2256)☆
左の値y1を変えていく時,直線がどのイチゴの間を通るか,が変わるのはイチゴやケーキの端たちによる直線と左の線の交点.y1を上記が変わらないように動かしている間は取りうるy2の値の範囲は"線形に"変化することに気づけば,y1として真ん中の値をとって区間幅をかければいいことがわかる.
RabbitWalking(2370)
dpへの帰着後,間に合わないことに気づいて固まる.
和が2nくらいのn個の正整数値があって和として(n以下らへんで)どんな値が取れるかを調べるのは愚直にやればO(n^2)かかるが,正整数値がO(√n)種類くらいしか無い(∵√2n以上は√2n個程度,以下はそもそも√2n種類しかない)ことに気づけば個数制限ナップザックでO(n√n)になる.
IkaNumber(2372)
"入力はイカの形式で与えられる"
フィボナッチ数の積として表せるn番目の値は?Fa*Fbがa+bが大きいほうがでかい(Fa,Fb>=2)とかそんな感じのことに気づけば偶奇で場合分けして終わり.
Driving an Icosahedral Rover(1319)
正二十面体を紙を切って作り,遷移規則を打ちこむだけ.プログラミングではない.
Runaway Domino(2346)
線分にそって動いていくドミノ(の倒壊)を二つ止める問題.倒壊より速く動けるので,できるだけ速く止めれば良いしそれはにぶたんで求まる.
Card(2436)
それぞれの数字がどこに何回足されるか,がわかればよい.その数字以外j個でi桁の数が何通り作れるか,がわかればよい.dpするだけ.0に注意(0を除いた奴の答えを引けば良い).
Ropeway(2229)
この問題の本質はClarを投げることです!!!
問題文に制約が全く書いてないという激ヤバ問題.AOJに入っているのでClarを投げるのは難しい.これが評価されて600点問題になっている.Clarを投げたら(あるいは解説スライドの1ページめを見るなどしたら)あとはやるだけ.
Usoperanto(2456)
自明DP.適当にやるとスタックオーバーフローするので、先にbfsでもして順序を決めておくと良い.これ400点位だと思うなあ.
Symmmetry(2159)
n個の点集合が線対称であるか,+例外処理.線としてはnC2個くらいあって、それぞれで全点確かめるとO(n^3)で通らない.線対称であるときはそういう線はn/2個位ある(重要)ので、線をO(n)回くらい乱択すれば間に合う.皆あまり通してないけど自明枠だと思う.
今のところこの23問.おもしろいのは箱根駅伝で、ためになるのはハコの魔女かなあ.
自前構造体のsetとかにcompareを入れたい時
struct a{ int x; bool operator <(const a& st) const { return x<st.x; } };
//setの定義には(かなり変なことをしないと)入れられない bool comp(const a& l,const a& r){ return l.x<r.x; }
//関数型 struct Comp { bool operator()(const a& l,const a& r) const { return l.x<r.x; } };
1つ目を使う
不参加
A:やるだけ
B:過去のある範囲maxのDP→segtree
C:{0,-1,+2,-3}(mod 4)とかで部分和で全種類出てくる
C気づかないのが幼稚園児
A.cpp
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl int main(){ int myh,mya,myd,eh,ea,ed,uph,upa,upd; cin>>myh>>mya>>myd>>eh>>ea>>ed>>uph>>upa>>upd; int ans=1e9; rep(i,300){ int a=mya+i; if(a<=ed) continue; int t=(eh+a-ed-1)/(a-ed); rep(j,300){ int money=i*upa+j*upd; int d=myd+j; if(d>=ea){ ans=min(ans,money); break; } int dam=ea-d; int needhp=t*dam+1; if(needhp<=myh){ ans=min(ans,money); }else{ ans=min(ans,money+(needhp-myh)*uph); } } } cout<<ans<<endl; }
B.cpp
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl const int p2=1<<17; int n,s,l,a[100000],r[100000],seg[p2*2]; multiset<int> msi; void update(int x){ while(true){ x=(x-1)/2; seg[x]=min(seg[x*2+1],seg[x*2+2]); if(x==0) break; } } int inf=1e8; int segmin(int a,int b,int l,int r,int k){ if(a>=b) return inf; if(b<=l||r<=a) return inf; if(a<=l&&r<=b) return seg[k]; return min(segmin(a,b,l,(l+r)/2,k*2+1),segmin(a,b,(l+r)/2,r,k*2+2)); } int main(){ cin>>n>>s>>l; rep(i,n) cin>>a[n-1-i]; int it=0; bool ok=false; rep(i,n){ int mn=0,mx=0; if(!msi.empty()) mn=*(msi.begin()),mx=*(msi.rbegin()); while(mx-mn<=s){ if(it==n){ ok=true; break; } msi.insert(a[it]); mn=*msi.begin(),mx=*(msi.rbegin()); it++; } r[i]=it-2; if(ok) r[i]=n-1; msi.erase(msi.lower_bound(a[i])); } reverse(r,r+n); rep(i,n) r[i]=n-1-r[i]; // rep(i,n) show(r[i]); rep(i,p2*2-1) seg[i]=inf; seg[p2-1]=0; update(p2-1); rep1(i,n){ seg[p2-1+i]=1+segmin(r[i-1],i-l+1,0,p2,0); update(p2-1+i); } int ans=seg[p2-1+n]; if(ans>=inf) ans=-1; cout<<ans<<endl; }
C.cpp
#include <iostream> #include <cstdio> #include <vector> #include <set> #include <map> #include <queue> #include <deque> #include <stack> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() #define fs first #define sc second #define pb push_back #define show(x) cout << #x << " " << x << endl typedef long long ll; const int ccc=100000; bool prime[ccc+1]; vector<int> pr; void makeprime(){ int i,j; for(i=2;i<=ccc;i++) prime[i]=true; for(i=2;i*i<=ccc;i++) if(prime[i]) for(j=2;j*i<=ccc;j++) prime[j*i]=false; for(i=2;i<=ccc;i++) if(prime[i]) pr.push_back(i); } int p[ccc+1]; int main(){ makeprime(); int n; cin>>n; if(n==1){ puts("YES"); puts("1"); return 0; } if(n==4){ puts("YES"); printf("1\n3\n2\n4\n"); return 0; } if(!prime[n]){ puts("NO"); return 0; } int g=2; for(;;g++){ ll now=1; bool can=true; rep(i,n/2){ now*=g; now%=n; if(now==1){ can=false; break; } } if(!can) continue; p[0]=1; rep(i,n) p[i+1]=p[i]*g%n; puts("YES"); rep(i,n-1){ if(i%2==0) cout<<p[i]<<" "; else cout<<p[n-1-i]<<" "; } cout<<n<<endl; return 0; } }
別解を友人に教えてもらった
1.逆からunionfind
2.Euler tour + BIT + doubling
については
http://sigma425.hatenablog.com/entry/2014/08/05/232421の通り.
3.(new)
Euler tour + segtree
それぞれのノードは"marked ancestorの候補"を持っている.
更新クエリ:in[v]~out[v]を覆うようなブロック達について,(まだ書き込まれていないor今書こうとしている値が既に書き込まれた値の子孫である)なら書き込む.
解答クエリ:in[v]のノードから上に0まで見ていって,最も子孫側を答える.
anc(x,y):xがyのancestor は in[x]<in[y]&&out[y]>out[x] とかける
コード見たほうがわかりやすそう.
正当性:
まず,in[v]の上にvの先祖以外が書き込まれてないことが,vを含む区間がin[x]~out[x]と表せるならxがvの先祖であることからわかる.
また,書き込まれた値は必ずin[v]の上のどこかにあり,そのうち直近のものは必ず残っている(rewriteされてない)ことがわかる.
#include <iostream> #include <vector> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) vector<int> G[100000],euler; const int p2=262144; int in[100000],out[100000],n,q; int seg[p2*2-1]; void dfs(int v){ in[v]=euler.size(); euler.push_back(v); rep(i,G[v].size()) dfs(G[v][i]); out[v]=euler.size(); euler.push_back(v); } bool anc(int x,int y){ return in[x]<in[y]&&out[x]>out[y]; } void change(int a,int b,int c,int l,int r,int k){ if(b<=l||r<=a) return; if(a<=l&&r<=b){ if(seg[k]==-1||anc(seg[k],c) ) seg[k]=c; return; } change(a,b,c,l,(l+r)/2,k*2+1); change(a,b,c,(l+r)/2,r,k*2+2); } int main(){ while(true){ cin >> n >> q; if(n==0) break; euler.clear(); rep(i,n) G[i].clear(); rep(i,p2*2-1) seg[i]=-1; rep(i,n-1){ int p; cin >> p; G[p-1].push_back(i+1); } dfs(0); long long ans=0; change(in[0],out[0]+1,0,0,p2,0); rep(i,q){ char c; int v; cin >> c >> v; v--; if(c=='M'){ change(in[v],out[v]+1,v,0,p2,0); }else{ int x=p2-1+in[v],ret=0; while(true){ if(seg[x]!=-1 && anc(ret,seg[x])) ret=seg[x]; if(x==0) break; x=(x-1)/2; } ans+=(ret+1); } } cout << ans << endl; } }