Yossi Survivor MAX:codeforces

カテゴリ：codeforces

• Codeforces #119
  [ 2012-05-10 23:17 ]
• ナランハジャグリングまつり(2日目) Codeforces #118
  [ 2012-05-04 23:23 ]
• タピオカうめぇす　Croc Champ Round 2(Unofficial)
  [ 2012-04-20 23:53 ]
• GoogleCodeJam Qualification Roundとcodeforces #115
  [ 2012-04-14 23:34 ]
• 紅の豚とCroc Champ 2012
  [ 2012-04-06 23:11 ]
• 大雪　codeforces #110
  [ 2012-02-29 23:41 ]
• ２度目の発表練習 codeforces #106
  [ 2012-02-10 23:02 ]
• Codeforces #104とかリフレクプラスとか
  [ 2012-01-22 16:57 ]
• codeforcesなんてなかった
  [ 2012-01-19 23:57 ]
• Codeforces #102
  [ 2012-01-12 23:53 ]

Codeforces #119

今日は昼の講義後は、ずっとカービィのエクストラをやっていました。
4面まで終了ですが、4時間ほど。


帰宅後はcodeforcesの準備にとりかかりました。

A問題。僕としては非常に苦手な問題でした。
紐の長さが与えられていて、a,b,cの数値の長さになるように切る。
なるべく沢山切った時の本数を求めよという問題。
つまり短いのを沢山生成しつつも、余りが出ないようにするということ。
1時間ほど悩んで提出した解答は、hackされました。
それを後日提出してみたところ、wrong answer 20。
少し一手間欠けたもののwrong answer 41なので、根本的な書き直しが必要かもしれません。

B問題は、幅と高さが与えられていて、ひし形の数を数える問題。
軸が必ずマス目に並行になります。
これは計算するだけ。

import java.util.Scanner;
public class Test {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int w = input.nextInt();
int h = input.nextInt();
System.out.println(maximum(w,h));
}

public static long maximum(int w,int h){
w += 1;
h += 1;
long count = 0;
for(int i = 3 ; i <= w ; i+=2){
for(int j = 3 ; j <= h ; j+=2){
count += (w-i+1)*(h-j+1);
}
}
return count;
}
}

C問題は、Aの数字の並びからBの数字の並びにする
操作は、Aのいちばんうしろの数字を1個取って、Aのどこかに挿入するということ。
この操作でBにする際の最短回数を求めよという問題。

たとえば 13245 12345であれば、13245→13524→13452→12345と3になります。
どういう法則かといいますと、Bの並びを順に見ていって、Aは1回だけ全部見ていって、
Bの並び順で1個でも該当しなくなった時点で終了ということです。
わかりづらいので例を解説に。

A 13245
B 12345　１は一致する。

A 13245
B 12345　A:3、B:2はダメ

A 13245
B 12345 　２は一致する

A 13245
B 12345　A:4、B:3はダメ

A 13245
B 12345　A:5、B:3はダメ

Aの配列を調べ終わったので終了。

つまり１，２の２つの部分だけ一致するので、
長さの５からこの２を引いた３が答えになります。
オーダですが、Aの配列を読み終わるまでなので、
for文を見ると二重ですが、O(n)です。
非常に高速！それを踏まえてコードを。

import java.util.Scanner;

public class Test {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] bn = new int[n];
int[] an = new int[n];
for(int i = 0 ; i < bn.length ; i++){
bn[i] = input.nextInt();
}
for(int i = 0 ; i < an.length ; i++){
an[i] = input.nextInt();
}
System.out.println(maximum(n,an,bn));
}

public static int maximum(int n,int[] an,int[] bn){
int stindex = 0;
int count = 0;
for(int i = 0 ; i < an.length ; i++){
boolean falseflag = true;
for(int j = stindex ; j < bn.length ; j++){
if(bn[i] == an[j]){
stindex = j+1;
count++;
falseflag = false;
break;
}
}
if(falseflag)break;
}
return an.length-count;
}
}

ナランハジャグリングまつり(2日目) Codeforces #118

今日も並んはジャグリングまつりに参加。
朝はクラブのワークショップに。
うん、やっぱり３つになるとほとんどできない。

ボールの輪に入っていると、
7ボールのエンデュランスどうですかと声かけられたので、
久しぶりに参戦。できないのわかっていたけど。
結局まともに続かず終了。
ジャグリングセールに関しても、お金はほとんど使わないと決めていたのと、
勝利できなかったのとで何も買わず。

10秒コンテストですが、うーん、まあ微妙なジャッジでした。
致し方ないのかもしれませんが・・・ね。
私だけでなく、知り合いも納得してなかったです。

夕方までにかけてはディアボロなども触ってみました。
後はシャッフルに関しての極め方について、詳しい方に教えてもらいました。

夜は友人と池袋のゲーセンへ。
さすがGW中、どこも混んでいて、プレーできる状況にありませんでした。
諦めてラーメン二郎へ。
これも、早めに行ったからよかったものの、後10分遅ければ高校生の団体のあとになり、
混み混みになっていました。

さっそく食べる。が、思ったより箸が進まず、結局スープは飲まずに行きました。
歳かなあ・・・。



その後はmayoさんが代表のぁ～んの6周年記念記念イベントのニコ生を見ました。
テルさんとPocariさんの対談って、やっぱりいろいろな意味ですごい。
特にPocariさんがラスベガス中継とかありえん！と。
TypeRacerについて結構テルさんが熱く語ってました。
あれって今そんなに流行ってるのかーと最認識させられました。
後、キーボード紹介で金持ちーとか言われましたが、まったくの誤解です。
確かにリアフォ3台、HHKB Pro無刻印はありますが・・・。

