AtCoder Beginner Contest 150に参加した記録
AtCoder Beginner Contest 150 – AtCoder
ABC 150に参加しました。年明け1発目のコンテストでしたがトラブルでUnratedになりました。
結果は10分くらいで3問ACして、Dが通せませんでした。
とりあえず問題を振り返ります。
A – 500 Yen Coins
高橋君は 500 円玉を K 枚持っています。 これらの総額が X 円以上である場合は Yes を、そうでない場合は No を出力してください。
ただの小学生レベルの算数です。四則演算がコードで書けるかどうかというだけですね。
if (500 * K >= X)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}B – Count ABC
英大文字のみからなる長さ N の文字列 S があります。
S の連続する部分列として ABC がいくつ含まれるかを求めてください。
制約: 3≤N≤50
連続する部分列を求めるのはよく見る問題パターンです。なんかいろいろ工夫しないと計算量的に解けない問題もありますが、これはB問題で制約も小さいので純粋に3文字の部分文字列を全探索をすればよいです。
なので文字列の扱いがわかれば解けそうです。
文字列を先頭から見ていき3文字ずつちぎってABCになるかどうかを判定すればよいです。はみ出さないように先頭にする文字はN-2文字目までにします。
あとは一致するパターンを数えるだけです。
var ans = 0;
for (int i = 0; i < N - 2; i++)
{
var s = S.Substring(i, 3);
if (s == "ABC") ans++;
}
Console.WriteLine(ans);C – Count Order
大きさ N の順列 ((1, 2, …, N) を並び替えてできる数列) P, Q があります。
大きさ N の順列は N! 通り考えられます。このうち、P が書順で a 番目に小さく、Q が辞書順で b 番目に小さいとして、|a−b| を求めてください。
順列を使う問題です。これは順列を生成する関数(C++の next_permutation)があると簡単です。これを使わずに解く方法はわかりません。
C#には順列を生成できる関数はないので自前で実装します。コンテスト時は用意しておいたライブラリを使いました。
[C#] 順列を求める next_permutation() 代わりを実装する方法 │ Web備忘録
↑のページに実装方法をまとめています。
順列の全列挙はN!通りあります。10!くらいまでなら計算量的にも全列挙してもOKです。
static void Main(string[] args)
{
// 入力略..
// 辞書順で全パターンを生成する
var x = Enumerable.Range(1, N).ToArray();
var p = AllPermutation(x);
// Pの辞書順を求める
var a = 0;
for (int i = 0; i < p.Count; i++)
{
var ok = true;
for (int j = 0; j < N; j++)
{
if (P[j] != p[i][j]) ok = false;
}
if (ok) a = i;
}
// Qの辞書順を求める
var b = 0;
for (int i = 0; i < p.Count; i++)
{
var ok = true;
for (int j = 0; j < N; j++)
{
if (Q[j] != p[i][j]) ok = false;
}
if (ok) b = i;
}
// 答え
var ans = Math.Abs(a - b);
Console.WriteLine(ans);
}
static List<T[]> AllPermutation<T>(params T[] array) where T : IComparable
{
var a = new List<T>(array).ToArray();
var res = new List<T[]>();
res.Add(new List<T>(a).ToArray());
var n = a.Length;
var next = true;
while (next)
{
next = false;
int i;
for (i = n - 2; i >= 0; i--)
{
if (a[i].CompareTo(a[i + 1]) < 0) break;
}
if (i < 0) break;
var j = n;
do
{
j--;
} while (a[i].CompareTo(a[j]) > 0);
if (a[i].CompareTo(a[j]) < 0)
{
var tmp = a[i];
a[i] = a[j];
a[j] = tmp;
Array.Reverse(a, i + 1, n - i - 1);
res.Add(new List<T>(a).ToArray());
next = true;
}
}
return res;
}D – Semi Common Multiple
どうやらこのD問題のテストケースに問題があったみたいでUnratedになったみたいです。が、それでもACできる問題だったみたいなので何が問題だったんでしょうか。
とりあえず次のような問題でした。
長さ N の偶数からなる正の整数列 A=a1,a2,…,aN と、整数 M が与えられます。
任意の k(1≤k≤N) に対して以下の条件を満たす正の整数 X を A の「半公倍数」と定義します。
- X=ak×(p+0.5) を満たす負でない整数 p が存在する。
1 以上 M 以下の整数のうちの A の半公倍数の個数を求めてください。
制約
- 1≤N≤10⁵
- 1≤M≤10⁹
- 2≤ai≤10⁹
- ai は偶数である。
- 入力は全て整数である。
数学問題です。一目解けなさそうでした。そして解けませんでした。結果難しい問題だったみたいですね。
解説PDF見てもわかりません。もう少し精進しようと思います。
全体の感想
ABCはやっぱりD問題が鬼門ですね。CとDにものすごく壁を感じます。Dを安定して解けるようになれば水色になれそうですが、まだまだ精進が足りない感じです。
数学というか整数問題を勉強しようと思います。
以上。
