C++の練習を兼ねて, AtCoder Beginner Contest 283 の 問題C (Cash Register) ~ 問題D (Scope) を解いてみた.
■感想.
1. 問題C, D は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 問題C, Dで, stack の 復習ができたので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 283 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題C/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) int main(){ // 1. 入力情報. char c[101010]; scanf("%s", c); string S(c); // 2. ボタンを押す. stack<char> st; rep(i, S.size()){ if(S[i] == '0'){ if(st.top() == '0'){ st.pop(); st.push('#'); continue; } } st.push(S[i]); } // 3. 出力. printf("%d\n", st.size()); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
[入力例] 40004 [出力例] 4 ※AtCoderテストケースより [入力例] 1355506027 [出力例] 10 ※AtCoderテストケースより [入力例] 10888869450418352160768000001 [出力例] 27 ※AtCoderテストケースより [入力例] 1785105004847100897567100964501590001439902666470652249691970000320000013530000000104684273796321391 [出力例] 89 [入力例] 3571062473377399226311502600000000004301915504888668914316992165195828227931444705642124895663068311926000000000045054240336955075967197575737372788176327545435301343481345241930400000000009421146625064611409952999586750537613571473170559487379667436957194682515291381049498170415074585728548619029623111459050903296706318360442471650277945689265336393231890647416832135999417085001286323056038363992774314332727674699730405414802563066090000000000866425809637278257270595877511414783956600000000006513705678364730000000000000000000006721682052138160981567818812652480667750977332524210157085359151119180863279995486949119316605057712921127513633488207757937038381405125526774362717463841138969384644539053504898570082901128121542454435470000000000000000000008961478441788048944020670000000000000000000000000000000000000000004260844879853898339838378889786310200781205635085522107726531271268138964441207708723659787845717080809950000000000596393212314806635887079962930925464621301488711126874284000 [出力例] 925 |
■C++版プログラム(問題D/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) int main(){ // 1. 入力情報. char c[303030]; scanf("%s", c); string S(c); // 2. 操作. bool ok = true; stack<char> st; set<char> box; rep(i, S.size()){ // 英小文字. if(S[i] >= 'a' && S[i] <= 'z'){ // ボールが既に箱に入っているか? if(box.count(S[i])){ ok = false; break; } // ボールを箱に追加. box.insert(S[i]); st.push(S[i]); } // 左括弧. if(S[i] == '(') st.push(S[i]); // 右括弧. if(S[i] == ')'){ while(1){ char b = st.top(); if(b != '('){ // ボールを箱から取り出す. st.pop(); box.erase(b); }else{ break; } } st.pop(); } } // 3. 出力. printf("%s\n", ok ? "Yes" : "No"); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
[入力例] ((a)ba) [出力例] Yes ※AtCoderテストケースより [入力例] (a(ba)) [出力例] No ※AtCoderテストケースより [入力例] (((()))) [出力例] Yes ※AtCoderテストケースより [入力例] abca [出力例] No ※AtCoderテストケースより [入力例] (ab)b(bc)c(ca) [出力例] No [入力例] (ab)b(ca)c(a)a [出力例] Yes [入力例] (a(bc)b(cd)c(de))(a(bc)b(cd)c(de))(a(bc)b(cd)c(de)) [出力例] Yes |
■参照サイト
ユニークビジョンプログラミングコンテスト2022 冬(AtCoder Beginner Contest 283)