タイパー(過去形)だもの、キーボードに7万かけてなにがわるいっ！

そして夜はcodeforcesへ。

A問題　文字列が２つ与えられていて、
１つめから１回だけ入れ替えを行なって２つ目にできるかどうかという話。入れ替え回数が無制限でも、Pretestは通ってしまったので、それでhackされた。
直したソースを。

import java.util.Scanner;

    public class Test {
            public static void main(String args[]){
            Scanner input = new Scanner(System.in);
                    String s = input.nextLine();
                    String t = input.nextLine();
                    System.out.println(maximum(s,t));
            }
            
          public static String maximum(String s,String t){
          int[] ss = new int[26];
          int[] ts = new int[26];
          for(int i = 0 ; i < s.length() ; i++){
          ss[s.charAt(i)-97]++;
          }
          for(int i = 0 ; i < t.length() ; i++){
          ts[t.charAt(i)-97]++;
          }
          boolean isng = false;
          for(int i = 0 ; i < ss.length ; i++){
          if(ss[i] == ts[i]){
          continue;
          }else{
          isng = true;
          break;
          }
          }
      int differ = 0;
          if(s.length() != t.length()){
          isng = true;
          }else{
          for(int i = 0 ; i < s.length(); i++){
          if(s.charAt(i) != t.charAt(i))differ++;
          }
          }
          if(isng || differ > 2){
          return "NO";
          }else{
          return "YES";
          }
          }
    }

B問題。前半戦がt1、後半戦がt2与えられていて、
前半戦と後半戦の間に、値がk%になってしまう。
最大値となるように戦略を考え、値の大きい順に、人数番号も含めて提出せよ。

import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Scanner;

    public class Test {
            public static void main(String args[]){
            Scanner input = new Scanner(System.in);
                   int n = input.nextInt();
                   int t1 = input.nextInt();
                   int t2 = input.nextInt();
                   int k = input.nextInt();
                   int[] a = new int[n];
                   int[] b = new int[n];
                   for(int i = 0 ; i < n ; i++){
                   a[i] = input.nextInt();
                   b[i] = input.nextInt();
                   }
                    maximum(n,t1,t2,k,a,b);
            }
            
          public static void maximum(int n,int t1,int t2,int k,int[] a,int[] b){
          double[] swapped = new double[n];
          for(int i = 0 ; i < n ; i++){
          swapped[i] = Math.max((double)b[i]*t1*((double)(100-k)/100)+a[i]*t2,(double)a[i]*t1*((double)(100-k)/100)+b[i]*t2);
          }
          while(true){
              double max = -1;
              int index = -1;
              boolean flag = true;
              for(int i = 0 ; i < swapped.length ; i++){
              if(max < swapped[i]){
              index = i;
              flag = false;
              max = swapped[i];
              }
              }
              if(flag)break;
              BigDecimal bd = new BigDecimal(max);
              BigDecimal bd4 = bd.setScale(2, BigDecimal.ROUND_HALF_UP);
              System.out.println((index+1)+" "+bd4);
              swapped[index] = -1;
          }
          }
    }

戦略は両方共計算してみて大きい方を取る。それだけ。後は誤差に気をつける。
インデックスを記憶してソート。

C問題
上三角形の中に下三角形を、下三角形の中に上三角形をn回入れるという動作を行う。上三角形となるような数を求めよ。
これは法則を探して漸化式を使って式を簡略化できる。
譬えばa[n]をn回目における上三角形の数、b[n]をn回目における下三角形の数とすると

a[n+1] = 3*a[n]+b[n]
b[n+1] = a[n]+3*b[n]
両方を足すと　a[n+1]+b[n+1] = 4*(a[n]+b[n])となる。
a[n]+b[n] = 4^n
両方を引くと　a[n+1]-b[n+1] = 2*(a[n]-b[n])となる。
a[n]-b[n] = 2^n
これらを足すと　2*a[n] = 4^n+2^n = 2^n(2^n+1)
a[n] = 2^n(2^n+1)/2　が答えとなる。

つまり、n=1 で答えが2*3/2 = 3 、 n=2 で答えが4*(4+1)/2 = 10　となり、辻褄が合う。

後ほどmod(1000000007)をしたら通った。死にたい。

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

    public class Test {
            public static void main(String args[]){
            Scanner input = new Scanner(System.in);
                   String s = input.nextLine();
                    maximum(s);
            }
            
          public static void maximum(String s){
          BigInteger a = new BigInteger(s);
          BigInteger b = new BigInteger("2");
          BigInteger mode = new BigInteger("1000000007");
          BigInteger d = new BigInteger("1");
          //BigInteger c = b.modPow(a,mode);
          BigInteger cs = b.modPow(a,mode);
          //System.out.println((c.multiply(c.add(d))).divide(b));
          if(cs.multiply(cs.add(d)).compareTo(d) <= 0){
              System.out.println(cs.multiply(cs.add(d)).mod(mode));
          }else{
          System.out.println(cs.multiply(cs.add(d)).divide(b).mod(mode));
          }
          
              //1000000007
          }

    }

結局Bしか合っていないのでレートはガタ落ちです。泣きそう。

タピオカうめぇす Croc Champ Round 2(Unofficial)

タピオカは全然関係ありません。今日は仕事でした。
お昼はうどんが安かったのでうどんに。


夜はゲーセン。某ゲーセンでこんなものがかざってありました。
発泡スチロールでできているんだとか。



ビーマニを中心にプレー。
タピオカウメェスの(H)で２連続２曲目落ちする屈辱を味わう。
あの全押しはやばい。

