プログラミングを上達させたい

プログラミングの勉強を始めた、情報学専攻の大学院生です。モチベーション維持のため、ブログに勉強したことを書いていきます。→就職。IT全然関係ない仕事をしています

CODE FESTIVAL 予選B

先ほど、CODE FESTIVALの予選Bが終わりました。
問題ページはコチラ、そもそもCODE FESTIVALについてはコチラ

関東圏に住んでいない僕としては、なんとしても予選通過しなければ、という思いでした(交通費が出ます!)。
一応、結果としては、4問全てクリアで、順位としては30位でした。
この予選Bの結果で上位から80人が本選に進めるということなので、どうやら大丈夫そうです。よかったよかった

思えば人生で初めてのコンテスト全完ということなので、ゴキゲンで回答を書いていこうと思います。ちなみに、すべてJavaで解きました。


まず、問題Aから。
これはifで書くだけ。
単純な問題ですね。コードはこんな感じに。

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;
		if(a >= b){
			c = a;
		}else{
			c = b;
		}
 		System.out.println(c);
	}
}

次に、問題B。forで書くだけ。

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
 		int nissuu = sc.nextInt();
 		int mokuhyou = sc.nextInt();

 		int i = 0;
 		int nowhosuu = 0;
 		for(i = 0; i < nissuu; i++){
 			nowhosuu += sc.nextInt();
 			if(nowhosuu >= mokuhyou){
 				break;
 			}
 		}

 		System.out.println(i+1);

	}
}

ここからが問題として難易度がガラッと変わりますね。思えば、CODE FESTIVALの予選Aは、2問目までしか解けなかったのでした。

さて、問題Cです。
ここで、問題発生です。
記事を書こうと、自分のコードを見てみたら、どうやら間違っていることに気づきました。
問題Cを部分的には解けているのですが、全ての入力に対しては正しい答えを返しません。
ちなみに、例えば入力として

AAAA
AAAA
AABB

を与えると、"AAAA"と"AAAA"からどのように2文字ずつ選んでも"AABB"にはならないですが、僕のプログラムでは"YES"となります。
これは、問題制作側がチェックするサンプルを作る際に見落としたのでしょうか。理由はどうあれ、正解には変わりありませんね。ラッキーです。
僕のコードはこんな感じ。

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
 		String zairyo1 = sc.next();
 		String zairyo2 = sc.next();
 		String mokuhyou = sc.next();

 		int len = zairyo1.length();


 		int[] zai1 = new int[26];
 		int[] zai2 = new int[26];

 		for(int i = 0; i < 26; i++){
 			zai1[i] = 0;
 			zai2[i] = 0;
 		}

 		for(int i = 0; i < len; i++){
 			int a = (int)zairyo1.charAt(i);
 			int b = (int)zairyo2.charAt(i);
 			zai1[a-65]++;
 			zai2[b-65]++;
 		}

 		int from1 = 0;
 		int from2 = 0;

 		for(int i = 0; i < len; i++){
 			int a = (int)mokuhyou.charAt(i);

 			if(zai1[a-65] > 0){
 				from1++;
 				zai1[a-65]--;
 			}
 			if(zai2[a-65] > 0){
 				from2++;
 				zai2[a-65]--;
 			}
 		}

 		if(from1 >= len / 2 && from2 >= len / 2){
 			System.out.println("YES");
 		}else{
 			System.out.println("NO"); 			
 		}
	}
}

つまり、S3内の文字に対して、S1、S2それぞれから最大で何文字提供できるかを調べ、どちらともN文字以上提供できるなら"YES"、そうでないなら"NO"ということですね。
このやり方だと、例えば、S3内のある文字に対して、S1にもS2にもないような文字があったときに、すぐさま"NO"と判定すべきところを、見過ごしてしまいます。

ただ、これを修正するのは、おそらくそんなに難しいことではないと思います。やらないけど。できるかな〜、できないかな〜


さて、疑惑の問題Cの次は、問題Dです。
これにのみ、部分点が設定されています。
定石通り(このCODE FESTIVAL予選では、3完+部分点で予選を通過できる、みたいななんとなくのラインが前回はありました)、まずは部分点を狙いにいきます。部分点狙いコードはコチラ。愚直にやっているだけですね。

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
 		int n = sc.nextInt();

 		int[] heights = new int[n];
 		for(int i = 0; i < n; i++){
 			heights[i] = sc.nextInt();
 		}

 		int[] answers = new int[n];

 		for(int i = 0; i < n; i++){
 			int nowcansee = 0;
 			for(int j = 1; i-j >= 0; j++){
 				if(heights[i-j] > heights[i]){
 					break;
 				}else{
 					nowcansee++;
 				}
 			}
 			for(int j = 1; i+j < n; j++){
 				if(heights[i+j] > heights[i]){
 					break;
 				}else{
 					nowcansee++;
 				}
 			}

 			answers[i] = nowcansee;
 		}

 		for(int i = 0; i < n; i++){
 			System.out.println(answers[i]);
 		}
	}
}

