7月, 2020 | 個人用メモ帳

2020年7月10日

C++ の動作確認をしてみた（２５７）

C++の練習を兼ねて, AtCoder Beginner Contest 008 の問題C (コイン) を解いてみた.

■感想.
1. 方針が全く見えなかったので, 解説を参考に実装したところ, AC版となった.
2. 数え上げの方法が, 目から鱗で, 非常に感嘆したとともに, 本問題の奥深さを感じた.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 008 解説をご覧下さい.

■C++版プログラム(問題C／AC版).

// 解き直し.
// https://www.slideshare.net/chokudai/abc008
#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 coin[111], divisors[111];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%d", &coin[i]);
    
    // 2. 約数の個数を保存.
    rep(i, N) rep(j, N) if(i != j && coin[i] % coin[j] == 0) divisors[i]++;
    
    // 3. 確率を集計.
    double ans = 0.0;
    rep(i, N){
        // あるコイン C の 約数 となっているコイン S枚 を 考慮.
        int S = divisors[i];
        ans += (S & 1) ? 0.5 : (double)(S + 2) / (double)(2 * S + 2);
    }
    
    // 4. 出力.
    printf("%.12lf\n", ans);
    return 0;
    
}

// 解き直し.

// https://www.slideshare.net/chokudai/abc008

#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 coin[111], divisors[111];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%d", &coin[i]);

// 2. 約数の個数を保存.

rep(i, N) rep(j, N) if(i != j && coin[i] % coin[j] == 0) divisors[i]++;

// 3. 確率を集計.

double ans = 0.0;

rep(i, N){

// あるコイン C の約数となっているコイン S枚を考慮.

int S = divisors[i];

ans += (S & 1) ? 0.5 : (double)(S + 2) / (double)(2 * S + 2);

}

// 4. 出力.

printf("%.12lf\n", ans);

return 0;

}

[入力例]
3
2
4
8

[出力例]
2.166666666667
※AtCoderテストケースより

[入力例]
4
5
5
5
5

[出力例]
2.000000000000
※AtCoderテストケースより

[入力例]
5
2
3
2
6
12

[出力例]
3.100000000000
※AtCoderテストケースより

[入力例]
12
3
14
15
9
26
53
58
9
79
32
3
8

[出力例]
9.166666666667

[入力例]
36
32
11
32
11
1
2
4
19
2
2
8
25
7
3
7
6
13
15
21
2
18
25
33
18
4
24
27
31
25
29
12
25
16
13
10
12

[出力例]
21.434565434565

[入力例]

[出力例]

2.166666666667

※AtCoderテストケースより

[入力例]

[出力例]

2.000000000000

※AtCoderテストケースより

[入力例]

[出力例]

3.100000000000

※AtCoderテストケースより

[入力例]

[出力例]

9.166666666667

[入力例]

[出力例]

21.434565434565

■参照サイト
AtCoder Beginner Contest 008

2020年7月8日

C++ の動作確認をしてみた（２５６）

C++の練習を兼ねて, AtCoder Regular Contest 053 の問題A (ドミノ色塗り) ～問題B (回文分割) を解いてみた.

■感想.
1. 久しぶりに, 躓かないで, 回答出来たので良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトARC 053 解説をご覧下さい.

■C++版プログラム(問題A／AC版).

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報.
    int H, W;
    scanf("%d %d", &H, &W);
    
    // 2. 2マスを黒く塗る方法の場合の数は？
    int ans = (H - 1) * W + H * (W - 1);
    
    // 3. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int H, W;

scanf("%d %d", &H, &W);

// 2. 2マスを黒く塗る方法の場合の数は？

int ans = (H - 1) * W + H * (W - 1);

// 3. 出力.

printf("%d\n", ans);

return 0;

}

[入力例]
2 3

[出力例]
7
※AtCoderのテストケースより

[入力例]
4 1

[出力例]
3
※AtCoderのテストケースより

[入力例]
1 1

[出力例]
0
※AtCoderのテストケースより

[入力例]
89 97

[出力例]
17080

[入力例]
100 100

[出力例]
19800

[入力例]

2 3

[出力例]

※AtCoderのテストケースより

[入力例]

4 1

[出力例]

※AtCoderのテストケースより

[入力例]

1 1

[出力例]

※AtCoderのテストケースより

[入力例]

89 97

[出力例]

17080

[入力例]

100 100

[出力例]

19800

■C++版プログラム(問題B／AC版).

#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 a[26];

int main(){
    
    // 1. 入力情報.
    char c[101010];
    scanf("%s", c);
    int l = strlen(c);
    
    // 2. 出現回数をカウント.
    rep(i, l) a[c[i] - 'a']++;
    
    // 3. 奇数回出現したものの英小文字の種類は？
    int odd = 0;
    rep(i, 26) if(a[i] & 1) odd++;
    
    // 4. なるべく差分を小さくする.
    // odd が 0でない場合は, (l - odd)個 の 英小文字 を 2個ずつ配分.
    int ans = l;
    if(odd) ans = 1 + (l - odd) / (2 * odd) * 2;
    
    // 5. 出力.
    printf("%d\n", ans);
    return 0;
    
}

#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 a[26];

int main(){

// 1. 入力情報.

char c[101010];

scanf("%s", c);

int l = strlen(c);

// 2. 出現回数をカウント.

rep(i, l) a[c[i] - 'a']++;

// 3. 奇数回出現したものの英小文字の種類は？

int odd = 0;

rep(i, 26) if(a[i] & 1) odd++;

// 4. なるべく差分を小さくする.

// odd が 0でない場合は, (l - odd)個の英小文字を 2個ずつ配分.

int ans = l;

if(odd) ans = 1 + (l - odd) / (2 * odd) * 2;

// 5. 出力.

printf("%d\n", ans);

return 0;

}

[入力例]
rokovoko

[出力例]
3
※AtCoderのテストケースより

[入力例]
tomtom

[出力例]
6
※AtCoderのテストケースより

[入力例]
vwxyz

[出力例]
1
※AtCoderのテストケースより

[入力例]
succeeded

[出力例]
3
※AtCoderのテストケースより

