ABC171解説

ABC171の解説と感想を書きます。使用言語はC++です。

A αlphabet

atcoder.jp

概要

  • 条件分岐(if文、else文)を用いる
  • char型の文字は大小比較ができる

実装

通常、競技プログラミングの問題を解く際は、「入力を受け取る→処理をする→出力する」の3ステップに分けて、それぞれのステップについて慎重にコードを書いていくのが確実だと思います。ただし、今回の問題の場合は、処理をしながら出力する方が楽なので、「入力を受け取る→処理をしながら出力する」の2ステップで説明します。

入力を受け取る

 入力と制約を確認すると、「入力は、αで与えられる。αは英大文字または英小文字。」と書いてあります。
英大文字や英小文字などの文字は、char型の変数を用いることで、受け取りができます。
*1

下のソースコードでは、char型の変数cを宣言し、入力を受け取っています。

	char c;
	cin >> c;
処理をする

cに入っている文字が大文字ならば答えとして"A"を出力し、小文字ならば"a"を出力するコードを書きたいです。
これは、if文を使って次のように書くことができます。
*2

	if (cが大文字) { cout << "A" << endl; }
	if (cが小文字) { cout << "a" << endl; }

ところで、「alphaが小文字」は、別の言い方をすると、
「cが大文字ではない」になります。
そこで、else文を使うことで、次のようにコードを書き換えることができます。

	if (cが大文字) { cout << "A" << endl; }
	else { cout << "a" << endl; }

さて、「cが大文字」はどのような条件式で書くことができるでしょうか？
一番思いつきやすいのは、すべての場合を書き下す方法だと思います。

	if (c == 'A') { cout << "A" << endl; }
	else if (c == 'B') { cout << "A" << endl; }
	else if (c == 'C') { cout << "A"<< endl; }
	・・・
	else if (c == 'Z') { cout << "A" << endl; }
	else { cout << 'a' << endl; }

この方法でも正解できますが、コードが長くなってしまうので、解くのに時間がかかります。
また、不正解だった時、間違っている箇所を見つけるのが難しくなってしまいます。
もっと良い方法はないのでしょうか？

実は、char型に代入される文字の性質を用いれば、上のコードを簡潔に書き直すことができます。
コンピューターの中では、char型に代入される文字は-128以上127以下の整数と対応しています。それを示したのが以下の表です。(負の数との対応については省略します。)*3

