ほねぶろぐ

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

AtCoder Grand Contest 034 に参加して

f:id:aftercider:20190428202214p:plain

AtCoder Grand Contest 034(略称AGC034)に参加しました。

いつもコンテストのタイミングにスタートできなかったんですが、今回は開幕と同時に参加!

結果はABの2完でした。

Cは…もう一歩って感じですね。

D以降はてんでだめでした。

A問題

「Aは瞬殺だぜ〜」と思ってましたが、今回はAGC。

実装自体はサクッとできたんですが、細かいif文の内容を逆にしちゃったりで、辛い思いをしました。。。(if(D < C)を逆に書いてた)

function Main(input) {
    var result;
    const N = parseInt(input.shift())
    const A = parseInt(input.shift())
    const B = parseInt(input.shift());
    const C = parseInt(input.shift())
    const D = parseInt(input.shift())
    const S = input[0];
    
    // 2連続があったらOUT
    const LastIndex = Math.max(C,D);
    var prevStone = false;
    for (var i = A - 1; i < LastIndex; i++) {
        var element = S.charAt(i);
        if(element === "#") {
            if(prevStone) {
                console.log("No");
                return;
            }
        }
        prevStone = element === "#";
    }
    
    // 追い越す必要があるとき
    if(D < C) {
        var spaceCount = 0;
        for (var i = B - 2; i < D + 1; i++) {
            var elem = S.charAt(i);
            if(elem === ".") {
                spaceCount++;
            } else {
                spaceCount = 0;
            }
            if(spaceCount == 3){
                console.log('Yes');
                return;
            }
        }
        console.log("No");
    } else {
        console.log("Yes");
    }
}

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

B問題

これは結構サクッと終わった。

if条件わけの漏れがあってWAもだしたけど、結果的には無事完了。

function Main(input) {
    const S = input[0];
    
    var currentA = 0;
    var sum = 0;
    var prevB = false;
    
    for (var index = 0; index < S.length; index++) {
        var element = S.charAt(index);
        if(element === "A") {
            if(prevB) {
                currentA = 0;
            }
            currentA++;
        }else if(element === "B") {
            if(prevB) { 
                currentA = 0;
            }
        } else {
            if(prevB) {
                sum += currentA;
            } else {
                currentA = 0;
            }
        }
        prevB = element === "B";
    }

    console.log(sum);
    
}

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

C問題

うーん、むずかしかった。

これ解けたら結構順位上だっただろうなぁ・・・

function Main(input) {
    const N = parseInt(input[0].split(/\s/)[0]);
    const X = parseInt(input.shift().split(/\s/)[1]);
    const BLU = [];
    input.forEach(element => {
        var sp = element.split(/\s/);
        var value = {
            B: parseInt(sp[0]),
            L: parseInt(sp[1]),
            U: parseInt(sp[2]),
        };
        value.MIN_POINT = value.B * value.L; // 最小優先度にした時の獲得ポイント
        value.MAX_DIV = (X - value.B) * value.U; // X時間勉強したら埋められる差
        BLU.push(value);
    });
    BLU.sort((a, b) => b.MAX_DIV - a.MAX_DIV); // 降順

    var enemySum = 0; // 全部最小優先度にした時の相手のポイント
    BLU.forEach(element => {
        enemySum += element.MIN_POINT;
    });

    var difference = enemySum;
    var learnTime = 0;
    var lastIndex = 0;
    for (var i = 0; i < N; i++) {
        var element = BLU[i];
        difference -= element.MAX_DIV + element.MIN_POINT;
        if (difference <= 0) {
            difference += element.MAX_DIV + element.MIN_POINT;
            // 超えたら元に戻してブレイク
            lastIndex = i;
            break;
        } else {
            learnTime += X;
        }
    }

    // 最後の調整
    var minLearnTime = Number.MAX_SAFE_INTEGER;
    for (var i = lastIndex; i < N; i++) {
        var element = BLU[i];
        minLearnTime = Math.min(minLearnTime, Math.ceil((difference - element.MIN_POINT) / element.U) + element.B);
    }
    learnTime += minLearnTime

    console.log(learnTime);
}

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

コンテスト結果

f:id:aftercider:20190603183458p:plain Contest Result - AtCoder

緑コーダーになった!

AtCoder Beginner Contest 128 に参加して

f:id:aftercider:20190428202214p:plain

AtCoder Beginner Contest 128(略称ABC128)に参加しました。

atcoder.jp

ABC128

今回も安定の20分おくれで遅刻スタート。結果はABCの3完でした。

A問題

書くだけ。

B問題

ソート順の設定と、ソート後のインデックスの保持だったので、これも書くだけ。

function Main(input) {
    var result;
    const N = parseInt(input.shift());
    const SP = [];
    for (var i = 0; i < N; i++) {
        SP.push({
            I: i + 1,
            S: input[i * 2],
            P: parseInt(input[i * 2 + 1])
        })
    }

    SP.sort((a, b) => {
        var stComp = a.S.localeCompare(b.S);
        if (stComp == 0) {
            return b.P - a.P;
        }
        return stComp;
    })
    SP.forEach(value => console.log(value.I));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n|\s/));

