CodeFestivalの企画の1つである、『あさプロ』というのがありました。
朝からプログラミング、ということで、昨日の本選の順位によってHard,Middle,Easyの3つの区分に分かれ、それぞれで競い合う形式でした(僕はMiddleでした)。
問題ページはコチラ。
90分の4問で、僕は2問解けました。
良いめの順位だったので、銀色の缶バッチをゲットできました。こういうレベル分けがあると、どの人にもそういう順位へのモチベーションが出るので良いですね。
さて、問題の話。
まず解こうとした問題Aから(結局一番に解けた問題は別の問題でした)。
『スタートおよびゴールの街から辿り着けない街もあり得る』という点を見逃していて、何回もミスしました。
最終的にACになったコードはコチラ。
import java.util.*; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int machinum = sc.nextInt(); int roadnum = sc.nextInt(); int startind = sc.nextInt(); int goalind = sc.nextInt(); int[][] mindis = new int[machinum][machinum]; int[][] roadinfo = new int[roadnum][3]; //0=from 1=to 2=distance for(int i = 0; i < roadnum; i++){ roadinfo[i][0] = sc.nextInt(); roadinfo[i][1] = sc.nextInt(); roadinfo[i][2] = sc.nextInt(); } int[] minfromstart = new int[machinum]; for(int i = 0; i < machinum; i++){ minfromstart[i] = 10000000; } minfromstart[startind-1] = 0; Queue<Integer> queue1 = new ArrayDeque<Integer>(); Queue<Integer> queue2 = new ArrayDeque<Integer>(); queue1.add(startind); queue2.add(0); while(!queue1.isEmpty()){ int fromind = queue1.poll(); int nowdis = queue2.poll(); for(int i = 0; i < roadnum; i++){ if(roadinfo[i][0] == fromind){ if(minfromstart[roadinfo[i][1]-1] >= nowdis + roadinfo[i][2]){ queue1.add(roadinfo[i][1]); queue2.add(nowdis + roadinfo[i][2]); minfromstart[roadinfo[i][1]-1] = nowdis + roadinfo[i][2]; } } if(roadinfo[i][1] == fromind){ if(minfromstart[roadinfo[i][0]-1] >= nowdis + roadinfo[i][2]){ queue1.add(roadinfo[i][0]); queue2.add(nowdis + roadinfo[i][2]); minfromstart[roadinfo[i][0]-1] = nowdis + roadinfo[i][2]; } } } } int[] minfromgoal = new int[machinum]; for(int i = 0; i < machinum; i++){ minfromgoal[i] = 10000000; } minfromgoal[goalind-1] = 0; queue1.add(goalind); queue2.add(0); while(!queue1.isEmpty()){ int fromind = queue1.poll(); int nowdis = queue2.poll(); for(int i = 0; i < roadnum; i++){ if(roadinfo[i][0] == fromind){ if(minfromgoal[roadinfo[i][1]-1] >= nowdis + roadinfo[i][2]){ queue1.add(roadinfo[i][1]); queue2.add(nowdis + roadinfo[i][2]); minfromgoal[roadinfo[i][1]-1] = nowdis + roadinfo[i][2]; } } if(roadinfo[i][1] == fromind){ if(minfromgoal[roadinfo[i][0]-1] >= nowdis + roadinfo[i][2]){ queue1.add(roadinfo[i][0]); queue2.add(nowdis + roadinfo[i][2]); minfromgoal[roadinfo[i][0]-1] = nowdis + roadinfo[i][2]; } } } } int answer = -1; for(int i = 0; i < machinum; i++){ // if(i == startind-1 || i == goalind-1){continue;} if(minfromstart[i] < 10000000 && minfromstart[i] == minfromgoal[i]){ answer = i + 1; break; } } System.out.println(answer); } }
最短距離を求める部分を書くのに時間がかなりかかったあたり、慣れが足りないという感じでしょうか。書けてよかったです。
もう1つ解けたのが、問題C。
こちらは、与えられる確率pが1か0なら特殊なケースとして処理、そうでない場合は普通に計算、というコードを書きました。
その計算の中で2分累乗法を使いました。また、誤差が10の-6乗以内ならよし、というのを利用して省略できる部分は省略したつもりです。
コードはこんな感じ。
僕が大きい数を扱うときに使うことで有名な、schemeで解きました。
(define kakuritsu (read)) (define ind (read)) (define (checksize a) (< (/ -1 1000) a (/ 1 1000))) (define (beki a n) (cond ((= n 0) 1) ((= (modulo n 2) 0) (let* ((hanbun (quotient n 2)) (half (beki a hanbun))) (if (checksize half) 0 (* half half)))) (#t (let* ((hanbun (quotient n 2)) (half (beki a hanbun))) (if (checksize half) 0 (* half half a)))))) (define answer (cond ((= kakuritsu 0) 0) ((= kakuritsu 1) (modulo ind 2)) (#t (* 0.5 (- 1 (beki (- 1 (* 2 kakuritsu)) ind)))))) (display answer) (newline)
これも、何回もWAを出しました。
ペナルティがなかったのが幸いでした。
さて、これ以降は問題を速く解くタイプのコンテスト以外のやつにも挑戦しようと思っています。
そういうのも記事として書けたら、と思っています。以上です。