最近、本当に最近、CodeForcesというサイトのコンテストに出ています。
これまではAtcoderしかやったことがなかったのですが、せっかくならもう一つくらいやってみようというのと、英語の問題をやってみようということで、新しいことをやるのにしました。
TopCoderの方がメジャーっぽいのですが、使える言語が少ないのと、なんかトップページ行ってもパッと分からなかったのもあり、CodeForcesを選びました。
また、やってみたところ、こちらの方が日本人としては参加しやすい時間にコンテストが開催されている気がします(今のところ、開始時間が18時〜25時の間です)。基本的にはモスクワ時間が基準のようです。TopCoderは深夜(明朝？)にやってたりするイメージがあります。
ちなみに、CodeForcesではレーティングがつきます。自分の成績を反映したものですね。上がったり下がったりします。
レーティングは1200から始まり、コンテストに出る度に変動します。また、コンテストに出るためにはレジスター(参加予約)(開始数時間前から開始直前(5分前?)までにしなければなりません)をしなければいけないのですが、レジスターして結局参加しなかった(or 1つもプログラムを提出しなかった)ら、レーティングはそのままのようです。0点という扱いにはならないようですね。気楽にレジスターできます。
あと、CodeForcesの定例大会？はレーティングによって１部(Div.1)と２部(Div.2)に分かれており、はじめは２部からのスタートです。レーティングが1700を越えると、１部で戦えるとのこと。ただ、１部と２部で問題が全く違うわけではなく、１部は２部の問題(の一部？)+さらに難しい問題が何問か、という感じのようです。
先日Round271、272と273に出て、そして今日274に出たのですが、AtcoderRegularContestよりも少し簡単な気がします(少なくとも今日のは)。まだ２部だから、というのもありそうですが。
今日のRound274では、５問中４問解けました(2時間)。４問目で残りが26分だったので、そこで諦めました。お腹も減っていたので。
４問目まではハイレベルなアルゴリズムを使う必要もなく、上手に、もれなく実装できるか、という問題のようでした。
ここからはRound274で解いた問題の話になります。
まず、ProblemAから。
大雑把に言うと、整数a,b,cが与えられたとき、()と+と*を使って最も大きくしましょう、という問題です。
とは言っても、以下の6通りしかありません。
a+b+c
a+b*c
(a+b)*c
a*b+c
a*(b+c)
a*b*c
全部比べて、最大値を返すようにすればよいですね。こんなコードで出しました(CodeForcesでは基本的にJavaで解いています)
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
int maxv = a + b + c;
if(maxv < a * b + c){
maxv = a * b + c;
}
if(maxv < a + b * c){
maxv = a + b * c;
}
if(maxv < a * b * c){
maxv = a * b * c;
}
if(maxv < (a + b) * c){
maxv = (a + b) * c;
}
if(maxv < a * (b + c)){
maxv = a * (b + c);
}
System.out.println(maxv);
}
}提出したのは、開始から5分後でした。
つぎに、ProblemB。
入力はタワーの数n、操作許可数k、そしてn個のタワーの高さです。
高さmのタワーは高さ1のブロックがm個積まれて出来ている、という設定です。
そしてこのとき、k回以内の操作(1回の操作=どれかのタワーの一番上のブロックを別のタワーの一番上に置く)で、一番高いタワーと一番低いタワーの差を最小にする方法のうち、最も操作回数が少ないやり方を一つ出力せよ、という問題です。
これも、愚直にやったやつを出してみたら通りました。タワー数が多くて100なので。
手順としては、
①一番高いタワーと一番低いタワーの差が1以内なら終わり
②一番高いタワーから一番低いタワーへ１つ動かす。
の繰り返しです。コードはこんな感じ。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int towernum = sc.nextInt();
int openum = sc.nextInt();
int[] tower = new int[towernum];
for(int i = 0; i < towernum; i++){
tower[i] = sc.nextInt();
}
int[] answers = new int[openum];
int countope = 0;
for(int i = 0; i < openum; i++){
int max = tower[0];
int min = tower[0];
int maxindex = 0;
int minindex = 0;
for(int j = 1; j < towernum; j++){
if(tower[j] > max){
max = tower[j];
maxindex = j;
}else if(tower[j] < min){
min = tower[j];
minindex = j;
}
}
if(max - min <= 1){
break;
}
answers[i] = (maxindex + 1) * 1000 + (minindex + 1);
tower[maxindex]--;
tower[minindex]++;
countope++;
}
int lastmax = tower[0];
int lastmin = tower[0];
for(int i = 0; i < towernum; i++){
if(tower[i] > lastmax){
lastmax = tower[i];
}else if(tower[i] < lastmin){
lastmin = tower[i];
}
}
System.out.println((lastmax - lastmin) + " " + countope);
for(int i = 0; i < countope; i++){
System.out.println((answers[i]/1000) + " " + (answers[i] % 1000));
}
}
}
そしてProblemC。
入力は、試験の数nと、各試験における『正規日程』と『特別前倒し日程』です(日程は、今から何日後かで表されています)。
各試験を、『正規日程順』に受けたい。各試験は『正規日程』と『特別前倒し日程(正規日程より早い)』のどちらかで受けられる。また、同じ日に複数の試験を受けることも可能である。
全ての試験を『正規日程順』に受けるとしたら、最速で何日目に終わるでしょう、という問題です。
これも以下を、全ての試験を受けるまで繰り返すという愚直なやり方で通りました(上手いやり方は思いつきませんでした)。
①受けてない試験の中で、最も『正規日程』が早いものを見る
②それの『特別前倒し日程』が、直前に受けた試験と同じ日か遅かった場合、『特別前倒し日程』で受ける
③そうでなかった場合は、『正規日程』で受ける
コードにするとこんな以下のような感じです。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int nn = sc.nextInt();
int[][] dates = new int[nn][2];
boolean[] check = new boolean[nn];
for(int i = 0; i < nn; i++){
dates[i][0] = sc.nextInt();
dates[i][1] = sc.nextInt();
check[i] = false;
}
int nowday = 0;
for(int i = 0; i < nn; i++){
int maxmin = 1000000001;
int minmin = 0;
int index = 0;
for(int j = 0; j < nn; j++){
if((maxmin > dates[j][0] && !check[j]) || (maxmin == dates[j][0] && minmin > dates[j][1] && !check[j])){
maxmin = dates[j][0];
minmin = dates[j][1];
index = j;
}
}
if(nowday <= minmin){
nowday = minmin;
}else{
nowday = maxmin;
}
check[index] = true;
}
System.out.println(nowday);
}
}これは貪欲法と呼ぶのでしょうか。貪ちゃん。
最後にProblemDです。
これは入力が、定規に書いてある印の数n、定規の長さl、長さx、長さy(x < y)と、定規に書いてあるn個の印がそれぞれ左端から何cmのところにあるか、です。
ちなみに印がある位置は小さい順に並んでいます。また、どうやら１つ目の印は常に0cmのところのようです。
そして、各印の間の長さのみ、測ることができます。つまり、100cmの定規に3つの印があり、それぞれ端から①0cm、②20cm、③100cmのところにあるのだったら、測れるのは①ー②間の20cm、①ー③間の100cm、②ー③間の80cm、というわけです。
そして、ぴったりxcmとycmを測れるように印を付け加えたい。また、新しく付ける印はなるべく少なくしたい。
どこに新しく印を付ければよいでしょう、という問題です。
解き方は、以下のようにしました。
①はじめからある印だけで、xcmとycmが測れるか調べる
②・どちらも測れる→新しく付ける印は0個
・どちらかしか測れない→測れない方を測れるようにする。例えばxcmの方が測れなかった場合、端っこからxcmのところに印をつける
・どちらも測れない場合、③へ
③１つ印を付け加えるだけで、xcmもycmも測れるようにならないか調べる。具体的には、次のどれかのような印[i]と印[j]の組(i < j)があればよい。
上の図(汚くてすみません)のような印の組があれば、上の図の印[i]と印[j]の間にあるところに新しい印を、無理だったら２つ印(左端からxcmのとことycmのところ)をつける。
コードにするとこんな感じです。
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int nn = sc.nextInt();
int ll = sc.nextInt();
int xx = sc.nextInt();
int yy = sc.nextInt();
int[] marks = new int[nn];
for(int i = 0; i < nn; i++){
marks[i] = sc.nextInt();
}
boolean checkxx = false;
// xxが測れるかどうかチェック
for(int i = 0; i < nn - 1; i++){
int nowleft = marks[i];
if(Arrays.binarySearch(marks,i+1,nn,nowleft+xx) > i){
checkxx = true;
}
}
// System.out.println(checkxx);
boolean checkyy = false;
// yyが測れるかどうかチェック
for(int i = 0; i < nn - 1; i++){
int nowleft = marks[i];
if(Arrays.binarySearch(marks,i+1,nn,nowleft+yy) > i){
checkyy = true;
}
}
// System.out.println(checkyy);
if(checkxx && checkyy){
System.out.println(0);
}else if(checkxx){
System.out.println(1);
System.out.println(yy);
}else if(checkyy){
System.out.println(1);
System.out.println(xx);
}else{
boolean candouble = false;
for(int i = 0; i < nn - 1; i++){
int nowleft = marks[i];
if(Arrays.binarySearch(marks,i+1,nn,nowleft+xx+yy) > i && nowleft+xx <= ll){
System.out.println(1);
System.out.println(nowleft + xx);
candouble = true;
break;
}
}
if(!candouble){
for(int i = 0; i < nn - 1; i++){
int nowleft = marks[i];
if(Arrays.binarySearch(marks,i+1,nn,nowleft + yy - xx) > i && nowleft + yy <= ll){
System.out.println(1);
System.out.println(nowleft + yy);
candouble = true;
break;
}
if(Arrays.binarySearch(marks,i+1,nn,nowleft + yy - xx) > i && nowleft - xx >= 0){
System.out.println(1);
System.out.println(nowleft - xx);
candouble = true;
break;
}
}
}
if(!candouble){
System.out.println(2);
System.out.println(xx);
System.out.println(yy);
}
}
}
}強いて言うなら工夫として、印の位置がソートされて並んでいるため、二分探索を用いました。
ProblemEは見すらしませんでした。
これで今回解いた分は終わりです。
２部に出ていた人(2300人くらい？)の中で、なんと上位１割に入れているかもしれないので、レーティングは上がると思います。
1700越えるのでしょうか・・・？でも、越えるの怖いですね。もう少し実力が付いてからでも良いかもしれません。
今回は以上です。
追記：本番中のpretestは通っていたのですが、残念なことに後でのチェックでミスが見つかったらしく、レーティングは上がりませんでした・・・
ちなみに、上のプログラムは直してちゃんとAcceptになったものにしてあります。