これだと、チェックのときに使うサンプルのうち、最後の2割あたりでTLE(時間制限オーバー)となってしまいます。
高速化のアルゴリズムを色々考えてみたのですが、どうしても思いつきませんでした。ここでいう高速化のアルゴリズムというのは、なんかソートしたり、二分探索したり、木がどうの、みたいなやつのことです。

そこで、とりあえずある程度高速化してみよう、それで無理だったらそれをそのままC言語で書いて出してみて、それでもTLEだったら諦めよう、という流れにすることにしました。
そしたら、なんとラッキーなことに(?)、Javaで書いた段階でAC(正解)となりました。

僕がやった高速化の説明をします。

まずそもそも、上の愚直なやり方は(0番目から(n-1)番目までのn個の山小屋があるとして)(そして西=左、東=右と書きます)、
・山小屋iに対し、1つずつ左を見ていって、山小屋iより高いのが出るか、山小屋0まで見たら終わり、
・同じことを、1つずつ右を見ていってやる
・その和を計算→出力
という流れですね。
この、左をどんどん見ていく、右をどんどん見ていく、というところを少し速くしました。
具体的な流れとしては、
・山小屋iから左側にある見える山小屋の数をleftcansee[i]、右側に見える数をrightcansee[i]と書く。
・当然、(0番目から(n-1)番目までのn個の山小屋があるとして) leftcansee[0]=0。ここから、leftcansee[1]、leftcansee[2]、・・・という順番で求めていく。
・山小屋iから左側を見ていくときに、まず(i-1)番目の山小屋から注目して、
 ・自分より高い→終わり
 ・自分以下→そこからleftcansee[i-1]個分は当然見える。よって、次に注目する場所を、今注目している山小屋から(leftcansee[i-1]+1)個分左に飛ばして、同じ操作を行う
・同じことを、rightcanseeについてもやる。rightcanseeは、rightcansee[n-1]=0から初めて、rightcansee[n-2]、rightcansee[n-3]、・・・と求めていきます。
というやり方です。

コードで書くと、こんな感じになります。

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
 		int n = sc.nextInt();

 		int[] heights = new int[n];
 		for(int i = 0; i < n; i++){
 			heights[i] = sc.nextInt();
 		}

 		int[] leftcansee = new int[n];
 		int[] rightcansee = new int[n];

 		for(int i = 1; i < n; i++){
 			leftcansee[i] = 0;
 			rightcansee[i] = 0;
 		}

 		for(int i = 1; i < n; i++){
 			int nowlookindex = i - 1;
 			//count left
 			while(nowlookindex >= 0){
 				if(heights[nowlookindex] > heights[i]){
 					break;
 				}else{
 					leftcansee[i] += leftcansee[nowlookindex] + 1;
 					nowlookindex -= leftcansee[nowlookindex] + 1;
 				}
 			}
 		}

 		for(int i = n - 2; i >= 0; i--){
 			int nowlookindex = i + 1;

 			//count right
 			while(nowlookindex < n){
 				if(heights[nowlookindex] > heights[i]){
 					break;
 				}else{
 					rightcansee[i] += rightcansee[nowlookindex] + 1;
 					nowlookindex += rightcansee[nowlookindex] + 1;
 				}
 			}
 		}

 		for(int i = 0; i < n; i++){
 			System.out.println(leftcansee[i] + rightcansee[i]);
 		}
	}
}

どれくらい高速になっているのか(オーダーは落ちているのか?とか)は分かりませんが、これでACとなりました。時間制限が2000msで、僕の回答は1862msでした。ギリギリ。

あと、変数の名前とかがダサいですね。もっとちゃんと名前を考えるか、意味のないドシンプルなやつにしたいところですが・・・
いや、でも自分の分かりやすさが優先ですね。しばらくはこういう感じの名前でも気にせずいくことにします。


そんなこんなで(ラッキーもありながら)、CODE FESTIVAL、おそらく本選に行きます。
今から楽しみです。以上。

広告を非表示にする