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

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

CodeFestival本選に出てきました

CodeFestivalの本選に参加してきました(一応、この記事内のURLはオープンコンテストの方にしておきます)。
結果としては、10問あって5完でした。5完の人がめっちゃ多かったです。200人いて、50人以上?が5完でした。
6完以上で記念パーカーだったのですが、やはり難易度設定が上手いですね。

さて、解答を書いていきます。ここに書いとくと、後で確認したくなったときに楽なので。


問題A。整数のまま計算しないように注意ですね。

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
		int a = sc.nextInt();
 
		System.out.println(50.0/(float)a );
	}
}

問題B。これもシンプルなやつですね。Aより簡単かも?

import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
 
		String a = sc.next();
 
		int sum = 0;
		for(int i = 0; i < a.length(); i++){
			if(i % 2 == 0){
				sum +=  (int)a.charAt(i) - 48;
			}else{
				sum -= (int)a.charAt(i) - 48;
			}
		}
 
		System.out.println(sum);	
	}
}

問題C。徐々に難易度が上がってきてます。
これは大きい数を扱うので、僕が大きい数を扱う時に使うことで有名な、schemeで解きました。

(define inp (read))
 
(define (ruijou n k)
  (if (= k 0) 1
      (* n (ruijou n (- k 1)))))
 
(define (n-in-n num)
  (define (sub n count shinsuu)
    (if (< n 10) (* n (ruijou shinsuu count))
        (+ (* (ruijou shinsuu count) (modulo n 10)) (sub (quotient n 10) (+ count 1) shinsuu))))
  (sub num 0 num))
 
(define (solve n count)
  (cond ((= n (n-in-n count)) count)
        ((< n (n-in-n count)) -1)
        (#t (solve n (+ count 1)))))
 
(display (solve inp 10))
(newline)

ちなみに、CodeFestival本選でschemeの解答を提出したのは僕だけでした。何かもらえないですかね。

問題D
はじめはピンと来なかったんですが、よく考えると、n段目の左から2番目の数字が(n-1)であることが分かります。だから、入力がmのとき、(m+1)段目の2番目が答えとなりますね。
ちなみに僕はprintの引数で『+』とかを使うのが怖いので、無駄な部分が少しある解答となっています。

import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
 
    int a = sc.nextInt();
 
    System.out.print(a+1);
    System.out.print(" ");
    System.out.println(2);   
  }
}


さて、僕が解けたラストの問題、問題E
動的計画法です。

import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
 
    int a = sc.nextInt();
 
    int[] graph = new int[a];
    for(int i = 0; i < a; i++){
      graph[i] = sc.nextInt();
    }
 
    int[] doutekip = new int[a+1];
    int[] doutekim = new int[a+1];
 
    doutekip[0] = 0;
    doutekim[0] = 0;
 
    for(int i = 1; i <= a; i++){
      int maxnum = 1;
      for(int j = 0; j < i; j++){
        if(graph[j] < graph[i-1]){
          if(maxnum < doutekim[j+1]+1){
            maxnum = doutekim[j+1]+1;
          }
        }
      }
      doutekip[i] = maxnum;
 
      maxnum = 1;
      for(int j = 0; j < i; j++){
        if(graph[j] > graph[i-1]){
          if(maxnum < doutekip[j+1]+1){
            maxnum = doutekip[j+1]+1;
          }
        }
      }
      doutekim[i] = maxnum;
    }
 
    if(doutekip[a] < 3 && doutekim[a] < 3){
      System.out.println(0);
    }else if(doutekip[a] > doutekim[a]){
      System.out.println(doutekip[a]);
    }else{
      System.out.println(doutekim[a]);
    }
  }
}


これで僕が正答した問題は以上です。
上の5問を解いた後、F問題をやり、残り2つの入力のWAがどうしても直らず、問題Hをやり、こちらも途中の入力までしか解けず(TLEとWAがありました)。そしてタイムアップでした。
解説を聞いて、問題Fで勘違いしていたことが分かりました。冷静にやることが大事ですね・・・
せっかくなので、問題Fと問題Hの途中までのコードを書いておきます。Fは貪欲法であることも分かってたよというアピールも兼ねて。せっかくですしね。

