AtCoder Beginner Contest 164 に C# で参加した記録
AtCoder Beginner Contest 164 – AtCoder
ABC164 にC#で参加しました。結果はABCDの4問ACでした。
D問題は過去問で類題というか完全上位互換の問題があったのでそのコードを改変して提出してACしました。
パフォーマンスは1500くらいでレートは30くらい上がりました。
以下、振り返ります。
A – Sheep and Wolves
羊が S 匹、狼が W 匹います。
狼の数が羊の数以上のとき、羊は狼に襲われてしまいます。
羊が狼に襲われるなら unsafe、襲われないなら safe を出力してください。
if文が書けるかどうか問題です。
if (W >= S)
{
Console.WriteLine("unsafe");
}
else
{
Console.WriteLine("safe");
}B – Battle
高橋君と青木君がモンスターを闘わせます。
高橋君のモンスターは体力が A で攻撃力が B です。 青木君のモンスターは体力が C で攻撃力が D です。
高橋君→青木君→高橋君→青木君→… の順に攻撃を行います。 攻撃とは、相手のモンスターの体力の値を自分のモンスターの攻撃力のぶんだけ減らすことをいいます。 このことをどちらかのモンスターの体力が 0 以下になるまで続けたとき、 先に自分のモンスターの体力が 0 以下になった方の負け、そうでない方の勝ちです。
高橋君が勝つなら Yes、負けるなら No を出力してください。
攻撃時の体力の変化をシミュレーションすればOKです。
// 高橋君が攻撃するターンかどうかのフラグ
var a = true;
// 両者の体力が残っている限り攻撃を繰り返す
while (A > 0 && C > 0)
{
if (a) C -= B;
else A -= D;
a = !a;
}
if (A > 0)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}C – gacha
くじ引きを N 回行い、i 回目には種類が文字列 Si で表される景品を手に入れました。
何種類の景品を手に入れましたか？
過去にもいろいろ類題がありました。とりあえず重複を除いて数え上げができるような実装を行えばOKです。
HashSet<string>に入れる- ソートして隣り合う要素が異なる場合を数え上げる
- Linq の
Distinctで重複を取り除く
コンテスト時は2つ目のソートして数え上げる方法を採りました。実装は3つのパターンを載せてみます。
まずは set に入れて数え上げをしてもらうやり方です。HashSet は Dictionary と異なり同じ値を何度 Add してもエラーになりません。
var N = sc.ReadInt();
var set = new HashSet<string>();
for (int i = 0; i < N; i++)
{
var s = sc.ReadStr(); // 入力
set.Add(s);
}
var ans = set.Count;
Console.WriteLine(ans);ソートしてから実装隣り合う要素を比較して答えを求めます。文字列のソートは予期せぬTLEに出会うので注意しましょう。比較関数を渡しておけばOKです。
AtCoder Beginner Contest 155 に参加してやらかした記録(C#の文字列比較は注意) │ Web備忘録
以前のコンテストでやらかしたのでその時の記事を参考にしてください。今回の場合は通常のソートでもTLEはなかったですが数倍の時間がかかってました。
var N = sc.ReadInt();
var A = sc.ReadStrArray(N);
// 文字列の比較は比較関数を渡さないと遅くなる
Array.Sort(A, string.CompareOrdinal);
var ans = 1;
for (int i = 1; i < N; i++)
{
if (A[i] != A[i - 1]) ans++;
}
Console.WriteLine(ans);C# の Linq には Distinct という重複を無視できる処理が用意されているのでこれを使えば簡単です。
var ans = A.Distinct().Count();
Console.WriteLine(ans);D – Multiple of 2019
1 から 9 までの数字のみからなる文字列 S が与えられます。
次のような条件を満たす整数の組 (i,j) (1≤i≤j≤|S|) の総数を求めてください。
条件: S の i 文字目から j 文字目までを 10 進法の整数としてみると、この整数は 2019 の倍数である。
制約
- 1≤|S|≤200000
- S は 1 から 9 までの数字のみからなる文字列
この問題は ABC158 E – Divisible Substring の完全な下位互換の問題です。この問題にたどり着けばほぼコピペでACできます。
私はこの問題を過去にAC済だったのでこの問題のコードのPを2019の定数に書き換えて提出してACでした。
甘えました。もう一度復習しておかないといけないですね。数学問題は難しいです。
典型問題っぽいので覚えておこうと思います。考え方としては以下の通りです。
まず 1817181712114 の場合を考えます。これは入力例1です。5-9文字目までの5文字 18171 は2019の倍数になります。この数字をMとすると、Mは以下のようにして求めることができます。
- 5文字目から末尾までの数をAとする
A = 181712114 - 10文字目から末尾までの数をBとする
B = 2114 M = (A-B)/104となる- A-B =
181710000 - 末尾の0を消すために104で割る
- A-B =
104で割っているのはBの長さが4桁だからです。Bの桁数分だけA-Bした時に0が続きます。
こうしてもとまったMが2019の倍数であればOKです。つまり以下の式が2019の倍数である必要があります。
(A-B)/10k
10と2019は互いに素なので、A-Bが2019の倍数でなければなりません。つまりAを2019で割った余りとBを2019で割った余りが等しいとき、2019の倍数と判断できます。
AとBはいずれもSの右端から何桁かで表される数なのでSの末尾から累積和みたいな感じで計算しておけば、O(N) ですべてのA, Bの値が求まります。2019の余りが等しいものについて2つ選ぶ方法を数え上げればOKです。
// 入力
var S = Console.ReadLine();
var N = S.Length;
// 逆順の数列にしておく
var A = S.Select(c => c - '0').Reverse().ToArray();
// 10のk乗を計算しておく
var pow = new int[N];
pow[0] = 1;
for (int i = 1; i < N; i++)
{
pow[i] = pow[i - 1] * 10;
pow[i] %= 2019;
}
// 元の文字列の右からi桁の10進法での数を計算し2019の余りをとる
var X = new long[N + 1];
for (int i = 0; i < N; i++)
{
X[i + 1] = X[i] + A[i] * pow[i];
X[i + 1] %= 2019;
}
// 余りが等しいものから2つ選ぶ組み合わせの数を求める
var ans = 0L;
foreach (var g in X.GroupBy(x => x))
{
// nC2 = N*(N-1)/2
ans += (long)g.Count() * (g.Count() - 1) / 2;
}
Console.WriteLine(ans);E – Two Currencies
1 から N までの番号がつけられた N 個の都市があります。 これらの都市は M 本の鉄道路線によって結ばれています。
あなたは現在、金貨を 10100 枚、銀貨を S 枚持った状態で都市 1 にいます。
i 番目の鉄道路線は、都市 Ui と都市 Vi を双方向に結んでおり、片道の運賃は 銀貨 Ai 枚、移動にかかる時間は Bi 分です。 運賃を金貨で払うことはできません。
各都市には両替所があり、都市 i の両替所では金貨 1 枚を銀貨 Ci 枚と交換することができます。 交換には、金貨 1 枚あたり Di 分かかります。各交換所では、金貨を何枚でも交換することができます。
t=2,…,N について、都市 1 から都市 t への移動にかかる最小の時間を求めてください。電車を待つのにかかる時間は無視して構いません。
制約
- 2≤N≤50
- N−1≤M≤100
- 0≤S≤109
- 1≤Ai≤50
- 1≤Bi,Ci,Di≤109
- 1≤Ui<Vi≤N(Ui,Vi)=(Uj,Vj) なる i,j(i≠j) は存在しない
- 都市 1 から都市 t=2,…,N にいくつかの鉄道路線を使って移動することができる。
- 入力はすべて整数である。
いろいろうんうん考えた結果、制約に注目してみると、制約 1≤Ai≤50 に気が付きました。つまり運賃が最大でも50しかなく、道が最大100で同じ駅を2度以上通る必要がないのは明らかなので、所持金は最大でも2500くらいしか必要ありません。つまりSは 109 も必要がなく2500で十分になります。
ここまではコンテスト中に理解したんですが、結局どうやって解くのかわかりませんでした。
解説を見て考えた結果、拡張ダイクストラ なるダイクストラ法の亜種みたいなアルゴリズムで解けるようになります。今回の問題でいうと、頂点数Nのグラフですが頂点とその頂点における所持金を状態として合わせて管理します。
つまり、頂点とその頂点にいるときの所持金(0-2500)の組み合わせを新しい頂点として考えると、これをダイクストラ法で解くことができます。頂点数がN*2500なので 105 くらいになります。辺の数もそれくらいです。
こうするとどのようになるかというと、金貨の交換も時間Diのコストがかかる移動経路になります。なぜなら交換で所持金が変わるので別の頂点とみなし、そこに移動すると考えられるからです。これがわかれば後はダイクストラに落とし込めるようにコードを書いてやればOKです。
// 入力を頑張って受け取る
var N = sc.ReadInt();
var M = sc.ReadInt();
// 所持金は2500以下で足りるので余計な数は捨てる
var S = Math.Min(2500, sc.ReadInt());
var G = new List<(int, int, long)>[N];
for (int i = 0; i < N; i++)
{
G[i] = new List<(int, int, long)>();
}
for (int i = 0; i < M; i++)
{
var u = sc.ReadInt() - 1;
var v = sc.ReadInt() - 1;
var a = sc.ReadInt();
var b = sc.ReadLong();
G[u].Add((v, a, b));
G[v].Add((u, a, b));
}
var C = new long[N];
var D = new long[N];
for (int i = 0; i < N; i++)
{
C[i] = sc.ReadLong();
D[i] = sc.ReadLong();
}
// 元の頂点N*2501の新しい頂点のグラフを考える
var dij = new Dijkstra(N * 2501);
// 元の頂点番号と所持金から新しい頂点番号を取得する関数
static int newV(int n, int s) => 2501 * n + s;
// 元の頂点
for (int i = 0; i < N; i++)
{
// 所持金の状態
for (int j = 0; j <= 2500; j++)
{
// 移動する
foreach (var e in G[i])
{
var next = e.Item1;
var cost = e.Item2; // a
var time = e.Item3; // b
if (j - cost >= 0)
{
// 所持金が足りている場合のみ移動可能
var nowv = newV(i, j);
var nextv = newV(next, j - cost);
dij.Add(nowv, nextv, time);
}
}
{
// 金貨を交換する(2500以下にする)
var s = (int)Math.Min(2500, j + C[i]);
var nowv = newV(i, j);
var nextv = newV(i, s);
dij.Add(nowv, nextv, D[i]);
}
}
}
// 開始位置からの最短経路をダイクストラで求める
var start = newV(0, S);
var dist = dij.Calc(start);
// 元の頂点番号に到達する最短経路を計算する
for (int i = 1; i < N; i++)
{
var ans = long.MaxValue;
for (int j = 0; j <= 2500; j++)
{
var index = newV(i, j);
ans = Math.Min(ans, dist[index]);
}
Console.WriteLine(ans);
}入力を受け取るのが大変ですが頑張ります。Sは制約では 109 までありますが、そんなにいらないので2500枚以下にしておきます。これは金貨を交換するときも同様です。
あとは所持金が道の移動コストを上回っているときに限り、その道をつなぎます。金貨の交換は最大2500枚に収まるように交換してその時の時間Diを移動コストとして移動経路とします。このとき(i, 2500) -> (i, 2500)の自己ループの辺が与えられますが、ダイクストラでは問題ないです。
static int newV(int n, int s) => 2501 * n + s; は元の頂点番号と所持金から新しい頂点番号を求める関数です。1頂点あたり0-2500の2501パターンあるのでそれに気を付けます。
あとはダイクストラを解くだけでした。
ダイクストラのコードは長くなるので省略してます。以下の記事を参考にしてください。
[C#] ダイクストラ法で最短経路を見つけるための実装方法 │ Web備忘録
今回は計算した結果すべて必要なのでそれを返すような関数にして使ってます。
F問題は見てませんが赤Diffというえげつない難易度だったみたいです。
以上。
