C++の練習を兼ねて, AtCoder Beginner Contest 308 の 問題C (Standings) ~ 問題E (MEX) を解いてみた.
■感想.
1. 問題C ~ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, 幅優先探索 の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 308 解説 の 各リンク を ご覧下さい.
■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 34 35 36 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) #define all(x) x.begin(), x.end() struct CoinToss { LL a, b, c; bool operator < (const CoinToss& rhs) const { return (a * (rhs.a + rhs.b) > rhs.a * (a + b)) || ((a * (rhs.a + rhs.b) == rhs.a * (a + b)) && (c < rhs.c)); } }; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vector<CoinToss> v(N); rep(i, N){ scanf("%lld %lld", &v[i].a, &v[i].b); v[i].c = i + 1; } // 2. sort. sort(all(v)); // 3. 出力. rep(i, N) printf("%d%s", v[i].c, (i < N - 1) ? " " : "\n"); 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 46 47 48 49 50 51 52 53 54 55 56 |
[入力例] 3 1 3 3 1 2 2 [出力例] 2 3 1 ※AtCoderテストケースより [入力例] 2 1 3 2 6 [出力例] 1 2 ※AtCoderテストケースより [入力例] 4 999999999 1000000000 333333333 999999999 1000000000 999999997 999999998 1000000000 [出力例] 3 1 4 2 ※AtCoderテストケースより [入力例] 5 0 1 1 2 2 0 3 1 3 2 [出力例] 3 4 5 2 1 [入力例] 10 1 2 4 1 11 10 5 4 1 8 8 2 7 10 4 1 0 5 8 6 [出力例] 2 6 8 10 4 3 7 1 5 9 |
■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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<int, int>; #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--) #define h first #define w second const int INF = 2020202020, dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1}; int board[505][505], memo[505][505]; int main(){ // 1. 入力情報. int H, W; scanf("%d %d", &H, &W); rep(i, 505) rep(j, 505) board[i][j] = memo[i][j] = INF; rep(i, H){ char c[505]; scanf("%s", c); rep(j, W){ if(c[j] == 's') board[i][j] = 0; if(c[j] == 'n') board[i][j] = 1; if(c[j] == 'u') board[i][j] = 2; if(c[j] == 'k') board[i][j] = 3; if(c[j] == 'e') board[i][j] = 4; } } // 2. bfs. // https://ja.wikipedia.org/wiki/幅優先探索 auto bfs = [&](P s) -> void{ // 空のキュー. queue<P> q; // 探索開始地点が条件を満たしてない. if(board[s.h][s.w]) return; // 訪問済み. memo[s.h][s.w] = 0; // 探索地点 s をキュー q に追加. q.push(s); while(!q.empty()){ // キューから取り出す. P c = q.front(); q.pop(); // 現在文字. int cur = board[c.h][c.w]; // 上下左右を見る. rep(i, 4){ // x: 列方向, y: 行方向 で考える. int nh = c.h + dy[i]; int nw = c.w + dx[i]; // 訪問不可能なマスは, Skip. if(nh < 0 || nh >= H || nw < 0 || nw >= W || board[nh][nw] == INF) continue; // 訪問先文字. int nex = board[nh][nw]; // 訪問可能 かつ 未訪問 であれば, 最短距離を設定. if(memo[nh][nw] == INF && nex == (cur + 1) % 5){ memo[nh][nw] = memo[c.h][c.w] + 1; q.push({nh, nw}); } } } }; bfs({0, 0}); // 3. 出力. printf("%s\n", memo[H - 1][W - 1] == INF ? "No" : "Yes"); 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 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 |
[入力例] 2 3 sns euk [出力例] Yes ※AtCoderテストケースより [入力例] 2 2 ab cd [出力例] No ※AtCoderテストケースより [入力例] 5 7 skunsek nukesnu ukeseku nsnnesn uekukku [出力例] Yes ※AtCoderテストケースより [入力例] 15 11 snutghbldly soklwsjxmii biesxbksmrr ezxnuwubdjj hvwskeshnl wnicaunupkx ffblnsekgoz qqqkuhuvxid qqqetipergn tttsnhqubln yyynukelgps nrlasxkukch zmnxuounetn zbgknusnsuv phokakenmnu [出力例] No [入力例] 30 25 skiomhacwfkafimcrvbqxwoai nufnexufygjwrycsasljzarvq pkfazxcdzlzguzxzdqwafcaaq iesnhesupiudqrrrsqdlmznpb mvhuzknphrmamxtdrnqscfhnc wlukeuuohmukqzywzowekgvwn wldcsnknlasoeoetwkuhfmnpt pekunsevbkdqenjuqsclgumfj sswwfwxgrubryhvnrplesonge anaiavxwjqtwlbdnaesknrogq tukerjjvazkyxdcdjknuuzxbx ryqsnukezrikzqvpnupakfzwj whfagpasqcyrehpeswvaesayx ctwhrbtndeyndmzkcetnpnsbl kosfhxjukeqztthuicwemuked xwcvwzchjshaqtsnrseuvojsi jnabnryfxnukemekbwuaekuna yravsmhdvywfsjkecwsksbiht tmtrwqptyylaneukkwlunukyf jeemxcxyjrbpuindsbrzbrezs wxxmxjekunsekaszuzfkunsql uxqexoszjgsnukeluyfetovrf hyvrsknubwevhpdjsetsnafqw uhatbihknukiyvnnllfzukezi jiwtergeszqexapybhuwztspw cstuslolbouninupufyjiunao xmqpegtadpbdryaolohdekjte lwxhvpxeqlxsgoitiyzosqesn ecyenmbsxlyzkkwjzenfnukku mnhwyfpsqcsdlqfojeywmmtes [出力例] Yes [入力例] 75 50 sjwbxqzfwknxcbhgjonlobwnqyveiazvaxqvwixktnvoxgkkim ndvnixsficwuarwlmlbklowjapvczpqlxmcrhuyejgwntqhntt uukewtqmnbtjvypobefunvmkyrststfrkeafofadjpqwzwookg knhseiftrluyrizoflrbonbwwfdluamnhaqnqpeufaushddnzo esfnwcndypqyuflcakdxfczfpicqdcdcqudobrycrrdhruaffy nozukeivbojircbotmpwlvndoacrxshbziwqypijxrcwsxednm tdyvrsgqtawusitwxozemczgpbqirxvavpfhcfhlslcwuuubpz stlsunwkehvxeuaqiwgulysylpaulrzqbjdqngekquagdofnqr nsuqjutooiwaceeylxjrelxaliefnvzytwfeszrhfhqiajdgot hzdhbkbscbuluwgcrkwerjhywfiqothraawvzedmuvsqfngdhv wkvqpesnjrmpszdvfbfuvhwiruecwkpgwqtajkcivcflmpxbrr meyrbdvukbzzqhzpuxucvihjgbkflfvdfaflmiydgkqscebker ojnekunseplmgtyziprylgcbijfkkgwtjpfrilrqkxzdtvcvyb cujsudrwcoozvpbewvlnzpkzytodvsivotdyoojnwfbgssshde hzcnjctmdakobdtwwrllxtyjuiorubbcxervnlotwsfkbbfuup ybnufmofgqkhxpqxmtqyyvnomjpqysqqjzsnwatrsytjwgneub dxhkunwngvylhdfkacugpfcjjogvjgrghtzlrutlxllpniuxle ilnesnhcuwhwbotbjlcpznuquqsmdzgyegzctnkxghffidqtjb jcetlukeyvoxwufnsmjnpgmupykuysumlbekgjprttodtgboof egaanjasnthjoltkmwjxfupcbojlrxlcdpqhddtfumsurnriwi zsyqyxgeukesnukdwllmnjgztrlqmmzhuffuxwofmduyvukhzv hwlywruitgcruaezlpyqpsgfplfzearxegrmzbbwjgjjxgonns utqnvudqqilmcusqnrzghjmvibkhbyrtpjqsxpwrzhrfjilxjg aawwdirgmcuofinmxlppruvsfpueoeuzdsjsuuwqxblajcwfpf lbbwfjbjodnhnpuqoyfnkecaquksjyyxyecfwdkdenkydtrgjs acmlgumjwhcttbkisyktpbbubqxikjwqaetdhlbtoqkbogdhbn mcygqwomflkbftesnukexakdksqvsycbeujghmavramlijamld chefsqcetmynklfqgiasnukeaaavzyjrxnomilnddranevsolg mixpgpcpjhtygiwygidndcsspibqbwpcxlmqppvykeqkloname dknfnsexdgehoivqurhuqbmnjdkgfxflubkhayonladaufusew xutojxtnjbdkizuhlyhkjxaunisicwdtbtrppefrjfoajmokde ghqcmemdvxcnxcogrssevbkkuxyynyfehnyfoggtsybjkzzrhl rrcxbkjibqtmpzhxlanelnsepzwefzpecvqmtyvovcsnilgcep tjssoziqntenvqwpwpuekuwteuleveajteqdstnsdyryhjvybd mameshtifwbhoshrgxkesnuaynwvcprbzhqkkqeaiyvgbtkrvh ictecttspdjkqxyoeerjqikwcuxgzwltiiiwolsfzwezjjyrfn jajvnsohngvzcvlvfpglkaeszjagruowhkdqdjbtogjhcueumn ahlfuwvzybdetepnetybuepnflyslqgtouphpydcgxzqwfwkjj xfaukwakjlkuefzwdhnrlvpuyuwinowsfladqazxfapbjrwczm xlmnhxpbecomfgfcehglckoknvhqtxewxblaradsmwyyivywfy rytpjiuyykoignzvqntqpzsesnbeddkqqsjbxbxzxsqjbsijcb lwuxjsftfdvsbnzmnvljceufnukeiltmaaqbnuaagohdfvcuwo anjvaywwrqlwxjdqhiaypjyatdusnorybmvyrjjxwynvijmqak vhqpdwcmwysdzjjpsufirydxemfoukhfaxyrsjxtpekqpjqmda shugheraxwlbfvzfmxsanhhoknlfcesvrzilhylbtbgmkgbimf ibtflhcmajvzggylhcqalscbojuntcnnmgdfksztkdghlhmzvi dswyhdgrnkutnrxrumjpqrgrnbgxjiueubqycmdarujuiwiqrq wyasqrnjqvaijwhfdxzsykaadrutbskgfnydcinwswgcytryel afnskzmdycrevmindguhibwlnvoegrepxtnuizqqnfadevcnku ukxjpxkhpttrpabqpvgacuwqztmtghssydxqpzfuzfqncciqyh pmaxftsnauxzdctlzobjyderarhjawnukesvzikgbbtnkfgjje gygtodoukwpmlgxqeimmwccidrmxnwjiuqnqthrdsaqxauukht egdvzucbzedkpvhvblvqjkkfngqdjnnideuukehhjidfmvpcwn hbtdimvghgxqedgqlzjgpwyttvqnetqoquksmzzqgcdazfdurd kaessfsbxssujdouugtgkeuegoxqqkbyhfeirfvmiqzlmwtnwa aklctewxvtkkwnnswqgbztcghdsgpkgjwbsphraacmyrmsqzez dniqhdqmfonvigwhqfqvracwcvhdfttfzrnigxymvzazpeyieh orubqbecyvhampinjcmtcjzwqithlrwngsuqdbsuutbpagphio pkrruaxemnpiyrfasachdrbvdwsqmlmdrlklwmdwydugycqemo jlnyzuhwnojgjujwpgdqvttkkclnecpzpvesnukefimsayxxgh jvieywspsoxuhdmalmyaxqdeouzikmecofypmaishlozomrvfr prjpigjskkrkaavtoyjeikftsimpjnvlimzkvnfnjpkcbijjgs omddbtixdmjwdtnavotayjqumchujthecmluedoupdaubtfxpu cmqncxyzgwodldnfrxugvfdfcflmivsihxbkseskabytsjbosa psapvbjjaoxovkwwdlhjbykkanbbkrsmejevlgceswxsjsmmsb acrrqxpplgqmfqhpthcxjrqztwvxcpmmfgyeezkongvwryrgju pnrvrjuklqmgwaciukkifteciplqvmlqjprtvtmguyjckxpazx ysdnxacyxycmxekjcrcrihigmeqbwjarecpvrlrfkpmxvqvvyq vcytyvttafpwnrgrszwksygibkwszcttkpavzinnesnujvmvkb xwwdoerbqsyzazlipioyifpottnhiqllyerfcupptoakroloxj jnjinqfmvoweotpmlhasaytlrlpfrgykyyjcgxeqohbesbuywg mcwccvpfnkpgpexpxnvcqrjhlmekxgmddiplrqugtycintzcho ubhiiirboygwpgqutzwkbfrktegpzcglkrohqxfvahrvukeszw bmkmzfdppbbgblcqonksogzysnwpxyxitmvvdneyobpbrxjnqj sxijddridzhdqpdbgspldnkrdfrrzvoxsouaekjdzaiskgluke [出力例] Yes |
■C++版プログラム(問題E/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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
// C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; #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--) #define pb push_back #define a first #define b second int a[202020], mCum[202020][3], xCum[202020][3]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N) scanf("%d", &a[i]); char c[202020]; scanf("%s", c); string s(c); // 2. MEX. map<string, LL> mex; rep(i, 3){ rep(j, 3){ rep(k, 3){ string key; key.pb('0' + i); key.pb('0' + j); key.pb('0' + k); set<int> st; st.insert(i); st.insert(j); st.insert(k); rep(x, 4){ if(!st.count(x)){ mex[key] = x; break; } } } } } // for(auto &x : mex) printf("%s %lld\n", x.a.c_str(), x.b); // 3. 累積和. rep(i, N){ rep(j, 3){ mCum[i + 1][j] = mCum[i][j]; xCum[i + 1][j] = xCum[i][j]; } if(s[i] == 'M') ++mCum[i + 1][a[i]]; if(s[i] == 'X') ++xCum[i + 1][a[i]]; } // 4. 集計. LL ans = 0; rep(i, N){ // Skip. if(s[i] != 'E') continue; // 左側 M, 右側 X. int e = a[i]; rep(m, 3){ // Skip(左側 M なし). LL mCount = mCum[i + 1][m]; if(mCount == 0) continue; rep(x, 3){ // Skip(右側 X なし). LL xCount = xCum[N][x] - xCum[i + 1][x]; if(xCount == 0) continue; // MEX の キー. string key; key.pb('0' + m); key.pb('0' + e); key.pb('0' + x); // 加算. ans += mex[key] * mCount * xCount; } } } // 5. 出力. printf("%lld\n", ans); 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 46 47 48 49 50 |
[入力例] 4 1 1 0 2 MEEX [出力例] 3 ※AtCoderテストケースより [入力例] 3 0 0 0 XXX [出力例] 0 ※AtCoderテストケースより [入力例] 15 1 1 2 0 0 2 0 2 0 0 0 0 0 2 2 EXMMXXXEMEXEXMM [出力例] 13 ※AtCoderテストケースより [入力例] 10 0 0 2 2 2 1 1 0 1 0 MMEMEMEXXM [出力例] 30 [入力例] 100 0 2 1 0 2 2 0 1 1 0 1 1 0 0 0 2 1 1 2 0 0 0 2 2 0 0 0 0 1 1 2 1 0 0 1 1 1 0 0 2 0 2 2 2 2 2 0 1 2 1 0 2 0 1 0 1 2 1 0 1 2 2 1 1 1 1 2 2 1 1 2 0 1 0 1 1 1 0 0 1 1 1 0 0 0 2 1 1 1 1 1 0 2 1 1 0 0 2 1 2 MEXMMMXMXXMMXMMEEXEEEXEEEMXMXEMMMEXEXMEXEXMXXMEEEXXEMMXMEXMEXEMXMXXXEEXEMEEMXXMEXEMXEMMEMMXXXEEEEMXX [出力例] 11356 [入力例] 500 2 1 0 0 0 0 0 2 0 1 1 2 0 1 1 0 2 0 0 0 2 0 1 1 1 0 0 0 0 2 2 1 2 1 1 2 1 2 0 0 2 1 1 1 0 2 1 1 1 1 0 1 2 2 0 1 2 0 1 0 1 2 1 2 0 0 0 1 0 0 2 0 2 0 0 0 1 1 0 2 2 1 1 0 0 2 1 0 0 2 1 2 2 0 2 1 0 2 0 1 1 0 1 0 0 2 1 1 2 2 2 1 1 2 0 1 2 2 1 1 1 2 0 1 0 1 2 2 2 0 0 1 1 0 2 1 2 1 1 0 0 2 0 1 2 2 0 2 1 0 0 1 2 1 2 2 2 1 0 2 0 2 2 2 1 0 0 0 1 2 0 1 2 2 2 0 0 1 2 1 1 0 0 2 1 2 0 1 2 0 0 0 1 1 1 1 0 2 0 1 0 2 1 1 1 1 1 2 2 1 1 1 2 1 1 2 0 1 0 1 2 2 1 1 0 1 0 0 1 2 0 0 0 1 0 2 1 2 2 2 1 1 1 1 0 2 0 2 1 2 2 0 1 2 2 2 0 1 2 0 2 1 2 0 1 1 0 1 0 0 0 0 1 1 1 1 1 0 1 0 1 1 2 0 1 2 2 2 2 2 2 1 2 1 2 1 1 2 1 1 1 2 2 2 0 1 1 1 2 2 1 1 2 1 2 1 0 1 2 1 1 0 2 1 2 2 1 1 0 0 2 0 2 2 2 1 0 2 1 0 2 0 0 2 2 1 0 0 1 1 0 2 2 1 0 1 2 0 1 0 1 1 0 0 0 0 0 0 1 0 1 0 1 1 2 2 2 1 2 1 1 0 2 0 0 0 1 2 0 2 0 0 1 0 0 1 0 2 2 2 0 2 2 0 1 2 2 2 2 2 1 1 1 1 0 2 1 2 1 1 1 2 2 1 2 1 0 0 0 2 1 2 2 0 0 2 0 2 2 2 1 2 0 0 1 2 2 2 0 2 0 0 0 0 0 0 0 2 0 1 1 2 0 2 0 2 1 0 1 1 0 1 2 0 0 1 1 1 0 2 1 1 0 2 0 2 1 2 0 0 0 0 1 1 1 0 1 0 2 2 XMEEMMMXEEEXXXMXXMMXMMXEEMMMMMMMEEXMEXMMXMEXMXXMXXMMMMMXEXEMXEEMEMXXEXMMMMMXEMMMXMMEMXMEXXEEXEEXEMEMEXMXMEXEXMEEXMMMMMMXXXMEXXMEEMXMXEEMMXXMXMMMMEMMMMEMXXEMXEMEXEXXXEEXXXMXMXEMMXXXEMXMXMMMXXXEXXXXMXMEXXXMXEMEEEMMEEXXMXMEXEMXXEXMEMMXEXXXEMXEEEXEEMXMXXMXMEXEEMXXMMXEXMMMXMEMEXEEXXXEEMMXXXMMXXMXXEMMEMEXMXXMEXXEMXXXEMEEEMEEXMXXEXMEMEEEXEXXEXMMMEEEXEXEMXMXXEEMMMEEXXXXXXEXXEEEEMEXEEMMEMXMXEXXEXXEMXMXXXMEXMEMEXEMEXXEEXEEEXEEEMXEEMXEMEEEXXMEEXEXXXMEMMMXEXEMXMXMXEXEEMXXEMMEEMXEEXEXMEXXXMEEEEMXMEXMMEEXXMEE [出力例] 1265815 |