後は激唱のhardの連打部分を粘っていましたが、マナーの悪い二人客に占拠されたので
諦めて地元ゲーセンでプレーすることにした。
基本的に筐体の前に一人プレーするのを見ていて、並んでいない状態はマナー違反です。
僕としてはプレー中の人がひとりいて、もう一人はギャラリーだという認識だったのですが、
彼らが交代でプレーしていたので、気分が悪くなりました。




ということで地元でようやく激唱hardのPerfectを達成。長かった。
ついでにサイハテGreat

しっかりお決まりの運動もした後でCodeforcesのCroc Champ Round 2　非公式に参加。


A問題
すでに長方形の３つの点が与えられているので、残り１点の座標を求めよ。
ただし斜めは考慮しなくて良い。

import java.util.Scanner;

    public class Test {
            public static void main(String args[]){
            Scanner input = new Scanner(System.in);
                    int row = input.nextInt();
                    int col = input.nextInt();
                    String[] map = new String[row];
                    for(int i = 0 ; i < row ; i++){
                    map[i] = input.next();
                    }
                    maximum(row,col,map);
            }
            
          public static void maximum(int row,int col,String[] map){
          int[] x = new int[3];
          int[] y = new int[3];
          int lx = -1;
          int ly = -1;
          int count = 0;
          for(int i = 0 ; i < map.length ; i++){
          for(int j = 0 ; j < map[i].length(); j++){
          if(map[i].charAt(j) == '*'){
          x[count] = j;
          y[count] = i;
          count++;
          }
          }
          }
          Arrays.sort(x);
          Arrays.sort(y);
          if(x[0] == x[1]){
          lx = x[2];
          }else{
          lx = x[0];
          }
          if(y[0] == y[1]){
          ly = y[2];
          }else{
          ly = y[0];
          }
          System.out.println((ly+1)+" "+(lx+1));  
          }
    }
 

B問題
２次元座標の点が与えられていて、A_x<=B_x<=C_x A_y<=B_y<=C_yを満たす
３つの点の組の数を求めよ

点が３０００個あるので、総当りすると
3000C3＝4,495,501,000でちょっと間に合いません。
結局解法が思いつかず、残り１時間あったのですが諦めて風呂に行きました。

GoogleCodeJam Qualification Roundとcodeforces #115

今日は朝8時から待ちに待ったGoogle Code JamのQualification Roundです。
なんと今日はGoogle Code Jam + codeforces + AtCoderという
プログラミングコンテストの日です。
忘れちゃいけないのは今日が情報処理試験の前日だということ。
ひどいものです（えっ

Google Code Jamは見た感じAもBもCも解けそうだったので解いていった。
しかしAは得点が高そうだったのでB→C→Aの順番で。
実際はAが一番簡単でした。

予選通過したかどうか判明したのは翌日の１５日ですが、
取り敢えず　o oo oo -- の60ptsで792位通過でした。

A問題

暗号の対応関係を見るだけ。問題文にもヒントがあることを見落とさないように。
1文字だけテストケースと問題文じゃわからない対応関係があるので、それだけ
残りの文字から判明させる。

非常につまらないソースですが。

import java.util.*;
import java.io.*;

public class Test {

public void dor() throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/A-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
input.nextLine();
for(int i = 0 ; i < n ; i++){
String s = input.nextLine();
pw.println("Case #"+(i+1)+": "+num(s));
}
input.close();
pw.flush();
pw.close();
}

public static String num(String s){
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < s.length() ; i++){
if(s.charAt(i) == ' '){
sb.append(' ');
}else if(s.charAt(i) == 'a'){
sb.append('y');
}else if(s.charAt(i) == 'b'){
sb.append('h');
}else if(s.charAt(i) == 'c'){
sb.append('e');
}else if(s.charAt(i) == 'd'){
sb.append('s');
}else if(s.charAt(i) == 'e'){
sb.append('o');
}else if(s.charAt(i) == 'f'){
sb.append('c');
}else if(s.charAt(i) == 'g'){
sb.append('v');
}else if(s.charAt(i) == 'h'){
sb.append('x');
}else if(s.charAt(i) == 'i'){
sb.append('d');
}else if(s.charAt(i) == 'j'){
sb.append('u');
}else if(s.charAt(i) == 'k'){
sb.append('i');
}else if(s.charAt(i) == 'l'){
sb.append('g');
}else if(s.charAt(i) == 'm'){
sb.append('l');
}else if(s.charAt(i) == 'n'){
sb.append('b');
}else if(s.charAt(i) == 'o'){
sb.append('k');
}else if(s.charAt(i) == 'p'){
sb.append('r');
}else if(s.charAt(i) == 'q'){
sb.append('z');
}else if(s.charAt(i) == 'r'){
sb.append('t');
}else if(s.charAt(i) == 's'){
sb.append('n');
}else if(s.charAt(i) == 't'){
sb.append('w');
}else if(s.charAt(i) == 'u'){
sb.append('j');
}else if(s.charAt(i) == 'v'){
sb.append('p');
}else if(s.charAt(i) == 'w'){
sb.append('f');
}else if(s.charAt(i) == 'x'){
sb.append('m');
}else if(s.charAt(i) == 'y'){
sb.append('a');
}else if(s.charAt(i) == 'z'){
sb.append('q');
}
}
return sb.toString();
}

public static void main(String[] args) throws Exception{
(new Test()).dor();
}


}

B問題
3人の審判がいる。3人の出すスコアは似通っていて0-10である。
2点以上の差があれば驚くべきスコアとなる。2点より差が大きくなることはない。
基準点pと演者の人数Nと驚くべきスコアの数Sと演者の得点a[0]・・・a[N-1]が与えられていて、
基準点p以上のスコアを出した審判が存在する演者の最大値を答えなさい。

重要なのは4通りに分類すること。