[入力例]
qvvofmfdouuyhtwmedxhlpbdzeiokaeigcmbnkwpgbgdkhjvygongbwxwvqgznzdkmsgfsefokrgilptfrlijckrdfxyxxdekyxm

[出力例]
7

[入力例]
nlylgyzywvahxcmsgzlbcbfdaluejurktxyzmytiyxswaxsypyrjomnbnpfmslblpsvdnhvfaxxnqxinzrsybjqqirwxwbyywzlzklhprontclrhlabozislfpluaxxfgagqbhnevodxpwqzcuxobfobwrxqknuudowfoqjdufrwfpzfptywotqwnktutprndeqxdjwuyvcpwfopjglrayvhrcjcvohlyuenqellzfpzurkterrjnztoewhfiryljxgzdnylqbespfzygfleaipzluewfbqvffvnarkjxhyakfkmlnlzwbdsovyrdzzxygkehmoutawaekzgrwzjcqyuhcqbcflwccrahwnxlglmvfxesxhzinktecvgtmquqxqzuomwoilejizusbxalxpwevdbdyszgfstdsjorounsiqxppggvkugrwxtlqsvsckilflbllboyvnczdixpptjjwjoecnuhzcdgeearshtxmytlzasfigyiqxhktadurisazuuirhcryjkbnyhpzkleigcuykmiezhsgrokdvuohtakfofedwynjzlrestwisshqjpxnyppuibwusuakdkynejzqnhuxhjywxaceglopyuicwcevxnwtzxccnhijpjruteuwmeidopjyfxeandolzqwxnpfcihucuqgxqebnkmjdrdjnvtuwqlnlzshwmszqdijxdlisbinqbtxcjhbaxzdiyvybloycvkdmtwwwmimxkwcsssfzdqlqbezinnubnwebdscjctfdjqnzodbklrgmkufxinpuirpmcjledlgrzbfjanxyqvaavealltqicoyjephmjhomcrgoufulpyngxuzslplecoqisjtcelnydapobvjrxdzxsoskrzmebwihdbfzfuqsgfsqaecjsiqajdrmdsojprdchesehuxworxcvqrlsbxkltffdgvtkzuugknbrxdevtoyvkauiypufvflgzmadtkpcwyvgdrskvurccdpfbpnprkardykoteztrgukquwlifaupxjusgstvsdcbghvtzvhnmrrtsqmqbzdahwajqsnccbsqubozvwrxzbeqnfvtvbwxjgjngeculqqeruopbgcqjaaqjcqqzusvcuidvprijkrrfuenilqrcnrpdpzcdbemczaijcjtyogxhkgjtutynbsvfevzknirkcmitbdttjbnlpjwvsdiacrdlnmhxxxalckhyycxwyvntrchakugqobevmfhkstvysxitxjwshmudebdnppzcrlrgvlengjiccmcybudadxzpnhrwdmrlbtnrsibnydtjgrziqctjnsgmhiolvvgjelmlyirhyzybsmcnlhtefjsiavvklskzzgauuuaaonjhzjstoxxarntynkfypxhwspqpqerbullkaztzfxdziikrevpwcslnxyqmldtygzgoaslpnrfrieroldlzipyrybemesofkmlppwnggigmhtowszzipthoxclnjtnezggamloqiexilmlybkwqnvnecuiyeaalmuwlqteazpgoidzzjxaiwuyzngkevnbfgatnksvivtmswusbjafqslxghrltpjhsjupykrklvopqmyxpjkcsfdhqvaqssezriwjpmieymwtzeuikltlodpxfaewsitxbyxopiynylkhymaelhdpvcxrmrojacclteashvatmfykdsxljgotpdblmaznpgedsrslyojijjlbnlddwykgbfjzymwmpjntkfmpmohpdgvpqcligbncuwlfpizqdffpntvxzjzpvvpwqmlnhgtlmjxcsildsnrlgduhilnngqtgropnkcoikjckcqjitbtojdetemgxwcbmjoiptabneuhyxaiixlohtxyllgowvztoosvrpduqvqywuepbbudhpzayjhrmtprpcgaukzjemtbvytalubunsboxrbkbkxjjwbusxaexxrsalydy

[出力例]
165