整数 文字
0～31 (制御文字)
32～47 記号('*,'+'など)
48～57 数字('0'～'9')
59～64 記号('=','?'など)
65～90 英大文字('A'～'Z')
91～96 記号('^','_'など)
97～122 英小文字('a'～'z')
123～126 記号('~'など)
127 (制御文字)

*4
詳しい対応関係を知りたい方は、「ASCII」で検索してみてください。wikipedia:ASCII

このように、char型の文字は整数と対応しているので、通常の整数と同じように、足し算や引き算、大小比較をすることができます。*5
今回の場合は、大小比較をすることで、cが大文字であるかを簡単に確かめることができます。
具体的には、
「alphaが大文字→cに対応する整数(65～90)は'Z'に対応する整数(90)以下である。」
「alphaが小文字→cに対応する整数(97～122)は'Z'に対応する整数(90)より大きい。」
という関係性があるので、次のようなコードに書き直すことができます。

	if (c <= 'Z') { cout << "A" << endl; }
	else { cout << "a" << endl; }
まとめ

まとめると、以下のコードを提出することで、この問題に正解できます。

#include <bits/stdc++.h>
using namespace std;

int main() {
	char c;
	cin >> c;

	if (c <= 'Z') { cout << "A" << endl; }
	else { cout << "a" << endl; }
}

類題

A - Next Alphabet　char型の文字に対する「足し算」を使うことで、簡潔に解けます。

B Mix Juice

atcoder.jp

概要

  • 配列を用いて入力を受け取る。
  • 合計金額を最小にする→安いものから順番に買う。
  • sort関数を用いることで、安いものから順番に並べることができる。

考え方

N個の果物からK個の果物を買って、合計価格を最も安くするためには、安い果物から順番に果物を買っていけばよいです。
サンプルで見てみましょう。

入力例1
5 3
50 100 80 120 80

この場合、N=5,K=3,p[1]=50,p[2]=100,p[3]=80,p[4]=120,p[5]=80です。
50円,100円,80円,120円,80円の5個の果物があり、そのうち3個を買ったときの合計価格は、最も安くていくらになりますか？という問題です。
プログラミングの問題だと意識せず、算数の問題だと思って解くとわかりやすいかもしれません。
安い順番に果物を並べると、50円,80円,80円,100円,120円になるので、合計価格の最小は、50+80+80=210円です。

そこで、この流れに沿って、以下の順番にコードを書いていきましょう。

  1. 入力を受け取る。
  2. p[1]からp[N]を小さい(安い)順番に並べなおす。
  3. 安いものから順にK個足し合わせる。
  4. 答えを出力する。

実装

B問題の実装には、for文や配列など、A問題の実装よりも高度な知識が必要になります。

入力を受け取る。

入力は、整数N,Kと、整数列p[1],...,p[N]で与えられます。
まず、int型の変数N,Kを宣言し、受け取ります。

int N, K;
cin >> N >> K;

続いて、整数列p[1]…p[N]は配列を用いて受け取ります。
配列の添え字はp[0]から始まるので、p[1]からp[N]まですべての入力を受け取るためには、最低でもN+1個の要素を確保する必要があります。

以下のコードでは、vectorを用いて、要素数N+1個の配列変数を宣言し、for文を用いて入力を受け取っています。
*6

vector<int> p(N + 1);
for (int i = 1; i <= N; i++) {
	cin >> p[i];
}
p[1]からp[N]を小さい(安い)順番に並べなおす。

配列の順番を小さい順に並べなおすには、sort関数を使うのがすごく便利です。
*7

sort(first,last)//[first,last)の範囲を小さい順に並べる(ソートする)。

今回は、一番前の次の位置(p[1])から、一番後ろまでをソートしたいので、

sort(++p.begin(), p.end())//++を前につけると次の位置に移動する。

とします。
細かい意味はよくわからないかもしれませんが、そういうものだと思ってください。
私もよくわかっていませんが、そういうものだと思っているうちにいつのまにか使いこなせていたりします。

安いものから順にK個足し合わせる。

今、p[1]からp[N]まで安い順に並んでいるので、p[1]からp[K]までを順番に足し合わせればよいです。
まず、答えを格納する変数ansを宣言し、0に初期化します。
続いて、for文を用いて、ansにp[1]からp[K]を順番に足し合わせていきます。

int ans = 0;
for (int i = 1; i <= K; i++) {
	ans += p[i];
}
出力する。

ansを出力します。

cout << ans << endl;
まとめ

まとめると、以下のコードを提出することで、この問題に正解できます。

#include <bits/stdc++.h>
using namespace std;

int main() {
	int N, K;
	cin >> N >> K;
	vector<int> p(N + 1);
	for (int i = 1; i <= N; i++) {
		cin >> p[i];
	}

	sort(++p.begin(), p.end());

	ll ans = 0;
	for (int i = 1; i <= K; i++) {
		ans += p[i];
	}

	cout << ans << endl;
}

C One Quadrillion and One Dalmatians

概要

  • まずは文字列の長さを求めて、それから具体的な答えを求める。

考え方、実装

幅優先探索を使うとO(N)でシンプルに実装することができます。(例:D - Lunlun Number)
しかし、今の問題でその方法をするとTLEしてしまうので、Nの値から直接答えにアタックする必要があります。
今回は、考え方と実装を同時に説明していきます。

入力を受け取る。
long long N;
cin >> N;
犬の名前の長さを求める。

まず、犬の名前は短い順に並んでいるので、N番目の犬の名前の長さLが気になります。
例えばN=27のときL=2、N=123456789のときL=6です。

犬の番号 名前の長さ
1～26 1
26+1～26*26+26 2
26*26+1～26*26*26+26*26+1 3
... ...

つまり、

  1. N<=26のとき、L=1で終了
  2. Nから26を引く。
  3. N<=26*26のとき、L=2で終了
  4. Nから26*26を引く。

・・・
のような操作を行えばよいです。
前もって、26の累乗を求める再帰関数を書いておき、while文を用いて実装するのが簡単だと思います。

long long power_26(int a) {
	if (a == 0) { return 1; }
	return 26 * power_26(a - 1);
}

int L = 1;
while (N > power_26(L)) {
	N -= power_26(L);
	L++;
}
犬の名前を求める。

さて、長さLの単語のうち、辞書式でN番目の単語を求める問題を解きましょう。
ところで、「K桁の整数Mが与えられたとき、その各桁の値d[1]…d[M]を上から順に求めよ」という問題には、次のような実装を行いました。

vector<ll> ans(M);
for (int i = 0; i < K; i++){
	d[K - 1 - i] = M % 10;
	M /= 10;
}

今回の問題は、Nを10進法(0...9)の代わりに26進法('a'…'z')だと思って、同じことをやればよいです。
ただし、1番目の単語が"aa…a"(="00...00")なので、Nから1を引く処理が必要です。

N--;
vector<char> ans(L);
for (int i = 0; i < L; i++){
	ans[L - 1 - i] = N % 26 + 'a';//'a'を足すことで、0...25を'a'...'z'になおす。
	N /= 26;
}
出力する。
for (int i = 0; i < L; i++) cout << ans[i];
cout << endl;
まとめ

まとめると、以下のコードを提出することで、この問題に正解できます。
Submission #14616506 - AtCoder Beginner Contest 171

D Replacing

atcoder.jp

概要

  • クエリの問題は、データの持ち方を考える。

考え方

この問題はクエリを順番に処理していくタイプの問題です。
処理の流れは次のようになると思います。

  1. 入力(今回はN,Ai)を読み取り、データを初期設定する。
  2. クエリを読み取り、データを更新する。
  3. クエリの答えを計算して出力する。
  4. ２と３を繰り返す。

ここで、Q\leq 10^5ですから、各クエリの処理は高速に行わなければなりません。
そのためには、「簡単に更新できるデータを保持する」ことがカギになります。

たとえば、A_1\cdots A_nの各値をいちいち更新していくことを考えましょう。
このとき、一回のクエリで更新するデータは最大N個なので、時間もO(N)かかります。
全体ではO(QN)なので、間に合いません。
そこで、より効率的な形でデータを保持する必要があります。

今の問題だと、各クエリでAの要素の和を求めたいので、そのために必要なデータは何か考えます。
j番目のクエリで、要素の和は(A_i=B_jをみたすiの個数)*(C_j-B_j)だけ変化します。
そこで、

  • count_x:A_i=xであるようなxの個数(x\leqq100000)
  • S:現在のAの要素の和

をデータとして持っておけば、一回のクエリで更新するデータはcount_{B_j},count_{C_j},Sの3個なので、高速に実行できるとわかります。

実装

入力を受け取り、初期値を設定する。

入力自体はint型でおさまりますが、和を計算するとオーバーフローの危険性があるので、long long型を用います。
*8

int N;//Nの受け取り
cin >> N;
vector<long long> A(N + 1);//A[i]の受け取り
for (int i = 1; i <= N; i++)cin >> A[i];

int M = 100000;//A[i]の上限値は100000
vector<long long> count(M + 1, 0);//count[x]の初期設定
for (int i = 1; i <= N; i++)count[A[i]]++;

long long S = 0;//Sの初期設定
for (int i = 1; i <= N; i++)S += A[i];
クエリの処理

各クエリで入力b,cを受け取ったとき、更新する値はcount_b,count_c,Sです。

int Q;
cin >> Q;
for (int q = 1; q <= Q; q++) {
	long long b, c;
	cin >> b >> c;

	long long memo = count[b];//更新前のcount[b]の値を保存
	count[b] = 0;
	count[c] += memo;
	S += memo * (c - b);
	cout << S << endl;
}
まとめ

まとめると、以下のコードを提出することで、この問題に正解できます。
Submission #14629167 - AtCoder Beginner Contest 171


E Red Scarf

概要

  • xorは怖くない。
  • a xor a=0を用いて式変形していく。

考え方

排他的論理和(xor)に関する問題はAtCoderでよく出題されます。なじみのない演算なので面食らうかもしれませんが、慣れれば問題ないです。
「xor 競技プログラミング」で検索すれば、競技プログラミングで使えるxorの技がいくつかでてくるので、問題を解きながら覚えていきたいところです(私もまだまだです)。

次の性質はxorの問題を解くときにしばしば用います。(上2つは当たり前ですが、3つ目はxor独自の性質だと思います。)

今回の問題も、これらの性質を用いて解いていきます。

求めたい整数の値をx_1,x_2,\cdots,x_Nとおきましょう。
いま、各iに対し、
a_i=x_1 \ xor \ x_2 \ xor \cdots x_{i-1} \ xor \ x_{i+1} \ xor \cdots x_N
であることがわかっています。
これを簡単な形に書き直したいです。
そこですべての要素をxorして、S=x_1 \ xor \ x_2 xor \cdots xor \ x_Nとおくと、
a_i=(x_1 \ xor \ x_2 \ xor \cdots x_{i-1} \ xor \ x_i \ xor \ x_{i+1} \ xor \cdots x_N) xor \ x_i =S \ xor \ x_{i}
になります。(累積和をxorバージョンに書き換えたものだと思えばわかりやすいと思います。)

あとは、Sの値を求めれば十分です。
あまり頭を働かせず、とりあえずすべてのa_iのxorをとってみます。
a_1 xor a_2 xor \cdots xor a_N =(S xor x_1) xor \cdots xor (S xor x_N)=x_1 xor \cdots x_N =S
N個の Sがみごとに相殺して、1つだけ残りました！([tex N]が偶数であることを用いています。)

よって、以下の手順で実装を行えば、この問題を解くことができます。

  1. 入力を受け取る
  2. S =a_1 xor a_2 xor \cdots xor a_Nを計算する。
  3. 各 iに対し、 S xor a_iを計算する。

F Strivore

概要

  • みょーん

*1:M - 1.12.文字列と文字

*2:G - 1.06.if文・比較演算子・論理演算子

*3:処理系によっては、char型に対応する整数の範囲が「0以上255以下」となることもあるようです。AtCoderの環境では「-128以上127以下」として問題ありませんが、いずれにせよ負の数との対応は考えない方が安全です。

*4:文字'0'～'9'に対応している数字が0～9ではないのには注意してください。(数字の0と文字の'0'は区別して考えましょう。)

*5:オーバーフローには注意が必要です。0以上127以内の範囲におさまるように足したり引いたりしてください。

*6:配列についてはN - 1.13.配列、 for文についてはL - 1.11.for文・break・continueをご覧ください。

*7:O - 1.14.STLの関数の後半をご覧ください。

*8:私は、MLEしてしまう時以外はいつも整数型にlong longを用いています。