C++の練習を兼ねて, AtCoder Beginner Contest 295 の 問題C (Socks) ~ 問題E (Kth Number) を解いてみた.
■感想.
1. 問題C ~ E は, 方針を絞り込めたので, AC版に到達できたと思う.
2. 個人的には, 問題D で, 一次元累積和の復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 295 解説 の 各リンク を ご覧下さい.
■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 |
// 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--) #define a first #define b second int main(){ // 1. 入力情報. int N; scanf("%d", &N); map<int, int> m; rep(i, N){ int a; scanf("%d", &a); ++m[a]; } // 2. 数え上げ. int ans = 0; for(auto &p : m) ans += p.b / 2; // 3. 出力. printf("%d\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 |
[入力例] 6 4 1 7 4 1 4 [出力例] 2 ※AtCoderテストケースより [入力例] 1 158260522 [出力例] 0 ※AtCoderテストケースより [入力例] 10 295 2 29 295 29 2 29 295 2 29 [出力例] 4 ※AtCoderテストケースより [入力例] 50 106 19 10 90 72 101 22 82 119 87 3 2 79 31 6 51 54 33 40 29 6 46 74 30 11 117 53 96 75 16 104 30 76 111 32 51 2 52 116 72 101 1 75 41 10 48 51 46 13 87 [出力例] 10 [出力例] 100 96 6 61 23 95 56 76 88 55 35 88 89 65 59 76 95 5 55 33 2 18 61 76 77 99 55 69 69 96 70 63 92 79 6 95 57 97 91 10 26 55 52 53 85 5 38 59 76 90 72 56 83 80 87 96 20 62 25 5 55 72 17 31 66 79 57 1 16 20 25 57 72 81 62 32 59 70 2 31 20 39 15 88 3 63 85 52 50 66 96 60 25 18 55 53 5 87 39 80 18 [出力例] 34 |
■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 |
// 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--) LL sCum[505050][10], p[1 << 10]; int main(){ // 1. 入力情報. char c[505050]; scanf("%s", c); string s(c); int n = s.size(); // 2. 累積和. rep(i, n){ rep(j, 10) sCum[i + 1][j] = sCum[i][j]; ++sCum[i + 1][s[i] - '0']; sCum[i + 1][s[i] - '0'] %= 2; } // 3. 0 ~ 9 の 出現状況. rep(i, n + 1){ int x = 0; rep(j, 10) if(sCum[i][j]) x += (1 << j); ++p[x]; } // 4. 集計. LL ans = 0; rep(i, 1 << 10) ans += p[i] * (p[i] - 1) / 2; // 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 |
[入力例] 20230322 [出力例] 4 ※AtCoderテストケースより [入力例] 0112223333444445555556666666777777778888888889999999999 [出力例] 185 ※AtCoderテストケースより [入力例] 3141592653589793238462643383279502884197169399375105820974944 [出力例] 9 ※AtCoderテストケースより [入力例] 0672399474713525344309392013100562405141933097426713800408602692352473255409543673131038281718215293 [出力例] 20 [入力例] 43822528221649586967940200326919217981214617997174645566916246429027035301160142726935216220663659002429777446705798098514754637046664769823895464470447839113645140314579441295003133693442118292076023029585905176686160152927670069097377211608662693688552989472022870695274946047128163632607233361118307126215978369445322356782736681676583947149227261084417279392373265251895002425146460442210632034427766477119809205298411207570678353852846722362757233262697098795068765642393454991793416984734622695 [出力例] 212 [入力例] 11805307412898056014811861952584801110638821485390195055179698385152688502845075255306732699755927047525484702021750019923218888888869807053392030277385707339025387971725950124571770122201914594405997876873167792867848680897398725786333899448556145640604856530998625779607965004719975275348094137930472084379538806599118885844496558015235792644856563252104424209154517968812102488169581318407277269237942006023595456804238446133378632081703362309940891767935389059893317188382651547788928398428024266161995658403840303194697969862443297485515454983593810569853098261801874588234556192061599590413849779313332937511503355421398259761508113373746391384029328819113695945586824934988795545015810184556828255096618452959664691321554707850917730348510551075906552244363632802266519115641184396436228716310950894609371745203598252791168435669502765588962692686091072679624998705512051491113304959605912354143123356348091902689563125445970395707077135026907428534457236694868484162027898219774573352737543482924313467617215632485601085057318243234590848320785308678093572812048259874230798802816025599049544548479708396320113421744137430427393930461399709491227106210168723749968668315657341934473686994033732147729260511833229733659482695350430911033244448852680751587103196509888920205150522453839742726222261371836165286423613851788531342658395087412284404493673271490348249160998127967763889956783578314168834629262587700264290708163173154830964079641201306714485249095153169243107422018002659316012623296652943544442544199065959481908810106490695540182227664180961331081163058688792761053447965226881684335219018006668104304476657522280708087471699103401808482313981181494229521752113511948035713754859385286834381670025628689225207317336626606999123542735012621120412152204064967838095637342851234056103688631774338813197765195732721366511235469631787506700865177243414518243788946309677856224589264305081227174286364192203858179517269954682973002820880310854943798900624247909762804411239473507521039175333697224608311744252312583266454424290517447401487576279400633184546072382054223242032445125709634042371832473687464057346549248346778634401954853525962293257794172383292239164303514276293495304464679646737790462960954830641029456521171295806745883271735787078772126646050466004624445914055095476184197375263162317362706655644045546596278657696865832837871336826594909944934135567388470036528519284692115980087028660007311280871975672176753031463618573182285565441922665565794572764402548245877155079827511515586755426356702738088830662049931708687541194530207725218207733921166416068810870103155990088178850162428475429167573764115138262005117041766733976016393197787028812060655593205744766905531128992854192938842958156671046169810581579937860282917065469238176537898498412564673585432363684506217785999646583119843196289395557832586462346090479848168152643113022195424648845992369139379447571288529241246737609645784566191676552420536030552431780638862283190079514691554026454659767149301195583540587307895107543469924113221255917010549062520435065371327452503456688468805743168723907665737043847277268088605087928934832071757157272826832793695980425322168918373496766430792924254727042047201389271006828219179911447853987373869494522260226860368105402254629086571949082455850025539064912725734347360707870226183383375629744253727927654470630302617135442973371896672745600917303745515334883455314882694428789677247992666117573648880947470515113716048144716527771138295278845094282730334284226373197288668226483181135499626734053912318887844449127055908277986623814435955878538373024356052678142727158374970717133606525957541929617160859472271411764672671249887514384546102059562477919369065957351711368227567648783197802897208592360611834278291341314420850042838567139936314791880337886430860584308942368809019370364321822818136667766656010075325425707713013563650328547445129209747049099864388191935232241079852720378201478395869034987683332238102922066325999143676107318586659699799168748795794092956062598379611972071344340291882097385718859597067634819077579298822594828706495365465189221731714594884283028093194237045662481144553602547493026579181015964494697455666093435445577344880065612460189484274889416651847773812107060380540908954494527833955503414456929914085795442447715824826673643188068688499404673709745288273756338588177048248224823618942413059694647337444469983111699421982856935862902096438779554482623451274339968637590503489408905774967602932644117055570851480603951728434286521222632007484559812448187861165542983465572612697958030561725736385172818426367060710702388840239965334073619556266008781829065074995020372154874770358348622301062860291310309901262302113786791157743621313987256404212616764512335501713755330860864678220497286677616294376383345670894445172879045334008190508927621270729241076553825982953567533372177227782392437928034813701396575178378906469637435757443107915790336255565209737147062647887920291690092209735451261147758438576523554190622187875 [出力例] 12678 |
■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 |
// 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--) const LL MOD = 998244353; const int LIMIT = 2020; LL FAC[LIMIT], INV[LIMIT]; int a[LIMIT], aCum[LIMIT]; // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t; } // 組み合わせ(nCk)計算用(mod版). // ※配列FAC, INV は, 事前に計算済のものを使う. // @param n: 対象となる要素の個数. // @param k: 選択する要素の個数. // @return: 組み合わせ(nCk)の計算結果(mod版). LL combination(LL n, LL k){ if(n < 0 || k < 0 || k > n) return 0; LL ret = FAC[n] * INV[k] % MOD * INV[n - k] % MOD; return ret; } int main(){ // 1. 入力情報. int N, M, K; scanf("%d %d %d", &N, &M, &K); rep(i, N){ int x; scanf("%d", &x); ++a[x]; } // 2. 事前準備. FAC[0] = INV[0] = 1; repx(i, 1, LIMIT){ FAC[i] = (LL)i * FAC[i - 1] % MOD; INV[i] = mPow(FAC[i], MOD - 2); } // 3. 累積和. repx(i, 1, M + 1) aCum[i] = aCum[i - 1] + a[i]; // 4. 数え上げ(分子). LL ans = 0, bef = 0; repx(i, 1, M + 1){ LL cur = 0; repr(j, a[0], 0){ // 0 ~ i までが, K個未満だったら, Skip. if(j + aCum[i] < K) continue; // 0 を 書き換える場合の数. // j個: 1 ~ i に 設定. // (a[0] - j)個: (i + 1) ~ M に 設定. cur += combination(a[0], j) * mPow(i, j) % MOD * mPow(M - i, a[0] - j) % MOD; cur %= MOD; } // 今回分反映. ans += i * (cur - bef + MOD) % MOD; ans %= MOD; // 前回分更新. bef = cur; } // 5. 数え上げ(分母). // -> 0 を 1 ~ M に 書き換えるので, (0 の 個数) の M乗 を 分母 とする. ans *= mPow(mPow(M, a[0]), MOD - 2); ans %= MOD; // 6. 出力. 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 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
[入力例] 3 5 2 2 0 4 [出力例] 3 ※AtCoderテストケースより [入力例] 2 3 1 0 0 [出力例] 221832080 ※AtCoderテストケースより [入力例] 10 20 7 6 5 0 2 0 0 0 15 0 0 [出力例] 617586310 ※AtCoderテストケースより [入力例] 5 6 3 2 0 3 0 4 [出力例] 305019111 [入力例] 7 4 5 1 0 1 0 2 4 0 [出力例] 358744067 [入力例] 12 10 7 6 1 5 3 7 9 7 6 6 2 4 9 [出力例] 6 [入力例] 20 15 12 9 13 1 0 7 0 1 3 11 8 7 10 8 5 0 2 9 20 8 9 [出力例] 569960562 [入力例] 50 77 30 31 66 28 70 49 30 51 40 58 0 20 43 50 9 4 26 49 0 70 22 61 31 25 26 3 69 11 24 63 0 5 3 77 23 68 63 27 50 53 0 32 58 5 24 34 24 0 23 10 5 [出力例] 352265950 [入力例] 100 30 55 23 20 16 18 22 1 1 28 7 7 9 19 24 1 12 26 8 10 17 10 1 25 5 29 17 21 7 6 5 12 24 22 19 0 10 14 12 7 8 17 13 18 16 1 14 12 10 28 26 29 19 12 9 2 20 5 19 10 22 11 25 19 4 19 2 30 8 21 29 10 17 12 30 10 16 6 22 16 3 9 7 0 28 13 11 17 3 7 5 18 15 0 27 5 30 16 29 27 21 23 [出力例] 160902217 |
■参照サイト
AtCoder Beginner Contest 295