[入力例]
hluchtttjbapsolzlyukdyjbbxaxtutwpwasvxxstymmbmfsaezsynmyzkyhbycnukjyubajhhkuoecryfslpvebweknmymcogncdhlstnikgmnsckrszzwsqwxatsqzpaatatdvfnfyjttywvvucezinawkeelstqyqabnvqwpugpzjzjrjxqpoqihlnvhodfvqwznqgbloexodbxcubuvbertxvhzaoehkpvksfmzzujwyvzkmxonabeijfxxpejnisevlnoinqogjejfnrvgzqbgewhwkjjocwfjglcezekdkdghmtoosomspdarmtdxetfcvolgnaxgbgzwjsnfzjizxdnrwtgymembkfbkrwzkpwsyzxbpqycwfdrndzuklpwnqszzaogwgfvhvbcwfevgzoubemhpqpvjqvgxjyjpequmjfdjkufjtfnnnedyievohwtejeqkusmtdpkswrimktbrpgpraogkypmdzkzxamtzespdmhfoebatfspcmkiysechpeiaxhpxiqevwhbudzpagjzjoxvtxwnydtlqqkgafqdihtlbkbwjeybhxqygoezzgwkvhrdtdmireotftrsrijwzvxralyzruiyrvnyzjxrcahjfoootkrklvaubvkqnpzxdlptotcphiyupwpeicyrxiuopqiwmbcfsxvtvkglkwwnzdhgxwhelrttbwmwpetayzfhmwwjgcaplkubvfclwpvqybbszruvofnnzdzeuasvavllkcyvdvxhufrnpyzwshmyedrlxtqrleluzoygvjbwwgzswjbqhzcntkldyfxrahqjnezmvcdlyztoymzwuwvcfokguemfkvajbxitbblvxreyuidattbdmzikxaqxcdqvqcxuzxhulzfpjujndarbhhkmaxduqjowdzcektycpiocriruarxudfanfvrrxtipwhjqxpjnqfvhjrvulgkikuqcrumldkyusxerrplbkmmvgljdsuqcjetflfkcirkzuuznxjjbsgmrhninqubwnedowyxihsoreefvitjagcvzscasqbbvkixhnujvqabqunnwkqkrlepfmiymzozmhshjslmypcuuydwpfudlozikhdjtsdiysshknkpjggkfduwshneuegrpkfwfcbioyezkcbgrjsjyttzvjornbpmadgkqjrgmrlrnzbfiqecvrryuhbemstfehstgssijrfgcixpzrseeyunxvmcvnbtihtuteezvmxsuzefqacszmxbywoapbrrtwbtgfbtdpjcpemakpivysukzqzenmqkqqchsskhmbordyrosipsukhhfyzxublfvcehtlvktiqisgonbipmsugorlcivkzxqxnmloeogmobojlsxogmtnyxrbyyrlmxnbjwiangbwhovvdermnltrlfqbqskeowywrqiahumcadbdjvnggimahpgsmtfdjcamoiifbvwxpwzvtnqxzvbtejoovttsnumsakctrerfkmjrmaigoxxecjmkaqyfkoeorcbpjgzwaubgoruaxguyjzdfgqiixjwpaibgywsnhfktdmzrxkihlgiaoqaqupabirdjgfemctvgxnpyqjrdyhkfzigsuepryeewqqapiynzdsyzradfazjqshskoqprjvetbyethjhvlrupfjkniqpiuotylttcvqepannjafspsyrozyffnvcrdrkzktlvkllpusdbzuoibbotuegdckydtmapcigcxptlenvqpwznyzynbbpobwvsutgnryilnnxrdsffzeqouudfbumwntzflbzwenpmtifseiwdqfbftblnotvzsuphchoharqfqeuwezzdijukudcpzhraqflbcpulcmcpatrtxfhtrymgaeiuiornfmavkjtwxgxlrvookxdjjmswklzvgglpcolflvidyyrauvvpocsmifbjsbhaxqlszpsggzkemcklggkryquyikntuoxlqmebjusifezshloeuvbasdjckswplauuvirlgzfcnkmrsqltaamztztpgijhyfiabkcemenipwzjkxbdbeltjgmyegjszjpczazypdnnhlnohwirtqcikfxqifddyytdngpvpunbtikgcvzscgimykwvmzicvmsythrrxksppzvdvnsloxuyjvymrvmgbeiwiqqxjnlabdzwaqwcirzeynjktvoqnfxvkwwrjafctlsancwxycushuydbmsdwrykggbjtddmxgwonkzikuwqrofebmnjgchplbdodjfzvitsagqugmijallbbzlfoxhublwugfusuumtttemnswjsaxsdkpidhgvvvvqnubpsidgwnogvdwjcrzmhlntgjpxcakuajfpzidvxoydzssstvdpdynqeikvbmvfvyieepiwebnqugcghynivsgylzibtvvclcmptmlsrmsanmpmtnyghvtqhowiaoekcprsqsrojaanuwabbahhkeyxwvnqefdpvwtfrxcsxmxvmsjcffqnejtkdbndgcngewloxnicwlgkvxggauvgxratpfqdngymzedidnnzfopeloeisrtkqhmilusjoyicovxjyktnhdacmazuddzeubfsvbsxzunetaikgjtzkghnejsxthwwcefgwuumhhhygcwrbduuxoawrkvrqhffmduyrgxzaqmeudqvgjgegwrcijegawjvdnqbvtqmfgfpxlzszsghokjzxpqnlxjsklarqfeywzwmkbubdhxhqgdbyyqxzqubwgppyvlykumqvhxzulbzzzjzlarijphojzfzulzaowaqtalvbdmxkvgrmycuiyfxpdocuvjolgonqoekpctnuavgtcxflascuagydkootnyzafuvzscxmhwmuembrhxvrnfpoabthizmnyoqynpajpopnojdlauxernyxdcfajswjusvrhbofyymjnbvnhhgbngyg
[出力例]
213

[入力例]

rokovoko

[出力例]

※AtCoderのテストケースより

[入力例]

tomtom

[出力例]

※AtCoderのテストケースより

[入力例]

vwxyz

[出力例]

※AtCoderのテストケースより

[入力例]

succeeded

[出力例]

※AtCoderのテストケースより

[入力例]

qvvofmfdouuyhtwmedxhlpbdzeiokaeigcmbnkwpgbgdkhjvygongbwxwvqgznzdkmsgfsefokrgilptfrlijckrdfxyxxdekyxm

[出力例]

[入力例]

