Latest Entries
TopCoder SRM460 DIV2 HARD (1000pt)
Problem Statement
ノード数9以下の森が与えられる．
枝を付け加えて木にする方法は何通りあるか?
(この解法はあまり良くない解法だと思います，他にシンプルで計算量の少ない解法があります)
最高で枝を付け加える候補は9*8/2 = 36か所で，そのうち最大8本付け加えれば良いから，パターンの数は36!/8!/28! = 30260340通りしかない．
実際の答えも，最大の場合は9^(9-2) = 4782969なので全探索してみた．
結論からいえば，全探索で通すのはかなり厳しいけど，通ることは通る．
以下のコードで，ノード数9で枝がない最悪ケースで1.6sぐらい，それ以外の最悪ケース(ノード数9で1本だけ既に枝がある)で0.5秒以外に答えを返す．
ノード数9で枝がない場合だけ答え埋め込んでおけばかなり余裕を持って通すことができる．
全探索解法なら，kusanoさんの解答が，シンプルかつ効率的に書かれていました．
これは上手い．
2010年02月07日02時から．
平和そうな部屋じゃないー．
k種類の質問の中からn回質問しました．
ただしどの質問も少なくても1回は質問してます．
同じ質問をしたら同じ答えが返ってきます．答えはYesかNoのどちらかです．
n回の質問の答えが得られたとき，考えうる質問のやり方は何通りあるか．
nは9以下．kはn以下．
？？？
問題読解に手こずる…．
全質問の答えがYesかNoか決めて，どの順番でやったか全探索…は計算量怪しい，ちゃんと組み合わせ的に計算した方が良いかも．
…．
……．
なんか，滅茶苦茶時間掛かった気がするけど，書けた．
これで大丈夫かな…？わからん．
もうサブミットしてしまえ．
AとBの2人がいる．
Aがある都市cに行くと，AはランダムでminA[c]点以上maxA[c]点以下の整数点数がもらえる．
Bがある都市cに行くと，BはランダムでminB[c]点以上maxB[c]点以下の整数点数がもらえる．
AとBはそれぞれランダムにn個の都市の中からk個の都市を選んで行く．
AとBの点数が等しくなる確率は幾つか？
nは最大で40で，もらえるポイントの上限値も40．
確率だ…．
DPなのか？
前からこの都市に行くかどうか場合分けしていって，残りr個の都市の中からm個の都市を訪れるなら，次の都市を訪れる確率はm/rとすれば良いのでは…？
本当か？これが本当ならDPでいけるけど…．
わからんけど，書いてみる，サンプル通れば大丈夫だろう．
サンプル通った！
サブミット．
枝を付け加えて，全ての都市間の同じ年を共有しない行き方が1通り以上2通り以下となるようにしたい．
何通り方法があるか，mod ほげほげで求めよ．
ノード数は20以下．
グラフきたー，全然わからん．
うーん？
これって，閉路が高々1個しかなくて，連結なものの数を数え上げれば良い？
全域木の数はn^(n-2)だから簡単で，枝を1個付け加えれば良い！
いやいや…，最初から繋がってるからn^(n-2)じゃないし…．
2^nの状態数でDPすれば求まる…か？→そんなこともない
いやいやいやいやいや，そもそも，全域木作ってから枝付け加えると同じのできるし！
えーと，どうやるんだ，同じの数えない方法って…．
ここで行き詰って，残り20分ぐらいあったけど，わからなかった．
勘違いして1ミス…．結構痛い．
だからチャレンジする前にはちゃんと確認しようよーorz
EASYとMEDIUM通る．良かったー．
ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4645
Aizu 1304
5*5のマップがあって，幾つかがウイルスに汚染されている．
自分は毎ターンの最初に隣接8マスのどこかに移動しなければならない．ウイルスに汚染されてるマスには移動できない．
毎ターンの終わりに，各マスは，隣接8マスでウイルスに汚染されているマスの数A，自分のいるマスの数B (B=0 or 1)の情報をもとに
自分がウイルスに汚染されていて，A+Bが2か3以外なら，ウイルスから解放される
自分がウイルスに汚染されていなくて，A+Bが3なら，ウイルスに汚染される
ということを繰り返す．
自分が上手く動けば，最小で何ターンで，全てのウイルスが無くなるか，を求める問題．
不可能なら，それを指摘する．
状態数が25*2^25で，幅優先探索．ビット演算使えば速い．
が妥当だと思うんだけど，答えがない場合を忘れていて，答えに適当な上限(仮定)を設けてiterative deepeningで解いた．
(どうやらジャッジデータに含まれてる最大の答えは10らしい…)
ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4643
Aizu 1302
この世界には128個の物質がある．
その物質は11個の特徴があるかないか，で完全に一意に決まる．
ここに，ある物質が1個ある．
それの特徴を調べて物質を特定したいのだけど，最悪ケースで最小で何個の特徴を調べれば良いか．
特徴を調べるとき，前に調べた特徴は知ってるものとして，次調べる特徴を決めて良い．
それぞれの特徴が，YES，NO，まだ知らない，の3^11の状態数でDPした．
ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4642
Aizu 1301
図のように，三角形の中に3つの円を互いに接するように入れる．
このとき，3つの円の半径を求める問題．
2次元幾何．無理やり，2分探索の中で，2分探索するコードで通した．
最初に，1つの円の半径を決めつけて，残りの2円を最初の円と三角形に接するように入れて，2円が重なるなら，最初の円が小さすぎて，2円が離れているなら最初の円が大きすぎる．
LiveArchiveだと，今のところ，オフィシャルのジャッジと一致しないといけないっぽく，小数点以下5桁出力する，かつ，10^-12程度の精度が必要．
ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4639
Aizu 1298
2次元平面上の白い点と黒い点が100個以下ずつ与えられる．
白い点と黒い点を分かつような直線が存在するかどうかを求める問題．
端だけ全部調べる系．
両方凸包を求めて，凸包の各辺を直線として，白い点と黒い点を分かつかどうか調べる．
ただし，一直線上にたくさんの点が乗っている場合は，ちゃんと考えないとダメ．
コーナーケースがたくさんあって難しいけど，基本的に，サンプルにコーナーケースがあるので，それを通るようにちゃんと書けば多分大丈夫．
ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4641
Aizu 1300
化学反応式が係数が書かれていない状態で与えられる．
係数を求める問題．
係数のGCDが1となるような配置方法は一意に定まることが保証されている．
問題サイズは大きくないし，答えの係数は40000以下，32bitで適切に計算すればがオーバーフローしないことが保証されている．
構文解析 + 連立一次方程式 で解いた．
連立一次方程式は，本来は有理数で解くべきなのかもしれないけど，手抜きしてdoubleで解いても大丈夫だった．
ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4638
Aizu 1297
2レーンある水泳教室．片方は行き専用，片方は戻り専用．
n人の人がそれぞれc[i]回往復分泳ぐのだけど，それぞれ行き帰りそれぞれにt[i]時間だけかかる．
泳いでる途中に追い抜くことはできないけれど，レーンの端についたとき，同時についたなら，速い人が遅い人を追い抜く．
全員が泳ぎ終わるまでにかかる時間を求める問題．
愚直にシミュレーションした．
ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4637
Aizu 1296
初期値の文字列と，目標の10文字以下の文字列が与えられる．
10個以下の変換規則が与えられたとき，目標の文字列を得るためにかかるターン数の最小値を求める問題．
変換規則は，
X → Y
という形で，現在の文字列の(オーバーラップしてない)部分文字列としてXの部分を前から順番にYに置き換えていくというもの．
XよりYの方が長い．
全探索．
少し計算時間が怪しいように思うのだけど，毎ターン適応できる規則の数がそんなに多くなかったりで間に合う．
ACM/ICPC Asia - Tokyo, Japan - 2009/2010
LiveArchive 4636
Aizu 1295
10*10以下の2次元グリッド上に0以上20以下の数字が書かれている．
各列，各行の最大の数字がそれぞれ与えられたとき，考えうる数字の配置の中で，全ての和が最小になるのはどんなときか？
和を求める問題．
各列，各行がその最大値をとるような配置が1個は存在することが保証されている．
xという数字が，各行の最大値にA個，各列の最大値にB個あれば，グリッド上にxはmax(A,B)個だけあれば十分，そしてそれだけは必要．
配置が存在することは保証されているので，これだけで大丈夫なのは少し考えればわかる．
ACM/ICPC Asia - Aizu, Japan - 2008/2009
LiveArchive 4160
Aizu 1288
線分が床の上に散らばっている．どの数字が何個あるか数える問題．
全ての線分は数字の一部になっているし，数字は重なっていないし，変な形のものは含まれていない．
線分の数は1000個以下．
2次元幾何実装問題．
変な形はないので，以外と簡単に判定できることが書いてみるとわかる．
Codechef Snackdown Onsite
SPOJ 5970 [FINDPRM]
エラトステネスの篩の逆バージョンで，Nから初めて，今見てる数字にチェックがついてなければ，Nを除くNの約数全てにチェックをつける．
次にN-1，N-2，…に対して同じことを行う．
さて，N以下でチェックの付いてない素数は幾つあるかを求める問題．
Nは10000000以下．
エラトステネスの篩でN/2より大きく，N以下の素数の数を求める．
エラトステネスの篩は，そこそこ効率よく書かないとTLEになる．もしくはもっと効率の良い篩を使う．
という名前の，chokudai先生の連載の最新記事．
二分探索の話．
最後の方に，二分探索の終了条件を書くときに while(high-low<1e-9) と書くと丸め誤差のせいで止まらないことがあるから，定数回回しなさい的なことがやんわり書いてあります．
これを押しつけるのは危険な考え方かな―という気がします．
まぁ，そもそもchokudai先生本人は，超頭柔らかで，定数回ループじゃない方が良い場合は，さくっとそっちで書いちゃう気がするのですが，読者はどうだろうか，ということで．
というか，そもそも，chokudai先生は，定数回ループじゃないとダメ的なことは考えてないと思うのですが，文章はそう言ってるようにも見えるという意味で．
そもそも，TopCoderで要求される精度は，絶対誤差が10^-9以下または相対誤差が10^-9以下．
while(high-low<1e-9) が悪いのは，丸め誤差が悪いんじゃなくて，絶対誤差しか考えていないこと．
相対誤差も考えて， while(high-low<1e-9 && high-low<1e-9*max(abs(high),abs(low))) と書けば良いし，定数回のループを回すよりはこっちの方が自然だと思うわけで．
ただし，TopCoderはあくまで競技プログラミングであって，実行時間が制限時間内に終わるならば，より簡潔でより悩みどころの少ないアルゴリズムを書くべきだと思います．
そういう意味では，定数回ループが正解ですね．
取り敢えず，定数回ループとかぬるいこと言ってるとTime Limit Exceededになる可能性のある問題として，LiveArchive 4412 - The Great Gameを紹介してみます．単純な二分探索の問題ではないですが．
(LiveArchiveって最近サーバ速くなった？ そうだったら普通に通りそうな気もする)
まぁ，そもそも自分はプログラミング的な思想とか基本的にはわからないのですが，こういう風に思いましたってことで．
TopCoder SRM285 DIV1 HARD (1000pt)
Problem Statement
要素数50以下の，各要素が1以上1000以下の整数列が与えられる．
1回の操作で，ある要素を選んで，1だけ増やすか，1だけ減らすかすることができる．
少なくても，K個の異なる要素が含まれるようにするための最小ステップ数を求める問題．
最小費用流で解いた．
グラフの作り方は，ノードは始点，終点，-25〜1025の数字のノードを作る．
始点から，数列内の要素に向かって，コスト0，流量1の枝をはる．
全ての数字のノードから，終点に向かって，コスト0，流量1の枝をはる．
各隣り合う数字の間に，コスト1，流量無限大の枝をはる．
このグラフにおいて，流量Kのフローを流すのに必要な最小コストが答えになる．
DPで解いている人も多かった．
TopCoder SRM285 DIV1 MEDIUM (500pt)
Problem Statement
長さ50以下の命令列が与えられる．ロボットはそれ命令を1つずつ行って，最後の命令の後には最初の命令を行う．
命令は，上下左右のどれかに1マス移動せよ，というもの．
最初，N*Nの盤面のどこかにロボットが等確率でいるものとする．
命令は，50000ステップ行うか，盤面から外に飛び出すまで，実行する．
実行される命令数の期待値を求める問題．
Nは1000以下．
今，どの命令を実行中か，今いる場所はどこか，を状態としてDPすると，状態数が最大で50*1000*1000となって駄目．
問題文にベタに書かれている数字50000が実は小さいということに気づけばOK．
各ステップごとに，上下左右にどれだけ，余裕があれば今までの全コマンドが実行されているかを考えれば解ける．
// #includeとusing namespace std;は略
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
class RobotTesting {
public:
double estimateCommands(int N, string program) {
int tm, dx, dy;
int x_min, y_min, x_max, y_max;
double res=0;
// 現在の場所は，初期位置からのどれだけずれてますか？
dx=dy=0;
// まだはみ出して止まってない初期位置の長方形の四隅の座標
x_min=y_min=0; x_max=y_max=N-1;
// 5万回，シミュレート
rep(tm,50000){
if(x_min > x_max || y_min > y_max) break; // もう全ての初期値が止まってる
if(program[tm%program.size()]=='D') dx++;
if(program[tm%program.size()]=='U') dx--;
if(program[tm%program.size()]=='R') dy++;
if(program[tm%program.size()]=='L') dy--;
// はみ出した分の長方形を削る
if(dx+x_min < 0) res += (tm+1)*(y_max-y_min+1), x_min++;
if(dx+x_max >= N) res += (tm+1)*(y_max-y_min+1), x_max--;
if(dy+y_min < 0) res += (tm+1)*(x_max-x_min+1), y_min++;
if(dy+y_max >= N) res += (tm+1)*(x_max-x_min+1), y_max--;
}
// まだ止まってないのは5万回で止まる
res += 50000.0 * (x_max-x_min+1) * (y_max-y_min+1);
return res/N/N;
}
};
TopCoder SRM285 DIV2 HARD (1000pt)
Problem Statement
0〜9の数字が50個以下並んでいる．
間に+と*のどちらかを入れて，答えを最小にしたい．
最小を達成する入れ方のうち，辞書順最小のものを求める．*の方が+より辞書順で早い．
方針1:
よくよく考えるとオンラインアルゴリズムで上手くいく．
左から眺めていって，(前に+が出てきて以降の)今までの積Aと，次の数字Bを考えて，
A=1 or B=1 ならば *
A=2 and B=2 ならば *
そうでなければ +
を入れていく．
直感的には殆ど自明に思えるのだけど，ちゃんと正当性を考えると結構難しいと思った．
方針2:
DP+経路復元．以下のソースはこれ．
// #includeとusing namespace std;は略
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
// 方針: DP. +と*の入れ方2^50パターンあるのを全探索するのだけど, 次の+の場所がどこかで場合分けして全探索することを考えて，それをメモ化する
// 与えられたsequenceの長さをsizeに, 中身の数字をinに入れておく
int in[60], size;
// dp[i]はseqence.substr(i)の間に+か*を入れてできる最小の数字
int dp[60];
// dp[now]を計算して返す関数
int solve(int now){
int i,res=INT_MAX,tmp,go;
if(dp[now]>=0) return dp[now]; // 既に計算したことがあるなら即座にreturn
if(now==size) return dp[now]=0; // 文字列が空なら0とする
tmp=in[now];
REP(i,now,size){
// この時点でtmpの値はsequence[now]からsequence[i]までの数字を全部かけた値
if(tmp > 100000) tmp = 100000; // 滅茶苦茶でかくなるとoverflowするので抑える (答えは大きくならないので大丈夫)
// seq[now]*seq[now+1]*...*seq[i]+seq[i+1]?...?seq[n] の最小値をgoに代入する
go = solve(i+1) + tmp;
if(res > go) res = go;
if(i+1<size) tmp *= in[i+1];
}
return dp[now]=res;
}
// 実際に答えの文字列を求める関数 (ほとんどsolveからコピペ)
string get_string(int now){
int i,j,res=solve(now),tmp,go;
string ans;
if(now==size) return "";
tmp=in[now];
REP(i,now,size){
if(tmp > 100000) tmp = 100000;
go = solve(i+1) + tmp;
if(res == go) j=i;
if(i+1<size) tmp *= in[i+1];
}
REP(i,now,j+1){
if(i!=now) ans += "*";
ans += (char)(in[i]+'0');
}
if(j+1!=size) ans += "+";
return ans + get_string(j+1);
}
class OperationsArrangement {
public:
string arrange(string sequence) {
int i;
size=sequence.size();
rep(i,size) in[i]=sequence[i]-'0';
rep(i,size+1) dp[i]=-1;
return get_string(0);
}
};
TopCoder SRM285 DIV1 EASY (250pt)
TopCoder SRM285 DIV2 MEDIUM (500pt)
Problem Statement
単語が1個の空白で区切られた1行の文章が与えられる．50文字以下．
最大でK個まで空白を改行に置き換えて良いとして，最大の行の長さを最小化する問題．
最小値のみを答える．
方針は大雑把に3通りぐらいある．
方針1:
まず，たくさん改行した方が良いので，K回改行する場合のみを考えれば良い．(Kが空白の数より大きければ全部改行する)
スペースの数は最大で24個しかないので，区切り方の最大でも 24!/12!/12! = 2704156 パターンしかないので，全部試す．
文字列が長くなると，この方針は駄目になる．
方針2:
最大の行の長さcを決めつけて，それに収まるように各単語を詰め込んで，改行の回数を数えて，それがKを超えるかどうかで答えがc以下か，それより大きいかを判定できる．
よって，cを1から50まで動かして，収まるようになる最小のcを求めれば良い．
cに対する2分探索で求めたのが以下のコード．
方針3:
DPで，現在まで使った改行の数，現在までの最長の行の長さ，を状態として探索する．
// #includeとusing namespace std;は略
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
// 方針: 2分探索で求める 各行の長さが c 以下にできるかどうかは, 簡単に判定できるので
class SentenceSplitting {
public:
int split(string sentence, int K) {
int i,j,now,rest;
int a,b,c; // 2分探索用
int len[100], n; // nは単語の数, lenに各単語の長さを代入
// 各単語の長さを代入する
n=0; j=0; sentence += " ";
rep(i,sentence.size()) if(sentence[i]==' '){
len[n++] = i-j;
j=i+1;
}
a=0; b=100;
while(a<b){
c = (a+b)/2;
now=-1; // 現在の行の長さ 最初スペース入れなくていいので -1 を初期値にする
rest=K; // 使える改行の残りの数
rep(i,n){
if(now + 1 + len[i] > c){ // 今の行に入らないとき, 改行する
now=-1; rest--;
if(rest<0) break;
}
if(now + 1 + len[i] > c) break; // ここの条件がtrueになるのは, cより長い単語があったとき
now += 1 + len[i];
}
// i==n なら範囲内に全文が収まった
if(i==n) b=c; else a=c+1;
}
return a;
}
};
TopCoder SRM266 DIV1 EASY (300pt)
TopCoder SRM266 DIV2 MEDIUM (550pt)
Problem Statement
未知なる1次元の世界がある．
最初，探査機が0の場所で止まっていて
進み始めろ (正の方向に)
進む向きを変えろ
止まれ
の3つのコマンドを送ることができる．
また，探査機は生物を見つけると，生物を見つけましたという合図を送ってくる．
ただし，通信には双方向ともdelayだけ時間がかかる．
ちょうど生物がいる場所に探査機を止めたい．
今，得られている情報だけから，最悪ケースを想定して，最小時刻で探査機を止める戦略をとる．
生物のいる場所が与えられたとき，探査機が止まる時間を求める問題．
速度は1で一定で，向きを変えるコマンドが探査機に届いた瞬間向きは変わる．
// #includeとusing namespace std;は略
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
class ExploringEuropa {
public:
int travelTime(string surface, int delay) {
int i,k;
int tm, place;
int res=INT_MAX, tmp;
// 動き始めた時刻をt=0として, 動き始めるまでの時刻はreturnする時に足します (コード書くとき忘れてた)
// 折り返して, 左に進んでいる最中に新しいVを発見することはないので,
// 最初のVを発見して 折り返す間までに発見したしたV全てに対して, 最小でどの時刻で止まることができるかを調べて, その最小値を求めます.
// 何故これで良いかというと(ここからの3行分の説明は以下のソースを見て考えてからの方がわかりやすい)，一番最短時間で止まれる場所は，最初に見つかったVからdelayだけ進んだ先にVがあるとき．
// それ以前にVがあっても，そこに止まろうとしてREVERSE命令送ることはないので，判断を保留してると思えば良い．
// また，もっと先のVに止まるのが最適になるなら，一番最初に出くわしたVが最適な場所であって，REVERSE命令を送っても大丈夫だから．
rep(k,surface.size()) if(surface[k]=='V') break; // 最初に見つかったVの位置, これを発見したと探査機がわかると即座にREVERSE命令が出される
rep(i,surface.size()) if(surface[i]=='V'){ // iに止まるために必要なな時刻をtmpに代入して, resを更新する
if(i > k+2*delay) continue; // このVの上を探査機は歩いてないから, 未発見
// tm は surface[i]のVが見つかった知らせが届く時刻
// place は 時刻tm での探査機の場所 (ただしまだ右向きに動いているなら, 折りかえす地点で対称に折りかえした先の場所)
tm = i + delay;
place = k + (k+4*delay - tm); // 場所kに時刻k+4*delayに戻ってくるはずなので
// 即座にstop命令を送っても, iを通りすぎちゃう場合, すぐREVERSE命令を送って, そのあと良い感じにSTOP命令をおくる (通りすぎちゃう時間分だけまってSTOP命令を出す)
if(place - delay < i) tmp = tm + delay + i-(place-delay);
// そうでなければ, iにぴったり止まれるようになるタイミングでSTOP命令を送る
if(place - delay >= i) tmp = tm + delay + (place-delay)-i;
// 上の2つの場合は tmp = tm + delay + abs(place-delay-i); とまとめれるけど, 解説のためこう書いただけです
// 最小値の更新
if(res > tmp) res = tmp;
}
// 最初に動き始めるまでの時間delayを足す
return res+delay;
}
};
TopCoder SRM284 DIV2 HARD (1000pt)
Problem Statement
蛇は，長さ3マス以上20マス以下の，4方向で隣接した一本の線．
自分と斜め方向に隣接しているのは良いか，他の蛇っぽいのと斜め方向で隣接しているのは蛇ではない．
蛇の数は幾つか．
盤面は50*50以下．
実装問題．問題文をちゃんと読んで，その通りに実装するのみ．
// #includeとusing namespace std;は略
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int dx[8]={1,-1,0,0,1,-1,1,-1};
int dy[8]={0,0,1,-1,1,-1,-1,1};
int x,y;
int mp[60][60];
// 上下左右で繋がっているfromが書かれたマスを，全部toに置き換えます
void nul(int i,int j,int from,int to){
int k;
if(mp[i][j]!=from) return;
mp[i][j]=to;
rep(k,4) nul(i+dx[k],j+dy[k],from,to);
}
class SnakeCount {
public:
int number(vector <string> image) {
int i,j,k,c,mx;
int head[5000], dame[5000], num[5000];
int res;
// 0の枠をつけるため，縦と横のサイズを+2します
x=image.size()+2; y=image[0].size()+2;
rep(i,x) rep(j,y) mp[i][j]=0;
rep(i,x-2) rep(j,y-2) if(image[i][j]=='1') mp[i+1][j+1]=1;
// 上下左右の身で移動できる区間にユニークな数字を割り振ります (3からなのはてきとーです)
// 00101110 00304440
// 00101010 -> 00304040
// 01001001 05004006
mx=3;
rep(i,x) rep(j,y) if(mp[i][j]==1) nul(i,j,1,mx++);
// head[i]は 蛇i の 頭(尻尾)候補の数 (4方向で，自分と隣接しているのが1マスしかないものの数)
// dame[i]は 蛇i は 2つ叉に分かれていたり，他の蛇にくっついているとtrue
// num[i] は 蛇i の 長さ
rep(i,mx) head[i]=dame[i]=num[i]=0;
rep(i,x) rep(j,y) if(mp[i][j]){
num[mp[i][j]]++;
// 隣接4マスで, 自分と接しているマスの数を求める
c=0; rep(k,4) if(mp[i+dx[k]][j+dy[k]]==mp[i][j]) c++;
if(c>=3) dame[mp[i][j]]++;
if(c==1) head[mp[i][j]]++;
// 隣接8マスで, 他の蛇と接しているかチェックします
c=0; rep(k,8) if(mp[i+dx[k]][j+dy[k]] && mp[i+dx[k]][j+dy[k]]!=mp[i][j]) c++;
if(c>=1) dame[mp[i][j]]++;
}
res=0;
rep(i,mx){
if(num[i]<3 || num[i]>20 || head[i]!=2 || dame[i]) continue;
res++;
}
return res;
}
};
Codechef Snackdown Onsite
SPOJ 5973 [SELTEAM]
n人の人から，最大でk人選んでチームを作る．
チームの中から，好きなだけメンバーを選んで，レギュラーを決める．
レギュラーの中から1人だけキャプテンを決める．
さて，この決め方は何通りあるか，mod 8388608で求める問題．
nとkは100000以下．
これは酷い気づきのゲーム．
キャプテンは誰か，何人チームにするか，各メンバーについてレギュラーにするかどうか，を考えると，答えは
n * Σ[i=0..k] C(n-1,i) 2^i (Cは2項係数)
となる．
ところで，8388608は実は2^23なので，後半の和は途中で切れる．
なのでそこまで計算するだけ．
Codechef Snackdown Onsite
SPOJ 5975 [TRKNIGHT]
2n*2nのチェス盤があって，最初左上にナイトの駒がある．
0ターン以上，Kターン以下動いて，ナイトが何処かの隅にある動き方は何通りあるかmod 1000007で求める問題．
nは12以下，Kは大きい．
行列べき乗．
盤面の対称性を利用して行列のサイズを減らす．
それでも制限時間が結構厳しめな気がした．
いつも，行列べき乗問題って制限時間に苦しめられてる気がするのだけど，皆どうやって高速なの書いているのだろう…．
Codechef Snackdown
SPOJ 5980 [MATGAME]
2人でゲームをする．順番に行動し，行動できなくなったら負け．
最初，各要素が1以上50以下のN*Mの行列が与えられる．
各ターン，正の要素の有る行を1つ選んで，その行の一番左の数字を1以上好きな数だけ減らす．
先手必勝か，後手必勝かを判定する問題．
行と列はそれぞれ50以下．
各行の状態は高々50^2しかないので，grundy numberを計算する．
上手く計算すると，各行でO(50^2)ぐらいの時間計算量でgrundy numberを計算できる．
Technovanza
SPOJ 5979 [YAPP]
1〜Nのpermutationのうち，全ての区間[i,j]に対して，その区間内の最大値が両端のどちらかにないといけない．
そのようなpermutationの数を求める問題．
Nは1000000000以下，数はmod 1000000007で答える．
両端のどちらかがNでないといけない．
それを除いた，両端のどちらかがN-1でないといけない．
と考えていくと，それぞれ両端がどちらかという分だけ自由度があって，2^(N-1)が答え．
Technovanza
SPOJ 5978 [FRQPRIME]
[2,N]の部分区間で，その中に素数をK個以上含むものは何個存在するかを求める問題．
Nは100000以下，Kは10000以下．
尺取りメソッドでカウントしていく．
intではオーバーフローすることとか，Kが0のこともあるのとかに注意．
Codechef Snackdown Onsite
SPOJ 5969 [FINDMAX]
各要素が1以上K以下からなる整数列を考える．
左からなぞって最大値を求めるとき，現在までの最大値より厳密に大きいものと出くわしたら値を更新する．
長さNと値の更新回数がP回となるような数列はいくつあるかmod 1000000007を求める問題．
Nは100以下，Kは300以下．
状態数O(NPK)のDPで，時間計算量もO(NPK)でやって，1回計算したら全てのクエリに対する答えが出てるようにする．
Codechef Snackdown Onsite
SPOJ 5977 Weird Function [WEIRDFN]
F[1] = 1
F[i] = (a*M[i] + b*i + c)%1000000007
ただし，
M[i]はF[1]〜F[i-1]の中央値．
F[1]+F[2]+…+F[n]を求める問題．
nは200000以下．
ヒープを2つ用意して，片方には，中央値より小さいものを入れておいて，大きいものをすぐ取り出せるようにしておく．
もう片方は，中央値より大きいものを入れておいて，小さいものをすぐ取り出せるようにしておく．
2つのピープ大きさのバランスが崩れたら，多い方から取り出して，小さい方に入れる．
そんな感じで解いた．
Codechef Snackdown Onsite
SPOJ 5976 [TRGRID]
長方形のグリッドを左上からまだ通ってない端のマスを時計回りにぐるぐると中心に向かって歩く．
最後に向いている向きはどちらか．
行数，列数どちらが多いか，行数，列数は奇数か偶数かで適当に場合分けして答える．
Codechef Snackdown Onsite
SPOJ 5976 [TRGRID]
長さ100000以下の整数列が与えられる．
その連続する部分の和の最大値と，その最大値となるような区間の数を求める問題．
整数の値は-1000から1000まで．
1回数列をなぞるだけで計算可能．数列を全部保存する必要すらない．
今までの和が0未満なら和を0にリセットしながら，最大値を記録する．
そのとき，最大値をとった時，今まで和が0になった回数だけ，区間の数を増やす．
Codechef Snackdown
SPOJ 5833 [XORROUND]
500要素以下の整数列が与えられる．それが円周上に順番に並んでいるとする．
時間1たつごとに，各要素は，自分と両隣のビット演算のXORを取ったものに変わる．
時間K後の整数列を求める問題．
最終的に各要素を何回XOR取れば良いのかというのを行列べき乗で計算することを考える．
それを単純に計算すると要素数をnとしてO(log(K)*n^3)になるけど，対称性を考慮するとO(log(K)*n^2)になる．
行列の掛け算は，対称性を考慮すると，1行目だけ計算すれば，他はその結果から求まる．
Codechef Snackdown
SPOJ 5832 [ANDROUND]
20000要素以下の整数列が与えられる．それが円周上に順番に並んでいるとする．
時間1たつごとに，各要素は，自分と両隣のビット演算の&を取ったものに変わる．
時間K後の整数列を求める問題．
自分と左右K個の&を取ったものが答え．
各ビットごとに計算するとして，自分か左右K個に0が1つでもあれば0にする．
1〜i個までの0のものの数を最初に求めておけば，各ビットごとの計算はO(n)でできる．