問題F。A_(N+1)=A_1というのを見落としてました。それを見落としてなくとも解けたかは微妙ですが。

import java.util.*;
public class Main {
 
  public static int gdc(int a, int b){
    int aa = a;
    int bb = b;
    while(aa % bb != 0){
      int sub = aa % bb;
      aa = bb;
      bb = sub;
    }
    return bb;
 
  }
 
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
 
    int a = sc.nextInt();
 
    int[] blist = new int[a];
    for(int i = 0; i < a; i++){
      blist[i] = sc.nextInt();
    }
 
    int count1 = 0;
 
    for(int i = 0; i < a; i++){
      if(blist[i] % gdc(blist[(i-1+a)%a],blist[(i+1)%a]) != 0){
        count1++;
        // System.out.println("now line is" + i);
        // System.out.println("blist[i] is" + blist[i]);
        i += 2;
      }
    }
 
    int count2 = 0;
    for(int i = a-1; i >=0; i--){
      if(blist[i] % gdc(blist[(i-1+a)%a],blist[(i+1)%a]) != 0){
        count2++;
        // System.out.println("now line is" + i);
        // System.out.println("blist[i] is" + blist[i]);
        i -= 2;
      }
    }
 
    int count;
    if(count1 > count2){
      count = count2;
    }else{
      count = count1;
    }
 
    System.out.println(count);
  }
}

問題H。TLEやWAが残りました。

import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
 
    int personnum = sc.nextInt();
    int roomnum = sc.nextInt();
 
    String info = sc.next();
 
    int[] rooms = new int[roomnum];
    int[] lastkintou = new int[roomnum];
 
    for(int i = 0; i < roomnum; i++){
      rooms[i] = 0;
    }
 
    int[] isin = new int[info.length()];
 
    int[] personleft = new int[personnum];
    int[] personright = new int[personnum];
 
    int nowminmin = 0;
    int nowmax = 0;
    int nowmin = 0;
 
    for(int i = 0; i < info.length(); i++){
      if(info.charAt(i) == '1'){
        rooms[0] += 1;
        isin[i] = 0;
        personleft[i] = 0;
        personright[i] = 0;
        // System.out.println(i + "th person room =0");
      }else{
        int target = rooms[roomnum-1];
        int left = 0;
        int right = roomnum-1;
        int center;
        //leftもrightも、目標indexになる
        while(left < right){
          if(right - left == 1){
            if(rooms[left] <= target){
              right = left;
              break;
            }else{
              left = right;
              break;
            }
          }
 
          center = (left + right) / 2;
          if(rooms[center] <= target){
            right = center;
          }else{
            left = center;
          }
        }
        int newroom = rooms[left] + 1;
        rooms[left] = newroom;
        isin[i] = left;
        personright[i] = left;
        personleft[i] = left;
 
        for(int j = 1; left - j >= 0; j++){
          if(rooms[left-j] > newroom){
            break;
          }else{
            personleft[i] = left - j;
          }
        }
      }
    }
 
    float[] personanswer = new float[personnum];
 
    int nowleft = 0;
    int nowright = 0;  
 
    for(int i = personnum-1; i  >= 0; i--){
      if(nowleft > personleft[i] || personright[i] > nowright){
        nowleft = personleft[i];
        nowright = personright[i];
      }else if(i < personnum-1){
        personanswer[i] = personanswer[i+1];
        continue;
      }
 
      if(nowright - nowleft == 0){
        personanswer[i] = rooms[isin[i]];
      }else if(nowleft <= isin[i] && isin[i] <= nowright){
        int sum = 0;
        for(int j = nowleft; j <= nowright; j++){
          sum += rooms[j];
        }
        personanswer[i] = (float)sum / (float)(nowright-nowleft+1);
      }else{
        personanswer[i] = rooms[isin[i]];
      }
    }
 
    if(roomnum == 1){
      for(int i = 0; i < personnum; i++){
        System.out.println(personnum);
      }
    }else{
      for(int i = 0; i < personnum; i++){
        System.out.println(personanswer[i]);
      }
    }
  }
}


以上です。
CodeFestivalというイベント自体は明日もあるので、色々楽しみたいと思います。

広告を非表示にする