nlylgyzywvahxcmsgzlbcbfdaluejurktxyzmytiyxswaxsypyrjomnbnpfmslblpsvdnhvfaxxnqxinzrsybjqqirwxwbyywzlzklhprontclrhlabozislfpluaxxfgagqbhnevodxpwqzcuxobfobwrxqknuudowfoqjdufrwfpzfptywotqwnktutprndeqxdjwuyvcpwfopjglrayvhrcjcvohlyuenqellzfpzurkterrjnztoewhfiryljxgzdnylqbespfzygfleaipzluewfbqvffvnarkjxhyakfkmlnlzwbdsovyrdzzxygkehmoutawaekzgrwzjcqyuhcqbcflwccrahwnxlglmvfxesxhzinktecvgtmquqxqzuomwoilejizusbxalxpwevdbdyszgfstdsjorounsiqxppggvkugrwxtlqsvsckilflbllboyvnczdixpptjjwjoecnuhzcdgeearshtxmytlzasfigyiqxhktadurisazuuirhcryjkbnyhpzkleigcuykmiezhsgrokdvuohtakfofedwynjzlrestwisshqjpxnyppuibwusuakdkynejzqnhuxhjywxaceglopyuicwcevxnwtzxccnhijpjruteuwmeidopjyfxeandolzqwxnpfcihucuqgxqebnkmjdrdjnvtuwqlnlzshwmszqdijxdlisbinqbtxcjhbaxzdiyvybloycvkdmtwwwmimxkwcsssfzdqlqbezinnubnwebdscjctfdjqnzodbklrgmkufxinpuirpmcjledlgrzbfjanxyqvaavealltqicoyjephmjhomcrgoufulpyngxuzslplecoqisjtcelnydapobvjrxdzxsoskrzmebwihdbfzfuqsgfsqaecjsiqajdrmdsojprdchesehuxworxcvqrlsbxkltffdgvtkzuugknbrxdevtoyvkauiypufvflgzmadtkpcwyvgdrskvurccdpfbpnprkardykoteztrgukquwlifaupxjusgstvsdcbghvtzvhnmrrtsqmqbzdahwajqsnccbsqubozvwrxzbeqnfvtvbwxjgjngeculqqeruopbgcqjaaqjcqqzusvcuidvprijkrrfuenilqrcnrpdpzcdbemczaijcjtyogxhkgjtutynbsvfevzknirkcmitbdttjbnlpjwvsdiacrdlnmhxxxalckhyycxwyvntrchakugqobevmfhkstvysxitxjwshmudebdnppzcrlrgvlengjiccmcybudadxzpnhrwdmrlbtnrsibnydtjgrziqctjnsgmhiolvvgjelmlyirhyzybsmcnlhtefjsiavvklskzzgauuuaaonjhzjstoxxarntynkfypxhwspqpqerbullkaztzfxdziikrevpwcslnxyqmldtygzgoaslpnrfrieroldlzipyrybemesofkmlppwnggigmhtowszzipthoxclnjtnezggamloqiexilmlybkwqnvnecuiyeaalmuwlqteazpgoidzzjxaiwuyzngkevnbfgatnksvivtmswusbjafqslxghrltpjhsjupykrklvopqmyxpjkcsfdhqvaqssezriwjpmieymwtzeuikltlodpxfaewsitxbyxopiynylkhymaelhdpvcxrmrojacclteashvatmfykdsxljgotpdblmaznpgedsrslyojijjlbnlddwykgbfjzymwmpjntkfmpmohpdgvpqcligbncuwlfpizqdffpntvxzjzpvvpwqmlnhgtlmjxcsildsnrlgduhilnngqtgropnkcoikjckcqjitbtojdetemgxwcbmjoiptabneuhyxaiixlohtxyllgowvztoosvrpduqvqywuepbbudhpzayjhrmtprpcgaukzjemtbvytalubunsboxrbkbkxjjwbusxaexxrsalydy

[出力例]

165

[入力例]

hluchtttjbapsolzlyukdyjbbxaxtutwpwasvxxstymmbmfsaezsynmyzkyhbycnukjyubajhhkuoecryfslpvebweknmymcogncdhlstnikgmnsckrszzwsqwxatsqzpaatatdvfnfyjttywvvucezinawkeelstqyqabnvqwpugpzjzjrjxqpoqihlnvhodfvqwznqgbloexodbxcubuvbertxvhzaoehkpvksfmzzujwyvzkmxonabeijfxxpejnisevlnoinqogjejfnrvgzqbgewhwkjjocwfjglcezekdkdghmtoosomspdarmtdxetfcvolgnaxgbgzwjsnfzjizxdnrwtgymembkfbkrwzkpwsyzxbpqycwfdrndzuklpwnqszzaogwgfvhvbcwfevgzoubemhpqpvjqvgxjyjpequmjfdjkufjtfnnnedyievohwtejeqkusmtdpkswrimktbrpgpraogkypmdzkzxamtzespdmhfoebatfspcmkiysechpeiaxhpxiqevwhbudzpagjzjoxvtxwnydtlqqkgafqdihtlbkbwjeybhxqygoezzgwkvhrdtdmireotftrsrijwzvxralyzruiyrvnyzjxrcahjfoootkrklvaubvkqnpzxdlptotcphiyupwpeicyrxiuopqiwmbcfsxvtvkglkwwnzdhgxwhelrttbwmwpetayzfhmwwjgcaplkubvfclwpvqybbszruvofnnzdzeuasvavllkcyvdvxhufrnpyzwshmyedrlxtqrleluzoygvjbwwgzswjbqhzcntkldyfxrahqjnezmvcdlyztoymzwuwvcfokguemfkvajbxitbblvxreyuidattbdmzikxaqxcdqvqcxuzxhulzfpjujndarbhhkmaxduqjowdzcektycpiocriruarxudfanfvrrxtipwhjqxpjnqfvhjrvulgkikuqcrumldkyusxerrplbkmmvgljdsuqcjetflfkcirkzuuznxjjbsgmrhninqubwnedowyxihsoreefvitjagcvzscasqbbvkixhnujvqabqunnwkqkrlepfmiymzozmhshjslmypcuuydwpfudlozikhdjtsdiysshknkpjggkfduwshneuegrpkfwfcbioyezkcbgrjsjyttzvjornbpmadgkqjrgmrlrnzbfiqecvrryuhbemstfehstgssijrfgcixpzrseeyunxvmcvnbtihtuteezvmxsuzefqacszmxbywoapbrrtwbtgfbtdpjcpemakpivysukzqzenmqkqqchsskhmbordyrosipsukhhfyzxublfvcehtlvktiqisgonbipmsugorlcivkzxqxnmloeogmobojlsxogmtnyxrbyyrlmxnbjwiangbwhovvdermnltrlfqbqskeowywrqiahumcadbdjvnggimahpgsmtfdjcamoiifbvwxpwzvtnqxzvbtejoovttsnumsakctrerfkmjrmaigoxxecjmkaqyfkoeorcbpjgzwaubgoruaxguyjzdfgqiixjwpaibgywsnhfktdmzrxkihlgiaoqaqupabirdjgfemctvgxnpyqjrdyhkfzigsuepryeewqqapiynzdsyzradfazjqshskoqprjvetbyethjhvlrupfjkniqpiuotylttcvqepannjafspsyrozyffnvcrdrkzktlvkllpusdbzuoibbotuegdckydtmapcigcxptlenvqpwznyzynbbpobwvsutgnryilnnxrdsffzeqouudfbumwntzflbzwenpmtifseiwdqfbftblnotvzsuphchoharqfqeuwezzdijukudcpzhraqflbcpulcmcpatrtxfhtrymgaeiuiornfmavkjtwxgxlrvookxdjjmswklzvgglpcolflvidyyrauvvpocsmifbjsbhaxqlszpsggzkemcklggkryquyikntuoxlqmebjusifezshloeuvbasdjckswplauuvirlgzfcnkmrsqltaamztztpgijhyfiabkcemenipwzjkxbdbeltjgmyegjszjpczazypdnnhlnohwirtqcikfxqifddyytdngpvpunbtikgcvzscgimykwvmzicvmsythrrxksppzvdvnsloxuyjvymrvmgbeiwiqqxjnlabdzwaqwcirzeynjktvoqnfxvkwwrjafctlsancwxycushuydbmsdwrykggbjtddmxgwonkzikuwqrofebmnjgchplbdodjfzvitsagqugmijallbbzlfoxhublwugfusuumtttemnswjsaxsdkpidhgvvvvqnubpsidgwnogvdwjcrzmhlntgjpxcakuajfpzidvxoydzssstvdpdynqeikvbmvfvyieepiwebnqugcghynivsgylzibtvvclcmptmlsrmsanmpmtnyghvtqhowiaoekcprsqsrojaanuwabbahhkeyxwvnqefdpvwtfrxcsxmxvmsjcffqnejtkdbndgcngewloxnicwlgkvxggauvgxratpfqdngymzedidnnzfopeloeisrtkqhmilusjoyicovxjyktnhdacmazuddzeubfsvbsxzunetaikgjtzkghnejsxthwwcefgwuumhhhygcwrbduuxoawrkvrqhffmduyrgxzaqmeudqvgjgegwrcijegawjvdnqbvtqmfgfpxlzszsghokjzxpqnlxjsklarqfeywzwmkbubdhxhqgdbyyqxzqubwgppyvlykumqvhxzulbzzzjzlarijphojzfzulzaowaqtalvbdmxkvgrmycuiyfxpdocuvjolgonqoekpctnuavgtcxflascuagydkootnyzafuvzscxmhwmuembrhxvrnfpoabthizmnyoqynpajpopnojdlauxernyxdcfajswjusvrhbofyymjnbvnhhgbngyg

