AtCoder Beginner Contest 173 に C# で参加した記録
AtCoder Beginner Contest 173 – AtCoder
ABC173 にC#で参加しました。
結果はABCDの4問ACでE問題はバグがとれずWAでした。
レートは微増しましたが変わらず。
では振り返ります。
A – Payment
お店で N 円の商品を買います。
1000 円札のみを使って支払いを行う時、お釣りはいくらになりますか？
ただし、必要最小限の枚数の 1000 円札で支払いを行うものとします。
制約も小さいので、ループしてすべてのパターンを試せばよいです。私は1000からN%1000を引いた値を求めました。最後に余りをとるのを忘れずにいします。
var N = sc.ReadInt();
var ans = 1000 - (N % 1000);
ans %= 1000;
Console.WriteLine(ans);B – Judge Status Summary
高橋君は、プログラミングコンテスト AXC002 に参加しており、問題 A にコードを提出しました。
この問題には N 個のテストケースがあります。
各テストケース i (1≤i≤N) について、ジャッジ結果を表す文字列 Si が与えられるので、ジャッジ結果が AC, WA, TLE, RE であったものの個数をそれぞれ求めてください。
Dictionaryなり配列なりで数え上げればよいです。
var N = sc.ReadInt();
var result = new string[] { "AC", "WA", "TLE", "RE" };
var count = new int[4];
for (int i = 0; i < N; i++)
{
var S = sc.ReadStr();
count[Array.IndexOf(result, S)]++;
}
for (int i = 0; i < 4; i++)
{
Console.WriteLine($"{result[i]} x {count[i]}");
}IndexOf で文字列が何番目の要素か探しています。あとは数え上げて出力しているだけです。
C – H and V
H 行 W 列に並ぶマスからなるマス目があります。上から i 行目、左から j 列目 (1≤i≤H,1≤j≤W) のマスの色は文字 ci,j として与えられ、ci,j が . のとき白、# のとき黒です。
次の操作を行うことを考えます。
- 行を何行か選び (0 行でもよい)、列を何列か選ぶ (0 列でもよい)。そして、選んだ行に含まれるマスと、選んだ列に含まれるマスをすべて赤く塗る。
正の整数 K が与えられます。操作後に黒いマスがちょうど K 個残るような行と列の選び方は何通りでしょうか。ここで、二つの選び方は、一方においてのみ選ばれる行または列が存在するときに異なるとみなされます。
制約
- 1≤H,W≤6
- 1≤K≤HW
- ci,j は . または #
制約が小さい(1≤H,W≤6)ので行と列の選び方をすべて試すことができます。具体的には、塗りつぶす行と列の組み合わせをすべて試します。
行と列は合わせて H+W 個だけあり、これらすべてについて塗りつぶすか塗りつぶさないかの2択あるので、組み合わせの数は 2H+W だけあります。制約が小さいので問題ありません。
ということで行列それぞれについてビット全探索で塗りつぶす位置を試します。試した結果黒になっている個数がK個であるか確認すればOKです。
// 入力
var H = sc.ReadInt();
var W = sc.ReadInt();
var K = sc.ReadInt();
var C = sc.ReadStrArray(H);
// ビット全探索で行列の塗りつぶし位置を試す
var ans = 0;
for (int x = 0; x < 1 << H; x++)
{
for (int y = 0; y < 1 << W; y++)
{
// 黒の個数を数える
var count = 0;
for (int i = 0; i < H; i++)
{
// 赤で塗りつぶした行は無視
if (((x >> i) & 1) == 1) continue;
for (int j = 0; j < W; j++)
{
// 赤で塗りつぶした列は無視
if (((y >> j) & 1) == 1) continue;
// 黒のとき
if (C[i][j] == '#') count++;
}
}
// 黒がちょうどK個残る組み合わせだった場合
if (count == K) ans++;
}
}
Console.WriteLine(ans);D – Chat in a Circle
あなたはオンラインゲーム「ATChat」のチュートリアルを終え、その場に居合わせたプレイヤー N 人で早速とある場所を訪ねることにしました。この N 人には 1 から N の番号が振られており、人 i (1≤i≤N) の フレンドリーさ は Ai です。
訪ねる際、N 人は好きな順番で 1 人ずつ到着します。あなたたちは迷子にならないために、既に到着した人たちで環状に並び、新たに到着した人は好きな位置に割り込んで加わるというルールを決めました。
最初に到着した人以外の各人は、割り込んだ位置から到着した時点で「時計回りで最も近い人」と「反時計回りで最も近い人」のフレンドリーさのうち小さい方に等しい 心地よさ を感じます。最初に到着した人の心地よさは 0 です。
N 人が到着する順番や割り込む位置を適切に決めたとき、N 人の心地よさの合計の最大値はいくらになるでしょう？
詳しイメージは問題の入力例1にあります。以下その画像です。
直感的に大きな値から座らせたほうがよさそうです。なぜなら次に来る人がその値から大きな心地よさを得られるからです。
詳しい証明は解説PDFを見るのが良いです。
最初に座った値を一番大きな値にすると、次に座る人だけがこの値から心地よさを得られます。3番目に座る人は1番目の人と2番目の人の間にしか座れず、2番目の人の値から心地よさを得ることになります。
2番目以降に座る人は、さらに次の人が自分の両隣のどちらかに座ることで、その値から心地よさを得ることになります。
例えば、X が A と B の間に座るとします。(X ≤ B ≤ A)
A ---- X ---- B このとき AとXの間、BとXの間の2つ新たに座る場所が生まれます。2つの場所とも、座ったときに得られる心地よさは必ず X になります。(X ≤ B ≤ A)のため。つまり座った人の値だけ心地よさが得られる場所が2か所生まれるということです。
あとはキューなりに座れる場所の心地よさを追加しながら、人を値の大きな順番で座らせればよいです。座るのは一番得られる心地よさが大きな場所です。
var N = sc.ReadInt();
var A = sc.ReadLongArray(N);
// 降順にしておく
Array.Sort(A);
Array.Reverse(A);
// 座れる場所の心地よさ
var q = new Queue<long>();
// 一番値の大きな人を座らせる
q.Enqueue(A[0]);
var ans = 0L;
for (int i = 1; i < N; i++)
{
// 一番心地よい場所に座る
var now = q.Dequeue();
ans += now;
// 座った場所の両隣に新たに座れる場所が生まれる
// その時隣り合う値は必ず自分の値より大きい(降順に見てるため)
q.Enqueue(A[i]);
q.Enqueue(A[i]);
}
Console.WriteLine(ans);E問題は1時間以上格闘して解けないという結果でした。
以上。
