AtCoder Beginner Contest 158 に参加した記録
AtCoder Beginner Contest 158 – AtCoder
ABC158 に参加しました。結果はABCDの4問ACでした。
今回はD問題が15分ちょっとで解けたので簡単でしたたぶん。最近はE問題に結構時間を使えるのですがなかなか解けないです。
ですが、なんだかんだで順位がいつもよりよくて結構なパフォーマンスが出てよかったです。まさかの青パフォでした。unrated疑惑のおかげかもしれないですがうれしいですね。E問題解けずに青パフォはラッキーだと思います。
次回D問題まですんなり解ければ水色になれそうです。
では問題を振り返ります。
A – Station and Bus
AtCoder 市には 3 つの駅があり、1,2,3 の番号がつけられています。
これらの駅は、それぞれ鉄道会社A, Bのいずれかが管理しています。管理状況は長さ 3 の文字列 S で表され、駅 i は Si が A のとき鉄道会社 A が、B のとき鉄道会社 B が管理しています。
鉄道会社 A が管理している駅と、鉄道会社 B が管理している駅の間には、交通の便のためにバスを運行することになりました。
実際にバスが運行することになる駅の組み合わせが存在するかどうかを判定してください。
問題文がわかりにくかったのですが、ようは文字列の中身にAとBの両方が含まれていなければ 'No' そうでなければ 'Yes' です。それだけです。
if (S.All(c => c == 'B') || S.All(c => c == 'A'))
{
Console.WriteLine("No");
}
else
{
Console.WriteLine("Yes");
}B – Count Balls
高橋君は青と赤の 2 色のボールを持っており、これらを一列に並べようとしています。
初め、列にボールはありません。
根気のある高橋君は、次の操作を 10100 回繰り返します。
列の末尾に、A 個の青いボールを加える。その後、列の末尾に B 個の赤いボールを加える。こうしてできる列の先頭から N 個のボールのうち、青いボールの個数はいくつでしょうか。
制約
- 1≤N≤1018
- A,B≥0
- 0<A+B≤1018
- 入力は全て整数である
B問題なのに制約に注意しないとACできない問題なのに注意です。与えられた操作を10100 回繰り返すことは不可能なので、計算によって求める必要があります。
A=3, B=4のとき、青をo赤をxにすると1回の操作で oooxxxx みたいなボールが加わることがわかります。操作後のボールから先頭N個を取り出すとき、N / (A+B) * A だけあることがわかります。さらに、min(N % (A+B), A) だけ余分に追加して答えになります。
入力例1の場合だと oooxxxx oooxxxx ... みたいになって、8/(3+4)*3 = 3 と min(1, 3) = 1 を足して4が答えになります。
実装例です。
var ab = A + B;
long ans = (N / ab) * A + Math.Min(A, N % ab);;
Console.WriteLine(ans);C – Tax Increase
消費税率が 8 %のとき A 円、10 ％のとき B 円の消費税が課されるような商品の税抜き価格を求めてください。
ただし、税抜き価格は正の整数でなければならないものとし、消費税の計算において小数点以下は切り捨てて計算するものとします。
条件を満たす税抜き価格が複数存在する場合は最も小さい金額を出力してください。また、条件を満たす税抜き価格が存在しない場合は -1 と出力してください。
制約
- 1≤A≤B≤100
- A,B は整数である
最初、AとBは税込み金額だと表ましたがよく問題を読むと消費税額のことでした。
実装は愚直に全探索でOKです。答えになりうる値を小さいほうから試していって見つかったら出力します。
A, Bの範囲が100までなので、10% 消費税率を考えると 10000 くらい試せばOKだと思います。大盤振る舞いで 100000 くらいループしてACしました。
for (double x = 1; x <= 100000; x++)
{
var y10 = (int)(x * 0.1);
var y8 = (int)(x * 0.08);
if (y8 == A && y10 == B)
{
Console.WriteLine((int)x);
return;
}
}
Console.WriteLine(-1);D – String Formation
高橋君は、英小文字から成る文字列 S を持っています。
この S から始めて、ある与えられた手順に従って文字列を作ることにしました。
手順は Q 回の操作から成ります。操作 i(1≤i≤Q) では、まず整数 Ti が与えられます。
- Ti=1 のとき : 文字列 S の前後を反転する。
- Ti=2 のとき : 追加で整数 Fi と英小文字 i が与えられる。
- Fi=1 のとき : 文字列 S の先頭に Ci を追加する。
- Fi=2 のとき : 文字列 S の末尾に Ci を追加する。
高橋君のために、手順の後に最終的にできる文字列を求めてあげてください。
制約
- 1≤|S|≤105
- S は英小文字から成る
- 1≤Q≤2×105
- Ti=1 または 2
- Fi=1 または 2
- Ci は英小文字である
D問題にしては珍しくあんまりアルゴリズムアルゴリズムしていませんでした。PASTの問題みたいなイメージを持ちました。
解法自体はすぐに思い浮かんで、deque (両端キュー) みたいな頭にもお尻にも O(1) で要素を追加できるデータ構造を用いて、反転する処理は実際には行わず、反転している状態かどうかを管理すればよさそうです。
反転している状態でデータを追加する場合は、先頭と末尾を逆にして追加すればよいです。そうすればデータの反転も O(1) でできるので、全体で計算量 O(N) くらいのイメージで解けそうです。
C# には deque はないので、LinkedList を使いました。
var list = new LinkedList<char>();
for (int i = 0; i < S.Length; i++)
{
list.AddLast(S[i]);
}
var Q = sc.ReadInt();
var rev = false;
for (int i = 0; i < Q; i++)
{
var T = sc.ReadInt();
if (T == 1)
{
// 反転
rev = !rev;
}
else
{
var F = sc.ReadInt();
var C = sc.ReadChar();
// 反転状態だと 1->0, 2->1 にして追加先を変更する
if (rev) F = (F + 1) % 2;
if (F == 1)
{
list.AddFirst(C);
}
else
{
list.AddLast(C);
}
}
}
// 反転状態の場合は後ろから出力するのを忘れない
if (rev)
{
foreach (var item in list.Reverse())
{
Console.Write(item);
}
}
else
{
foreach (var item in list)
{
Console.Write(item);
}
}
Console.WriteLine();E問題はいろいろ考えたんですが難しかったです。最近はE問題がかなりの壁になています。1時間以上余しても解けないので精進不足でしょうか。
頑張ります。
以上。