[出力例]

213

■参照サイト
AtCoder Regular Contest 053

2020年7月7日

C++ の動作確認をしてみた（２５５）

C++の練習を兼ねて, AtCoder Beginner Contest 170 の問題E (Smart Infants) を解いてみた.

■感想.
1. 方針が見えなかったので, 解説を参考に実装したところ, AC版となった.
2. なじみの薄い multiset の訓練が出来たので, 非常に良かったと思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 170 解説をご覧下さい.

■C++版プログラム(問題E／AC版).

// 解き直し.
// https://img.atcoder.jp/abc170/editorial.pdf
#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
LL A[202020];
int B[202020];
multiset<LL> rate[202020]; // それぞれの幼稚園に所属する幼児のレートの集合.
multiset<LL> maxRate;      // それぞれの幼稚園の最強園児のレートの集合.

int main(){
    
    // 1. 入力情報.
    int N, Q;
    scanf("%d %d", &N, &Q);
    repx(i, 1, N + 1) scanf("%lld %d", &A[i], &B[i]);
    
    // 2. 事前準備(以下, 解説通り).
    repx(i, 1, N + 1) rate[B[i]].insert(A[i]);
    repx(i, 1, 202020){
        if(rate[i].size() > 0){
            auto itr = rate[i].end();
            maxRate.insert(*(--itr));
        }
    }
    
    // 3. クエリ回答.
    int C, D;
    rep(i, Q){
        // 3-1. 転園情報.
        scanf("%d %d", &C, &D);
        int at = B[C]; // 転園元幼稚園.
        
        // 3-2. maxRate から 転園元幼稚園の最強園児のレートを削除.
        auto it1 = rate[at].end();
        auto it2 = maxRate.find(*(--it1));
        maxRate.erase(it2); // 1個だけ削除.
        
        // 3-3. 転園元幼稚園から転園する園児のレートを削除.
        auto it3 = rate[at].find(A[C]);
        rate[at].erase(it3); // 1個だけ削除.
        
        // 3-4. maxRate に 転園元幼稚園の最強園児のレートを追加.
        if(rate[at].size() > 0){
            auto it4 = rate[at].end();
            maxRate.insert(*(--it4));
        }
        
        // 3-5. maxRate から 転園先幼稚園の最強園児のレートを削除.
        if(rate[D].size() > 0){
            auto it5 = rate[D].end();
            auto it6 = maxRate.find(*(--it5));
            maxRate.erase(it6); // 1個だけ削除.
        }
        
        // 3-6. 転園先幼稚園に, 転園する園児のレートを追加.
        rate[D].insert(A[C]);
        
        // 3-7. maxRate に 転園先幼稚園の最強園児のレートを追加.
        auto it7 = rate[D].end();
        maxRate.insert(*(--it7));
        
        // 3-8. 転園する園児の所属する幼稚園の番号を更新.
        B[C] = D;
        
        // 3-9. 出力.
        auto it8 = maxRate.begin();
        LL ans = *it8;
        printf("%d\n", ans);
    }
    return 0;
    
}

// 解き直し.

// https://img.atcoder.jp/abc170/editorial.pdf

#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

LL A[202020];

int B[202020];

multiset<LL> rate[202020]; // それぞれの幼稚園に所属する幼児のレートの集合.

multiset<LL> maxRate; // それぞれの幼稚園の最強園児のレートの集合.

