AtCoder Beginner Contest 161 に C# で参加した記録
AtCoder Beginner Contest 161 – AtCoder
ABC161 にC#で参加しました。結果はABCDの滑り込みで4問ACでした。
パフォーマンスは残念な緑になって、レートは減少しました。次回も同じようなパフォーマンスだと水色から陥落します。
敗因はC問題の数学アレルギーと、D問題での迷走でした。結果はひどかったですが、何とかコンテスト内でDを通せたのはよかったです。
以下、振り返ります。
A – ABC Swap
3 つの箱 A,B,C があります。
それぞれの箱には、整数が 1 つ入っています。現在、箱 A,B,C に入っている整数はそれぞれ X,Y,Z です。
これらの箱に対して以下の操作を順に行った後の、それぞれの箱に入っている整数を求めてください。
- 箱 A と箱 B の中身を入れ替える
- 箱 A と箱 C の中身を入れ替える
値のスワップ処理が書けますかという問題です。C#だと今のところ一時変数に入れて交換していく方法しか現行のジャッジ環境では不可能だと思います。
とはいえ入れ替え操作が固定なので、スワップ操作すら不要ですが。
// A と B をスワップ
var tmp = X;
X = Y;
Y = tmp;
// A と C をスワップ
tmp = X;
X = Z;
Z = tmp;
Console.WriteLine(X + " " + Y + " "+ Z);B – Popular Vote
N 種類の商品に対して人気投票を行いました。商品 i は Ai 票を得ています。
この中から人気商品 M 個を選びます。ただし、得票数が総投票数の 1/4M 未満であるような商品は選べません。
人気商品 M 個を選べるなら Yes、選べないなら No を出力してください。
この問題も書いてある通りに処理すればよいです。
// 得票数の多い順にソート
Array.Sort(A);
Array.Reverse(A);
// 最小の得票数を計算しておく(1/4M)
var min = (double)A.Sum() / (4.0 * M);
// 上位M個がすべて最小の得票数以上であればYes
if (A.Take(M).Count(a => a < min) > 0)
{
Console.WriteLine("No");
}
else
{
Console.WriteLine("Yes");
}C – Replacing Integer
青木君は任意の整数 x に対し、以下の操作を行うことができます。
操作: x を x と K の差の絶対値で置き換える。
整数 N の初期値が与えられます。この整数に上記の操作を 0 回以上好きな回数行った時にとりうる N の最小値を求めてください。
制約
- 0≤N≤1018
- 1≤K≤1018
- 入力は全て整数
3WAしました。冷静になるとWAも減らせそうですが、やっぱり算数脳が弱すぎるのでやらかしてしまいます。
この問題は制約が大きいので愚直にシミュレートなりをすることはできず、計算式一発で答えを求めなければいけません。
いろいろ考えた結果、KがNの倍数だと操作を繰り返すことで0にできます。そうでない場合は0にできません。何度繰り返しても差が生まれます。
ということで、min(abs(k-N%k), N%K) が答えになります。
N = N % K;
var ans = Math.Min(N, Math.Abs(N - K));
Console.WriteLine(ans);この手の問題はACできない、ということはないのですが、WAと時間が嵩んで結果、パフォーマンスが悪くなりがちです。
D – Lunlun Number
正の整数 X が以下の条件を満たすとき、 X はルンルン数であると言います。
X を(leading zeroなしで)十進数表記した際に、隣り合うどの 2 つの桁の値についても、差の絶対値が 1 以下例えば、 1234 , 1 , 334 などはルンルン数ですが、 31415 , 119 , 13579 などはルンルン数ではありません。
正の整数 K が与えられます。小さい方から K 番目のルンルン数を求めてください。
制約
- 1≤K≤105
- 入力はすべて整数である。
D問題は冷静になって考えるとそこまで難しくはなかったです。
私の実装方針は以下の通りです。
- ルンルン数のリストSを作ります。初期値を1桁のルンルン数1..9で埋めておきます。
- KがSの個数以下であれば答えを出力して終了します。
- KがSの個数より大きければ次の桁数のルンルン数のリスト昇順で作成して、
K-=Sの個数します。 - 2に戻ります。
ルンルン数のリストSには同じ桁のルンルン数が昇順で入っているようにします。ここから次の桁のルンルン数を作るには
- Sから取り出した値の
aの1の位をxとする。 a*10 + x-1,a*10 + x,a*10 + x+1が次の桁のルンルン数になる。
とします。x-1, x+1 の部分は0の場合と9の場合には気を付ける必要があります。
例えば [1,2,3,4,5,6,7,8,9] から2桁のルンルン数を作ると
[10+(1-1), 10+1, 10+(1+1), 20+(2-1), 20+2, 20+(2+1) ... 90+(9-1), 90+9]
みたいになります。これで昇順に並んでいるので、見つかった数を管理しておけばK番目が見つかります。
解説PDFを見るとキューに突っ込んで行くのがいいみたいです。確かに取り出した値から生成すれば必ず順序通りに取り出せますね。
今回は最大ケースが入力例においてあって、これがTLEしなければ基本的には大丈夫だとわかります。私の場合は心配だったのでソートまでしてましたがもちろん不要でした。
// 1桁のルンルン数リスト
var list = new List<long>() { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
while (true)
{
if (list.Count() >= K)
{
// 見つかった
Console.WriteLine(list[K - 1]);
return;
}
else
{
K -= list.Count();
// 見つからなかったので次の桁のルンルン数を作る
var nextList = new List<long>();
foreach (var now in list)
{
// ルンルン数の1桁目
var d = now % 10;
var next = now * 10;
// 直前の桁の値-1が1桁目に来る場合
if (d > 0)
{
nextList.Add(next + d - 1);
}
// 直前の桁の値が1桁目に来る場合
nextList.Add(next + d);
// 直前の桁の値+1が1桁目に来る場合
if (d != 9)
{
nextList.Add(next + d + 1);
}
}
// ルンルン数のリストを更新
list = nextList;
}
}緑Difficultyの問題でした。終了3分前くらいに滑り込みACでした。危なかったです。
以上。
