2010年7月14日水曜日

Aizu Online Judge

0011
0013
0014
0015
0016
0017
0018
0019
0020

2010年7月13日火曜日

PKU Judge Online

1298
1519
1546
1552
1658
2105
2305
2371
2390
2623
3062

Aizu Online Judge

0000
0001
0002
0003
0004
0005
0006
0007
0008
0009

2010年7月11日日曜日

Codeforces Beta Round #23

Codeforces Beta Round #23(7/9 0:00~2:00)

■A. You're Given a String...

□問題
文字列が与えられる.文字列中に2回以上現れる部分文字列の内,最大の長さを求めよ.

□解法
文字列の長さが100以下なので書くだけ.

□コード
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class A{
Scanner sc=new Scanner(System.in);

void run(){
String s=sc.nextLine();
int n=s.length();
int ans=0;
for(int len=1; len<n; len++){
for(int i=0; i+len<=n; i++){
String t=s.substring(i, i+len);
if(s.indexOf(t, i+1)!=-1){
ans=len;
break;
}
}
}
println(ans+"");
}

void println(String s){
System.out.println(s);
}

void print(String s){
System.out.print(s);
}

public static void main(String[] args){
new A().run();
}
}

■B. Party

□問題
N人がパーティにやってきた.最初に友達が0人の人が省かれる.次に現在いるパーティ内での友達が1人の人が省かれる,次に現在いるパーティ内での友達が2人の人が省かれる,…最後に現在いるパーティ内での友達がN-1人の人が省かれる.最後まで残った人の数が最大のものを求める.

□解法
問題の趣旨が掴めない….
→しかし,結構な人数の人が提出している.
→よく分からないけど,実は答え全部1なんじゃね?
→提出,WA,あわわわわ.
→試しに,N=3で手書きシミュレートしてみよう.
→なるほど,2人以上が残ることは出来ないなぁ.
→N=4で(ry
→最大2人残った.
→あぁ,N>=2の時は最大N-2人残るのか(N<2の時は0人).
→提出,AC.

□コード
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
Scanner sc=new Scanner(System.in);

void run(){
int t=sc.nextInt();
for(int i=0; i<t; i++){
int n=sc.nextInt();
println(""+max(0, n-2));
}
}

void println(String s){
System.out.println(s);
}

void print(String s){
System.out.print(s);
}

public static void main(String[] args){
new B().run();
}

}

C,D,Eは解けませんでした….

■Result
○○×××

■Rating
1554 -> 1633

CDEのどれかを解くことが出来れば安定して上昇すると思われます.

2010年7月9日金曜日

TopCoder 練習

RouteIntersection(Member SRM 474 DIV1 Easy)

