| 
文字列Sと、隣り合ってはいけない２つの文字(Ai,Bi)が何セットか与えられる。各Ai,Biで同じ文字は１回しか出てこない。
Sから最低何文字消せばいいか。
禁止文字が高々１回なので、ある (Ai,Bi) に関する制約を満たす操作をした後に新たに別の制約が破られるようにはならない。
たとえば (a,b)が禁止という条件で (ab以外) aかbの並び (ab以外) を処理する場合、(?,a), (?,b)という禁止セットはないことがわかっているので、
aかbの並びからどういう消し方をしても (ab以外)とaまたはbが隣接することになるので、この部分に関してはほかの条件を満たしている。
ということで連鎖しないことがわかったので、禁止文字セットは１回ずつ処理するだけでいい。
(ab以外) aかbの並び (ab以外) を処理するには、aかbの並びを全てaかbにするしかないので、aとbで文字数の少ない方を消せばいい。（実際には消さないで数えるだけでOK）
というわけで O(Sの長さ*制約の数) で処理できる。
int main() { string s; cin>>s; int N; cin>>N; int ans=0; REP(i, N) { string ng; cin>>ng; char a=ng[0]; char b=ng[1]; REP(i, s.size()) { int ca=0, cb=0; for(;i<s.size();i++) { if(s[i]!=a && s[i]!=b) break; ca+=s[i]==a; cb+=s[i]==b; } ans += min(ca, cb); } } cout<<ans<<endl; return 0; }
| 
1〜N(in [1, 10**5]) を ON か OFF にする依頼が最大 10**5 個来るので、ON になっている全ての数字が互いに素（最大公約数が１）になるように依頼を処理する問題。
すでにONまたはOFFになってたら Already on/off, ONにできないときは Conflict with ?(これがONだからONにできないという数字), 処理した場合は Success と出す。
普通にやると O(N**2) になってだめなので、ON になってる約数を map なり vector なりで管理する。Nの約数の数は(ループがsqrtN回なので) N**0.5 のオーダーなので O(N**1.5) になる。
（約数としたけどほんとは素因数で書くべきだったか。）
「約数 1 は ON になっていても conflict にしない」という処理の一部が抜けてて40分ほどずっと pretest wrong answer の原因がわからず、TLEを疑って cinをscanfに変えたりしながら７回ほど submit したが結局最後まで気づかなかった。。
（そういえばpretestでもかかった時間とメモリ量はわかるのだから、TLEじゃないことはわかったのか）
惜しくないよりはマシだけど、なんか詰めが甘い。
↓ Accepted on practice
int main() { int N,M; cin>>N>>M; //map<int, int> pst; vector<int> pst(N+1); vector<char> st(N); //scanf("\n"); REP(i, M) { char si; int k=0; //scanf("%c", &si); //scanf("%d", &k); //scanf("\n"); cin>>si>>k; //cout<<"------ "<<si<<" "<<k<<endl; if(si=='-') { if(st[k-1]==0) { cout<<"Already off"<<endl; } else { for(int v=1;v*v<=k;v++) { if(k%v==0) { pst[v]=0; pst[k/v]=0; } } cout<<"Success"<<endl; st[k-1]=0; } } else { if(st[k-1]==1) { cout<<"Already on"<<endl; } else { int ok=1; for(int v=1;v*v<=k;v++) { if(k%v==0) { if((v!=1 && pst[v]) || (k/v!=1 && pst[k/v])) { ok=0; //cout<<"Conflict with "<<pst[v]?pst[v]:pst[k/v])<<endl; // NG cout<<"Conflict with "<<((v!=1 && pst[v])?pst[v]:pst[k/v])<<endl; // OK break; } } } if(ok) { for(int v=1;v*v<=k;v++) { if(k%v==0) { pst[v]=k; pst[k/v]=k; } } cout<<"Success"<<endl; st[k-1]=1; } } } } return 0; }
| 
Nvodskは寒いので、直前に書いた整数の自明でない約数を１つ紙に書いてその回数だけホテルの周りを走るゲームをするｗ
（ロシア企業(?)運営のサイトらしくていい）
約数を書けなくなった方が勝ち。最初に q ( <= 10**13) が書いてあって二人が最適なゲームをする場合、どっちが勝つか、最初(1)が勝つなら初手も出力する。
n が Win number か Lose number か計算する関数 f を書いた。
をメモ化再帰で。そしたら TLE になった。
（後ほど）
１つでも Lose があったら f(n)==Win に決定するのでそこで抜けて良いのに抜けてなかった。そこを抜けるようにしたら accepted.
しかし正解者のコードを見てるとみなさん再帰させてない。
この問題の場合はもっと簡単なロジックで答えがでるらしい。今のところ理解できず。
あと、こういう約数とか素数とかからむとオーダーがよくわからなくなる。
メモ化のキーの範囲は long long だけどうまく重複するので大丈夫とか、そのへん。
map<ll, int> memo; ll move=0; int f(ll n) { if(memo.count(n)) return memo[n]; int allW=1; int win = 1; for(ll i=2;i*i<=n;i++) { if(n % i == 0) { int r0=f(i); int r1=f(n/i); allW &= r0; allW &= r1; if(!r0) move=i; if(!r1) move=n/i; win=0; if(!r0||!r1) return memo[n] = 1; //// ここ入れたら accepted } } int ret = win ? win : (allW ? 0 : 1); //cout<<n<<" "<<ret<<endl; return memo[n] = ret; } int main() { ll q; cin>>q; int r = f(q); cout<<(r?1:2)<<endl; if(r) cout<<move<<endl; return 0; }
| 
長さ N で M 種類の文字を使った文字列のうち、どの長さ K の部分文字列も回文になっているようなものの個数を出す。
1 <= N,M,K <= 2000
N 頂点のグラフを考えて、同じでないといけない頂点を辺で結ぶ。それで、M の「連結な部分の数」乗が答え。
こういうグラフに帰着させるようなのは１年前はできなかった気がする。よかよか。
struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; int main() { int n, m, k; cin>>n>>m>>k; //if(n<k) { // cout<<0<<endl; // return 0; //} UnionFind uf(n); REP(i, n-k+1) { REP(j, k/2) { uf.unionSet(i+j, i+k-1-j); } } map<int, int> mm; REP(i, n) { mm[uf.root(i)]=1; } ll ans=1; REP(i, mm.size()) { ans *= m; ans = ans % 1000000007LL; } cout<<ans<<endl; return 0; }
| 
N 曲から P 曲のプレイリストを作る。何種類作れるか。ただし N 曲すべて１回は使うこと。かつ、同じ曲を使う場合は間に M 曲以上おかないといけない。
N==P なら N! 通りである。ふむ。
最近の M 回はどれも違う曲だから、その次の曲は N-M 通りだな。ふむ。
じゃあ N! * (N-M)**(P-N) だと思って書いてみたけど、これだと最初の N 回で N 曲使うパターンしか見てないな。だめだ。
DP ぽいけど漸化式が思いつかん。
で、ちょっと考えて hard に行って戻ってきてやっぱりできず。
editorial などによると、dp[プレイリストの曲数][使った曲の種類数] == 可能なプレイリストの数 というきれいな式になるらしい。
dp[i][j] = dp[i-1][j-1] * (N-(j-1)) // 使ってない曲は N-(j-1) 種類 + dp[i-1][j] * max(j-M, 0) // 既に使った j 種類のうち、最近の M 曲は使えない。 // さらにその M 曲は全部異なるので j-M 曲使える
class NoRepeatPlaylist { public: int numPlaylists(int N, int M, int P) { ll mod = 1000000007LL; VVI dp(P+1, VI(N+1)); dp[0][0]=1; for(int i=1;i<=P;i++) for(int j=1;j<=N;j++) { dp[i][j] = (dp[i-1][j-1] * (N-(j-1)) + dp[i-1][j] * max(0, j-M)) % mod; } return dp[P][N]; } };
| 
辺を追加削除するコストが与えられた時、無向グラフを最小コストで木にする問題。
辺の変更コストの小さい順に、重複した（消しても到達性が変わらない）辺を消していく。
その後同じくコストの小さい順に連結に寄与する辺を追加していく。
warshall-floyd でごりごり。冗長なコードになった。
自分への辺を追加していなかったり、隣接行列上で (i, j) を繋いだら (j, i) も繋がないといけないのを忘れていたりしてしばらく苦戦していたが、
ようやく終了 10 秒くらい前に手元のテストが通ったのでアプレットでコンパイルしたところで 糸冬 了 。
↓あとで (practice system test pass)
int dec(char c) { if('A'<=c&&c<='Z') return c-'A'; if('a'<=c&&c<='z') return c-'a'+26; return -1; } class KingdomReorganization { public: int getCost(vector <string> ki, vector <string> build, vector <string> destroy) { int N=ki.size(); vector<pair<int, pair<int, int> > > bu(N*N); vector<pair<int, pair<int, int> > > de(N*N); //VVI bu(N, VI(N, 0)); //VVI de(N, VI(N, 0)); REP(i, N) REP(j, N) bu[i*N+j] = MP(dec(build[i][j]), MP(i, j)); REP(i, N) REP(j, N) de[i*N+j] = MP(dec(destroy[i][j]), MP(i, j)); sort(ALL(de)); sort(ALL(bu)); cout<<bu<<endl; cout<<de<<endl; VVI orig(N, VI(N, 0)); REP(x, N) REP(y, N) if(ki[x][y]=='1') orig[x][y]=1; REP(x, N) orig[x][x]=1; int ans = 0; { VVI orig_r(N, VI(N, 0)); REP(x, N) REP(y, N) orig_r[x][y] = orig[x][y]; REP(k, N) REP(i, N) REP(j, N) orig_r[i][j] |= orig_r[i][k]&orig_r[k][j]; REP(ii, N*N) { int ei = de[ii].second.first; int ej = de[ii].second.second; int co = de[ii].first; VVI w(N, VI(N, 0)); REP(x, N) REP(y, N) w[x][y]=orig[x][y]; if(w[ei][ej]==0) continue; w[ei][ej] = w[ej][ei] = 0; REP(k, N) REP(i, N) REP(j, N) w[i][j] |= w[i][k]&w[k][j]; int ok=1; REP(i, N) REP(j, N) if(orig_r[i][j]==1 && w[i][j]==0) ok=0; if(ok) { ans+=co; orig[ei][ej] = orig[ej][ei] = 0; } } } { VVI orig_r(N, VI(N, 0)); REP(x, N) REP(y, N) orig_r[x][y] = orig[x][y]; REP(k, N) REP(i, N) REP(j, N) orig_r[i][j] |= orig_r[i][k]&orig_r[k][j]; cout<<orig_r<<endl; REP(ii, N*N) { int ei = bu[ii].second.first; int ej = bu[ii].second.second; int co = bu[ii].first; VVI w(N, VI(N, 0)); REP(x, N) REP(y, N) w[x][y]=orig[x][y]; if(w[ei][ej]==1 || w[ej][ei]==1) continue; w[ei][ej] = w[ej][ei] = 1; REP(k, N) REP(i, N) REP(j, N) w[i][j] |= w[i][k]&w[k][j]; cout<<w<<endl; int ok=0; REP(i, N) REP(j, N) if(orig_r[i][j]==0 && w[i][j]==1) ok=1; if(ok) { cout<<ei<<" "<<ej<<endl; ans+=co; orig[ei][ej] = 1; orig[ej][ei] = 1; REP(x, N) REP(y, N) orig_r[x][y] = orig[x][y]; REP(k, N) REP(i, N) REP(j, N) orig_r[i][j] |= orig_r[i][k]&orig_r[k][j]; cout<<"orig_r " <<orig_r<<endl; } } } return ans; } };
さらに後から、一旦すべて消して最小全域木に帰着させたやつを書いた。
最初に全部消すコストを数えておいて、辺の重みとして
を持つグラフの最小全域木を union-find を使った Kruskal で求める。
union-find は spaghetti source さんから。
int dec(char c) { if('A'<=c&&c<='Z') return c-'A'; if('a'<=c&&c<='z') return c-'a'+26; return -1; } struct UnionFind { vector<int> data; UnionFind(int size) : data(size, -1) { } bool unionSet(int x, int y) { x = root(x); y = root(y); if (x != y) { if (data[y] < data[x]) swap(x, y); data[x] += data[y]; data[y] = x; } return x != y; } bool findSet(int x, int y) { return root(x) == root(y); } int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } int size(int x) { return -data[root(x)]; } }; class KingdomReorganization { public: int getCost(vector <string> ki, vector <string> build, vector <string> destroy) { int ans = 0; int N=ki.size(); vector<pair<int, pair<int, int> > > bu; REP(i, N) REP(j, N) { if(ki[i][j]=='1') { bu.PB(MP(-dec(destroy[i][j]), MP(i, j))); ans += dec(destroy[i][j]); ki[i][j]=ki[j][i]='0'; } else { bu.PB(MP(dec(build[i][j]), MP(i, j))); } } sort(ALL(bu)); //cout<<bu<<endl; UnionFind uf(N); REP(ii, bu.size()) { int ei = bu[ii].second.first; int ej = bu[ii].second.second; int cost = bu[ii].first; if(uf.unionSet(ei, ej)) ans += cost; } return ans; } };
| 
できなかった問題を editorial や他の人のコードを見ながら書いてみるシリーズ。
N, K, 長さ N の数列が与えられるので、数列から K 個を選ぶ方法の数を MOD 1000000007 で出力する。
ただし、各桁が 4 or 7 だけでできている lucky number に関しては同じ数字を１回までしか使ってはいけない。という問題。
非 lucky number の数字を２回以上使う場合、同じ数字でも取ってくる元の位置が違えば異なるとみなす。
lucky number を i 個使った場合、K-i 個の非 lucky number を選ぶ組み合わせは「非lucky numberの個数 C K-i」になる
lucky number の選び方は...
10**9 以下の lucky number は 1022 個しかないので、次の DP が考えられる。
pos: 何番目までの lucky number を使ったか (0-)
cnt: lucky number をいくつ使ったか
dp[i][0] = 1 dp[i][j] = dp[i-1][j] (i番目を使わない場合) + dp[i-1][j-1] * count[i] (i番目を使う場合、その数の出現個数だけ選択肢がある)
nl : lucky number の(重複を除いた)個数
rest : 非lucky numberの個数
comb : 二項係数
で最終的な答えは Σi=[0, nl] comb(rest, K-i) * dp[nl][i] で計算できる。
で、いくつか知見が得られた。（間違ってたら指摘お願いします..）
| 
gcd(M, a)==1 の場合、extgcd(a, M, x, y) として x が a の逆元。
// ax+by=gcd(a,b) ll extgcd(ll a, ll b, ll &x, ll &y) { ll g = a; x = 1; y = 0; if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x; return g; }
特に M が素数の場合、フェルマーの小定理より a**(M-2) mod M が a の逆元。
a**(M-1) ≡ 1 mod M → a * a**(M-2) ≡ 1 mod M なので。
参考
http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Cong.html
http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html
| 
nCr mod M = ( Π(i in [1, r]) n-i+1 / i ) mod M
= Π(i in [1, r]) n-i+1 * inv(i) mod M
ということで、ループの i 回目の時点で nCi が求まる。その都度結果を保存していけば O(r) で nC0 から nCr まで計算できる。
もしくは、1!, 2!, ..., n! まで逆元も含めて求めておいて n!/(r! * (n-r)!) = n! * inv(r!) * inv((n-r)!) としてもいい。
| 
（LuXueQi さん、xhl_kogitsune さんのコードも参考にしました）
#define MOD 1000000007LL #define MAXN 100003 int dp[1024][1024]; int b[MAXN]; int lucky(ll x) { for(;x>0;x/=10) if(x%10!=4 && x%10!=7) return 0; return 1; } ll modpow(ll v, int p) { if(p==1) return v; ll vv = modpow(v, p/2); vv = (vv * vv) % MOD; if(p&1) vv = (vv * v) % MOD; return vv; } ll comb(int n, int k) { ll c=1; for(int i=1;i<=k;i++) { c = (c * (n-i+1)) % MOD; c = (c * modpow(i, MOD-2)) % MOD; } return c; } int main() { int N,K; cin>>N>>K; memset(dp, 0, sizeof(dp)); map<ll, int> hi; VI lu; int rest=0; REP(i, N) { int v; scanf("%d",&v); if(lucky(v)) { if(hi[v]==0) lu.PB(v); hi[v]++; } else rest++; } int nl=hi.size(); dp[0][0] = 1; for(int y=1;y<=nl;y++) { dp[y][0] = 1; for(int x=1;x<=nl;x++) { dp[y][x] = ( dp[y-1][x] + ((ll)dp[y-1][x-1] * hi[lu[y-1]])%MOD ) % MOD; } } b[0]=1; for(int i=1;i<=rest;++i){ b[i]=1LL*b[i-1]*(rest-i+1)%MOD*modpow(i, MOD-2)%MOD; } ll ans = 0; REP(i, nl+1) { int lrest = K-i; if(lrest < 0 || rest < lrest ) continue; ans += (ll)b[lrest] * dp[nl][i]; ans = ans % MOD; } cout<<ans<<endl; return 0; }
| 
問題が長くて読むのが大変だった。
class GogoXBallsAndBinsEasy { public: int solve(vector <int> T) { int ans=0; for(int i=0;i<(T.size()+1)/2;i++) { ans+=T[T.size()-i-1]-T[i]; } return ans; }
| 
左上から置けるだけ置いていく。
class GogoXCake { public: string solve(vector <string> ca, vector <string> cu) { int caW=ca[0].size(), caH=ca.size(), cuW=cu[0].size(), cuH=cu.size(); while(1) { int changed=0; REP(y, caH-cuH+1) REP(x, caW-cuW+1) { int ok=1; REP(yy, cuH) REP(xx, cuW) { if(ca[y+yy][x+xx]=='X' && cu[yy][xx]=='.') ok=0; } if(ok) { REP(yy, cuH) REP(xx, cuW) if(cu[yy][xx]=='.') ca[y+yy][x+xx]='X'; changed=1; } //REP(y, caH) cout<<ca[y]<<endl; } if(changed==0) break; } REP(y, caH) REP(x, caW) if(ca[y][x]=='.') return "NO"; return "YES"; }
| 
40分ほど考えたができず。
その後、解の構造は「スタート→→未使用の辺→→ゴール」となってるんじゃないかと思って、
floyd-warshal して i < j && reach[0][i] && choices[i][j]=='Y' && reach[j][N-1] なら ans++ としてみたけど sample0 でなんか大きめの値がでてきてあきらめる。
（追記）
さらに他の人のコードとか editorial 見て以下のコードで system test 通った。
未使用の辺が (0, k) または (k, N-1) の場合(0 < k < N-1)、どちらの経路も 0→k→N-1 となり重複してカウントされるので、
reach[0][k] && reach[k][N-1] の個数だけ後から引くと正しい答えが求まるようだ。
納得したようなしないような。少なくとも本番中に思いつく気がしない。。
class GogoXReimuHakurai { public: int solve(vector<string> ch){ int N=ch.size(); VVI w(N, VI(N, 0)); // w[i][j] ... can reach from i to j REP(i, N) REP(j, N) w[i][j]=ch[i][j]=='Y'; REP(i, N) w[i][i]=1; REP(k, N) REP(i, N) REP(j, N) w[i][j] |= w[i][k]&w[k][j]; // floyd-warshall if(!w[0][N-1]) return 0; //cout<<w<<endl; int ans=0; REP(i, N) REP(j, N) if(w[0][i] && ch[i][j]=='Y' && w[j][N-1]) ans++; ans+=2; REP(i, N) if(w[0][i] && w[i][N-1]) ans--; return ans; }
