AtCoder Beginner Contest 100を解きました

急にやる気が出て、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を解きまくっているおかげで、「書くこと自体の速さ」や「知ってる関数」は増えてきたようなので、「難易度の高い問題にじっくり取り組む力」もちゃんとつけていきたいですね。
終わり。