Google Code Jam 2013 R1C、Codeforces Round #183

今日は何かとコンテスト日和でした。
日記を粘っていたせいで、起床は11時。
親に誘われて40分かけて歩いて外食に。

サラダ、ドリンク取り放題でした。
最初からスパートかけたせいで、これを食べるだけで半ばお腹いっぱいに。
f0019846_1352260.jpg

その後はメインディッシュのハンバーグ
f0019846_1354635.jpg


これだけ食べて980円でした。まあまあ。
その後はゲーセンに入る。
ビーマニはすぐに混み合ったので、ドラマニを頑張ることに。
新曲をあまりやってなかったので、新曲スキル新規導入で
色が一気に緑へ。

f0019846_1364449.jpg


f0019846_137072.jpg

ここまで頑張った。上がりづらくなってやめました。

その後はjubeat。
f0019846_1374289.jpg


f0019846_1375882.jpg


f0019846_1381188.jpg


f0019846_1382431.jpg


あんまりやっていなかったせいか、jubeatはめちゃくちゃのびる。
お米SS,デイリーS、イエローヘッドジョーSS、アルビダSS。

帰宅後は日記を少し進めつつ、GCJに備える。

GCJの結果ですが、またもやA-largeを落とし、oxo---で2451位。
去年は予選突破しましたが、今年は予選落ちです。

A問題ですが、文字列と数値nが与えられていて、子音が連続n個以上含まれる部分文字列が
いくつ取り出せるかという問題。
tsetse 2であれば

ts
tse
tset
tsets
tsetse
ts
tse
ets
sets
etse
setse

の11個になる。違う位置であればカウントする。

アルゴリズムとしては、子音がn個連続する部分を左から調べ、2箇所(最初と次)を取る。
そこから2カ所目に含まれないところまででいくつ作れるか調べる。
これを繰り返す。

large通ってる解です。テストケース弱い気がするけど。

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

public class Test2 {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/A-large-practice.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int num = input.nextInt();
for(int i = 0 ; i < num ; i++){
String s = input.next();
int n = input.nextInt();
//System.out.println(s);
pw.print("Case #"+(i+1)+": "+radius(s,n));
pw.println();
pw.flush();
}
input.close();
pw.close();
}

public static long radius(String s,int n){
long sum = 0;
int stindex = 0;
int enindex = 0;
int st2index = 0;
int en2index = 0;
int stlength = s.length();

boolean isok = false;
for(int i = stindex ; i < s.length() ; i++){
//System.out.println(i);
if(s.charAt(i) == 'a' || s.charAt(i) == 'i' || s.charAt(i) == 'u' || s.charAt(i) == 'e' || s.charAt(i) == 'o'){
stindex = -1;
enindex = -1;
}else{
if(stindex == -1){
stindex = i;
enindex = i;
}else{
enindex = i;
}
}
if(stindex != -1 && enindex != -1 && enindex-stindex+1 == n){
isok = true;
break;
}
}

if(!isok)return 0;
st2index = stindex+1;

while(true){

boolean last = true;
for(int i = st2index ; i < s.length() ; i++){
if(s.charAt(i) == 'a' || s.charAt(i) == 'i' || s.charAt(i) == 'u' || s.charAt(i) == 'e' || s.charAt(i) == 'o'){
st2index = -1;
en2index = -1;
}else{
if(st2index == -1){
st2index = i;
en2index = i;
}else{
en2index = i;
}
}
if(st2index != -1 && en2index != -1 && en2index-st2index+1 == n){
last = false;
break;
}
}

if(!last){
sum += (long)(stindex+1)*(en2index-enindex);
stindex = st2index;
enindex = en2index;
st2index++;
}else{
sum += (long)(stindex+1)*(stlength-enindex);
break;
}
}
return sum;
}
}


B問題は、移動するごとに飛び跳ねる数が1ずつ増えていく状況で、
0,0からx,yに行くときにどうやって行けばいいかを出力せよという問題。
smallは500文字以内であればok、largeは最短ルートでないといけない。
largeは思いつかず、smallは最悪、たとえば5であれば、-1,2,-3,4,-5,6,-7,8,-9,10
とかやってりゃたどり着くだろうということでこの方針で書く。


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

public class Test2 {

public static void main(String args[]) throws Exception{
Scanner input = new Scanner(new FileReader("./iothings/B-small-attempt0.in"));
PrintWriter pw = new PrintWriter(new FileWriter("./iothings/output.txt"));
int num = input.nextInt();
for(int i = 0 ; i < num ; i++){
int x = input.nextInt();
int y = input.nextInt();
//System.out.println(s);
pw.print("Case #"+(i+1)+": "+radius(x,y));
pw.println();
pw.flush();
}
input.close();
pw.close();
}

public static String radius(int x,int y){
StringBuilder sb = new StringBuilder();
int stx = 0;
int sty = 0;
int index = 1;
boolean ms = false;
if(x < 0){
ms = true;
}
while(x != stx){
if(ms){
if(index % 2 == 1){
stx += index;
sb.append("E");
}else{
stx -= index;
sb.append("W");
}
}else{
if(index % 2 == 1){
stx -= index;
sb.append("W");
}else{
stx += index;
sb.append("E");
}
}
index++;
}
ms = false;
if(y < 0){
ms = true;
}
while(y != sty){
if(ms){
if(index % 2 == 1){
sty += index;
sb.append("N");
}else{
sty -= index;
sb.append("S");
}
}else{
if(index % 2 == 1){
sty -= index;
sb.append("S");
}else{
sty += index;
sb.append("N");
}
}
index++;
}
return sb.toString();
}
}


