AtCoder Beginner Contest 151 に参加した記録
AtCoder Beginner Contest 151 – AtCoder
ABC 151に参加しました。ここ最近のABCがUnrated続きだったのですが、今回はレートがつくコンテストになりました。
今回の結果は ABCDEの5問ACでした。初めてE問題をコンテスト中にACできました。
問題を振り返ります。
A – Next Alphabet
z でない英小文字 C が与えられます。アルファベット順で C の次の文字を出力してください。
if文でaからyを25分岐しても解けますが、これは文字をASCIIコードで整数値で表せることを知っていたら簡単に溶ける問題です。
var ans = (char)(C + 1);
Console.WriteLine(ans);B – Achieve the Goal
高橋君は N 科目のテストを受けます。各テストは K 点満点であり、点数はそれぞれ 0 以上の整数です。
高橋君は N−1 科目のテストを既に受けており、i 番目の科目のテストの点数は Ai 点でした。
高橋君の目標は、N 科目のテストの平均点を M 点以上にすることです。
高橋君が目標を達成するためには、最後のテストで最低何点取る必要があるか出力してください。
達成不可能である場合は、代わりに -1 を出力してください。
制約
- 2≤N≤100
- 1≤K≤100
- 1≤M≤K
- 0≤Ai≤K
- 入力中のすべての値は整数である。
平均を求めるのではなく、目標の平均点を満たす最小の値を求める問題です。
B問題にしては少しややこしいような問題に感じましたが、単純に候補の点数を全探索しても間に合う制約になっています。0..Kの範囲をループして平均点を全パターン計算し、条件を満たすかどうか確認しましょう。
// 入力省略..
var sum = A.Sum();
var ans = -1;
for (int i = 0; i <= K; i++)
{
var avg = (sum + i) / N;
if (avg >= M)
{
ans = i;
break;
}
}
Console.WriteLine(ans);答えの初期値を-1にしておくと平均点を満たせないときもうまく判定できます。
C – Welcome to AtCoder
高橋君は AtCoder のコンテストに参加しています。
このコンテストでは、 N 問の問題が出題されます。
高橋君はコンテスト中に M 回の提出を行いました。
i 回目の提出は pi 番目の問題への提出であり、結果は Si (AC または WA) でした。
高橋君の正答数は、AC を 1 回以上出した問題の数です。
高橋君のペナルティ数は、高橋君が AC を 1 回以上出した各問題において、初めて AC を出すまでに出した WA の数の総和です。
高橋君の正答数とペナルティ数を答えてください。
制約
- N , M , pi は整数
- 1≤N≤10⁵
- 0≤M≤10⁵
- 1≤pi≤N
- Si は AC か WA のいずれか
Nが多くても10⁵なので、すべての問題に対して「ACしたかどうか」「WAの回数」をそれぞれ配列を使って管理できます。辞書型 Dictionary を使ってもいけると思います。
ACとWAを管理できればあとは答えを求めるだけです。
var waCount = 0;
var acCount = 0;
var ac = new bool[N + 1];
var wa = new int[N + 1];
for (int i = 0; i < M; i++)
{
var p = sc.ReadInt();
var s = sc.ReadStr();
// すでにACしている問題の結果は無視
if (ac[p]) continue;
// まだACしていない問題でWAの場合は数える
if (s == "WA") wa[p]++;
else
{
// ACしたとき、この問題でのWAをペナルティとして数える
ac[p] = true;
acCount++;
waCount += wa[p];
}
}
Console.WriteLine(acCount + " " + waCount);ここまでは順調に10分程度で解けましたがD問題が鬼門でした。
D – Maze Master
高橋君は、縦 H マス、横 W マスの H×W マスからなる迷路を持っています。
上から i 行目、左から j 列目のマス (i,j) は、 Sij が # のとき壁であり、. のとき道です。
道のマスからは、上下左右に隣接する道のマスに移動することができます。
迷路の外に移動すること、壁のマスへ移動すること、斜めに移動することはできません。
高橋君は、道のマスからスタートとゴールを自由に決め、迷路を青木君に渡します。
青木君は、移動回数が最小になるようにしてスタートからゴールまで移動します。
高橋君がスタートとゴールの位置を適切に定めたとき、青木君の移動回数は最大で何回になるでしょうか？
制約
- 1≤H,W≤20
- Sij は . か #
- S は . を 2 つ以上含む
- 任意の道のマスから任意の道のマスまで 0 回以上の移動で到達できる
一目簡単に行けそうと思いました。
縦横の制約が小さいので、すべての始点終点の組み合わせを試しても大丈夫だと考えました。最短経路を求めるのは幅優先探索で実装できます。これは幅優先(BFS)の典型というか、最初に実装例としてよく見られるやつなので簡単です。
が、実装してみたところTLEになりました。ちゃんと計算量を考えないといけないですね。
その後、実装がまずくていろいろ試しているうちに結局WAがかさみました。
結局前提がそもそも間違っていて、スタートを固定して一番遠い場所をゴールとすればよかったみたいです。
// 入力省略..
var dh = new int[] { -1, 0, 1, 0 };
var dw = new int[] { 0, -1, 0, 1 };
var ans = 0;
for (int sh = 0; sh < H; sh++)
{
for (int sw = 0; sw < W; sw++)
{
if (S[sh][sw] == '#') continue;
var res = 0;
var q = new Queue<Tuple<int, int, int>>();
q.Enqueue(Tuple.Create(sh, sw, 0));
var visited = new bool[H, W];
visited[sh, sw] = true;
while (q.Count > 0)
{
var now = q.Dequeue();
var h = now.Item1;
var w = now.Item2;
var c = now.Item3;
res = Math.Max(res, c);
for (int i = 0; i < 4; i++)
{
var nh = h + dh[i];
var nw = w + dw[i];
if (nh < 0 || H <= nh || nw < 0 || W <= nw) continue;
if (visited[nh, nw] || S[nh][nw] == '#') continue;
visited[nh, nw] = true;
q.Enqueue(Tuple.Create(nh, nw, c + 1));
}
}
ans = Math.Max(ans, res);
}
}いろいろあってACはできました。
解説PDFにはワーシャルフロイドでも解けるとありました。ワーシャルフロイドはとりあえず実装してみたことがあったので後で使って解いてみようと思います。
4近傍の座標をfor文で書く方法を解説動画で知りました。便利ですね。スニペットに入れとこうと思います。
E – Max-Min Sums
有限個の整数からなる集合 X に対し f(X)=maxX−minX と定義します。
N 個の整数 A1,…,AN が与えられます。
このうち K 個を選び、それらからなる集合を S とします。同じ値であっても添字が異なる要素を区別すると、そのような選び方は NCK 通りありますが、その全てについての f(S) の合計を求めてください。
答えは非常に大きくなる可能性があるので、mod10⁹+7 で出力してください。
制約
- 1≤N≤10⁵
- 1≤K≤N
- |Ai|≤1⁹9
Dが解けてほっとしましたが、少し時間があったのでE問題にもチャレンジしました。E問題もぱっと見た感じ、何とかなりそうな気がしました。
入力ケースを見ながらノートにいろいろ書いているとひらめいたのが以下の考えです。
Aはソートしておきます。
入力例1について考えます。1 1 3 4 から2個選んでf(X)を求めます。
- 4が最大になるのは
1 1 3の3個から1個選ぶパターン数だけあり得ます。 - 3が最大になるのは
1 1の2個から1個(K-1個)選ぶパターン数だけあります。 - 1が最大になるのは
1の1個から1個選ぶパターン数だけあります。
なので maxX の部分だけ先に計算できます。
4*3C1 + 3*2C1 + 1*1C1 = 12+6+1 = 19 .. こんな感じです。
同様に minX の部分も計算できます。
- 1が最小になるのは
1 3 4の3個から1個選ぶパターン数だけあり得ます。 - 1が最小になるのは
3 4の2個から1個選ぶパターン数だけあり得ます。 - 3が最小になるのは
4の1個から1個選ぶパターン数だけあり得ます。
1*3C1 + 1*2C1 + 3*1C1 = 3+2+3 = 8 .. こんな感じです。
minXの合計からminXの合計を引けば答えになります。
19-8=11
これでACしました。コンテスト終了間際に滑り込みでした。
解説動画を見ればこの考えであっているっぽいです。
回答部分のコード
// 入力省略..
Array.Sort(A);
ModInt ans = 0;
for (int i = N - 1; i >= K - 1; i--)
{
ans += A[i] * ModInt.nCr(i, K - 1);
}
Array.Reverse(A);
for (int i = N - 1; i >= K - 1; i--)
{
ans -= A[i] * ModInt.nCr(i, K - 1);
}
Console.WriteLine(ans);ModIntは剰余計算を手抜き計算できるようにした型です。四則演算がすべてできます。べき乗、nCrの組み合わせ、階乗等の計算がたぶん効率よく計算できるようになっています。
二項係数を使って nCr を計算できると解説PDFに書かれていますが、ここでは普通に割り算で計算しています。違いはわかりません。
public struct ModInt
{
public const long Mod = (int)1e9 + 7;
public long num;
public ModInt(long n) { num = n; }
public override string ToString() { return num.ToString(); }
public static ModInt operator +(ModInt l, ModInt r) { l.num += r.num; if (l.num >= Mod) l.num -= Mod; return l; }
public static ModInt operator -(ModInt l, ModInt r) { l.num -= r.num; if (l.num < 0) l.num += Mod; return l; }
public static ModInt operator *(ModInt l, ModInt r) { return new ModInt(l.num * r.num % Mod); }
public static ModInt operator /(ModInt l, ModInt r) { return l * Inverse(r); }
public static implicit operator ModInt(long n) { n %= Mod; if (n < 0) n += Mod; return new ModInt(n); }
public static ModInt Pow(ModInt v, long k) { return Pow(v.num, k); }
public static ModInt Pow(long v, long k)
{
long ret = 1;
for (k %= Mod - 1; k > 0; k >>= 1, v = v * v % Mod)
if ((k & 1) == 1) ret = ret * v % Mod;
return new ModInt(ret);
}
public static ModInt Inverse(ModInt v) { return Pow(v, Mod - 2); }
private static List<ModInt> Facs = new List<ModInt> { 1 };
public static ModInt Fac(int n)
{
for (int i = Facs.Count; i <= n; i++)
{
Facs.Add(i * Facs[i - 1]);
}
return Facs[n];
}
public static ModInt nCr(int n, int r)
{
if (n < r) return 0;
if (n == r) return 1;
return Fac(n) / (Fac(r) * Fac(n - r));
}
}いろんな人の実装と解説ページを参考につぎはぎして作りました。一応いろんな問題でACできてるので正しく動いているはずです。
感想
Dがかなりてこずりましたが何とかなってよかったです。E問題はコンテスト中だと初めて解けました。ModIntを用意しておいて助かりました。
パフォーマンス的には水色でした。Dの実装でもつまずいていたのでもう少しいいパフォーマンスが狙えそうでしたが、まだまだ精進が足りない感じです。
だいぶんレベルアップしてきたような気がしますが、問題の相性によっては解けたり解けなかったりなので、このD問題くらいは安定して解けるようになりたいところです。
以上。