int main(){

// 1. 入力情報.

int N, Q;

scanf("%d %d", &N, &Q);

repx(i, 1, N + 1) scanf("%lld %d", &A[i], &B[i]);

// 2. 事前準備(以下, 解説通り).

repx(i, 1, N + 1) rate[B[i]].insert(A[i]);

repx(i, 1, 202020){

if(rate[i].size() > 0){

auto itr = rate[i].end();

maxRate.insert(*(--itr));

}

// 3. クエリ回答.

int C, D;

rep(i, Q){

// 3-1. 転園情報.

scanf("%d %d", &C, &D);

int at = B[C]; // 転園元幼稚園.

// 3-2. maxRate から転園元幼稚園の最強園児のレートを削除.

auto it1 = rate[at].end();

auto it2 = maxRate.find(*(--it1));

maxRate.erase(it2); // 1個だけ削除.

// 3-3. 転園元幼稚園から転園する園児のレートを削除.

auto it3 = rate[at].find(A[C]);

rate[at].erase(it3); // 1個だけ削除.

// 3-4. maxRate に転園元幼稚園の最強園児のレートを追加.

if(rate[at].size() > 0){

auto it4 = rate[at].end();

maxRate.insert(*(--it4));

}

// 3-5. maxRate から転園先幼稚園の最強園児のレートを削除.

if(rate[D].size() > 0){

auto it5 = rate[D].end();

auto it6 = maxRate.find(*(--it5));

maxRate.erase(it6); // 1個だけ削除.

}

// 3-6. 転園先幼稚園に, 転園する園児のレートを追加.

rate[D].insert(A[C]);

// 3-7. maxRate に転園先幼稚園の最強園児のレートを追加.

auto it7 = rate[D].end();

maxRate.insert(*(--it7));

// 3-8. 転園する園児の所属する幼稚園の番号を更新.

B[C] = D;

// 3-9. 出力.

auto it8 = maxRate.begin();

LL ans = *it8;

printf("%d\n", ans);

}

return 0;

}

[入力例]
6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2

[出力例]
6
2
6
※AtCoderテストケースより

[入力例]
2 2
4208 1234
3056 5678
1 2020
2 2020

[出力例]
3056
4208
※AtCoderテストケースより

[入力例]
20 25
48039234 1
106894727 3
54034116 4
29384308 1
25419214 1
41960290 2
113411995 1
105430452 5
101633542 2
63004981 3
15337594 4
10494255 3
113037996 2
31400866 1
38043117 4
64839068 4
80433133 4
106837808 5
101886442 5
48230109 2
1 3
4 2
9 3
15 3
19 3
2 1
9 1
12 4
17 3
17 1
18 1
20 5
10 5
7 5
4 1
16 1
20 3
3 1
5 5
8 2
11 1
13 5
14 3
6 5
1 5

[出力例]
80433133
80433133
80433133
80433133
80433133
80433133
80433133
80433133
64839068
64839068
64839068
64839068
64839068
64839068
64839068
54034116
54034116
15337594
15337594
15337594
10494255
10494255
10494255
10494255
10494255

100

101

102

103

104

[入力例]

6 3

8 1

6 2

9 3

1 1

2 2

1 3

4 3

2 1

1 2

[出力例]

※AtCoderテストケースより

[入力例]

2 2

4208 1234

3056 5678

1 2020

2 2020

[出力例]

3056

4208

※AtCoderテストケースより

[入力例]

20 25

48039234 1

106894727 3

54034116 4

29384308 1

25419214 1

41960290 2

113411995 1

105430452 5

101633542 2

63004981 3

15337594 4

10494255 3

113037996 2

31400866 1

38043117 4

64839068 4

80433133 4

106837808 5

101886442 5

48230109 2

1 3

4 2

9 3

15 3

19 3

2 1

9 1

12 4

17 3

17 1

18 1

20 5

10 5

7 5

4 1

16 1

20 3

3 1

5 5

8 2

11 1

13 5

14 3

6 5

1 5

[出力例]

80433133

64839068

54034116

15337594

10494255

■参照サイト
AtCoder Beginner Contest 170

2020年7月7日

C++ の動作確認をしてみた（２５４）

C++の練習を兼ねて, AtCoder Regular Contest 051 の問題A (塗り絵) ～問題B (互除法) を解いてみた.

■感想.
1. 問題A は, 図形の性質を絞り込めた点, 問題B は, Fibonacci数列に帰着出来たので, AC版になったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトARC 051 解説をご覧下さい.

■C++版プログラム(問題A／AC版).

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    // 1. 入力情報.
    int x1, y1, r;
    int x2, y2, x3, y3;
    scanf("%d %d %d %d %d %d %d", &x1, &y1, &r, &x2, &y2, &x3, &y3);
    
    // 2. 赤が無い場合.
    int cLx = x1 - r, cRx = x1 + r, cUy = y1 + r, cDy = y1 - r;
    if(x2 <= cLx && x3 >= cRx && y2 <= cDy && y3 >= cUy){
        puts("NO");
        puts("YES");
        return 0;
    }
    
    // 3. 青が無い場合.
    // -> 円の中心から, 長方形の四隅が, いずれも 距離 r 以下となっている場合.
    int lu = (x2 - x1) * (x2 - x1) + (y3 - y1) * (y3 - y1); // 左上.
    int ld = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // 左下.
    int ru = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1); // 右上.
    int rd = (x3 - x1) * (x3 - x1) + (y2 - y1) * (y2 - y1); // 右下.
    int r2 = r * r;
    if(lu <= r2 && ld <= r2 && ru <= r2 && rd <= r2){
        puts("YES");
        puts("NO");
        return 0;
    }
    
    // 4. それ以外.
    puts("YES");
    puts("YES");
    return 0;
    
}

#include <bits/stdc++.h>

using namespace std;

int main(){

// 1. 入力情報.

int x1, y1, r;

int x2, y2, x3, y3;

scanf("%d %d %d %d %d %d %d", &x1, &y1, &r, &x2, &y2, &x3, &y3);

// 2. 赤が無い場合.

int cLx = x1 - r, cRx = x1 + r, cUy = y1 + r, cDy = y1 - r;

if(x2 <= cLx && x3 >= cRx && y2 <= cDy && y3 >= cUy){

puts("NO");

puts("YES");

return 0;

}

// 3. 青が無い場合.

// -> 円の中心から, 長方形の四隅が, いずれも距離 r 以下となっている場合.

int lu = (x2 - x1) * (x2 - x1) + (y3 - y1) * (y3 - y1); // 左上.

int ld = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1); // 左下.

int ru = (x3 - x1) * (x3 - x1) + (y3 - y1) * (y3 - y1); // 右上.

int rd = (x3 - x1) * (x3 - x1) + (y2 - y1) * (y2 - y1); // 右下.

int r2 = r * r;