C問題は読んでる途中でおわった。

残念な結果に終わったが、めげずにCodeforces Round #183へ。
こちらもかなりひどい結果になった。

Aは、長さnまでで、ピタゴラスの三角形が何種類作れるかという問題。
nが10^5まであるので、O(n^2)までに収めないと落とされるということに気づかなかった。
しかも予想以上に手間取った。Math.sqrtをintでキャストして、それを二乗したものが、
i*i+j*jと等しくなるかで見ていけばO(n^2)で可能。


import java.util.Scanner;

public class Main2 {

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

public static int pytagoras(int n){
int count = 0;
for(int i = 3 ; i <= n ; i++){
for(int j = i+1 ; j <= n ; j++){
int mx = i*i+j*j;
if((int)Math.sqrt(mx) > n)break;
if((int)Math.sqrt(mx)*(int)Math.sqrt(mx) == mx){
count++;
}
}
}
return count;
}
}


B問題は、yyyy:mm:ddのフォーマットで日付が2つ与えられていて、
間に何日あるか求める問題。
単純に書くだけ。うるう年を求める関数は別に作ったほうが良い。


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

public class Main2 {

public static void main(String args[]){
Scanner input = new Scanner(System.in);
String[] s = input.next().split(":");
String[] e = input.next().split(":");
if(Integer.parseInt(s[0]) < Integer.parseInt(e[0])){
System.out.println(calendar(s,e));
}else if(Integer.parseInt(s[0]) > Integer.parseInt(e[0])){
System.out.println(calendar(e,s));
}else{
if(Integer.parseInt(s[1]) < Integer.parseInt(e[1])){
System.out.println(calendar(s,e));
}else if(Integer.parseInt(s[1]) > Integer.parseInt(e[1])){
System.out.println(calendar(e,s));
}else{
if(Integer.parseInt(s[2]) < Integer.parseInt(e[2])){
System.out.println(calendar(s,e));
}else if(Integer.parseInt(s[2]) > Integer.parseInt(e[2])){
System.out.println(calendar(e,s));
}else{
System.out.println(0);
}
}
}
}

public static int calendar(String[] s,String[] e){
int sy = Integer.parseInt(s[0]);
int sm = Integer.parseInt(s[1]);
int sd = Integer.parseInt(s[2]);
int gy = Integer.parseInt(e[0]);
int gm = Integer.parseInt(e[1]);
int gd = Integer.parseInt(e[2]);
int day = 0;
int[] days = {31,28,31,30,31,30,31,31,30,31,30,31};
if(sy != gy){
if(sm == 2 && isleap(sy)){
day += days[sm-1]-sd+1;
}else{
day += days[sm-1]-sd;
}

for(int i = sm ; i < 12 ; i++){
if(i == 1 && isleap(sy)){
day += days[i]+1;
}else{
day += days[i];
}
}

sy++;
for(int i = sy ; i < gy ; i++){
if(isleap(i)){
day += 366;
}else{
day += 365;
}
}

for(int i = 0 ; i < gm-1 ; i++){
if(i == 1 && isleap(gy)){
day += days[i]+1;
}else{
day += days[i];
}
}
return (day+gd);
}else{
if(sm != gm){
if(sm == 2 && isleap(sy)){
day += days[sm-1]-sd+1;
}else{
day += days[sm-1]-sd;
}
for(int i = sm ; i < gm-1 ; i++){
if(i == 1 && isleap(gy)){
day += days[i]+1;
}else{
day += days[i];
}
}
return day+gd;
}else{
return gd-sd;
}
}
}

public static boolean isleap(int n){
if(n % 4 == 0){
if(n % 100 == 0){
if(n % 400 == 0){
return true;
}
return false;
}
return true;
}
return false;
}

}


C問題は、0からn-1の数を2列並べて、
それぞれの要素ごとに足しあわせてmod nを取ったら、
やはり0からn-1で構成されるようなものを求めて、2列と最後の解を出力せよ。
求められないなら-1を返せという問題。

nが偶数の時は、解が存在しません。
ちなみにn=1のときは0で問題ないです。

自分はてっきり2列は違うものでなければならないと思っていましたが、
その必要はありません。

01234
12345
13524
のように自分はやりましたが
01234
01234
02413
のように2列が同じでもまったく問題ありません。


import java.util.Scanner;

public class Main2 {

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

public static void pytagoras(int n){
int[] a = new int[n];
int[] b = new int[n];
if(n % 2 == 0){
System.out.println(-1);
}else{
for(int i = 0 ; i < n ; i++){
if(i != n-1){
System.out.print(i+" ");
}else{
System.out.println(i);
}
a[i] = i;
}
for(int i = 0 ; i < n ; i++){
if(i != n-1){
System.out.print((i+1)+" ");
b[i] = (i+1);
}else{
System.out.println(0);
b[i] = 0;
}
}
for(int i = 0 ; i < n ; i++){
if(i != n-1){
System.out.print((a[i]+b[i]) % n+" ");
}else{
System.out.println((a[i]+b[i]) % n);
}
}
}
}
}


コドフォで不正を見かけました。こういうのされるとコンテストも楽しくないですね。
f0019846_1544061.png


終了後はひたすら日記を書く。天鳳は一戦やって1位。
f0019846_1551546.png


f0019846_1552330.png


こういうのがきっちり決まるのは楽しい。

  by ddrer-yossi | 2013-05-12 23:33 | 日常生活

<< 難易度10を2つフルコン、ドラ... 日記日和、後にゲーセン、TCOR2C >>

SEM SKIN - DESIGN by SEM EXE