VNOI
SPOJ 3267 [DQUERY]

30000要素以下の数列が与えられる．
その数列に対して200000個以下のクエリが与えられる．
各クエリは，ある数列の区間[a,b]に入っている異なる要素の数を求める．

自力で思いつかなくてTopCoderのForumを頼った
まず，クエリを区間の終端の値bでソートしておく．
で，数列を加えつつ，クエリを順番に処理していくと，数列の中でa番目以降に出てくる要素の数が答え．
各数字が，最後に出現した場所を覚えつつ，最後に出現した場所のヒストグラムをFenwick treeで保持しておけば良い．

第7回 日本情報オリンピック本選問題 2007年02月12日
Aizu 0517

問題文が日本語なので省略．

入力の零の数zを覚えて置いて，間に入ってないカードの数がzを超えない区間の最長を尺取りメソッドで求めれば良い．

#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n,z;
  int sum[100010],st,ed,res;

  for(;;){
    scanf("%d%d",&n,&k); if(!n)break;
    z=0;
    rep(i,n+1) sum[i]=1; sum[0]=0;
    rep(i,k){
      scanf("%d",&j);
      if(!j) z++; else sum[j]=0;
    }
    rep(i,n) sum[i+1]+=sum[i];

    res=0; st=0; ed=0;
    while(ed<=n){
      if(sum[ed]-sum[st] > z) st++;
      if(ed-st > res) res = ed-st;
      ed++;
    }

    printf("%d\n",res);
  }

  return 0;
}

第7回 日本情報オリンピック本選問題 2007年02月12日
Aizu 0518

問題文が日本語なので省略．

正方形の右回りで連続する頂点を2つ指定すれば残りの頂点の座標はわかる．
なので，柱の座標をハッシュに全部突っ込んでおけば，2頂点が与えられれば，それを頂点とする正方形が作れるかどうかの判定はO(1)でできる．
なので，合計でO(n^2)で解ける．

第7回 日本情報オリンピック 予選 2007年12月16日
Aizu 0523

問題文が日本語なので省略．

シミュレーションするだけ．
問題サイズが小さいので，愚直な実装で良い．

日本情報オリンピック予選 2006年12月17日
Aizu 0511

問題文が日本語なので省略．

やるだけ．30要素の配列を用意して，入力した数の場所に印をつける．印が付いてないものを出力する．

日本情報オリンピック予選 2006年12月17日
Aizu 0510

問題文が日本語なので省略．

やるだけ．

日本情報オリンピック予選 2006年12月17日
Aizu 0512

問題文が日本語なので省略．

やるだけ．

第7回 日本情報オリンピック 予選 2007年12月16日
Aizu 0522

問題文が日本語なので省略．

やるだけ．全部調べる．

第7回 日本情報オリンピック 予選 2007年12月16日
Aizu 0521

問題文が日本語なので省略．

日本の硬貨なのでgreedyにやれば良い．

第8回 日本情報オリンピック 予選1 2008年12月14日
Aizu 0532

問題文が日本語なので省略．

やるだけ．全て秒単位に直して計算する．

第8回 日本情報オリンピック 予選2 2008年12月14日
Aizu 0533

問題文が日本語なので省略．

ソートして足すだけ．

第8回 日本情報オリンピック 予選3 2008年12月14日
Aizu 0534

問題文が日本語なので省略．

色の変え方を全て試してシミュレーションする．
O(N^2)だけど，それほど凶悪なテストケースは無いっぽし，実際に作るのも難しそう．

第8回 日本情報オリンピック 予選4 2008年12月14日
Aizu 0535

問題文が日本語なので省略．

制約がDFSで探索しても間に合うよ，って言ってくれているのでそうする．

第7回 日本情報オリンピック 2008年02月10日
Aizu 0527

問題文が日本語なので省略．

連続する石の数をスタックに積んでおけばO(n)で解ける．

昨日でした．参加者の皆様お疲れさまでした．

難易度的には
　(簡単) A = B < D = E < C <<<< F (難しい)
だったのかな…．

去年と比べて，Bが簡単になったなぁ．
今年もDはダイクストラのD．
Eはまさかのマッチング．知らないと解けない．
今年の最終防衛問題Fは幾何．

実行時間制限がないのでCは愚直に書いてもOKだったみたいだけど，結構時間がかかるらしい．
ある程度最初に，各文字の使える数字を選別しておいて，探索は下の桁から決めていって枝刈りバックトラックするぐらいかなぁ…．

