■Aizu Online Judge
Solved:235/43th■TopCoder/Codeforces
ほとんど参加できていません．そのためレーティングも代わり映えしていません．そのため来月は，レーティングの昇降は兎も角として，出来るだけ参加することを重視しようと思います．■専門書
「計算理論の基礎」を読み進めています．5章辺りを読んでいますが，練習問題に全く手を付けていないため，そちらにも着手する必要がありそうです．また，「コンピュータの数学」は今の自分なら十分読めると判断したため，そろそろ真面目に読もうかと考えている次第です．■0125 Day Count
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
public class Main{
Scanner sc=new Scanner(System.in);;
int INF=1<<28;
double EPS=1e-9;
void run(){
for(;;){
int y1=sc.nextInt();
int m1=sc.nextInt();
int d1=sc.nextInt();
int y2=sc.nextInt();
int m2=sc.nextInt();
int d2=sc.nextInt();
if(y1<0||m1<0||d1<0||y2<0||m2<0||d2<0){
break;
}
int a=day(y1, m1, d1);
int b=day(y2, m2, d2);
println((b-a)+"");
}
}
int day(int y, int m, int d){
int res=0;
int[] days={31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for(int i=0; i<m-1; i++){
res+=days[i];
}
res+=y*365+d-1;
if((m==2&&d<=28)||m==1){
y--;
}
if(y>=0){
res+=y/4+1;
res-=y/100+1;
res+=y/400+1;
}
return res;
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
new Main().run();
}
}
■0121 Seven Puzzle
先に，全てのパターンについて最小ステップ数を計算しておく．BFSで可能．
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
HashMap<Integer, Integer> map;
int[] a;
int w=4, h=2;
void run(){
a=new int[w*h];
init();
for(; sc.hasNext();){
for(int i=0; i<w*h; i++){
a[i]=sc.nextInt();
}
println(""+map.get(id(a)));
}
}
void init(){
LinkedList<S> que=new LinkedList<S>();
map=new HashMap<Integer, Integer>();
que.offer(new S(0, 0, new int[]{0, 1, 2, 3, 4, 5, 6, 7}));
map.put(id(que.peek().a), 0);
int[] dx={0, 0, -1, 1};
int[] dy={-1, 1, 0, 0};
for(; !que.isEmpty();){
S s=que.poll();
int p=s.y*w+s.x;
for(int i=0; i<4; i++){
int x2=s.x+dx[i];
int y2=s.y+dy[i];
int p2=y2*w+x2;
if(x2>=0&&x2<w&&y2>=0&&y2<h){
int[] a2=s.a.clone();
int t=a2[p];
a2[p]=a2[p2];
a2[p2]=t;
S s2=new S(x2, y2, a2);
if(!map.containsKey(id(s2.a))){
que.offer(s2);
map.put(id(s2.a), map.get(id(s.a))+1);
}
}
}
}
}
int id(int[] a){
int res=0;
for(int e : a){
res=res*10+e;
}
return res;
}
class S{
int x, y;
int[] a;
S(int x, int y, int[] a){
this.x=x;
this.y=y;
this.a=a;
}
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
■0120 Patisserie
r1のロールケーキにr2のロールケーキを並べると，import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
int len, n;
int[] a;
void run(){
for(;sc.hasNext();){
String[] ss=sc.nextLine().split(" ");
len=Integer.parseInt(ss[0]);
n=ss.length-1;
a=new int[n];
for(int i=0; i<n; i++){
a[i]=Integer.parseInt(ss[i+1]);
}
solve();
}
}
void solve(){
double[][] dp=new double[1<<n][n];
for(int j=0; j<1<<n; j++){
fill(dp[j], INF);
}
for(int i=0; i<n; i++){
dp[1<<i][i]=2*a[i];
}
for(int s=1; s<1<<n; s++){
for(int j=0; j<n; j++){
if((s>>j&1)==0){
continue;
}
for(int i=0; i<n; i++){
if((s>>i&1)==0){
dp[s|1<<i][i]=min(dp[s|1<<i][i],
dp[s][j]+2*sqrt(a[j]*a[i])-a[j]+a[i]);
}
}
}
}
double min=INF;
for(int i=0; i<n; i++){
min=min(min, dp[(1<<n)-1][i]);
}
println(min<len+EPS?"OK":"NA");
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
■0514 Quality Checking
合格
→3つ共正常
失敗
→2つが正常なら残り1つが失敗
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
void run(){
for(;;){
int na, nb, nc;
na=sc.nextInt();
nb=sc.nextInt();
nc=sc.nextInt();
if((na|nb|nc)==0){
break;
}
int n=sc.nextInt();
int[] as=new int[na];
int[] bs=new int[nb];
int[] cs=new int[nc];
Arrays.fill(as, 2);
Arrays.fill(bs, 2);
Arrays.fill(cs, 2);
R[] rs=new R[n];
for(int i=0; i<n; i++){
int a=sc.nextInt()-1;
int b=sc.nextInt()-na-1;
int c=sc.nextInt()-na-nb-1;
int r=sc.nextInt();
rs[i]=new R(a, b, c, r);
if(r==1){
as[a]=1;
bs[b]=1;
cs[c]=1;
}
}
for(int i=0; i<n; i++){
if(rs[i].r==0){
int a=as[rs[i].a];
int b=bs[rs[i].b];
int c=cs[rs[i].c];
if(a==1&&b==1){
c=0;
}else if(b==1&&c==1){
a=0;
}else if(c==1&&a==1){
b=0;
}
as[rs[i].a]=a;
bs[rs[i].b]=b;
cs[rs[i].c]=c;
}
}
for(int i=0; i<na; i++){
println(as[i]+"");
}
for(int i=0; i<nb; i++){
println(bs[i]+"");
}
for(int i=0; i<nc; i++){
println(cs[i]+"");
}
}
}
class R{
int a, b, c, r;
R(int a, int b, int c, int r){
this.a=a;
this.b=b;
this.c=c;
this.r=r;
}
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
■0231 Dangerous Bridge
時刻aと時刻b-1について調べるだけ．
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
int n;
int[] m, a, b;
void run(){
for(;;){
n=sc.nextInt();
if(n==0){
break;
}
m=new int[n];
a=new int[n];
b=new int[n];
for(int i=0; i<n; i++){
m[i]=sc.nextInt();
a[i]=sc.nextInt();
b[i]=sc.nextInt();
}
solve();
}
}
void solve(){
for(int j=0; j<n; j++){
int sum1=0, sum2=0;
for(int i=0; i<n; i++){
if(a[i]<=a[j]&&a[j]<b[i]){
sum1+=m[i];
}
if(a[i]<=b[j]-1&&b[j]-1<b[i]){
sum2+=m[i];
}
}
if(sum1>150||sum2>150){
println("NG");
return;
}
}
println("OK");
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
コンテストが随分ご無沙汰だったので参加してきました．
Codeforces Round #61 (Div. 2)
A. Petya and Java
面倒だったので，BigIntegerを使って読み込み．実は，入力は必ず正の数なので，負の方向へのチェックは必要ありませんでした…．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);
int INF=1<<28;
double EPS=1e-9;
void run(){
BigInteger b=sc.nextBigInteger();
long[] s={-128, -32768, -2147483648, -9223372036854775808L};
long[] e={127, 32767, 2147483647, 9223372036854775807L};
String[] ss={"byte", "short", "int", "long"};
for(int i=0; i<4; i++){
if(b.compareTo(new BigInteger(s[i]+""))>=0
&&b.compareTo(new BigInteger(e[i]+""))<=0){
println(ss[i]);
return;
}
}
println("BigInteger");
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
public static void main(String[] args){
new A().run();
}
}
B. Petya and Countryside
全探索すればOK．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);
int INF=1<<28;
double EPS=1e-9;
int n;
int[] a;
void run(){
n=sc.nextInt();
a=new int[n];
for(int i=0; i<n; i++){
a[i]=sc.nextInt();
}
int max=0;
for(int j=0; j<n; j++){
int s=1;
for(int i=j-1; i>=0; i--){
if(a[i]<=a[i+1]){
s++;
}else{
break;
}
}
for(int i=j+1; i<n; i++){
if(a[i-1]>=a[i]){
s++;
}else{
break;
}
}
max=max(max, s);
}
println(max+"");
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
public static void main(String[] args){
new B().run();
}
}
C. Petya and File System
書けば通ると思いましたが，落ちてしまいました．D. Petya and His Friends
私が考えたのは以下のやり方．| a1 | a2 | a3 | a4 | … | an |
| 2 | 2 | 2 | 2 | … | |
| 3 | 3 | 3 | … | 3 | |
| 5 | 5 | 5 | … | 5 | |
| 7 | 7 | 7 | … | 7 |
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class D{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
void run(){
int n=sc.nextInt();
if(n==2){
println("-1");
return;
}
BigInteger[] bis=new BigInteger[n];
for(int i=0; i<n; i++){
bis[i]=BigInteger.ONE;
}
int max=1000;
int p=0;
int[] prime=new int[max];
boolean[] isPrime=new boolean[max+1];
Arrays.fill(isPrime, true);
isPrime[0]=isPrime[1]=false;
for(int i=2; i<=max; i++){
if(isPrime[i]){
prime[p++]=i;
for(int j=2*i; j<=max; j+=i){
isPrime[j]=false;
}
}
}
for(int j=0; j<n; j++){
BigInteger bi=new BigInteger(prime[j]+"");
for(int i=0; i<n-1; i++){
bis[(j+i)%n]=bis[(j+i)%n].multiply(bi);
}
}
for(int i=0; i<n; i++){
if(bis[i].toString().length()>100){
println("-1");
return;
}
}
for(int i=0; i<n; i++){
println(bis[i]+"");
}
}
void println(String s){
System.out.println(s);
}
void print(String s){
System.out.print(s);
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
public static void main(String[] args){
new D().run();
}
}
ooxo- 3226p 68位■0212 Highway Express Bus
拡張Dijkstra．ノードを(今いる町, 残りチケット枚数)とする．後は次状態に遷移する際に，チケットを使った場合と使わなかった場合で更新．
import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
public class Main{
Scanner sc=new Scanner(System.in);
int INF=1<<28;
double EPS=1e-9;
int c, n, m, s, g;
LinkedList<E>[] es;
@SuppressWarnings("unchecked")
void run(){
for(;;){
c=sc.nextInt();
n=sc.nextInt();
m=sc.nextInt();
s=sc.nextInt()-1;
g=sc.nextInt()-1;
if((c|n|m|(s+1)|(g+1))==0){
break;
}
es=new LinkedList[n];
for(int i=0; i<n; i++){
es[i]=new LinkedList<E>();
}
for(int i=0; i<m; i++){
int u=sc.nextInt()-1;
int v=sc.nextInt()-1;
int w=sc.nextInt()/10;
es[u].add(new E(v, w));
es[v].add(new E(u, w));
}
solve();
}
}
void solve(){
int[][] d=new int[n][c+1];
PriorityQueue<P> que=new PriorityQueue<P>();
for(int i=0; i<n; i++){
Arrays.fill(d[i], INF);
}
d[s][c]=0;
que.offer(new P(s, c, 0));
for(; !que.isEmpty();){
P p=que.poll();
if(d[p.v][p.c]<p.d){
continue;
}
for(E e : es[p.v]){
if(d[e.to][p.c]>d[p.v][p.c]+e.cost){
d[e.to][p.c]=d[p.v][p.c]+e.cost;
que.offer(new P(e.to, p.c, d[e.to][p.c]));
}
if(p.c>0&&d[e.to][p.c-1]>d[p.v][p.c]+e.cost/2){
d[e.to][p.c-1]=d[p.v][p.c]+e.cost/2;
que.offer(new P(e.to, p.c-1, d[e.to][p.c-1]));
}
}
}
int min=INF;
for(int i=0; i<=c; i++){
min=min(min, d[g][i]);
}
min*=10;
println(""+min);
}
class E{
int to, cost;
E(int to, int cost){
this.to=to;
this.cost=cost;
}
}
class P implements Comparable<P>{
int v, c, d;
P(int v, int c, int d){
this.v=v;
this.c=c;
this.d=d;
}
@Override
public int compareTo(P p){
return d-p.d;
}
}
void debug(Object... os){
System.err.println(Arrays.deepToString(os));
}
void print(String s){
System.out.print(s);
}
void println(String s){
System.out.println(s);
}
public static void main(String[] args){
// System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
new Main().run();
}
}
