Codeforces Round #201
お昼はぼっち飯が確定したので、時間待って釜玉にしてみた。
でもそんなにおいしくはなかったかな・・・。
香川で食べた肉釜玉が最強だった。
退勤後はゲーセンへ。
リフレク左手のみプレーを始めました。
レザクラフルコン
ノスタルジックフルコン
マクバ更新
エッセンシャリー銅◆
ここから片手リフレク
片手最初は朧MEDIUMでした。
手応えあるので隅田川
ヴァリスはさすがに・・・。
宇宙戦争
中華急行
おこめ
FLOWER
ゼータ
デイリー
帰宅後はCodeforces #201
A問題は、数列を並び替えて
a1-a2 + a2-a3 +a3-a4...の値を最大になるようにして出力せよという問題。
見ればわかりますが、a2,a3などの途中過程は消滅するので、a1-a4を最大にすればよいです。
つまりa1に最大値、a4に負の最大値を持ってくれば良し。
import java.util.Arrays;
import java.util.Scanner;
public class Main2 {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
for(int i = 0 ; i < n ; i++){
a[i] = sc.nextInt();
}
Arrays.sort(a);
for(int i = 0 ; i < n ; i++){
if(i == n-1){
System.out.println(a[0]);
}else if(i == 0){
System.out.print(a[n-1]+" ");
}else{
System.out.print(a[i]+" ");
}
}
}
}
B問題は、数列の要素を1回だけスワップして、順列をなす個数の最大値を求める問題。
全通り調べるとO(n^2)TLEしてしまうので、ある程度目星をつけて、
スワップで2つ増えることができるかどうかを探す必要があります。
つまり、b[a[i]] = i なところがあれば、2つ増やせるといった具合です。
import java.util.Arrays;
import java.util.Scanner;
public class Main2 {
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n];
int[] b = new int[n];
for(int i = 0 ; i < n ; i++){
a[i] = sc.nextInt();
b[i] = -1;
}
int count = 0;
int ctp = 0;
boolean ocm = false;
for(int i = 0 ; i < n ; i++){
if(a[i] == i){
count++;
a[i] = -1;
}else if(b[a[i]] == i){
ctp = 2;
}else{
ocm = true;
b[i] = a[i];
}
}
if(ocm){
System.out.println(count+Math.max(ctp, 1));
}else{
System.out.println(count);
}
}
}
C問題は数列が与えられていて、
任意の2つを選んでその絶対値を取ってそれを集合に加えるということを、
交互に行い、できなくなったほうが負けという問題。
hackされてしまったので・・・。
by ddrer-yossi | 2013-09-20 23:31 | codeforces