import java.util.*;
import java.lang.*;
import java.math.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class RouteIntersection {
public String isValid(int N, int[] coords, String moves) {
TreeSet<Integer> set=new TreeSet<Integer>();
int len=coords.length;
for(int a:coords)
set.add(a);
int n=set.size();
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
Iterator<Integer> it=set.iterator();
for(int i=0;i<n;i++)
map.put(it.next(),i);
LinkedList<int[]> list=new LinkedList<int[]>();
int[] p=new int[n];
list.add(p);
for(int i=0;i<len;i++){
int[] q=new int[n];
System.arraycopy(p,0,q,0,n);
if(moves.charAt(i)=='+')
q[map.get(coords[i])]++;
else
q[map.get(coords[i])]--;
for(int[] a:list)
if(Arrays.equals(a,q))
return "NOT VALID";
list.add(q);
p=q;
}
return "VALID";
}
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor


API使いまくり.

TopCoder 練習

RabbitStepping(SRM 475 DIV1 Easy)

import java.util.*;
import java.lang.*;
import java.math.*;
public class RabbitStepping {
public double getExpected(String field, int r) {
int n=field.length();
int cnt=0, sum=0;
for(int i=0; i<1<<n; i++){
if(Integer.bitCount(i)==r){
int r1=0, r2=0;
for(int k=0; k<n; k++){
if((i>>k&1)==1){
if(k%2==0) r1++;
else r2++;
}
}
cnt+=r1%2+r2%2;
sum++;
}
}
return (double)cnt/sum;
}
}


// Powered by FileEdit
// Powered by TZTester 1.01 [25-Feb-2003]
// Powered by CodeProcessor

PKU Judge Online

1046
1207
1663
2000

2010年7月8日木曜日

ACM/ICPC国内予選 コード

汚いけどコード晒しあげ.

A
import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class A{
Scanner sc;
PrintWriter pw, db;

int[] dx={-1, 0, 1, 0};
int[] dy={0, 1, 0, -1};

void run(){
init();
for(;;){
int m=sc.nextInt();
if(m==0)
break;
P[] ps=new P[m];
ps[0]=new P(0, 0);
for(int i=1; i<m; i++){
int n=sc.nextInt();
int d=sc.nextInt();
ps[i]=new P(ps[n].x+dx[d], ps[n].y+dy[d]);
}
int xmin=0, xmax=0;
int ymin=0, ymax=0;
for(P p : ps){
xmin=min(xmin, p.x);
xmax=max(xmax, p.x);
ymin=min(ymin, p.y);
ymax=max(ymax, p.y);
}
int w=xmax-xmin+1;
int h=ymax-ymin+1;
db.println(w+" "+h);
pw.println(w+" "+h);
}
close();
}

public static void main(String[] args){
new A().run();
}

void init(){
try{
sc=new Scanner(new FileInputStream("A"));
pw=new PrintWriter("A.out");
db=new PrintWriter(System.out);
}catch(IOException e){}
}

void close(){
sc.close();
pw.close();
db.close();
}

static class P{
int x, y;

P(int x, int y){
this.x=x;
this.y=y;
}
}

}

B
import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class B{
Scanner sc;
PrintWriter pw, db;

int w, h;
int[][] right, down;

void run(){
init();
for(;;){
w=sc.nextInt();
h=sc.nextInt();
if(w==0&&h==0)
break;
right=new int[h][w-1];
down=new int[h-1][w];
for(int k=0; k<h-1; k++){
for(int i=0; i<w-1; i++)
right[k][i]=sc.nextInt();
for(int i=0; i<w; i++)
down[k][i]=sc.nextInt();
}
for(int i=0; i<w-1; i++)
right[h-1][i]=sc.nextInt();
bfs();
}
close();
}

void bfs(){
int[][] map=new int[h][w];
LinkedList<P> q=new LinkedList<P>();
P s=new P(0, 0);
map[0][0]=1;
q.addLast(s);
while(!q.isEmpty()){
P p=q.removeFirst();
int x=p.x, y=p.y;
int d=map[p.y][p.x];

// up
int nx=x;
int ny=y-1;
if(ny>=0&&down[y-1][x]==0&&map[ny][nx]==0){
map[ny][nx]=d+1;
q.addLast(new P(nx, ny));
}

// down
nx=x;
ny=y+1;
if(ny<h&&down[y][x]==0&&map[ny][nx]==0){
map[ny][nx]=d+1;
q.addLast(new P(nx, ny));
}

// left
nx=x-1;
ny=y;
if(nx>=0&&right[y][x-1]==0&&map[ny][nx]==0){
map[ny][nx]=d+1;
q.addLast(new P(nx, ny));
}

// right
nx=x+1;
ny=y;
if(nx<w&&right[y][x]==0&&map[ny][nx]==0){
map[ny][nx]=d+1;
q.addLast(new P(nx, ny));
}
}
db.println(map[h-1][w-1]);
pw.println(map[h-1][w-1]);
}

public static void main(String[] args){
new B().run();
}

void init(){
try{
sc=new Scanner(new FileInputStream("B"));
pw=new PrintWriter("B.out");
db=new PrintWriter(System.out);
}catch(IOException e){}
}

void close(){
sc.close();
pw.close();
db.close();
}

static class P{
int x, y;

P(int x, int y){
this.x=x;
this.y=y;
}
}

}

C

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class C{
Scanner sc;
PrintWriter pw, db;

LinkedList<Integer> list1, list2;
int[] dp1;

static final int INF=1>>28;

void run(){
init();
f();
for(;;){
int n=sc.nextInt();
if(n==0)
break;
int a1=dp1[n];
int a2=cal(n);
db.println(a1+" "+a2);
pw.println(a1+" "+a2);
}
close();
}

void f(){
int n=1000000;

list1=new LinkedList<Integer>();
list2=new LinkedList<Integer>();
for(int i=1;; i++){
int t=i*(i+1)*(i+2)/6;
if(t>n)
break;
list1.add(t);
if(t%2==1)
list2.add(t);
}

// 予め計算しておく
dp1=new int[n+1];
Arrays.fill(dp1, INF);
dp1[0]=0;
for(int j=1; j<=5; j++){
for(int i=0; i<n; i++){
if(dp1[i]!=j-1)
continue;
for(int k : list1){
if(i+k<=n)
dp1[i+k]=min(dp1[i+k], j);
}
}
}
}

int cal(int n){
int[] dp=new int[n+1];
Arrays.fill(dp, INF);
dp[0]=0;
for(int j=1;; j++){
for(int i=0; i<n; i++){
if(dp[i]!=j-1)
continue;
for(int k : list2){
if(i+k==n)
return j;
if(i+k<n)
dp[i+k]=min(dp[i+k], j);
}
}
}
}

public static void main(String[] args){
new C().run();
}

void init(){
try{
sc=new Scanner(new FileInputStream("C"));
pw=new PrintWriter("C.out");
db=new PrintWriter(System.out);
}catch(IOException e){}
}

void close(){
sc.close();
pw.close();
db.close();
}

}

D
import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class D{
Scanner sc;
PrintWriter pw, db;

static final int INF=1<<28;
static final double EPS=1e-6;

int w, h;
int[][] field;

int n;
B[] bs;
B root;

boolean stable;

boolean[][] visited;

void run(){
init();
for(;;){
w=sc.nextInt();
h=sc.nextInt();
sc.nextLine();
if(w==0&&h==0)
break;
field=new int[h][w];
for(int j=0; j<h; j++){
String s=sc.nextLine();
for(int i=0; i<w; i++){
char c=s.charAt(i);
if(c=='.')
field[j][i]=-1;
else
field[j][i]=Integer.parseInt(""+c);
}
}
identify();
bs=new B[n];
for(int i=0; i<n; i++)
bs[i]=new B();
genG();
genTree();
stable=true;
dfs(root);
db.println(stable?"STABLE":"UNSTABLE");
pw.println(stable?"STABLE":"UNSTABLE");
}
close();
}

// id付け
void identify(){
n=0;
visited=new boolean[h][w];
for(int j=0; j<h; j++){
for(int i=0; i<w; i++){
if(!visited[j][i]&&field[j][i]!=-1){
search(i, j, field[j][i]);
n++;
}
}
}
}

void search(int x, int y, int i){
if(x<0||x>=w||y<0||y>=h)
return;
if(visited[y][x])
return;
if(field[y][x]!=i)
return;
visited[y][x]=true;
search(x-1, y, i);
search(x+1, y, i);
search(x, y-1, i);
search(x, y+1, i);
field[y][x]=n;
}

// 重心の生成
void genG(){
LinkedList<Double>[] lists=new LinkedList[n];
for(int i=0; i<n; i++)
lists[i]=new LinkedList<Double>();

for(int j=0; j<h; j++)
for(int i=0; i<w; i++)
if(field[j][i]!=-1)
lists[field[j][i]].add(i+0.5);
for(int i=0; i<n; i++){
double sumx=0;
for(double x : lists[i])
sumx+=x;
bs[i].g=sumx/4;
}
}

// 木の生成,接地面のx座標の計算,根の決定
void genTree(){
for(int j=0; j<h-1; j++){
for(int i=0; i<w; i++){
int f1=field[j][i];
int f2=field[j+1][i];
if(f1==-1||f2==-1||f1==f2)
continue;
B b1=bs[f1];
B b2=bs[f2];
b1.left=min(b1.left, i);
b1.right=max(b1.right, i+1);
if(!b2.children.contains(b1))
b2.children.add(b1);
}
}
root=null;
for(int i=0; i<w; i++){
int id=field[h-1][i];
if(field[h-1][i]!=-1){
root=bs[id];
root.left=min(root.left, i);
root.right=max(root.right, i+1);
}
}
}

void dfs(B rt){
if(!stable)
return;
if(rt==null)
return;
double mass=0;
double mg=0;
for(B b : rt.children){
dfs(b);
mass+=b.mass;
mg+=b.mass*b.g;
}
// マージ
rt.g=(mg+rt.mass*rt.g)/(mass+rt.mass);
rt.mass+=mass;

if(rt.g>rt.left+EPS&&rt.g+EPS<rt.right)
;
else
stable=false;
}

class B{
LinkedList<B> children;
double left, right;
double g;
double mass;

B(){
children=new LinkedList<B>();
left=INF;
right=-INF;
mass=1;
}
}

public static void main(String[] args){
new D().run();
}

void init(){
try{
sc=new Scanner(new FileInputStream("D"));
pw=new PrintWriter("D.out");
db=new PrintWriter(System.out);
}catch(IOException e){}
}

void close(){
sc.close();
pw.close();
db.close();
}

}

2010年7月7日水曜日

専門書を読む #19

・Prologの技芸
第8章まで

2010年7月6日火曜日

TopCoder SRM 475

SRM 475 20:00~22:00

・RabbitStepping(DIV1 Easy)
何か難しそう
→fieldの長さが高々17なので愚直にシミュレーションしよう
→とりあえずサンプル1,2,3あたりは正解
→何かサンプル5が通らない
→終了条件が間違っているのかしら?
→ちまちまデバッグ
→まさかの終了あばばばば

以下略.

実のところ,うさぎの移動ルールは結構どうでもよかったようです.うさぎはステップ毎に必ず右か左に移動するので,初期値セルpにいたとして最終的にセル0,1のどちらにいるかというのは,(k+size-2)%2で調べられます(多分).で,セルに重なっているのが偶数匹なら結果的に0匹,奇数匹なら1匹.あとはこれを足すだけ.

今回学んだこと
nビットの整数でrビットが1であるものを生成するには,Integer.bitCountを使いましょう.
for(int i=0; i < i<<n; i++){
if(Integer.bitCount(i)==r){
// TODO
}
}
・Result
××× 0 0

・Rating
1276 -> 1233

DIV2がお迎えに来たようです….

2010年7月4日日曜日

セルオートマトン #34 ルール32

ルール32
クラス1

時刻tでの状態■■■■■□■□■■□□□■■□■□□□■□□□
時刻t+1での状態



Fig.1 rule32

2010年7月3日土曜日

ACM/ICPC国内予選

ACM/ICPC国内予選 7/2 16:31~19:31

そして約1週間後,国内予選本番が始まりました.

問題と順位表はこちらから.

■チーム紹介
・大学名
Tokyo National College of Technology
・チーム名
nyama
・メンバ
todo
nyama
ando

■当日の流れ(時間はおおよそ合ってる)
16:31~
問題を印刷後,todoがテンプレを打ち込む.その間nyamaとandoが問題解析.

16:35~
2人の問題解析の結果を聞いてtodoがAを実装.若干ひよったためandoに助太刀してもらう.実装後は一発でAC.

17:00~
todoがBを実装.基本的にはただのBFSだが,壁であるかどうかの判定が怪しかった.更にこの時点で完全にtodoがひよってしまい,BFSを冷静に書く事が出来なかった.どうにか組んだもののWA.デバッグしても原因がわからなかったので,Cに移る.

17:30~
Cを解く,問題解析はすでに終わっていて,DPで解けるということが判明していたので,ある程度サクサクと組む.サンプルが通ったため,入力ファイルを落として試してみた所,挙動がおかしい.出力が非常に重い.andoより,関数呼び出し毎にnewするのではなく最初にだけnewすれば無駄に時間がかからない,と助言してもらい修正.AC.

17:55~
Bのデバッグに復帰.冷静に考えた結果,LinkedListをQueueとして使うはずなのに,pushとpopを用いていた.恥ずかしい.addLastとremoveFirstに修正後AC.

18:05~
ここまで来て実装担当のtodoが完全に疲れてしまったので,andoにEの実装を受け渡す.その間,todoとnyamaでDの実装について考える.木構造を作りDFSのように再帰的に重心を更新していけば判定が出来るという所までは分かった.

19:00~
Eのバグがとれずandoダウン.回復したtodoがDの実装を開始する.脳内コーディングは70%以上完了していた&神が降臨したため,尋常ではないスピードでコーディング.重心の更新式の間違いをandoに指摘してもらいつつ実装完了.が,挙動がおかしい.再帰呼び出しの際にxとyを逆にしてしまったのが原因であったが,暫く気付かなかった.その後色々早とちりを修正したらサンプルが通った.入力1はACしたが,焦っていた為入力2に対し入力1の出力を提出してしまいWA.この時点で残り10分を切っていたが,一旦心を落ち着けた後,入力2,3に対してAC.4問正解したのでStandingsを見てほっと一息.残り5分を切っていたのでこれ以上は何もしなかった.

19:31
終了.

■結果
○○○○×××
順位 - 14/288
大学別順位 - 7/68

模擬予選と同じ順位.アジア地区予選進出決定.

これが東京高専の本気(キリリリッ

■感想
模擬予選と同じ順位でほっとしています.もし,本番での順位がもっと低かったら模擬予選での順位はマグレだったという事になるからです.
今回は,実装担当のtodoの調子が中々上がらず,序盤では随分とヘマをしてしまいました.仮に1人でやっていたら,せいぜい2問程度しか解けなかったと思われます.また,全体的に俄か仕込みで臨みましたが,実装をtodo,問題の解析をnyamaとandoと役割を(序盤では)完全に分離したのが功を奏しました.加えて,実装中は(主に)andoにチェックしてもらったのがバグ抑制に繋がりました.単独で実装すると,どうしてもちょっとしたミスが出てきてしまい,そこに気付かずにハマる,というパターンが多いためです.これらはチーム戦特有の作戦だと感じました.また,最後の勝因はラスト30分の追い込みでした.はっきり言って残り30分でDを実装できるとは思いませんでした.もしかしたら,標準的な人間の域を脱することがそろそろ出来るかもしれません.気のせいかもしれませんが.
チームのメンバーにとっても,東京高専全体にとっても,ICPCへの参加は初でしたが,恥ずかしくはない成績だと思います.

…でも,これはあくまで国内予選.

アジア地区予選ではまた別次元ですので,あと5ヶ月でそのレベルまで到達しなければなりません.
各人課題が見えたので,本格的にトレーニングを開始する…ということで….