・そもそもの平均点がp以上である
・平均点はpより1低いけど、驚くべきスコアがなくてもp以上を出す審判がいる
・驚くべきスコアを使わないとp点以上に行かない
・そもそも無理

import java.util.*;
import java.io.*;

public class Test {

public void dor() throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/B-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
for(int i = 0 ; i < n ; i++){
int N = input.nextInt();
int S = input.nextInt();
int P = input.nextInt();
int[] person = new int[N];
for(int j = 0 ; j < N ; j++){
person[j] = input.nextInt();
}
pw.println("Case #"+(i+1)+": "+num(N,S,P,person));
}
input.close();
pw.flush();
pw.close();
}

public static int num(int N,int S,int P,int[] person){
Arrays.sort(person);
int mone = 0;
//int mtwo = 0;
int oks = 0;
int preoks = 0;
for(int i = 0 ; i < person.length ; i++){
if(person[i]/3 == 0){
if(P == 2){
if(person[i] == 2)mone++;
}else if(P == 1){
if(person[i] >= 1){
preoks++;
}
}else if(P == 0){
preoks++;
}
}else if(person[i]/3 >= P || (person[i]/3 >= P-1 && person[i] % 3 == 1) || (person[i]/3 >= P-1 && person[i] % 3 == 2)){
oks = person.length-i;
break;
}else if(person[i]/3 >= P-1){
mone++;
}else if(person[i]/3 >= P-2 && person[i] % 3 == 2){
mone++;
}
}
oks += preoks;
if(S <= mone){
oks += S;
}else{
oks += mone;
}
return oks;
}

public static void main(String[] args) throws Exception{
(new Test()).dor();
}


}

C問題　リサイクル数の定義　たとえば12345と34512はリサイクル数。
前からn文字を後ろにくっつけた数をリサイクル数の組と表現する。
この組の数がAからBの範囲内で何組あるか答える。

１，数字を前から順番に調べていく
２，その数字の先頭を後ろにつけるという作業をもとの数字に戻るまで行う
３，この数字がA以上B以下に収まっていて、かつ今調べている数字より大きな数であれば組として加える

たとえば 1234と3412の例

1234,2341 1234, 3412 1234, 4123は組である
3412,4123は組であるが、3412,1234 3412,2341は上記に重複するのでダメ。
ということ。3つ目の条件が超重要である。

boolean型の配列を用意してわざわざやっていましたが、
3つ目の条件を使えばこれは不要です。

import java.util.*;
import java.io.*;

public class Test {

public void dor() throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/C-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int n = input.nextInt();
for(int i = 0 ; i < n ; i++){
int A = input.nextInt();
int B = input.nextInt();
boolean[] ispaired = new boolean[B+1];
pw.println("Case #"+(i+1)+": "+num(A,B,ispaired));
}
input.close();
pw.flush();
pw.close();
}

public static int num(int A,int B,boolean[] ispaired){
int count = 0;
for(int i = A ; i <= B ; i++){
StringBuilder sb = new StringBuilder(i+"");
boolean same = false;
ispaired[i] = true;
while(!same){
sb.append(sb.charAt(0));
sb.deleteCharAt(0);
if(Integer.parseInt(sb.toString()) == i){
same = true;
}else if(A <= Integer.parseInt(sb.toString()) && Integer.parseInt(sb.toString()) <= B && sb.charAt(0) != '0' && !ispaired[Integer.parseInt(sb.toString())]){
count++;
}
}
}
return count;
}

public static void main(String[] args) throws Exception{
(new Test()).dor();
}
}


その後はcodeforcesへ。

A問題　数字の文字列を３つに分類して、最高値になるようにせよ。
ただし、先頭が0は認めず、かつ1000000以下になるものとする。
区切り用のfor文を二重に回してO(n^2)オーダで可能。
nが30しかないので、総当りで問題ない。


import java.util.Scanner;

public class Test {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
String s = input.nextLine();
System.out.println(maximum(s));


}

public static int maximum(String s){
if(s.length() <= 2)return -1;
int maximum = -1;
for(int i = 1 ; i < s.length()-1 ; i++){
for(int j = 2 ; j < s.length(); j++){
if(i >= 8 || j-i >= 8 || s.length()-j >= 8 || i >= j)continue;
String first = s.substring(0,i);
String second = s.substring(i,j);
String third = s.substring(j,s.length());
//System.out.println(i+","+j);
if((first.charAt(0) == '0' && first.length() >= 2) || (second.charAt(0) == '0' && second.length() >= 2) || (third.charAt(0) == '0' && third.length() >= 2))continue;
int firstnum = Integer.parseInt(first);
int secondnum = Integer.parseInt(second);
int thirdnum = Integer.parseInt(third);
if(firstnum > 1000000 || secondnum > 1000000 || thirdnum > 1000000)continue;
int tmp = firstnum+secondnum+thirdnum;
//System.out.println(firstnum+","+secondnum+","+thirdnum);
maximum = Math.max(tmp, maximum);
}
}
return maximum;
}
}

B問題
名前と得点が与えられている。
その得点が
上位50%以下ならnoob
上位20%以下～50%より大きいならrandom
上位10%以下～20%より大きいならaverage
上位1%以下～10%より大きいならhardcore
上位1%より大きいならpro

名前とスコアは同一人物で複数個あることもあり、
それらに関しては一番大きいスコアを取る。
まずはこれの判定が必要。
pairを使いたくなかったので、名前とスコアにそれぞれArrayListで動的に配列を用意した。
それらについて調べて、スコアが負けていたらカウントするといった方式です。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Test {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
//input.nextLine();
ArrayList list = new ArrayList();
ArrayList score = new ArrayList();
for(int i = 0 ; i < n ; i++){
String name = input.next();
int sc = input.nextInt();
if(list.contains(name)){
int tscore = score.get(list.indexOf(name));
tscore = Math.max(tscore,sc);
score.remove(list.indexOf(name));
score.add(list.indexOf(name),tscore);
}else{
list.add(name);
score.add(sc);
}
}
maximum(list,score);


}