第7回 日本情報オリンピック 予選1 2007年12月16日
Aizu 0525

問題文が日本語なので省略．

行のひっくり返すやり方についての全探索．
列の方は，1が多ければひっくり返せば良い．
ってことでO(2^R * C)だけど，2^Rの方がCより小さいので，C行の状態を2^Rに分類しておけばO(4^R)で解ける．
ビット演算を使わず素直に書くとO(2^R * R * C)だけど，それでも通るようなタイムリミット設定になっているっぽい．
コードは続きに．

続きを読む

IPSC 2009 (Internet Problem Solving Contest)
SPOJ 4454 [BRCKTS2]

括弧の対応関係を問題文に描かれているような図と対応させる．
括弧の文字列が与えられるので，黒い部分の面積を求める問題．

まずスタックに積みながら1回なぞって，対応する括弧を求めておく．
後は，適当に再帰処理すればO(length)で解ける．

第7回 日本情報オリンピック 2008年02月10日
Aizu 0528

問題文が日本語なので省略．

2分探索する．k文字の共通部分文字列が存在するかどうかはrolling hashを使うなど．
これだと計算量はO(n log n)．
SPOJ 1812でTLEもらってたコードを送ったら通った．

第7回 日本情報オリンピック 2008年02月10日
Aizu 0529

問題文が日本語なので省略．

0点の的を1個加えると4回投げる場合のみ考えれば良くなる．
2回投げて得られる点数を全部列挙して，ソートして，後は尺取りメソッドすれば良い．
計算量は，ソートにO(n^2 log n)，尺取りメソッドにO(n^2)．

SPOJ 4415 [INTEGER1]

2以上の自然数xに対してf(x)をm^n=xなる最大のnで定義する．ただしmとnは自然数．
　f(a) + f(a+1) + ... + f(b)
を求める問題．
aとbは10^18以下．

2以上a以下の自然数xのうちでf(x)がt以上のものの数はaの1/t乗を計算することでわかる．
なので，tが大きい方から計算すれば，f(x)=tのものの数を数えることができる．

World Final Warm-up Contest
UVa 10251

上から見ると，円形または正方形のケーキがある．
そのケーキの上の1点に花が乗っている．
1回だけ直線でケーキを切って2つにわけるとして，花が含まれている方の体積を最小化したい．
体積を求める問題．

数学．
円の場合，体積最小の切り方は簡単にわかる．
正方形の場合は一瞬難しいかと思うんだけど，良く考えて，
切り口のちょうど真ん中の点に花がのっていなければならないことに気づけば，暗算で求まるぐらい簡単．

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define EPS 1e-10

int main(){
  double r,h,dx,dy,res,th;
  int i,size,mode;
  char in[999];

  gets(in); size=atoi(in);
  while(size--){
    gets(in);
    mode = sscanf(in,"%lf%lf%lf%lf",&r,&h,&dx,&dy);
    if(mode==3){
      th = 2*atan2(sqrt(r*r-dx*dx),dx);
      res = (th-sin(th))/2*r*r;
    } else
      res = (r/2-dx)*(r/2-dy)*2;

    printf("%.3lf\n",res*h+EPS);
  }

  return 0;
}

2009年06月28日13時から3時間，6問．
[ Link ]

13時10分．寝坊した…orz
参加するかどうか微妙になったけど，取り敢えず裏で解いてみよう．

どこの福縞軒だよ！
やるだけ．書いた．

うーん，文字だけ見てなぞれば解ける…のかなぁ？
まぁ，よくわからないし，シミュレーションも線形オーダーでできるし，シミュレーションでいいか．
書いた．

DPするだけ．
ノード数的には全探索でも可ってことなんだろうけど．
書いた．

状態数は…64^4 + αか．メモリ的にちょっときつい(100^4では駄目)．なんとかなる範囲ではあるけど．
どうせ，コンテナは押したら止まらないので，疎なんだろうけど．
保留．

幾何シミュレーション．
二次方程式解きながらシミュレーションするだけ．
書いた．

どうせ探索何だろうけど…，うまく探索する方法が思いつかない．
DPとかでも解けるかもとか思ったけど，それもきつそうだ．
保留．

