急にやる気が出て、AtCoderの過去問を解こうと思い立ちました。
ということで、やっていなかったABC100
abc100.contest.atcoder.jp
を解くことに。A,B,C問題まではスムーズに自分で解け、D問題は解説動画(Youtube)を見て解きました(何故か解説PDFがなく・・・動画で見ました)。
意味なく、各問題を別々の言語で解きました。特にD問題はSchemeで解いたのですが、久々に"Schemeだから綺麗に書けた"問題でした(もっと綺麗に書けるとは思うのですが・・・でも僕がJavaやらで書くよりは綺麗なコードになりました)。
A問題
問題文はややこしく書いていますが、結局は「入力されるA,Bがともに8以下であればOK」ですね。
Rubyで書きました。
a,b=gets.chomp.split(" ").map(&:to_i); if a < 9 && b < 9 then print("Yay!") else print(":(") end
B問題
「あれ? 100^D * Nで一発じゃないの?」と思ってしまいそうですが、「N=100」の場合のみ例外が発生します。注意!
JavaScriptで書きました。
// inputに入力データ全体が入る function Main(input) { // 1行目がinput[0], 2行目がinput[1], …に入る input = input.split(" "); d=~~input[0] n=~~input[1] bai = 1 if(d==0){ if(n<100){ console.log('%d',n) }else{ console.log('%d','101') } }else if(d==1){ if(n<100){ console.log('%d',n*100) }else{ console.log('%d','10100') } }else{ if(n<100){ console.log('%d',n*10000) }else{ console.log('%d','1010000') } } } //*この行以降は編集しないでください(標準入出力から一度に読み込み、Mainを呼び出します) Main(require("fs").readFileSync("/dev/stdin", "utf8"));
C問題
ややこしい問題・・・のように見えますが、「3倍する」という動作が失敗することはないので、
「"1つの数字を2で割って残りを3倍する"」をしまくるのが一番操作回数が多くなることになります。
つまりは、各数字の"2で何回割れるか"の和が答えになりますね。
Javaで書きました。
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int ans = 0; for(int i = 0; i < n; i++){ int num = sc.nextInt(); while(num % 2 == 0){ ans++; num /= 2; } } System.out.println(ans); } }
D問題
解き方を考えていたんですが、思いつかず・・・諦めて解説動画をみたら、シンプルな解き方でびっくりしました。
各要素をx,y,zとしたら、
|x|+|y|+|z|
を最大化したい、ということになります。
ただ、実はこれは「下記の8つの式それぞれを最大化したなかで最大なもの」とイコールになります。
x+y+z x+y-z x-y+z x-y-z -x+y+z -x+y-z -x-y+z -x-y-z
つまり、上記8個の式それぞれについて、最大化された場合の値を求め、その8つのうち最大なものを返せばよいのです。
そして、各式の最大化は簡単ですね。
たとえば「x+y+z」が最大となる組み合わせを求めるには、
各要素のx+y+zを求め、大きい順にM個足せばよいです。
Schemeで書きました。入力される数がint超えるくらいこともあるという設定ですが、Schemeはそのあたり気にしなくていいので楽です。
行数こそ多いですが、ほぼコピペなので割とスムーズに書けました!
(define N (read)) (define M (read)) (define (nlist n) (if (= n 0) '() (let* ((a (read)) (b (read)) (c (read)) (l (list a b c))) (cons l (nlist (- n 1)))))) (define input (nlist N)) ;先頭からn個の和 (define (topn list n) (define (top list n ans) (if (= n 0) ans (top (cdr list) (- n 1) (+ ans (car list))))) (top list n 0)) ;ここからの8行、もう少し綺麗に書きたかった (define (c1 list)(let*((a (car list))(b (car (cdr list)))(c (car (cdr (cdr list)))))(+ (+ a b) c))) (define (c2 list)(let*((a (car list))(b (car (cdr list)))(c (car (cdr (cdr list)))))(- (+ a b) c))) (define (c3 list)(let*((a (car list))(b (car (cdr list)))(c (car (cdr (cdr list)))))(- (+ a c) b))) (define (c4 list)(let*((a (car list))(b (car (cdr list)))(c (car (cdr (cdr list)))))(- (+ b c) a))) (define (c5 list)(let*((a (car list))(b (car (cdr list)))(c (car (cdr (cdr list)))))(- a (+ b c)))) (define (c6 list)(let*((a (car list))(b (car (cdr list)))(c (car (cdr (cdr list)))))(- b (+ a c)))) (define (c7 list)(let*((a (car list))(b (car (cdr list)))(c (car (cdr (cdr list)))))(- c (+ a b)))) (define (c8 list)(let*((a (car list))(b (car (cdr list)))(c (car (cdr (cdr list)))))(- 0 (+ a b c)))) ;(map func list) (define a1 (topn (sort (map c1 input) >) M)) (define a2 (topn (sort (map c2 input) >) M)) (define a3 (topn (sort (map c3 input) >) M)) (define a4 (topn (sort (map c4 input) >) M)) (define a5 (topn (sort (map c5 input) >) M)) (define a6 (topn (sort (map c6 input) >) M)) (define a7 (topn (sort (map c7 input) >) M)) (define a8 (topn (sort (map c8 input) >) M)) (display (topn (sort (list a1 a2 a3 a4 a5 a6 a7 a8) >) 1))
ということで、やっぱりBeginnerContestのD問題あたりが僕の"ちょうど解けないライン"のようです。
他の過去問も解いてみて、力付けていきたいです。
CodinGameのClash of Codeを解きまくっているおかげで、「書くこと自体の速さ」や「知ってる関数」は増えてきたようなので、「難易度の高い問題にじっくり取り組む力」もちゃんとつけていきたいですね。
終わり。