public static void maximum(ArrayList list,ArrayList score){
int size = list.size();
System.out.println(size);
for(int i = 0 ; i < list.size(); i++){
int noob = 0;
for(int j = 0 ; j < list.size() ; j++){
if(score.get(i) < score.get(j))noob++;
}
double lost = ((double)noob/(double)size)*100;
if(lost > 50){
System.out.println(list.get(i)+" "+"noob");
}else if(lost <= 50 && lost > 20){
System.out.println(list.get(i)+" "+"random");
}else if(lost <= 20 && lost > 10){
System.out.println(list.get(i)+" "+"average");
}else if(lost <= 10 && lost > 1){
System.out.println(list.get(i)+" "+"hardcore");
}else{
System.out.println(list.get(i)+" "+"pro");
}
}
}
}


C問題は問題文をちゃんと把握していなかったか、wrong answer 3でした。
あ、今でも理由はわかっていません。

n点のブロックがm個あるというのがいくつかあって
ボーナスポイントがnターン後に増えるといった仕様。
ブロックの取り方によってスコアの最大値が変わるので、そのなかの最大値を返せ。

ターン数のほうが多い時は、
序盤スコアが低いのを取っていって、
終盤スコアが高いの取るだけじゃないかと思っているのですが。

ブロックの方が多い場合は、ターンが終わる時に
低いブロックだけ残るように取るといった具合だと思っています。

終了後はご飯を食べてAtCoderに参戦！とおもったのですが、
サーバーが落ちてしまい、結局コンテストなしとなりました。
記念すべき１回でした。
開始時に集中するアクセスの分散などを適切に行わないと厳しそうです。

その後は午後の参考書をようやく読み始める。こんなんで受かるのかすら怪しいです。
４時ぐらいまで粘って寝る。

紅の豚とCroc Champ 2012

今日もひたすら日記を書いていました。
去年8月あたりを漸く書き終えたといったところ。実はこの辺は大変心が折れた時期でした。

夜は紅の豚を見る。実は初めてです。
時代描写が多い感じですね。感動！って感じのものではなかったです。
フィオがいいキャラしてましたね。

テストもしないでリリースだのホワイト企業だの、なんかアレな発想ばっかりでしたが（笑）


後は足早に運動を済ませる。
最近Break DownよりもBaby love meのほうが元凶に思えます。
あれ難しいですし・・・。

Level100プロジェクトを見た限りではこうなっています
baby love me 82
break down 83
stay 86
waka laka 88

ですが、フルコン難易度としては
stay = waka laka < break down < baby love meです。
stay と waka lakaは初見は厳しいかもしれませんが、
同時押しの部分を把握すればかなり楽です。
baby love meは地団駄と同方向八部押し＋押しづらい両足の絡みがあるので、
だいたい乙女☆道をやるとここでコンボが切れます。最悪落ちることも・・・。

後はcodeforcesのCroc Champについて。

ということでAを解く。ジャンケンでAの人がある順番に出す、Bの人もある順番に出す
この状況でn回戦行った時に、負けた回数を出力する。

import java.util.Arrays;
import java.util.NoSuchElementException;
import java.util.Scanner;

public class Test {
static StringBuilder sb = new StringBuilder();
static boolean isnew = true;
static boolean ssharp;
static int count = 0;
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int round = input.nextInt();
String nik = input.next();
String pol = input.next();
janken(round,nik,pol);

}

public static void janken(int round, String nik, String pol){
int nikl = nik.length();
int poll = pol.length();
int nikc = 0;
int polc = 0;
int lcms = (nikl*poll)/gcd(nikl,poll);
if(round <= lcms){
for(int i = 0 ; i < round ; i++){
int nikb = i % nikl;
int polb = i % poll;
if((nik.charAt(nikb) == 'P' && pol.charAt(polb) == 'R') || (nik.charAt(nikb) == 'S' && pol.charAt(polb) == 'P') || (nik.charAt(nikb) == 'R' && pol.charAt(polb) == 'S')){
polc++;
}else if((nik.charAt(nikb) == 'R' && pol.charAt(polb) == 'P') || (nik.charAt(nikb) == 'P' && pol.charAt(polb) == 'S') || (nik.charAt(nikb) == 'S' && pol.charAt(polb) == 'R')){
nikc++;
}
}
}else{
for(int i = 0 ; i < lcms ; i++){
int nikb = i % nikl;
int polb = i % poll;
if((nik.charAt(nikb) == 'P' && pol.charAt(polb) == 'R') || (nik.charAt(nikb) == 'S' && pol.charAt(polb) == 'P') || (nik.charAt(nikb) == 'R' && pol.charAt(polb) == 'S')){
polc++;
}else if((nik.charAt(nikb) == 'R' && pol.charAt(polb) == 'P') || (nik.charAt(nikb) == 'P' && pol.charAt(polb) == 'S') || (nik.charAt(nikb) == 'S' && pol.charAt(polb) == 'R')){
nikc++;
}
}
//System.out.println(lcms);
int nokori = round % lcms;
polc = polc * (round/lcms);
nikc = nikc * (round/lcms);
for(int i = 0 ; i < nokori ; i++){
int nikb = i % nikl;
int polb = i % poll;
if((nik.charAt(nikb) == 'P' && pol.charAt(polb) == 'R') || (nik.charAt(nikb) == 'S' && pol.charAt(polb) == 'P') || (nik.charAt(nikb) == 'R' && pol.charAt(polb) == 'S')){
polc++;
}else if((nik.charAt(nikb) == 'R' && pol.charAt(polb) == 'P') || (nik.charAt(nikb) == 'P' && pol.charAt(polb) == 'S') || (nik.charAt(nikb) == 'S' && pol.charAt(polb) == 'R')){
nikc++;
}
}
}
System.out.println(nikc+" "+polc);
}

