AtCoder Grand Contest 034 に参加して
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/));
コンテスト結果
緑コーダーになった!
AtCoder Beginner Contest 128 に参加して
AtCoder Beginner Contest 128(略称ABC128)に参加しました。
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 に参加して
AtCoder Grand Contest 033(略称AGC033?)に参加しました。
AGC033
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 にエア参加して
AtCoder Beginner Contest 125に参加!するつもりだったけど、家庭の事情により今回は参加できず。
あと、EテレのSWITCHインタビューもみなければならなかった。Clusterの加藤さんが出た回。
ABC125
コンテスト後のエア参加だったけど、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の参加
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/));
次の参加時はもっと解けるようになっておきたいな。