C問題

条件結構絞ってあるので、全探索いけそうと思って取り組んだけども、バリエーション作る関数が思ったより作るの大変だった。。。

あと、毎回やってしまうところで、インデックスを1スタートとすべきところを0のままやってしまい、タイムロス。。。

function Main(input) {
    var result;
    const N = parseInt(input[0].split(/\s/)[0]);
    const M = parseInt(input.shift().split(/\s/)[1]);
    const KS = input.slice(0, M).map(value => value.split(/\s/).map(v => parseInt(v)));
    const P = input.slice(M)[0].split(/\s/);

    var count = 0;
    generateMap(N).forEach(SW => check(SW, KS, P) == true ? count++ : 0);
    console.log(count);
}

function generateMap(N) {
    var arr = [];
    for (var index = 0; index < Math.pow(2, N); index++) {
        var value = index;
        var insert = [];
        for (var i = 0; i < N; i++) {
            insert.push(value % 2);
            value = Math.floor(value / 2);
        }
        arr.push(insert);
    }
    return arr;
}

function check(sw, KS, P) {
    for (var index = 0; index < KS.length; index++) {
        var ks = KS[index];
        var check = 0;
        for (var i = 1; i < ks.length; i++) {
            var s = ks[i] - 1;
            if (sw[s] == 1) check++;
        }

        if (P[index] == "1") check++;
        if (check % 2 > 0) return false;
    };
    return true;
}

Main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split(/\n/));

D問題

大体の方針は立ったので、あとは実装するだけだとなったけど、スムーズに実装ができず、時間切れ。

定番の関数をストックしておくといいのかな・・・

解答見たら、方針はあっていたのでその点はよかった。

感想

今回のコンテストでとりあえず茶色コーダーになった。

コンテストの問題も難しいけど、一番難しいのはコンテスト開催の時間にPCの前にいることだな・・・

毎度思うことだけど、コンテストで使うNodeJSのバージョンを今のv5.12からv10あたりまで上げてほしい。。。

AtCoder Grand Contest 033 に参加して

f:id:aftercider:20190428202214p:plain

AtCoder Grand Contest 033(略称AGC033?)に参加しました。

atcoder.jp

AGC033

f:id:aftercider:20190504235029p:plain

50分おくれでの参加だったんですが、結果はABの2完でした。

AにTLEで結構手こずってしまった一方、Bは実装中に閃いて比較的にすぐおわりました。

残り時間でDを解こうと思ったんですが、足りなかったですね・・・

A問題

とりあえず「毎回全探索でどのくらいのもんだろう?A問題だしいけるんじゃない?」と思って、ひたむきに実装しましたが、ABCのA問題とは違いましたね・・・

あえなくTLEでダメでした。

ということで、回答にもあった通り、チェックするマスを絞って塗っていく手法を採用してAC。

実装はとても汚い感じ(涙)

function getCell(w, h, input, W, H) {
    return input[Math.max(0, Math.min(h, H - 1))][Math.max(0, Math.min(W - 1, w))];
}

function insert(w, h, input, W, H, value) {
    input[Math.max(0, Math.min(h, H - 1))][Math.max(0, Math.min(W - 1, w))] = value;
}

function checkValid(w, h, W, H) {
    return h == Math.max(0, Math.min(h, H - 1)) && w == Math.max(0, Math.min(W - 1, w));
}

function Main(input) {
    const H = parseInt(input.shift());
    const W = parseInt(input.shift());

    isBlack = false;
    var count = 0;

    var currentMap = [];
    var targetMap = [];
    input.forEach(element => {
        currentMap.push(element.split(""));
    });

    for (var h = 0; h < H; h++) {
        for (var w = 0; w < W; w++) {
            var cell = getCell(w, h, currentMap, W, H);
            if (cell == "#") {
                if (checkValid(w - 1, h, W, H) && getCell(w - 1, h, currentMap, W, H) == ".") targetMap.push([w - 1, h]);
                if (checkValid(w + 1, h, W, H) && getCell(w + 1, h, currentMap, W, H) == ".") targetMap.push([w + 1, h]);
                if (checkValid(w, h + 1, W, H) && getCell(w, h + 1, currentMap, W, H) == ".") targetMap.push([w, h + 1]);
                if (checkValid(w, h - 1, W, H) && getCell(w, h - 1, currentMap, W, H) == ".") targetMap.push([w, h - 1]);
            }
        }
    }

    while (targetMap.length > 0) {
        var nextTarget = [];
        var lightTarget = [];
        targetMap.forEach(element => {
            if (getCell(element[0], element[1], currentMap, W, H) == ".") {
                lightTarget.push(element);
            }
            insert(element[0], element[1], currentMap, W, H, "#");
        });
        targetMap = lightTarget;
        targetMap.forEach(element => {
            var w = element[0];
            var h = element[1];
            if (checkValid(w - 1, h, W, H) && getCell(w - 1, h, currentMap, W, H) == ".") nextTarget.push([w - 1, h]);
            if (checkValid(w + 1, h, W, H) && getCell(w + 1, h, currentMap, W, H) == ".") nextTarget.push([w + 1, h]);
            if (checkValid(w, h - 1, W, H) && getCell(w, h - 1, currentMap, W, H) == ".") nextTarget.push([w, h - 1]);
            if (checkValid(w, h + 1, W, H) && getCell(w, h + 1, currentMap, W, H) == ".") nextTarget.push([w, h + 1]);
        });
        count++;
        targetMap = nextTarget;
    }

    console.log(count);
}

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