public static int gcd(int x,int y){
int r;
while((r = x % y) != 0){
x = y;
y = r;
}
return y;
}


}

頑張ってlcmとか求めちゃっていましたが、実はいらなかったらしいです。

B問題は秘密の部屋ネタ。Chamberって部屋なんですね。チャンバラかと（違
ヴォルデモートの気持ちになってハリーたちを邪魔しましょうという問題（え
石化させるバジリスクだか何かが右下にいて、左を向いている。
この光を4方向反射させる何かをおける位置が決まっていて、
最低何箇所置けば左上に届かせることが出来るか。出来ないなら-1を返せ

作っては見たものの、再帰でスタックオーバーフローを起こしてダメでした。

大雪 codeforces #110

今日は朝見てみたら雪が降り積もっていて荒れ模様でした。
近所の子供がわーいゆきだゆきだーとか言うけど、まったく嬉しくありません。
それどころか靴がびしょぬれになって非常に憎いです。
なぜこんな日に限って仕事が・・・。

ということでお昼はきのこペペロンチーノで。これが大好きです。
（３月現在はもうやっていません）



夜は雪も解けていてわりとまともになっていたので、ゲーセンへ。



が、ゲーセンでイヤホンのイヤーピースが両方共なくなりました。
片方は後々見つかりましたが、もう片方は完全に落としたようです。
とても残念でした。

そしてcodeforces#110をレジストして開始。

A問題　そのマス目の行と列をみて列のほうが多い部分を数えるだけ。

import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[][] math = new int[n][n];
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
math[i][j] = input.nextInt();
}
}
System.out.println(lucky(n,math));
}

public static int lucky(int n,int[][] math){
int count = 0;
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < n ; j++){
int col = 0;
int row = 0;
for(int k = 0 ; k < n ; k++){
col += math[i][k];
row += math[k][j];
}
if(row > col)count++;
}
}
return count;
}

}

B問題。
赤と青でターゲットのように塗りつぶす。
一番外側は青で固定。交互に塗りつぶした時の赤の面積を求める。

import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] circles = new int[n];
for(int i = 0 ; i < n ; i++){
circles[i] = input.nextInt();
}
System.out.println(lucky(n,circles));
}

public static double lucky(int n,int[] circles){
Arrays.sort(circles);
double sum = 0;
int count = 0;
for(int i = circles.length-1 ; i >= 0 ; i--){
if(count % 2 == 0){
sum += (circles[i]*circles[i]);
}else{
sum -= (circles[i]*circles[i]);
}
count++;
}
return Math.PI*sum;
}

}

C問題　any end of the stringの解釈を間違える。
実はこれ、始まりと終わり両方を指すというオチ。

最後に文字を付け加える、もしくは最初か最後の文字を消すもしくは文字を変更する
これらの動作を１ターン１回として行い、与えられた文字列から目的の文字列を部分列として出すのに
最少何回かかるかを求める。

D問題　読んだけど無理。
容疑者を指す番号と容疑者でないを指す番号があって、
それぞれが主張している。　何人の容疑者がいて、何人が正しいことを言っているかだけわかる。
その人が嘘を言っているか本当のことを言っているか、それとも判別できないか
それぞれ判定せよ。

２度目の発表練習 codeforces #106

今日は強制的に２度目の発表練習に行くことになりました。
前回の発表内容の資料の訂正も含めて、発表したところ、やはり２分オーバーでした。
終了後は提出した文章の校正が返って来ました。
これから相当な編集を要すると思われます。

夕方はジャングルスピードを持ってきていたので、友人３人でバトル。
最終的にはヒューマンアタックとか訳のわからない攻撃が入るようになっていました。
コワイコワイ。

夜は他の友人とスノボの日程決めなどをしつつ、千葉某所のサイゼリヤへ。

ミラノ風ドリアだけ食べて、少しゲーセンに居た後に帰宅へ。

ぎりぎりcodeforcesのRegisterに間に合った。
A問題
大きい順にソートして、規定数以上になるまでの要素をカウントするだけ。
import java.util.Arrays;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int k = input.nextInt();
int month[] = new int[12];
for(int i = 0 ; i < 12 ; i++){
month[i] = input.nextInt();
}
System.out.println(lucky(k,month));
}

public static int lucky(int k,int[] month){
if(k == 0)return 0;
Arrays.sort(month);
int count = 0;
for(int i = 11 ; i >= 0 ; i--){
count++;
k -= month[i];
if(k <= 0)break;
}
if(k > 0){
return -1;
}
return count;
}

}

B問題。進数を扱う問題。どっかでミスってhackされた。
C問題。チーム分け。多い順にソートして順番に取っていくだけだったらしい。

という訳で全く出来はよくありませんでした。

Codeforces #104とかリフレクプラスとか

今日は16時にcodeforcesがありましたので参加しました。

A問題
4と7だけ含むチケットをラッキーとする。
前半の半分の数値と後半の半分の数値の合計が一致する条件を付け加えて、
そのチケットがラッキーかどうかを判別しろという問題。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
input.nextLine();
String s = input.nextLine();
System.out.println(lucky(n,s));
}

