ほねぶろぐ

アニメとAndroidが好きなほねっとのブログです。

Tenka1 Programmer Beginner Contest 2019の参加

f:id:aftercider:20190422130013p:plain

atcoder.jp

https://atcoder.jp/contests/tenka1-2019-beginner

2つしか解けなかった〜〜〜。残念。 Cは問題の意味を間違って、最初完全に違う実装してたのがもったいなかった。 解説ほどスマートではなかったにしろ、あと少しまで行ったので悔やまれる。

DはDPだろうなーと思いつつも、どこをDPにするかがわからず時間切れ。 とりあえずTLEはするけどDPなしのコード作るまでは行った。

全部いつも通りJSで書いた。

A問題

チャチャッと終わらせた。

function Main(input) {
    const A = parseInt(input[0])
    const B = parseInt(input[1])
    const C = parseInt(input[2])
    
    if((A < C && C < B) || (B < C && C < A)) {
        console.log("Yes");
    } else {
        console.log("No");
    }
}

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

B問題

正規表現使うかなーと思ったけど、調べるの面倒だったのでこれでやった。

function Main(input) {
    var result;
    const N = parseInt(input[0])
    const S = input[1]
    const K = parseInt(input[2])-1
    
    const target = S.charAt(K);
    var ret = "";
    for(var i = 0; i < N; i++){
        ret += S.charAt(i) == target ? target : "*";
    }
    console.log(ret);
}

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

C問題

変に配列を分割・整理して、そこの実装ミスに時間を取られてしまった。 これは悔しいやつだった。 下のコードはWAでる状態。

function Main(input) {
    const N = parseInt(input[0])
    const S = input[1]
    
    var BW = [];
    if(S.charAt(0) == "."){
        BW.push(0);
    }

    var prev = S.charAt(0);
    var count = 0;
    for (var i = 0; i < N; i++) {
        const element = S.charAt(i);
        if(element == prev){
            count++
        } else {
            BW.push(count);
            prev = element;
            count = 1;
        }
    }
    if(count > 0) {
        BW.push(count);
    }
    if(BW.length %2 > 0){
        BW.push(0);
    }

    var min = Number.MAX_SAFE_INTEGER;
//    console.log(BW);

    for (var i = 0; i < BW.length/2 + 1; i++) {
        var sum = 0;
        for (var j = 0; j < BW.length/2; j++) {
            sum += i <= j ? BW[j*2+1]: BW[j*2];
        }
        
        min = Math.min(sum, min);
    }

    console.log(min);
}

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

D問題

TLEと一部WAが出るのを潰す時間がなかったやつ。 これがすんなり解けるようになったらかっこいいな〜。

function canBuild(a, b, c) {
    return (a + b > c && b + c > a && c + a > b);
}

function check(r, g, b, As, index, memo) {
    if (As.length == index) {
        return canBuild(r, g, b) ? 1 : 0;
    } else {
        var rgb = [r, g, b];
        rgb.sort((a, b) => { return a - b; });
        var key = "" + rgb[0] + "-" + rgb[1] + "-" + rgb[2] + "-" + index;
        if (typeof memo[key] != "undefined") {
            return memo[key];
        } else {
            const a = As[index];
            var result = (
                check(r + a, g, b, As, index + 1, memo) 
            + check(r, g + a, b, As, index + 1, memo) 
            + check(r, g, b + a, As, index + 1, memo));
            memo[key] = result;
            return result;
        }
    }
}

function Main(input) {
    const N = parseInt(input[0])
    var As = [];
    input.slice(1).forEach(element => {
        const value = parseInt(element);
        As.push(value);
    });
    var memo = {};

    console.log((check(As[0], 0, 0, As, 1, memo) * 3) % 998244353);
}

// 改行・空白で分割
Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

次の参加時はもっと解けるようになっておきたいな。