新宿東南口のタイトーへ、Codeforces Round #182

今日は某氏とゲーセンで待ち合わせ。
ビーマニ、DDR、jubeat、リフレクあたりをプレーして、
ついに学園最後の曲も解禁が終わりました。
後はrunrunマラソンかー。

f0019846_11512782.jpg


f0019846_11514516.jpg


f0019846_11515950.jpg


ALBIDAもAA乗る。
f0019846_11522455.jpg


f0019846_1152434.jpg


f0019846_1153734.jpg


f0019846_11532230.jpg


リフレク未クリアもハエレのみに。後はダンエボも1クレ。
キモプリの振り付けを大体覚えたかな。
その後はつけめんを食べに行きました。

f0019846_1154521.jpg


あっさり豚骨。悪くない。

解散後は、地元ゲーセンへ。
フルコンしづらい奴をつぶしていく。

f0019846_11553618.jpg


f0019846_11555336.jpg


f0019846_11561577.jpg

ビースティ難つきました。

f0019846_11574622.png


ただしお米タルが変な癖ついて、序盤でコンボを切るようになってしまいました。
帰宅後はcodeforces待機。
しかし、サーバーダウンが何度もあり、始まったのは30分後ぐらいでした。しかもunrated。

昼12時現在でも死んでいるので、後で書きます。
15時現在復帰しているので。

A問題は、-1と1で与えられている配列があり、
AからBの範囲で配列を並び替えなおして合計値が
0となるような出力ができるなら1、できないなら0を返す。

単純に-1と1の数を数えて、範囲が奇数なら必ず0、
偶数なら、各個数が範囲/2以上あれば1を返す。
Javaだとそのまま出力するとTLEするので要注意。
今回はStringBuilderを使ってまとめた。


import java.util.Scanner;

public class Main2 {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
int minus = 0;
int plus = 0;
for(int i = 0 ; i < n ; i++){
if(input.nextInt() == 1){
plus++;
}else{
minus++;
}
}
int min = Math.min(minus, plus)*2;
StringBuilder sb = new StringBuilder();
for(int i = 0 ; i < m ; i++){
int st = input.nextInt();
int en = input.nextInt();
int num = en-st+1;
if(num % 2 != 0 || num > min){
sb.append("0"+"\n");
}else{
sb.append("1"+"\n");
}
}
System.out.println(sb);
}
}


B問題は、曲の長さと曲をリピートする回数が与えられていて、
感動した時の時間が書かれている。その時間にどの曲を聴いていたかを出力する問題。
単純に一番上の曲の時間から足していって、その値を超えない範囲であれば、その曲の番号を出し、
超えた場合は、次の曲の時間を足していく。


import java.util.Scanner;

public class Main2 {
public static void main(String args[]){
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
int[] time = new int[n];
int[] times = new int[n];
for(int i = 0 ; i < n ; i++){
time[i] = input.nextInt();
times[i] = input.nextInt();
}
int[] ftime = new int[m];
for(int i = 0 ; i < m ; i++){
ftime[i] = input.nextInt();
}
int index = 1;
int stime = time[0]*times[0];
for(int i = 0 ; i < m ; i++){
if(ftime[i] <= stime){
System.out.println(index);
}else{
stime += time[index]*times[index];
index++;
i--;
}
}
}
}


C問題は、配列が2n-1個与えられていて、
毎回n個の配列の正負を変えることができる。
合計値の最大値を求めよという問題。
nが奇数のときは、実は全部正の数に必ず変えられる。
nが偶数のときは、2n-1を超えない偶数個までしか変えられない。
ので、偶数のときに注意して、ソートして全探索で答えが求められる。


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();
int[] a = new int[2*n-1];
for(int i = 0 ; i < 2*n-1 ; i++){
a[i] = input.nextInt();
}
Arrays.sort(a);
if(n % 2 == 0){
int nc = 0;
int oc = 0;
for(int i = 0 ; i < 2*n-1 ; i++){
nc += a[i];
}
int max = nc;
for(int j = 2 ; j <= 2*n-1 ; j+=2){
oc = 0;
for(int i = 0 ; i < 2*n-1 ; i++){
if(i < j){
oc += (-a[i]);
}else{
oc += a[i];
}
}
max = Math.max(oc, max);
}
System.out.println(max);
}else{
int max = 0;
for(int i = 0 ; i < 2*n-1 ; i++){
max += Math.abs(a[i]);
}
System.out.println(max);
}
}
}


D問題は、スタートとゴール以外のある地点に到達すると、タイムボーナスが加算される。
ただし、どの地点も行けるのは1回のみ。
ある地点からある地点の距離はマンハッタン距離。
距離*コスト分だけ時間がかかる。
時間はお金を払えばその分だけ増やせる。
かかるお金の最小値を求めよ。
ある地点からある地点の距離からコストを算出して、ボーナス分を引いて、
後はダイクストラ法を用いて計算する。


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();
int d = input.nextInt();
int[] x = new int[n];
int[] y = new int[n];
int[][] dij = new int[n][n];
int[] minuscost = new int[n];
for(int i = 1 ; i < n-1 ; i++){
minuscost[i] = input.nextInt();
}
for(int i = 0 ; i < n ; i++){
x[i] = input.nextInt();
y[i] = input.nextInt();
}
for(int i = 0 ; i < n ; i++){
for(int j = i ; j < n ; j++){
if(i != j){
int mc = (Math.abs(x[i]-x[j])+Math.abs(y[i]-y[j]))*d-minuscost[i];
int mc2 = (Math.abs(x[i]-x[j])+Math.abs(y[i]-y[j]))*d-minuscost[j];
dij[i][j] = mc;
dij[j][i] = mc2;
}
}
}
System.out.println(dijkstra(0,n-1,n,dij));
}

public static long dijkstra(int st,int g,int n,int[][] dist){
int x;
long min;
long INF = 1000000000000000000l;
boolean[] used = new boolean[n];
long[][] cost = new long[n][n];
int rindex = -1;
for(x = 0; x < n; x++){
for(int y = 0 ; y < n ; y++){
cost[y][x] = INF;
}
}
cost[g][g] = 0;
while(true){
min = INF;
for(x = 0; x < n; x++){
if(!used[x] && min > cost[g][x]){
min = cost[g][x];
rindex = x;
}
}

if(min == INF)break;
for(x = 0; x < n; x++){
if(cost[g][x] > dist[x][rindex] + cost[g][rindex]){
cost[g][x] = dist[x][rindex] + cost[g][rindex];
}
}
used[rindex] = true;
}
if(cost[g][st] == INF){
return -1;
}else{
return cost[g][st];
}
}
}


61/1696位ですがunrated。

天鳳1-3-2

  by ddrer-yossi | 2013-05-05 23:48 | 日常生活 | Comments(0)

<< 溜まりきった日記の消化活動 ナランハジャグリングまつり二日... >>

SEM SKIN - DESIGN by SEM EXE