if(lu <= r2 && ld <= r2 && ru <= r2 && rd <= r2){

puts("YES");

puts("NO");

return 0;

}

// 4. それ以外.

puts("YES");

return 0;

}

[入力例]
-1 -1 2
2 3 4 5

[出力例]
YES
YES
※AtCoderのテストケースより

[入力例]
0 1 1
-2 0 4 3

[出力例]
NO
YES
※AtCoderのテストケースより

[入力例]
0 0 5
-2 -2 2 1

[出力例]
YES
NO
※AtCoderのテストケースより

[入力例]
0 0 2
0 0 4 4

[出力例]
YES
YES
※AtCoderのテストケースより

[入力例]
0 0 5
-4 -4 4 4

[出力例]
YES
YES
※AtCoderのテストケースより

[入力例]

-1 -1 2

2 3 4 5

[出力例]

YES

※AtCoderのテストケースより

[入力例]

0 1 1

-2 0 4 3

[出力例]

YES

※AtCoderのテストケースより

[入力例]

0 0 5

-2 -2 2 1

[出力例]

YES

※AtCoderのテストケースより

[入力例]

0 0 2

0 0 4 4

[出力例]

YES

※AtCoderのテストケースより

[入力例]

0 0 5

-4 -4 4 4

[出力例]

YES

※AtCoderのテストケースより

■C++版プログラム(問題B／AC版).

#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 f[41];

int main(){
    
    // 1. 入力情報.
    int K;
    scanf("%d", &K);
    
    // 2. Fibonacci数列を計算.
    f[0] = 1, f[1] = 1;
    repx(i, 2, 41) f[i] = f[i - 1] + f[i - 2];
    // rep(i, 41) printf("%d\n", f[i]);
    
    // 3. 出力.
    printf("%d %d\n", f[K - 1], f[K]);
    return 0;
    
}

#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 f[41];

int main(){

// 1. 入力情報.

int K;

scanf("%d", &K);

// 2. Fibonacci数列を計算.

f[0] = 1, f[1] = 1;

repx(i, 2, 41) f[i] = f[i - 1] + f[i - 2];

// rep(i, 41) printf("%d\n", f[i]);

// 3. 出力.

printf("%d %d\n", f[K - 1], f[K]);

return 0;

}

[入力例]
1

[出力例]
1 1
※AtCoderのテストケースより

[入力例]
3

[出力例]
4 5
※AtCoderのテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.
2 3

[入力例]
12

[出力例]
314159265 358979323
※AtCoderのテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.
144 233

[入力例]
25

[出力例]
75025 121393

[入力例]
40

[出力例]
102334155 165580141

[入力例]

[出力例]

1 1

※AtCoderのテストケースより

[入力例]

[出力例]

4 5

※AtCoderのテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.

2 3

[入力例]

[出力例]

314159265 358979323

※AtCoderのテストケースより

但し, 上記のプログラムでは, 以下の内容が出力される.

144 233

[入力例]

[出力例]

75025 121393

[入力例]

[出力例]

102334155 165580141

■参照サイト
AtCoder Regular Contest 051

2020年7月6日

C++ の動作確認をしてみた（２５３）

C++の練習を兼ねて, AtCoder Beginner Contest 173 の問題D (Chat in a Circle) を解いてみた.

■感想.
1. 大きい方から, 最大2回ずつ加算していく方針で, AC版となった.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 173 解説をご覧下さい.

■C++版プログラム(問題D／AC版).

// 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 A[202020];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &A[i]);
    
    // 2. sort.
    sort(A, A + N, greater<LL>());
    
    // 3. 集計(※大きい値から, 最大2回ずつ加算).
    LL ans = A[0];
    int add = 1;
    repx(i, 1, N / 2 + 1){
        if(++add < N) ans += A[i];
        if(++add < N) ans += A[i];
    }
    
    // 4. 出力.
    printf("%lld\n", ans);
    return 0;
    
}

// 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 A[202020];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &A[i]);

// 2. sort.

sort(A, A + N, greater<LL>());

// 3. 集計(※大きい値から, 最大2回ずつ加算).

LL ans = A[0];

int add = 1;

repx(i, 1, N / 2 + 1){

if(++add < N) ans += A[i];

}

// 4. 出力.

printf("%lld\n", ans);

return 0;

}

[入力例]
4
2 2 1 3

[出力例]
7
※AtCoderテストケースより

[入力例]
7
1 1 1 1 1 1 1

[出力例]
6
※AtCoderテストケースより

[入力例]
10
5 2 2 1 8 3 7 9 10 13

[出力例]
81

[入力例]
13
18 23 27 1 5 9 7 13 17 22 8 19 28

[出力例]
263

[入力例]
33
314159265 35897932 3846264 338327 95028 8419 716 93 9 937 5105 82097 494459 23078 1640 628 620 89 986 28034 82 534 211 7067 982 14808 65132 823066470 938446095 50582231 725359 40812848 11174502

[出力例]
3501242955

[入力例]

2 2 1 3

[出力例]

※AtCoderテストケースより

[入力例]

1 1 1 1 1 1 1

[出力例]

※AtCoderテストケースより

[入力例]

5 2 2 1 8 3 7 9 10 13

[出力例]

[入力例]

18 23 27 1 5 9 7 13 17 22 8 19 28

[出力例]

263

[入力例]

314159265 35897932 3846264 338327 95028 8419 716 93 9 937 5105 82097 494459 23078 1640 628 620 89 986 28034 82 534 211 7067 982 14808 65132 823066470 938446095 50582231 725359 40812848 11174502

[出力例]

3501242955

■参照サイト
AtCoder Beginner Contest 173

2020年7月3日2020年7月3日

C++ の動作確認をしてみた（２５２）

C++の練習を兼ねて, AtCoder Beginner Contest 172 の問題F (Unfair Nim) を解いてみた.

■感想.
1. 解答方針が, 全く見えなかったので, 解説を参考に実装したところ何とかAC版となった.
2. bit を計算する時, 1 でなく, 1LL を使うとか, S = a + b のチェックなど, 考慮事項も多く, いろいろ苦労したように思う.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.

本家のサイトABC 172 解説をご覧下さい.

