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というイベント自体は明日もあるので、色々楽しみたいと思います。