こんな方法でも良いかも，とかいろいろ考えたけど，結構トリッキーなケースがちゃんと作れる．
てか，コンテナ3つしかないし，メモなんか付けずに全探索DFSとかでも良いんじゃないか？
毎回，出口，コンテナの上下左右のどこかに移動して，コンテナの横だったら押す．
書いてみた．TLEが不安．まあ，いいか．送ってみよう．枝刈りも何もしていない．
2.9秒で通った．通ったけども遅すぎる…．

Dを送っちゃったので，AからEまで全部送ってみる．
全部一発AC．すんなり通るとか自分らしくない．

残り70分ぐらい．
10分ぐらい考えて，良い探索方法思いつかなかったのと，他にやることがあったので放棄．

送ったコードは続きにおいておく．

続きを読む

第7回 日本情報オリンピック本選問題 (2007年02月12日)
Aizu 0516

問題文が日本語なので略．

やるだけ．
ソースコード貼り付けテストその2．

#include<stdio.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
int main(){
  int i,k,n,res,sum,d[100000];
  for(;;){
    scanf("%d%d",&n,&k); if(!n)break;
    rep(i,n) scanf("%d",d+i);
    sum=0; rep(i,k) sum+=d[i]; res=sum;
    REP(i,k,n){
      sum+=d[i]-d[i-k];
      if(res<sum) res=sum;
    }
    printf("%d\n",res);
  }
  return 0;
}

2009年06月24日10時から．

ソースコードを本文に張り付けるテストをしてみる．
色付けとかはさっき5分で適当に書いたコードに出力させてみた．

Match Overview
Match Editorial
Summary of Japanese (otinn.com)
参加記録 (blog)

2次元平面．互いに共通点を持たない円周が50個以下与えられる．
始点と終点が与えられるので，始点から終点まで連続的に移動する場合，跨がなければならない円周の最小数を求める問題．

片方のみを含む円の数を返せばよい．

A個の0とB個の1がある．
1ターンに厳密にK個の数を選んで0と1を反転させる．
最小何ターンで全て1になるかを求める問題．不可能なら-1を返す．
A, B, Kはそれぞれ100000以下．

解法は2通り．
1つ目はBFSする．
ただし普通にやるとTLEなので，状態をmod 2で分けておくと，枝は連続した区間にはられるのでそれを利用する．

2つ目はiターンで可能かどうかを逐次判定していく方法．
判定方法は，A個フリップするとして，残りのフリップ回数を無駄に消費できるかどうかを判定する．
ソースは次の通り．

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

