Open17
AtCoder: 鹿本 特訓 (JavaScript)
ピン留めされたアイテム
mae616環境構築
※コンテストはローカル環境の方が便利だけど、過去問をやるのはChrome拡張機能が便利
mae616テンプレ
P00 例題01: Title
問題
解いたコード
// 使ってるテンプレファイル
function main(input) {
const args = input.split('\n');
const nums = args[0].split(' ');
// (処理)
console.log(b);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
mae616P47 例題01: Multiplication 1
問題
解いたコード
function main(input) {
const args = input.split('\n');
const [a, b] = args[0].split(' ').map(Number);
console.log(a * b);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
メモ
array.map((v)=>Number(v))がarray.map(Number)(GitHub Copilotさんが書いたコード)と書ける理由
前者はmapの関数に、あくまで(v) => Number(v)という関数参照を渡している。
引数vというのはmapメソッドが引数を渡すよ、て構造のもと書かれている。
後者のNumberは通常Number('123')とかで使われる。要はNumber(v)に変えられる。ただ渡すのは関数参照。Number関数は言い換えると
function Number(v){
// (引数vを数値に変換する処理)
}
なので、array.map(Number)で変わらず動作する。
(高階関数とかの考え方が関わっているらしいが今後勉強する)
mae616P51 例題02: Product
問題
解いたコード
function main(input) {
const args = input.split('\n');
const [a, b] = args[0].split(' ').map(Number);
console.log(a*b % 2 === 0 ? 'Even' : 'Odd');
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
mae616P56 例題03: Serval vs Monster
問題
解いたコード
function main(input) {
const args = input.split('\n');
const [hp, attack] = args[0].split(' ').map(Number);
console.log(Math.ceil(hp / attack));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
切り上げ
mae616P67 例題04: We Love Golf
問題
解いたコード
function main(input) {
const args = input.split('\n');
const k = Number(args[0]);
const [a, b] = args[1].split(' ').map(Number);
for(let i=a; i<=b; i++){
if(i % k === 0){
console.log('OK');
return;
}
}
console.log('NG');
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
mae616P71 例題01: Some Sums
問題
解いたコード
function main(input) {
const args = input.split('\n');
const [n, a, b] = args[0].split(' ').map(Number);
let sum = 0;
for(let i=1; i<=n; i++){
// iの各桁の合計を文字列の特性を利用して求める
let temp = 0;
const str_i = String(i);
for(const str of str_i){
temp += Number(str);
}
// 問題の合計を求める処理
if(a <= temp && temp <= b){
sum += i;
}
}
console.log(sum);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
改善
function main(input) {
const args = input.split('\n');
const [n, a, b] = args[0].split(' ').map(Number);
// 関数 各桁の合計を求める
const sumDigits = (num) => {
let temp = 0;
const str = String(num);
for(const c of str){
temp += Number(c);
}
return temp;
};
// メイン処理
let sum = 0;
for(let i=1; i<=n; i++){
const digits = sumDigits(i);
if(a <= digits && digits <= b){
sum += i;
}
}
console.log(sum);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
このくらいのものなら関数分割しなくてもいいと思うけど、複雑な問題にも対応できるように、本に書いてある通りに初級的な問題から関数分割を意識したほうがいいのかも、と思った。
mae616P85 例題06: Shift only
問題
解いたコード
function main(input) {
const args = input.split('\n');
const n = Number(args.shift());
let a = args[0].split(' ').map(Number);
let count = 0;
while(a.every(item => item % 2 === 0)){
count++;
a = a.map(item => item / 2);
}
console.log(count);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
mae616P99 例題07: Card Game for Two
問題
解いたコード
function main(input) {
const args = input.split('\n');
const n = Number(args[0]);
const a = args[1].split(' ').map(Number);
a.sort((a, b) => a - b).reverse(); // 降順に並び替える
let arice = 0;
let bob = 0;
for(let i=0; i<n; i++){
if(i % 2 === 0){
arice += a[i];
}else{
bob += a[i];
}
}
console.log(arice - bob);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
mae616P110 例題08: AcCepted
問題
解いたコード
function main(input) {
const args = input.split('\n');
const result = (function _ (s) {
const n = s.length;
if(s[0] !== 'A') return false;
let count = 0;
for(let i=1; i<n; i++){
if(2 <= i && i <= n-2 && s[i] === 'C'){
count++;
}else if(!/^[a-z]$/.test(s[i])){
return false;
}
}
return count === 1 ? true : false;
})(args[0]);
console.log(result ? 'AC' : 'WA');
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
Cがある範囲を誤読していてハマってしまった...
ついついそのまま書きがちだけど、関数分割は使ったほうがいいっぽい。
参考
mae616P124 例題09: Coins
問題
解いたコード
function main(input) {
const [a, b, c, x] = input.split('\n').map(Number);
let count = 0;
for(let i=0; i<=a; i++){
for(let j=0; j<=b; j++){
for(let k=0; k<=c; k++){
if(500 * i + 100 * j + 50 * k === x) count++;
}
}
}
console.log(count);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
これで全検索できたんだ...。for文のお題で出てこなければ、ずっと再帰でやってた。勉強になった。
参考
mae616P131 例題10: Minesweeper
問題
解いたコード
function main(input) {
const args = input.split('\n');
const [h, w] = args.shift().split(' ');
const s = args.map(item => item.split(''));
const countBom = (inArray, i, j) => {
if(inArray[i][j] === '#'){
return '#';
}
let count = 0;
if(i>0 && inArray[i-1][j] === '#') count++;
if(i<h && inArray[i+1][j] === '#') count++;
if(j>0 && inArray[i][j-1] === '#') count++;
if(j<w && inArray[i][j+1] === '#') count++;
if(i>0 && j>0 && inArray[i-1][j-1] === '#') count++;
if(i>0 && j<w && inArray[i-1][j+1] === '#') count++;
if(i<h && j<w && inArray[i+1][j+1] === '#') count++;
if(i<h && j>0 && inArray[i+1][j-1] === '#') count++;
return count;
}
for(let i=0; i<h; i++){
for(let j=0; j<w; j++){
s[i][j] = countBom(s, i, j);
}
}
s.forEach(item => console.log(item.join('')));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
改善
function main(input) {
const args = input.split('\n');
const [h, w] = args.shift().split(' ');
const s = args.map(item => item.split(''));
const d = [
//上下左右
{x: -1, y: 0},
{x: 1, y: 0},
{x: 0, y: -1},
{x: 0, y: 1},
// 斜め
{x: -1, y: -1},
{x: -1, y: 1},
{x: 1, y: -1},
{x: 1, y: 1},
];
const countBom = (inArray, i, j) => {
if(inArray[i][j] === '#'){
return '#';
}
let count = 0;
for(const diff of d){
const tempI = i + diff.x
const tempJ = j + diff.y;
if(tempI < 0 || tempI >= h || tempJ < 0|| tempJ >= w) continue; // 範囲外
if(inArray[tempI][tempJ] === '#') count++;
}
return count;
}
for(let i=0; i<h; i++){
for(let j=0; j<w; j++){
s[i][j] = countBom(s, i, j);
}
}
s.forEach(item => console.log(item.join('')));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
実行時間は最初の方が微妙に速いな。まあ、こう言う書き方もある程度で。
参考
mae616P158 例題11: Otoshidama
問題
解いたコード
function main(input) {
const args = input.split('\n');
const [n, y] = args[0].split(' ').map(Number);
for(let i=n; i>=0; i--){
for(let j=n-i; j>=0; j--){
for(let k=n-i-j; k>=0; k--){
if(i+j+k === n
&& i * 10000 + j * 5000 + k * 1000 === y){
console.log(`${i} ${j} ${k}`);
return;
}
}
}
}
console.log(`-1 -1 -1`);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
メモ
これだとTLEになったからfor文の回す数を変えた。
function main(input) {
const args = input.split('\n');
const [n, y] = args[0].split(' ').map(Number);
for(let i=n; i>=0; i--){
for(let j=n; j>=0; j--){
for(let k=n; k>=0; k--){
if(i+j+k === n
&& i * 10000 + j * 5000 + k * 1000 === y){
console.log(`${i} ${j} ${k}`);
return;
}
}
}
}
console.log(`-1 -1 -1`);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
アルゴリズムを工夫するといっても、そんなに難しく考える必要ないのかも。
本の解説見ると、3つのループでなく2つのループでできるよ、てことだったみたい。
下記でできた。確かにこっちの方がいい
function main(input) {
const args = input.split('\n');
const [n, y] = args[0].split(' ').map(Number);
for(let i=n; i>=0; i--){
for(let j=n-i; j>=0; j--){
const k = n - i - j;
if(i * 10000 + j * 5000 + k * 1000 === y){
console.log(`${i} ${j} ${k}`);
return;
}
}
}
console.log(`-1 -1 -1`);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
P167 例題12: Kagami Mochi
問題
解いたコード
function main(input) {
const args = input.split('\n');
const n = Number(args.shift());
const mochi = new Set();
for(let i=0; i<n; i++){
mochi.add(args[i]);
}
console.log(mochi.size);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
mae616P174 例題13: Green Bin
問題
解いたコード
function main(input) {
const args = input.split('\n');
const n = Number(args.shift());
const s = args.slice(0, n).map(item => item.split('').sort().join('')).sort();
let result = 0;
let count = 1;
let prev = s[0];
for(let i=1; i<n; i++){
if(prev === s[i]){
count++;
}else{
result += count * (count-1) / 2;
count = 1;
prev = s[i];
}
}
result += count * (count-1) / 2;
console.log(result);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
組み合わせの問題か。読解力はそこまで苦手意識なかったんだけど、問題がうまく読めとけないな。
mae616P184 例題14: DoubleCamelCase Sort
問題
解いたコード
function main(input) {
const [s] = input.split('\n');
let flg = false;
let str = '';
const ary = [];
for(let i=0; i<s.length; i++){
const code = s.charCodeAt(i);
str += s[i];
if (65 <= code && code <= 90){ // A to Z
// 大文字
flg = !flg;
if(!flg){
ary.push(str);
str = ''
}
}
}
ary.sort((a,b) =>
a.toUpperCase().localeCompare(b.toUpperCase()));
console.log(ary.join(''));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));
参考
mae616P192 例題15: スプリンクラー
問題
問題咀嚼
の番号がついた 1,2,3,…,N 個の頂点と N の番号がついた 1,2,3,…,M 本の無向辺からなる無向グラフが与えられます。 辺 M は頂点 i と u_i を双方向につないでいます。 v_i
- 無向辺...方向のない辺。
- 無向グラフ...無向グラフとは、グラフ理論における一種のグラフで、頂点同士が「辺」でつながっている構造です。無向グラフでは、辺に方向がありません。つまり、頂点Aと頂点Bを結ぶ辺がある場合、その辺はAからBへも、BからAへも同じ意味を持ちます。(ChatGPT)
それぞれの頂点には色を塗ることが可能で、はじめ頂点
は色 i で塗られています(この問題において、色は c_i 以上 1 以下の整数で表されます)。 10^5
それぞれの頂点にはスプリンクラーが設置されています。 頂点
にあるスプリンクラーを起動すると、頂点 i に隣接する全ての頂点の色がスプリンクラー起動時点の頂点 i の色で塗り替えられます。 i
以下の形式で与えられる
個のクエリ Q を順番に処理してください。 s_1,s_2,…,s_Q
- 頂点
の現在の色を出力する。その後、頂点 x にあるスプリンクラーを起動する。 x 1 xという形式で与えられる。- 頂点
の現在の色を出力する。その後、頂点 x の色を x で上書きする。 y 2 x yという形式で与えられる。
入力
入力は以下の形式で標準入力から与えられる。
N M Q
u_1 v_1
⋮
u_M v_M
c_1 c_2 ⋯ c_N
s_1
⋮
s_Q
出力
解いたコード
// 使ってるテンプレファイル
function main(input) {
const args = input.split('\n');
const nums = args[0].split(' ');
// (処理)
console.log(b);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));