public static String lucky(int n,String s){
for(int i = 0 ; i < s.length(); i++){
if(!(s.charAt(i) == '4' || s.charAt(i) == '7'))return "NO";
}
String front = s.substring(0,n/2+1);
String last = s.substring(n/2,s.length());
int fsum = 0;
int lsum = 0;
for(int i = 0 ; i < n/2 ; i++){
fsum += Character.digit(front.charAt(i),10);
lsum += Character.digit(last.charAt(i),10);
}
if(fsum == lsum)return "YES";
return "NO";
}
}

B問題
ある数aとラッキーナンバーbが与えられている。
マスクという法則があり、3403790などの数字から4と7だけとってきたものである。（例は47）
a以上の数値でマスクしてbというラッキーナンバーになる最小の値を求めるプログラムを作る。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int a = input.nextInt();
int b = input.nextInt();
System.out.println(lucky(a,b));
}

public static int lucky(int a,int b){
a+=1;
while(true){
StringBuilder sb = new StringBuilder();
String s = String.valueOf(a);
for(int i = 0 ; i < s.length() ; i++){
if(s.charAt(i) =='4' || s.charAt(i) == '7'){
sb.append(s.charAt(i));
}
}
if(sb.length() != 0 && Integer.parseInt(sb.toString()) == b)return a;
a++;
}
}
}

C問題
ラッキーナンバーaとbが与えられている。
aに操作を加えbにする。
aにできる操作は、4を7にしたり7を4にしたり、aのある桁とある桁の数をチェンジするといったことである。
これらの操作を加えてbにするときの最少の回数を求める。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
String a = input.nextLine();
String b = input.nextLine();
System.out.println(lucky(a,b));
}

public static int lucky(String a,String b){
int a4sum = 0;
int a7sum = 0;
int b4sum = 0;
int b7sum = 0;
int f47 = 0;
int f74 = 0;
for(int i = 0 ; i < a.length() ; i++){
if(a.charAt(i) == '4'){
a4sum++;
}else{
a7sum++;
}
if(b.charAt(i) == '4'){
b4sum++;
}else{
b7sum++;
}
if(a.charAt(i) == '4' && b.charAt(i) == '7'){
f47++;
}
if(a.charAt(i) == '7' && b.charAt(i) == '4'){
f74++;
}
}
int gosa = Math.abs(a4sum-b4sum);
return Math.min(f47, f74)+gosa;
}
}

D問題（時間内は失敗し、その後提出）

4の数、7の数、47の数、74の数が与えられている。
これらを満たす最少のラッキーナンバーを求めよ。存在しない場合は-1を返せ。

条件分岐の問題です。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int a = input.nextInt();
int b = input.nextInt();
int c = input.nextInt();
int d = input.nextInt();
System.out.println(lucky(a,b,c,d));
}

public static String lucky(int a,int b,int c,int d){
if(c == d){
if(Math.min(a, b) >= (c+1)){//ok
StringBuilder s = new StringBuilder();
int r47 = c-1;
int pkt4 = a-2-r47;
int pkt7 = b-2-r47+1;
for(int i = 0 ; i < pkt4 ; i++){
s.append(4);
}
for(int i = 0 ; i < r47 ; i++){
s.append(47);
}
s.append(47);
for(int i = 0 ; i < pkt7 ; i++){
s.append(7);
}
s.append(4);
return s.toString();

}else if(Math.min(a, b) == c){
if(a == b)return "-1";
StringBuilder s = new StringBuilder();
if(a == c){
s.append(7);
for(int i = 0 ; i < c ; i++){
s.append(47);
}
int res7 = b-c-1;
for(int i = 0 ; i < res7 ; i++){
s.append(7);
}
return s.toString();
}else if(b == c){
int res4 = a-c-1;
for(int i = 0 ; i < res4 ; i++){
s.append(4);
}
for(int i = 0 ; i < c ; i++){
s.append(47);
}
s.append(4);
return s.toString();
}
return "-1";
}else{
return "-1";
}
}

if((a+b) <= (c+d) || Math.abs(c-d) >= 2 || Math.min(a, b) < Math.max(c, d)){
return "-1";
}else{
if(c > d){
int pkt4 = a-c;
int pkt7 = b-c;
StringBuilder s = new StringBuilder();
for(int i = 0 ; i < pkt4 ; i++){
s.append(4);
}
for(int i = 0 ; i < c ; i++){
s.append(47);
}
for(int i = 0 ; i < pkt7 ; i++){
s.append(7);
}
return s.toString();
}else{
int pkt4 = a-d;
int pkt7 = b-d;
StringBuilder s = new StringBuilder();
for(int i = 0 ; i < d ; i++){
if(i != d-1){
s.append(74);
if(i == 0){
for(int j = 0 ; j < pkt4 ; j++){
s.append(4);
}
}
}else{
s.append(7);
for(int j = 0 ; j < pkt7 ; j++){
s.append(7);
}
s.append(4);
}
}
return s.toString();
}
}
}
}

3問解けたので、レーティングは上昇しました。

後はリフレクを少々。

codeforcesなんてなかった

昨日帰っていないのと、酒飲みだったのとで、参加を見送りました。
といいたいところですが、実際は参加登録を忘れていました。
なのでこの件はA問題だけ皆で問題を読みつつ解いて、たこ焼きを食べつつ人狼をやりました。

A問題だけ軽く。
最初の人が身長が一番高く、最後の人が一番身長が低ければok。
つまり最小値となる人と最大値となる人のインデックスを見つけて、入れ替えていくだけ。
入れ替える制約として隣の人としかできないので、そこに注意するぐらいか。

import java.math.BigDecimal;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int[] soldiers = new int[n];
for(int i = 0 ; i < n ; i++){
soldiers[i] = input.nextInt();
}
System.out.println(plate(n,soldiers));
}

