AtCoder Beginner Contest 171 に C# で参加した記録
AtCoder Beginner Contest 171 – AtCoder
ABC171 にC#で参加しました。
結果はABCDEの5問ACでレート微増でした。20分弱1WAで5完したんですが、F問題が1時間かけても解けませんでした。いいところまではいったんですが。。。
今回はDが普段のC問題並に簡単で、E問題はザ・典型という感じで簡単でした。鬼門はC問題で、多くの人がWAを重ねてました。私の場合はyukicoderで同じ問題を解いたことがあったので何とかなりました。
今回の問題は、C,D,Eが茶Diffで全体的に易しく、Fだけ変わらず青Diffというような感じでした。レート増なのでまあ良しとしましょう！
ということで振り返ります。
A – αlphabet
英大文字か英小文字のいずれか 1 文字 α が入力されます。α が英大文字なら A、英小文字なら a と出力してください。
var C = sc.ReadStr()[0];
if ('A' <= C && C <= 'Z')
{
Console.WriteLine('A');
}
else
{
Console.WriteLine('a');
}大文字小文字の判定に文字コードでの比較を使用しています。知らなかったんですが、大文字小文字を判定する char.IsUpper(), char.IsLower() という関数がC#にもあるみたいですね。
B – Mix Juice
ある店で N 種類の果物、果物 1,…,N が売られており、それぞれの価格は一個あたり p1,…,pN 円です。
この店で K 種類の果物を一個ずつ買うとき、それらの合計価格として考えられる最小の金額を求めてください。
安いほうからK個選ぶのが最小になるパターンです。なので価格を昇順ソートして先頭からK個選んで合計すればよいです。
var N = sc.ReadInt();
var K = sc.ReadInt();
var A = sc.ReadIntArray(N);
// ソート
Array.Sort(A);
// 先頭K個を合計する
var ans = A.Take(K).Sum();
Console.WriteLine(ans);こういう時、Linqワンライナーでかけるのが微妙に便利でうれしいです。
C – One Quadrillion and One Dalmatians
C – One Quadrillion and One Dalmatians
ロジャーは、彼のもとに突如現れた 1000000000000001 匹の犬をすべて飼うことを決意しました。犬たちにはもともと 1 から 1000000000000001 までの番号がふられていましたが、ロジャーは彼らに以下のルールで名前を授けました。
- 1,2,⋯,26 番の番号がついた犬はその順に a,b,…,z と命名されます。
- 27,28,29,⋯,701,702 番の番号がついた犬はその順に aa,ab,ac,…,zy,zz と命名されます。
- 703,704,705,⋯,18277,18278 番の番号がついた犬はその順に aaa,aab,aac,…,zzy,zzz と命名されます。
- 18279,18280,18281,⋯,475253,475254 番の番号がついた犬はその順に aaaa,aaab,aaac,…,zzzy,zzzz と命名されます。
- 475255,475256,⋯ 番の番号がついた犬はその順に aaaaa,aaaab,… と命名されます。
- (以下省略)
つまり、ロジャーが授けた名前を番号順に並べると:a,b,…,z,aa,ab,…,az,ba,bb,…,bz,…,za,zb,…,zz,aaa,aab,…,aaz,aba,abb,…,abz,…,zzz,aaaa,… のようになります。
ロジャーはあなたに問題を出しました。
「番号 N の犬の名前を答えよ。」
制約
- N は整数
- 1≤N≤1000000000000001
鬼門となったC問題です。わりと問題自体はわかりやすく、なんとなく26進数っぽくすればいいように見えます。
が、単純に26進数にして文字を割り当てるとうまくいきません。例えば27とか703の時におかしくなります。
解法はライターのツイートで詳しく解説されています。
アライグマ「ABC171のB,C問題の原案だったのだ。C問題はだいたい26進法っぽい感じだけど、ちょっと違うのをどうするかで2通りの考え方があるのだ。1つは、答えの文字数を求めて、普通に26進法に変換する方法なのだ」 pic.twitter.com/nCohvkBbMS
— 競技プログラミングをするフレンズ (@kyopro_friends) June 21, 2020
26進数で計算する過程で-1を挟む方法でうまくいきます。
var N = sc.ReadLong();
var ans = "";
while (N > 0)
{
N--; // 0を特別扱いするために
ans += (char)('a' + N % 26);
N /= 26;
}
ans = new string(ans.Reverse().ToArray());
Console.WriteLine(ans);先に桁数を決めて、26進数で計算する方法だと以下の通りです。
// 桁数と、その桁の何番目の文字列かを計算しておく
var N = sc.ReadLong();
var p = 1L;
var count = 1;
while (p * 26 < N)
{
p *= 26;
N -= p;
count++;
}
N--; // 2桁の場合だとaaが0番目なので-1しておく
// 26進数でN番目の文字列を求める
var a = new char[count];
for (int i = count - 1; i >= 0; i--)
{
a[i] = 'a';
if (N == 0) continue;
a[i] += (char)(N % 26);
N /= 26;
}
var ans = new string(a);
Console.WriteLine(ans);これは難しかったです。が、実はこの問題解いたことがあって、それが以下の問題です。
Nが0始まりかどうかの違いだけでまったく一緒です。これを解いていたのですが、さっぱり解法が頭から抜けてました。復習します。。。
D – Replacing
あなたは、N 個の正整数 A1,A2,⋯,AN からなる数列 A を持っています。
あなたは、これから以下の操作を Q 回、続けて行います。
- i 回目の操作では、値が Bi である要素すべてを Ci に置き換えます。
すべての i (1≤i≤Q) に対して、i 回目の操作が行われた後の数列 A のすべての要素の和、Si を求めてください。制約
- 入力は全て整数
- 1≤N,Q,Ai,Bi,Ci≤105
- Bi≠Ci
C問題と打って変わってとっつきやすい問題です。
Q回の操作で愚直にやるとTLEしますが、あらかじめAに含まれる数の個数を1~105まで数え上げておけば、操作後の合計は簡単に求まります。
例えば 1 を 3 に帰るとき、1が5個あるとすると、5*(3-1) だけ要素の和が増えます。1つ書き換わると2だけ増え、それが5個あるので5倍だけ和に影響します。あらかじめ全要素の和を求めておけば各操作後における状態を O(1) で求めることができます。
もちろん小さい数に書き換えられると和が小さくなります。
あとは操作後に個数の更新を忘れないようにすればOKです。
var N = sc.ReadInt();
var A = sc.ReadLongArray(N);
// あらかじめ個数を数えておく
var count = new int[(int)1e5 + 1];
foreach (var a in A)
{
count[a]++;
}
// 初期状態の総和を求める
var ans = A.Sum();
var Q = sc.ReadInt();
while (Q-- > 0)
{
// b を c に更新する
var b = sc.ReadLong();
var c = sc.ReadLong();
// 差*個数で状態を更新する
var d = c - b;
ans += count[b] * d;
Console.WriteLine(ans);
// bの個数が0になってその分bの個数が増える
count[c] += count[b];
count[b] = 0;
}E – Red Scarf
猫のすぬけくんが N(偶数) 匹います。各すぬけくんには 1,2,…,N の番号が振られています。
各すぬけくんは首に赤いスカーフを巻いており、スカーフにはそのすぬけくんが一番好きな非負整数が 1 つ書き込まれています。
すぬけくんたちは最近、整数の xor（排他的論理和）と呼ばれる演算を覚えました。
xor とは早速この演算を使いたくなったすぬけくんたちは、自分以外のすぬけくんのスカーフに書かれた整数の xor を計算することにしました。
番号 i が振られたすぬけくんが計算した、自分以外のすぬけくんのスカーフに書かれた整数の xor が ai であることが分かっています。 この情報を元に、各すぬけくんのスカーフに書かれた整数を特定してください。
制約
- 入力はすべて整数である
- 2≤N≤200000
- N は偶数
- 0≤ai≤109
- 与えられた情報と整合するようなスカーフ上の整数の組合せが存在する
XORを使う問題の中でも典型的な知識を問う問題だと思います。
この問題で使うXORの知識は以下の通りです。
a xor a = 0a xor 0 = aa xor b = b xor aa xor b xor a = b
ようは同じ数をXORすると0になり、0とXORするとその数自身になり、XORは計算順序を入れ替えてもよいということです。また、このことから同じ数を偶数回XORすると0になり、奇数回XORするとその数自身になります。
あと、aとbをXORした数からaを求めたい場合はbでXORをすると取り出せます。
今回の問題ではスカーフに書かれた非負整数をB(B0, B1, B2, B3)とすると、入力で与えられる整数列Aは以下の計算を行った結果となります。
A0 = B1 xor B2 xor B3
A1 = B0 xor B2 xor B3
A2 = B0 xor B1 xor B3
A3 = B0 xor B1 xor B2例えば、A0には0番目以外の猫のスカーフに書かれた整数のXORとなっています。
今回はBのすべての要素を求める必要があります。今、B0について注目すると、
A1 xor A2 xor A3
= B0 xor B0 xor B0 xor B1 xor B1 xor B2 xor B2 xor B3 xor B3
= B0となります。計算順序を入れ替えて、B1, B2, B3 についてはそれぞれ偶数回XORされているので全部0になります。B0は奇数回XORされているのでそのまま残り、0とXORしたらそのまま残るので結果B0だけが求まります。
B1, B2, B3 についても同様に求まります。
ということで、i番目猫のスカーフに書かれた整数はAi以外の数のXORで求まることがわかりました。あとは高速に自分以外のAについてXORできればそれが答えになります。
N個のAについてXORを全部まとめて計算しておき、そこからAiについてさらにXORするとAiのXORだけが取り除かれたような状態の計算結果が得られます。
ということで実装です。
var N = sc.ReadInt();
var A = sc.ReadLongArray(N);
// A全部のXORを計算しておく
var xorSum = 0L;
for (int i = 0; i < N; i++)
{
xorSum ^= A[i];
}
for (int i = 0; i < N; i++)
{
var ans = xorSum ^ A[i];
Console.WriteLine(ans);
}方針が決まれば実装は簡単です。5分くらいで解けました。
実は私の解法はこのやり方と違って、左右から累積XORを計算しておき、自分を挟む左右の区間の累積XORをXORして答えを求めました。
XORは掛け算に対する割り算、足し算に対する引き算みたいな逆演算?みたいなことができるので、全部計算してからいらない値を消すみたいなことができるのを忘れてました。
これが累積GCDとかだと全部計算しておくみたいなことはできずに左右に分けて計算する必要があります。その問題が最初に頭に浮かんだためそんな感じの解法になりました。
一応参考までに貼っておきます。XORではなくGCDすれば解けます。
F – Strivore
解けませんでした。
S+K文字の文字列について、部分列にSを含むものの個数になることはわかりました。また、愚直なDPでその個数を求めることもできました。
その結果をみてSは文字数のみ依存し、中身は関係ないこともわかりました。
あとは計算過程をうまく処理してやればいけそうだったんですが、無理でした。数え上げは厳しいです。。。
以上。
