AtCoder Beginner Contest 162 に C# で参加した記録
AtCoder Beginner Contest 162 – AtCoder
ABC162 にC#で参加しました。結果はABCDの4問ACでした。今回から新ジャッジ環境でのコンテストになり、使用可能言語のバージョンアップが行われています。
コンテスト中にジャッジが詰まることもありましたが、無事レートが更新されました。パフォーマンス1336の結果で、レートも微増しました。この辺で安定しているので、水色DifficultyのE問題が解けないと上には進めなさそうです。
以下、振り返ります。
A – Lucky 7
3 桁の整数 N が与えられます。N のいずれかの桁に数字の 7 は含まれますか？
含まれるなら Yes を、含まれないなら No を出力してください。
文字列で受け取って判定するのがわかりやすいと思いました。
if (S.Contains('7'))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}B – FizzBuzz Sum
FizzBuzz列 a1,a2,… を次のように定めます。
- i が 3 でも 5 でも割り切れるなら、ai=FizzBuzz
- そうではなく i が 3 で割り切れるなら、ai=Fizz
- そうではなく i が 5 で割り切れるなら、ai=Buzz
- そうではないなら、ai=i
FizzBuzz列の N 項目までに含まれる数の和を求めてください。
有名なFizzBuzz問題そのままです。今回は何も考えずに条件を上から順番にif文に落とし込めばうまくいきます。
var ans = 0L;
for (int i = 1; i <= N; i++)
{
if (i % 3 == 0 && i % 5 == 0)
{
continue;
}
if (i % 3 == 0)
{
continue;
}
if (i % 5 == 0)
{
continue;
}
ans += i;
}
Console.WriteLine(ans);総和が32bit整数の上限を超えます。入力例にオーバーフローになるパターンもありました。
C – Sum of gcd of Tuples (Easy)
C – Sum of gcd of Tuples (Easy)
K∑a=1 K∑b=1 K∑c=1 gcd(a,b,c) を求めてください。
ただし、gcd(a,b,c) は a,b,c の最大公約数を表します。
制約
- 1≤K≤200
- K は整数
シグマの部分はfor文ループして足し算するというやつです。
for(int a=1; a<=k; a++) {} みたいなコードになります。これが3つ並んでいるので3重のループを書けばいいです。
今回は制約もKが102なので3重ループしてもO(K^3 * logk)=O(10^7)くらい？でTLEしません。
static int Gcd(int a, int b)
{
if (b == 0) return a;
return Gcd(b, a % b);
}
var K = sc.ReadLong();
var ans = 0L;
for (int a = 1; a <= K; a++)
{
for (int b = 1; b <= K; b++)
{
for (int c = 1; c <= K; c++)
{
var g = Gcd(a, b);
g = Gcd(g, c);
ans += g;
}
}
}
Console.WriteLine(ans);Gcdはユークリッドの互除法で求めます。
[C#] ユークリッドの互除法で最大公約数を求める方法 │ Web備忘録
D – RGB Triplets
R, G, B のみからなる、長さ N の文字列 S があります。
以下の 2 つの条件をともに満たす組 (i, j, k) (1≤i<j<k≤N) の数を求めてください。
- Si≠Sj かつ Si≠Sk かつ Sj≠Sk である
- j−i≠k−j である
制約
- 1≤N≤4000
- S は R, G, B のみからなる、長さ N の文字列である
制約的に i, j, k の全探索は O(N^3) でTLEします。
条件1について
最初に考えたのは、条件の2つ目を無視すると数え上げはうまくいきそうということです。類題を過去問で解いた気がします。
とりあえず条件2を無視して考えたときのコンテスト中の実装は以下の通りです。実際は無駄な考えでした。
- (i, j, k) の真ん中の j を全通り試す
- j文字目が'R'の時の組み合わせは以下の計算の和
- j-1文字目までの'G'の数 * j+1文字目以降の'B'の数
- j-1文字目までの'B'の数 * j+1文字目以降の'R'の数
- j文字目が'G','B'の時も同様に求まる。
例えば入力例1の "RRGB" の場合、jが2の時に直前までで'R'が2回出てきており、j+1文字目以降に'B'が1回出てきているので、2*1で2通りとなります。それ以外は0になります。
累積和で各文字の出現数を前計算(O(N))しておけば、各区間での文字の出現数は O(1) で求まります。つまりjの全探索で O(N) で条件1の場合の答えが求まりす。
一応実装は上のやり方でも問題ないんですが、あとあと考えたら単純に
Rの個数 * Gの個数 * Bの個数
で条件1の数え上げは済みますね。取り出す位置もくそも関係なく、単純に選べる組み合わせの計算式がこうなります。
過去問に引きずられずに冷静にならなければいけませんね。いずれにせよ条件1を満たす通りの数は求まりました。
条件2について
次に条件2について考えますが、これは iとj, jとk の差が等しいときには数え上げてはいけないというものなので、条件1を満たし、j-i=k-j も満たす(条件2を満たさない)通り数を別途求めて、上で求めた答えから引けば、この問題の答えが求まります。
ということで d = j-i としたときに、このdを全探索して条件1を満たすものを上で求めた組み合わせから引けば答えになります。dの全探索は O(N^2) になり、全体で O(N^2) の計算量となりACできました。
var N = sc.ReadInt();
var S = sc.ReadStr();
// 各文字の出現回数を数えておく
var count = new long[3];
foreach (var c in S)
{
if (c == 'R') count[0]++;
if (c == 'G') count[1]++;
if (c == 'B') count[2]++;
}
// 条件1を満たす通りの数
var ans = count[0] * count[1] * count[2];
// d=j-k=j-i としたとき、条件1を満たす組み合わせを答えから引く
for (int d = 1; d < N; d++)
{
for (int i = 0; i < N; i++)
{
if (i + d + d >= N) break;
if (S[i] != S[i + d] && S[i] != S[i + d + d] && S[i + d] != S[i + d + d]) ans--;
}
}
Console.WriteLine(ans);累積和は無駄な実装でしたが、j-i を固定して全探索は想定解法っぽいのでよかったです。1発ACだったのでよしとします。
類題
[C#] 三井住友信託銀行プログラミングコンテスト2019 の記録 │ Web備忘録
以前のコンテストであったD問題にも3文字を選ぶときに真ん中を固定して累積和という実装方針を使いました。それが上の問題です。
想定解法ではなかったですが、同じような実装を使って解けます。コンテスト中にもそれで通したので印象に残ってました。
E – Sum of gcd of Tuples (Hard)
解けませんでした。いろいろ試行錯誤しましたが、、、後日考えます。
以上。