public static int plate(int n,int[] soldiers){
int min = 999999999;
int max = -1;
int minindex = -1;
int maxindex = -1;
int sum = 0;
for(int i = 0 ; i < soldiers.length ; i++){
if(min >= soldiers[i]){
min = soldiers[i];
minindex = i;
}
if(max < soldiers[i]){
max = soldiers[i];
maxindex = i;
}
}
if(minindex < maxindex){
sum = maxindex+(soldiers.length-1-minindex)-1;
}else{
sum = maxindex+(soldiers.length-1-minindex);
}
return sum;
}
}

人数が少ない（５人）ので、一人二役にしたところ、超絶カオスなゲームになっていました。
自分とか占い師＋人狼というすごい組み合わせに。最後ミスったせいで、ばれてしまいましたが、
うまくやれば人狼側の勝利に導けました。ざんねん！



朝に頃合いを見計らって帰宅し、畳み込み積分に悩まされる一日でした。

Codeforces #102

朝帰りして、後は原稿を書く。
しかし、帰宅後に実験で動かしていたデスクトップPCが自動的に再起動していたことが発覚する。
その実験データをRAMDISKに保存していたのですべて飛びました。あはは・・・。

夜はcodeforces #102に参加。

A問題は愚直に斜め１行目２行目１列目２列目の合計がいくつと指定されていて、
その条件に当てはまるマス目の組み合わせを求める問題。
実装が面倒。できない場合は-1を返す。ちなみに一桁のみ。

import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int r1 = input.nextInt();
int r2 = input.nextInt();
int c1 = input.nextInt();
int c2 = input.nextInt();
int d1 = input.nextInt();
int d2 = input.nextInt();
plate(r1,r2,c1,c2,d1,d2);
}

public static void plate(int r1,int r2,int c1,int c2,int d1,int d2){
int f1 = 0;
int f2 = 0;
int f3 = 0;
int f4 = 0;
boolean isOk = false;
for(int i = 1 ; i <= 9 ; i++){
for(int j = 1 ; j <= 9 ; j++){
for(int k = 1 ; k <= 9 ; k++){
for(int l = 1 ; l <= 9 ; l++){
if(i == j || i == k || i == l || j == k || j == l || k == l)continue;//don't
if(i+j == r1 && k+l == r2 && i+k == c1 && j+l == c2 && i+l == d1 && j+k == d2){
f1 = i;
f2 = j;
f3 = k;
f4 = l;
isOk = true;
}
}
if(isOk == true)break;
}
if(isOk == true)break;
}
if(isOk == true)break;
}
if(f1 != 0){
System.out.println(f1+" "+f2);
System.out.println(f3+" "+f4);
}else{
System.out.println("-1");
}
}
}

B問題は単位づけの問題。3桁ごとにカンマで区切り、マイナスならカッコを付けるといった条件があり、
しっかりとそれを実装すれば良い。実装ゲーである。

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
String d = input.nextLine();
plate(d);
}

public static void plate(String d){
String rd;
if(d.contains("-")){
if(d.contains(".")){
if(d.indexOf(".")+3 <= d.length()){
rd = d.substring(0,d.indexOf(".")+3);
}else{
rd = d+"0";
}
}else{
rd = d+".00";
}
StringBuilder sb = new StringBuilder(rd);
int dotnum = rd.indexOf(".");
int nume = 0;
while(dotnum != 1){
if(nume != 0 && nume % 3 == 0){
sb.insert(dotnum, ",");
}
nume++;
dotnum--;
}
sb.deleteCharAt(0);
System.out.println("($"+sb.toString()+")");
}else{
if(d.contains(".")){
if(d.indexOf(".")+3 <= d.length()){
rd = d.substring(0,d.indexOf(".")+3);
}else{
rd = d+"0";
}
}else{
rd = d+".00";
}
StringBuilder sb = new StringBuilder(rd);
int dotnum = rd.indexOf(".");
int nume = 0;
while(dotnum != 0){
if(nume != 0 && nume % 3 == 0){
sb.insert(dotnum, ",");
}
nume++;
dotnum--;
}
System.out.println("$"+sb.toString());
}
}
}

C問題は A*B*C-(A - 1) × (B - 2) × (C - 2)が最小幾つで最大幾つになるかという問題。
(A - 1) × (B - 2) × (C - 2)の値が与えられているので、A,B,Cのパラメータは自分で設定する。
平方根まで調べるというのがミソ。あ、時間内に解けませんでした。

import java.math.BigInteger;
import java.util.Scanner;

public class Test {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
plate(n);
}

public static void plate(int n){
BigInteger min = new BigInteger("99999999999999999");
BigInteger max = new BigInteger("0");
BigInteger tmp = new BigInteger("0");

for(int i = 1 ; i <= Math.sqrt(n) ; i++){
if(n % i != 0)continue;
int nr = n / i;
//System.out.println(nr);
for(int j = 1 ; j <= Math.sqrt(nr) ; j++){
if(nr % j != 0)continue;
int nr2 = nr / j;
tmp = BigInteger.valueOf(i+1).multiply(BigInteger.valueOf(j+2)).multiply(BigInteger.valueOf(nr2+2)).subtract(BigInteger.valueOf(n));
min = min.min(tmp);
max = max.max(tmp);
tmp = BigInteger.valueOf(j+1).multiply(BigInteger.valueOf(i+2)).multiply(BigInteger.valueOf(nr2+2)).subtract(BigInteger.valueOf(n));
min = min.min(tmp);
max = max.max(tmp);
tmp = BigInteger.valueOf(nr2+1).multiply(BigInteger.valueOf(i+2)).multiply(BigInteger.valueOf(j+2)).subtract(BigInteger.valueOf(n));
min = min.min(tmp);
max = max.max(tmp);
}
}
System.out.println(min+" "+max);
}
}