ARC102 参加記
AtCoder Regular Contest 102 - AtCoder
C問題 Triangular Relationship(300)
・問題: N以下の正の整数の組(a,b,c)でa+b,b+c,c+aのすべてがKの倍数になるようなものの個数を求めよ。
倍数であるかを判定するのでmodに注目します。するとa,b,cの関係は対称なのでa≡b≡c(mod K)になることがわかります。よってa+b≡0(mod K)にするためにはa≡b≡c≡0またはa≡b≡c≡K/2(Kは偶数)である必要があります。
a≡0となるaの個数はN/Kなのでa≡b≡c≡0になるような(a,b,c)の組の個数は(N/K)^3, 同様にKが偶数のときa≡b≡c≡K/2となるような(a,b,c)の個数は((N+K/2)/K)^3
Kの偶奇で場合分けして以上でもとめた個数を出力します。
D問題 All Your Paths are Different Length(700)
D - All Your Paths are Different Lengths
L≦10^6, N≦20から二進数を使うのではないかと推測します。(2^20≧10^6)
Lが2の累乗数ならば頂点を一列に並べて頂点i-1とiの間に0と2^iの辺(1≦i)を引けばよいのでそこから辺をどう追加したらよいかを考察していったらなんとか答えにたどり着きました。
感想
CD2完で217位でした。コンテスト中に700が解けていままで一番いい順位が出ました。
これで晴れて青になれて正直嬉しいです。これからも精進します。
