Codeforces Round #175

黄色イベントが始まりました。
が、そんなものにかまってる暇もなく、
午前から午後にかけてアルゴリズムの学習。
再帰関数で結構つまずく。

しかし、誘惑に負けてゲーセンへ。
FIRE FIREフルコンから。

f0019846_21532469.jpg


f0019846_21533926.jpg

キルトもなかなか良い記録。

f0019846_2154136.jpg

Do it!ついた!!!

f0019846_21542897.jpg

めうめうフルコンしておく。

f0019846_21545153.jpg

桜イージーついた。

意外にやってる人がいなくて、スムーズでした。
夜はcodeforcesに参戦。

A問題は、n個の数と、k個の減少列が与えられるような数列を出力するという問題。
n = 5 k = 2であれば、
3 2 1 4 5という具合。

つまりk+1分だけ順に下げていって、後はその位置から上げていくだけで作れる。

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main2 {

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

public static void saiki(int n,int k){

for(int i = n ; i > n-k ; i--){
System.out.print(i+" ");
}
for(int i = 1 ; i <= n-k ; i++){
if(i == n-k){
System.out.println(i);
}else{
System.out.print(i+" ");
}
}
}

}


B問題は、n個の数が与えられていて、スタート地点はs、ゴールはt。
残りの数列は、次に移動する場所が与えられていて、何回でゴールできるか、
できなければ-1を返せという問題。
愚直に最大回数でもn-1回なので、n-1回シミュレートして駄目だったら
-1を返すのがバグが一番少ない。


import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main2 {

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

public static int saiki(int n,int s,int t,int[] a){

if(s == t){
return 0;
}else{
int num = s;
int turn = 0;
while(num != t){
num = a[num-1];
turn++;
if(turn >= n)return -1;
}
return turn;
}
}

}


Cは、n個の数と数列が与えられてて、それを1,2,3...nにするには、
足したり引いたりする回数が何回いるか、最小値を求めよという問題。
単純にソートして足していくだけで良いが、
Javaの場合、型をLongにしないとTLEしてしまうので要注意。
longだとTLEします。ソートkillが入っている可能性が高い。


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

public class Main2 {

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

public static long saiki(int n,Long[] a){
Arrays.sort(a);
Long sum = 0L;
for(int i = 0 ; i < n ; i++){
sum += Math.abs((i+1)-a[i]);
}
return sum;
}
}

  by ddrer-yossi | 2013-03-21 23:49 | 日常生活 | Comments(0)

<< スノボ旅行一日目 ~目指すは新潟~ 学習後ゲーセン >>

SEM SKIN - DESIGN by SEM EXE