class BinaryFlips {
public:
int minimalMoves(int A, int B, int K) {
  long long i,rest,use;
  rep(i,A+B+1){
    rest=i*K-A;
    use=((i/2)*B+((i-1)/2)*A)*2;
    if(rest>=0 && rest%2==0 && rest<=use) return i;
  }
  return -1;
}

iターン行うとしてフリップする合計回数はi*K．
もともと0だったものをフリップするものとして，残りのフリップ回数rest=i*K-A．
B枚それぞれfloor(i/2)回までひっくり返して元に戻すということを行えるし，
A枚は，最初に1回ひっくり返したとしてfloor((i-1)/2)回までひっくり返して元に戻せる．
なので，無駄に消費できるフリップの回数use=( (i/2)*B+((i-1)/2)*A )*2．
rest>=0 かつ rest%2=0 かつ rest<=useであれば全て1にできる．

曲のリストが与えられるので，続けてa分以上，b分以下聞く方法は何通りあるかを求める問題．
ただし，それぞれ曲は高々9種類のカテゴリに属し，長さは1以上9分以下で整数*分．
あるカテゴリの曲の次に，聞けるカテゴリが制限されている．
aとbは大きい．

遷移行列作ってべき乗する．
参加記録で書いた方法でもできると思うけど，そんな面倒なことするまでもなく，行列を1回かけたら1分だけ時が進むとしても作れる．

2009年06月24日10時から．

11時からだと勘違いしてて寝るのが遅くなった．
まあ，この時間帯のSRMは参加者少ないので，直前登録でも良いだろうと踏んで寝る．
6時半就寝，9時45分起床．眠い．とりあえず眠い．
予想通り登録はできた．目は覚めてない．なんで最近プラクティスルームが1個分しかないの？

300-600-1000の変則セット．
1000はいつもどおりの難易度として，300と600が面倒な問題なんだと予想．
　→　今回は完全に外れた．

半分寝てる状態で問題オープン．
なんか取り敢えず絵を眺めてうとうとしてる．
駄目だよ！問題読まなきゃ！
読んだ．
…，2点の片方を内部に含んでいて，片方が外部の円の数が答えなんじゃ…．
　→　300なんだし，そんな簡単なわけないじゃん！
　→　…，いや，たぶん証明できるぞ．
書いた．寝ぼけててx2とx1を書き間違える．直した．送った．
皆瞬殺してる．300なのに，やっぱりこんなのでよいのか．

状態数が高々200000．
　→　BFSでいけるに決まっている，という良くわからない思考回路が働く．
3行ぐらいプログラム書いたところで，枝数が200000*100000ぐらいになることに気づいた．
いや，でも枝刈ればいけそうな気もするぞ…．
いや，次数が10000とかだったら1ステップでも苦しいのにそれを10ステップしなければいけない…？
グリーディーでもいけるんじゃないか？
閃いた！
i回スワップすると，合計でi*k文字スワップすることになる．
A個はスワップするとして，残りのスワップ回数を無駄に消費できるかどうかだけ調べれば良いんだ！
とても簡単なプログラムなはずなのに，寝ぼけてふわふわしている頭で，理論的になかなか書けない．
なんとか書けた．超簡単．寝ぼけてなければ後数分早く書けたはず…．
サブミット．
サマリーを見ると，medium提出，自分で2人目！
なんで，皆こんなに梃子摺っているのだろう．不安になってきた．
まぁ，点数的にhardを先に解いているんだと思って納得．

与えられる行列の行と列が直感的に捕らえると逆になっているように見える．
　→　これはチャレンジポイントか！？
　→　逆向きにたどれば同じ答えが出てくるのでチャレンジできない．
　→　そもそも自分の部屋ではhard提出者0でした．
で，問題自体は，どうみても遷移行列作ってべきを計算する問題にしか見えない．
てか，この前のWaterlooコンテストの問題Cの類題だ．
最後の曲のカテゴリと長さ mod 10を状態に，その区間の長さに始めて到着した時点だけに着目すれば遷移行列が作れる．
行列サイズは100でちょうど何とかなりそう．
書き出すと，いろいろなところが厄介なのに気づく．
ある時間以下のものを全て求めなければいけない．
　→　行列n乗だけじゃなくて，I+A+A^2+...+A^nとかいうのも必要．
　→　DPして行列をいじった後またDPしなければいけない．
気づけば残り5分とかになってた．
諦めた．

easyは流石に間違えないだろうし，mediumを見ていく．
あれ，自分以外全員BFSしてるぞ！？
　→　適当につつけば落ちるんじゃないのか？
　→　教えてPetr先生ー．
　→　Petr先生がBFSしてる…．落ちるんだったら僕のほうだ…orz
取り敢えず，10分ぐらい掛けてBFSの解法を理解する．
なるほどー，状態をmod 2で分けておけば，張られる枝は連続な区間に張られるので，まだ到達してない状態の列挙が簡単にできる．
それでO(n+m)ぐらいで結局解けちゃうって寸法か．賢すぎる．
で，チャレンジ自体は何もできないまま終了．

何事もなく通った．良かった．
頭が(良い方向に)おかしいターゲットのwataとかいう人がいなければ，medium最速だったみたい．惜しい…．
レートは前回暴落した分，少し取り戻した．

UVa 10257

簡単にいえば，非負整数s,p,y,jが与えられるので
　a = b + s または a = b + s + 1
　b = c + p または b = c + p + 1
　a = c + y または a = c + y + 1
a + b + c = 12 + j
を満たす非負整数a,b,cを求める問題．

やるだけ．
全通り試して矛盾が無いものを出力しても良いし，場合分けでも良い．

第5回 日本情報オリンピック本選問題 (2006年02月12日)
Aizu 0508

問題文が日本語なので略．

問題文を焼きなおすと，無向グラフで同じ頂点を高々1回通る，最も長いパスの長さを求める問題．
DFSで全探索で通った．

第5回 日本情報オリンピック本選問題 (2006年02月12日)
Aizu 0507

問題文が日本語なので略．

実装するだけ．再帰．

第5回 日本情報オリンピック本選問題 (2006年02月12日)
Aizu 0506

問題文が日本語なので略．

実装するだけ．

第5回 日本情報オリンピック本選問題 (2006年02月12日)
Aizu 0505

問題文が日本語なので略．

ソートするだけ．