はじめに
- プログラミング歴半年の素人が書いています。
- 不正確な内容、間違いがあったら申し訳ございません。
Hello, 競プロ！
初めて競技プログラミングなるものに挑戦してみます。
言語はJavaScriptです。調べたところあまりJSでAtcoderする人はいないようですね。今回参戦したコンテストの提出状況をみても、JSの提出は数える程でした。
それでも、初心者がやってみる分には言語の差なんて大したことないと思いますので、JSで今後もやって行こうと思っています。
なにより、私のように初心者の方にとってはJSはとっつきやすくていいのではないでしょうか。
今回の結果
AtCoderのコンテストでは、難易度別に複数の問題が出題されます。
今回参加した【AtCoder Beginner Contest 154】では、A問題〜F問題まで6問出題されました。
今回、私が正解できたのは
- A問題
- B問題
- C問題
の３つでした。
ABC154A - Remaining Balls
A問題は初歩中の初歩。与えられた文字列が一致しているか調べるだけでした。
"use strict";
const main = arg => {
const input = arg.trim().split("\n");
const strngs = input[0].split(" ");
const A = Math.floor(input[1].split(" ")[0], 10);
const B = Math.floor(input[1].split(" ")[1], 10);
const U = input[2];
if ( U === strngs[0]) {
console.log((A - 1), B);
} else {
console.log(A, (B - 1));
}
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
ABC154B - I miss you...
与えられた文字列の文字数分、'x'を出力するだけのシンプルな問題ですが、なぜかWA（不正解）に。
調べたところ、標準入力で受け取った文字列には、見えないスペースや改行が含まれている場合もあるとのこと。
入力された文字列の長さを.lengthで取得するまえに.trim()処理することで、ACになりました。
"use strict";
const main = arg => {
const inputLength = arg.trim().length; // .trim() する！
const letter = "x";
const answer = letter.repeat(inputLength).trim().replace(/\r?\n/g, '');
console.log(answer);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
ABC154C - Distinct or Not
標準入力として与えられる整数列に、重複する値があるかどうかを調べる。
配列をSetオブジェクト化することで、重複を取り除く処理ができる。
Setオブジェクトをもう一度Arrayオブジェクトに戻し、要素数が変わったかどうかを調べた。
"use strict";
const main = arg => {
const input = arg.trim().split("\n");
const nums = input[1].split(" ");
const set = new Set(nums);
const uniqueNums = Array.from(set);
nums.length === uniqueNums.length ? console.log("YES") : console.log("NO");
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
ABC154D - Dice in Line
D問題は不正解。
動作するプログラムは書けたが、TLE（Time Limit Exceeded：処理時間かかりすぎエラー）だった。
コードが動くかどうかだけでなく、どうやって処理を減らして効率よく実装するかが重要らしい。
このD問題は、累積和というテクニックをつかうことで処理を大幅に減らすことができると解説に書いてあった。コンテスト終了後に、ACするプログラムを作り上げた。
「配列内のある区間」を特定する問題では、累積和が必要になることがある
それと、何故かいままで文字列を整数に変換するときに
Math.floor()を使っていたけどparceInt()のほうが高速らしい。メモリを使わないほうが高速に動くっぽい。つまり、コンピュータにたくさん記憶しないようにするってことだろうか？
"use strict";
const main = arg => {
const input = arg.trim().split("\n");
const N = parseInt(input[0].split(" ")[0],10);
const K = parseInt(input[0].split(" ")[1],10);
const pArray = input[1].split(" ").map(n => parseInt(n,10));
// サイコロの期待値を得る関数
const kitaichi = i => (i + 1) / 2;
const kitaichiArray = pArray.map(p => kitaichi(p));
// 累積和を作成する関数
const cumulativeSum = (array) => {
let arr = [0];
array.reduce((a, i) => {
a === 0 ? arr.push(i) : arr.push(a + i);
return a + i
}, 0)
return arr;
}
// 期待値の累積和配列を作成
const cumulativeSumArray = cumulativeSum(kitaichiArray);
// 累積和配列の要素をループしながら最も大きい組を見つける
let answer = 0;
for (let i=K; i<N+1; i++) {
if (answer < (cumulativeSumArray[i] - cumulativeSumArray[i-K])) {
answer = (cumulativeSumArray[i] - cumulativeSumArray[i-K]);
} else {
continue;
}
}
console.log(answer);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
今回学んだこと
.trim()でデータを綺麗にする「配列内のある区間」を特定する問題では、累積和が必要になることがある
何故かいままで文字列を整数に変換するときに
Math.floor()を使っていたけどparseInt()のほうが高速らしい。処理を減らすことが、ACのカギ！
なんかメモリをうまく使えとどこかに書いてあったけど、それって例えばどんなことなんでしょう...？