■C++版プログラム(問題F／AC版).

// C++ (GCC 9.2.1)
// 解き直し.
// https://img.atcoder.jp/abc172/editorial.pdf
#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 A[333];

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    rep(i, N) scanf("%lld", &A[i]);
    
    // 2. 解説通り.
    // 2-1. S, X を 設定.
    LL S = A[0] + A[1], X = 0LL;
    repx(i, 2, N) X ^= A[i];
    
    // 2-2. D を 設定.
    LL D = (S - X) / 2LL;
    // printf("S=%lld X=%lld D=%lld\n", S, X, D);
    
    // 2-3. D が 非負整数で無い, または, D と X の 共通ビットがある,
    // または, D が A[0] よりも大きい場合.
    if(D < 0LL || (D & X) != 0LL || D > A[0]){
        puts("-1");
        return 0;
    }
    
    // 2-4. Y を 設定.
    LL Y = 0LL, a = D;
    repr(i, 40, 0){
        LL bit = 1LL << i;
        // printf("bit=%lld (X & bit)=%lld X=%lld Y=%lld (X + Y)=%lld\n", bit, (X & bit), X, Y, X + Y);
        if(X & bit){
            LL c = D ^ (Y | bit);
            // printf("c=%lld\n", c);
            if(c <= A[0]) Y |= bit, X -= bit, a = D ^ Y;
        }
    }
    
    // 2-5. S = a + b が成立しているかのチェック.
    // -> n2_03 などへの対策.
    // ex.
    // 2
    // 5 6
    // -> S = 11, a + b = 10 の ように 差分が出る場合がある.
    LL b = D ^ X;
    // printf("a=%lld b=%lld (a + b)=%lld\n", a, b, a + b);
    if(S != a + b){
        puts("-1");
        return 0;
    }
    
    // 2-6. a < A[0] であるかのチェック.
    // -> sample_03 などへの対策.
    if(a == 0){
        puts("-1");
        return 0;
    }
    
    // 3. 出力.
    printf("%lld\n", A[0] - a);
    return 0;
    
}

// C++ (GCC 9.2.1)

// 解き直し.

// https://img.atcoder.jp/abc172/editorial.pdf

#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 A[333];

int main(){

// 1. 入力情報.

int N;

scanf("%d", &N);

rep(i, N) scanf("%lld", &A[i]);

// 2. 解説通り.

// 2-1. S, X を設定.

LL S = A[0] + A[1], X = 0LL;

repx(i, 2, N) X ^= A[i];

// 2-2. D を設定.

LL D = (S - X) / 2LL;

// printf("S=%lld X=%lld D=%lld\n", S, X, D);

// 2-3. D が非負整数で無い, または, D と X の共通ビットがある,

// または, D が A[0] よりも大きい場合.

if(D < 0LL || (D & X) != 0LL || D > A[0]){

puts("-1");

return 0;

}

// 2-4. Y を設定.

LL Y = 0LL, a = D;

repr(i, 40, 0){

LL bit = 1LL << i;

// printf("bit=%lld (X & bit)=%lld X=%lld Y=%lld (X + Y)=%lld\n", bit, (X & bit), X, Y, X + Y);

if(X & bit){

LL c = D ^ (Y | bit);

// printf("c=%lld\n", c);

if(c <= A[0]) Y |= bit, X -= bit, a = D ^ Y;

}

// 2-5. S = a + b が成立しているかのチェック.

// -> n2_03 などへの対策.

// ex.

// 2

// 5 6

// -> S = 11, a + b = 10 のように差分が出る場合がある.

LL b = D ^ X;

// printf("a=%lld b=%lld (a + b)=%lld\n", a, b, a + b);

if(S != a + b){

puts("-1");

return 0;

}

// 2-6. a < A[0] であるかのチェック.

// -> sample_03 などへの対策.

if(a == 0){

puts("-1");

return 0;

}

// 3. 出力.

printf("%lld\n", A[0] - a);

return 0;

}

[入力例]
2
5 3

[出力例]
1
※AtCoderテストケースより

[入力例]
2
3 5

[出力例]
-1
※AtCoderテストケースより

[入力例]
3
1 1 2

[出力例]
-1
※AtCoderテストケースより

[入力例]
8
10 9 8 7 6 5 4 3

[出力例]
3
※AtCoderテストケースより

[入力例]
3
4294967297 8589934593 12884901890

[出力例]
1
※AtCoderテストケースより

[入力例]
10
192 210 39 247 115 265 70 299 85 250

[出力例]
3

[入力例]
15
321 92 304 214 1 298 69 321 220 298 186 233 189 320 192

[出力例]
10

[入力例]

5 3

[出力例]

※AtCoderテストケースより

[入力例]

3 5

[出力例]

-1

※AtCoderテストケースより

[入力例]

1 1 2

[出力例]

-1

※AtCoderテストケースより

[入力例]

10 9 8 7 6 5 4 3

[出力例]

※AtCoderテストケースより

[入力例]

4294967297 8589934593 12884901890

[出力例]

※AtCoderテストケースより

[入力例]

192 210 39 247 115 265 70 299 85 250

[出力例]

[入力例]

321 92 304 214 1 298 69 321 220 298 186 233 189 320 192

[出力例]

■参照サイト
AtCoder Beginner Contest 172

C++の練習を兼ねて, AtCoder Beginner Contest 008 の 問題C (コイン) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 053 の 問題A (ドミノ色塗り) ～ 問題B (回文分割) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 170 の 問題E (Smart Infants) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 051 の 問題A (塗り絵) ～ 問題B (互除法) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 173 の 問題D (Chat in a Circle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 172 の 問題F (Unfair Nim) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 008 の問題C (コイン) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 053 の問題A (ドミノ色塗り) ～問題B (回文分割) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 170 の問題E (Smart Infants) を解いてみた.

C++の練習を兼ねて, AtCoder Regular Contest 051 の問題A (塗り絵) ～問題B (互除法) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 173 の問題D (Chat in a Circle) を解いてみた.

C++の練習を兼ねて, AtCoder Beginner Contest 172 の問題F (Unfair Nim) を解いてみた.