AtCoder Beginner Contest 152 に参加した記録
2日連続のコンテスト参加でした。結果は残念ながらABCの3問しかACできませんでした。
前回ABCが5問ACしたことを考えると大きな落ち込みです。D問題は解けなければいけなかったです。
とりあえず問題を振り返ります。
A – AC or WA
高橋君は、プログラミングコンテスト AXC001 に参加しており、問題 A にコードを提出しました。
この問題には N 個のテストケースがあり、すべてのテストケースに正解した場合のみ提出は AC となります。
高橋君の提出は、N 個のテストケースのうち M 個のテストケースに正解しました。
高橋君の提出が AC となるか判定してください。
N と M が一致する場合、すべてのテストケースが正解になります。
if (N == M)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}if文が書けるかどうかを問う問題でした。
B – Comparing Strings
1 桁の正整数 a ,b が与えられます。整数 a を b 回繰り返してできる文字列と 整数 b を a 回繰り返してできる文字列のうち、辞書順で小さい方を答えてください。
例えば 4, 3 が与えられたとき、"444" と "3333" でどちらが辞書順で小さい文字列かというのを答える問題です。
入力された数値の小さいほうを使った文字列が辞書順でも必ず小さくなります。
if (A < B)
{
var ans = new string(A.ToString()[0], B);
Console.WriteLine(ans);
}
else
{
var ans = new string(B.ToString()[0], A);
Console.WriteLine(ans);
}2つの文字列を作ってif文で比較してもOKです。
var s1 = new string(A.ToString()[0], B);
var s2 = new string(B.ToString()[0], A);
if (s1.CompareTo(s2) < 0)
{
Console.WriteLine(s1);
}
else
{
Console.WriteLine(s2);
}C – Low Elements
1,…,N の順列 P1,…,PN が与えられます。
次の条件を満たす整数 i(1≤i≤N) の個数を数えてください。
- 任意の整数 j(1≤j≤i) に対して、 Pi≤Pj
制約
- 1≤N≤2×10⁵
- P1,…,PN は 1,…,N の順列である。
- 入力はすべて整数である。
問題文が言いたいことは、ある要素(Pi)の手前にあるすべての要素(Pj)がその要素(Pi)より大きいとき、その条件を満たすiを数え上げろということです。
入力例1 の 4 2 5 1 3 の場合について考えます。
- 4 はOKです。(4も含みますが、4≤4を満たします。)
- 2 の手前の要素には自分より大きい
4だけがあるのでOKです。 - 5 の手前は
4 2で小さい値がのでNGです。 - 1 の手前は
4 2 5ですべて自分より大きいのでOKです。 - 3 の手前は
4 2 5 1で1が 3 より小さいのでNGです。
全部で3つ条件を満たすものが見つかりました。
数列をループして、各要素ごとに直前までの要素をループすることで全パターンの条件を判定できますが、O(N²) の計算量となりTLEしてしまいます。
しかし、比較は直前までの要素で見つかった最小の値さえ分かっていれば、2重ループしなくても判定できます。
var ans = 1;
var min = A[0];
for (int i = 1; i < N; i++)
{
if (min > A[i])
{
ans++;
min = A[i];
}
}
Console.WriteLine(ans);解説見たらこんな感じでした。
D – Handstand 2
正の整数 N が与えられます。
N 以下の正の整数の組 (A,B) であって、次の条件を満たすものの個数を求めてください。
- A,B を先頭に 0 のつかない 10 進数表記で表したときに、 A の末尾の桁が B の先頭の桁に等しく、 A の先頭の桁が B の末尾の桁に等しい
解けなかった問題です。
Aを固定してループして何とかしようとするところまではあってたんですが、すべての組み合わせの数を前計算しておけばよかったんですね。
static void Main(string[] args)
{
var N = sc.ReadInt();
// N以下で <先頭, 末尾> になる数を先に数えておく
var dic = new Dictionary<Tuple<int, int>, int>();
for (int i = 1; i <= N; i++)
{
var tup = GetTuple(i);
if (dic.ContainsKey(tup))
{
dic[tup]++;
}
else
{
dic[tup] = 1;
}
}
var ans = 0;
// aの候補(1-N)をループする
for (int i = 1; i <= N; i++)
{
// aの先頭と末尾の値を取得する
var tup = GetTuple(i);
// bはaの先頭と末尾を入れ替えた値
var key = Tuple.Create(tup.Item2, tup.Item1);
if (dic.ContainsKey(key))
{
// bの個数
ans += dic[key];
}
}
Console.WriteLine(ans);
}
// 整数nの先頭と末尾をタプルで返す
static Tuple<int, int> GetTuple(int n)
{
var a = n.ToString()[0] - '0';
var b = n % 10;
return Tuple.Create(a, b);
}レート下がって残念でした。
以上。
