Codeforces #119

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


帰宅後は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 1は一致する。

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

A 13245
B 12345  2は一致する

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

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

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

つまり1,2の2つの部分だけ一致するので、
長さの5からこの2を引いた3が答えになります。
オーダですが、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;
}
}

  by ddrer-yossi | 2012-05-10 23:17 | codeforces | Comments(0)

<< 久しぶりにポップン TopCoder SRM 54... >>

SEM SKIN - DESIGN by SEM EXE