B問題

着手して最初、累積和の問題かな?と思って、累積和を作るロジックを書いていました。

途中、子供が泣いて様子を見に行った時に、「あ、これじゃだめだ」と気づき、方針転換。

その結果、シンプルなコードでACになりました。

A問題よりこっちの方が簡単だった感じ。

function Main(input) {
    const H = parseInt(input.shift());
    const W = parseInt(input.shift());
    const N = parseInt(input.shift());
    const sr = parseInt(input.shift());
    const sc = parseInt(input.shift());
    const S = input.shift();
    const T = input.shift();

    var left = sc, right = sc, top = sr, bottom = sr;

    for (var i = 0; i < N; i++) {
        var s = S.charAt(i);
        var t = T.charAt(i);
        if (s == "L") {
            left--;
        } else if (s == "R") {
            right++;
        } else if (s == "U") {
            top--;
        } else {
            bottom++;
        }
        if (left <= 0 || right > W || top <= 0 || bottom > H) {
            console.log("NO");
            return;
        }

        if (t == "L") {
            right = Math.max(1, right - 1);
        } else if (t == "R") {
            left = Math.min(W, left + 1);
        } else if (t == "U") {
            bottom = Math.max(1, bottom - 1);
        } else {
            top = Math.min(H, top + 1);
        }
    }
    console.log("YES");
}

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

感想

AGCは難しい。。。

ただ、やりごたえはあるので、過去問やってみよう。

AtCoder Beginner Contest 125 にエア参加して

f:id:aftercider:20190428202214p:plain

AtCoder Beginner Contest 125に参加!するつもりだったけど、家庭の事情により今回は参加できず。

あと、EテレのSWITCHインタビューもみなければならなかった。Clusterの加藤さんが出た回。

f:id:aftercider:20190428195950p:plain
SWITCHインタビュー 達人達(たち)「諏訪部順一×加藤直人」

ABC125

f:id:aftercider:20190428195618p:plain

コンテスト後のエア参加だったけど、4問とも難なく回答できた。

C問題

最大公約数っていう、C問題が結構難しそうな雰囲気出してた。

ただ、計算量が線形に落ち着いてたのでいけるかなー?

と思って出したのが無事ACだったのでよかった。

function checkAll(div, As) {
    var mod = 0
    var result = true;
    As.forEach(element => {
        if (element % div > 0) {
            mod++;
            if (mod > 1) {
                result = false;
            }
        }
    });
    return result;
}

function Main(input) {
    const N = parseInt(input.shift());
    var As = input.map(x => parseInt(x));

    As = As.sort((a, b) => { return a - b; }); // 昇順ソート

    var firstDiv = 0;
    var secondDiv = 0;

    for (var div = As[0]; div > 0; div--) {
        if (As[0] % div == 0) {
            // 約数なら
            if (checkAll(div, As)) {
                firstDiv = div;
                break;
            }
        }
    }

    for (var div = As[1]; div > firstDiv; div--) {
        if (As[1] % div == 0) {
            // 約数なら
            if (checkAll(div, As)) {
                secondDiv = div;
                break;
            }
        }
    }

    console.log(Math.max(firstDiv, secondDiv));
}

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

D問題

CとDは入れ替えてもよさそうな難易度だった。

function Main(input) {
    const N = parseInt(input.shift())
    const As = input.map(x => parseInt(x));

    var isOdd = false;
    var absSum = 0;
    var minAbs = Number.MAX_SAFE_INTEGER;

    As.forEach(element => {
        if (element < 0) {
            isOdd = !isOdd;
            element *= -1;
        }
        absSum += element;
        minAbs = Math.min(minAbs, element);
    });

    if (isOdd) {
        absSum -= minAbs * 2;
    }

    console.log(absSum);
}

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

# 感想

かなりスムーズにとけたとはいえ、30分くらいはかかってて、順位上位の人たちって何者なんだろうかと謎が深まるABC125だった。

あと、最大公約数・最小公倍数ってのは解く定石があるんですね・・・しらなかった。


[http://tota66.hatenablog.com/entry/2019/04/27/235849:title]


[https://qiita.com/tawatawa/items/408b872a7092be0d7b3c:title]

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/));

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