AtCoder Beginner Contest 175のA,B,C問題を、Python3でなるべく丁寧に解説していきます。
ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。
- シンプル：余計なことを考えずに済む
- 実装が楽：ミスやバグが減ってうれしい
- 時間がかからない：パフォが上がって、後の問題に残せる時間が増える
目次
ABC175 まとめ
A問題『Rainy Season』
B問題『Making Triangle』
C問題『Walking Takahashi』
ABC175 まとめ
全提出人数: 8812人
パフォーマンス
| パフォ | AC | 点数 | 時間 | 順位(Rated内) |
|---|---|---|---|---|
| 200 | AB---- | 300 | 47分 | 6625(6462)位 |
| 400 | AB---- | 300 | 17分 | 5762(5599)位 |
| 600 | ABC--- | 600 | 90分 | 4751(4592)位 |
| 800 | ABC--- | 600 | 54分 | 3674(3517)位 |
| 1000 | ABC--- | 600 | 34分 | 2668(2512)位 |
| 1200 | ABC--- | 600 | 21分 | 1849(1694)位 |
| 1400 | ABCD-- | 1000 | 96分 | 1232(1085)位 |
| 1600 | ABC-E- | 1100 | 86分 | 798(657)位 |
| 1800 | ABCDE- | 1500 | 109分 | 498(371)位 |
| 2000 | ABCDE- | 1500 | 84分 | 296(194)位 |
| 2200 | ABCDE- | 1500 | 65分 | 171(94)位 |
| 2400 | ABCDE- | 1500 | 49分 | 101(43)位 |
色別の正解率
| 色 | 人数 | A | B | C | D | E | F |
|---|---|---|---|---|---|---|---|
| 灰 | 3581 | 95.2% | 68.6% | 37.0% | 1.1% | 1.1% | 0.0% |
| 茶 | 1688 | 99.3% | 96.4% | 79.7% | 4.6% | 4.5% | 0.0% |
| 緑 | 1284 | 99.8% | 99.0% | 89.7% | 18.0% | 11.0% | 0.0% |
| 水 | 715 | 99.4% | 99.0% | 94.1% | 45.7% | 37.6% | 1.3% |
| 青 | 349 | 99.7% | 99.7% | 96.0% | 74.2% | 76.8% | 4.0% |
| 黄 | 133 | 92.5% | 93.2% | 91.0% | 79.7% | 86.5% | 15.8% |
| 橙 | 28 | 96.4% | 96.4% | 96.4% | 96.4% | 96.4% | 75.0% |
| 赤 | 5 | 100.0% | 100.0% | 100.0% | 100.0 | 100.0% | 100.0% |
※表示レート、灰に初参加者は含めず
簡易解説
- A問題 (8513人AC)『Rainy Season』
- forループを使うとスマートですが、3文字だけなので、$2^3=8$ 通りすべてを書き出してもいいです。
- B問題 (7207人AC)『Making Triangle』
- $N=100$ なので、$O(N^3)$ の3重forループで棒の選び方をすべて列挙できます。三角形が作れる条件は、一番長い辺が、他の2辺の和より短いことです。B問題にしてはかなり難しいです。
- C問題 (5316人AC)『Walking Takahashi』
- 最初の座標が負の場合、分けるが面倒なので、絶対値を取ってしまって構いません。
- D問題 (1103人AC)『Moving Piece』[この記事では解説しません]
- $N\le5000$ なので、$O(N^2)$ が間に合います。$K$ は非常に大きいですが、$N$ 回以下でループするので、それを利用して点数を求めます。気にすることが多くて面倒な問題です。
- E問題 (984人AC)『Picking Goods』[この記事では解説しません]
- 行・列・拾った回数の3次元の動的計画法で解けます。
- F問題 (73人AC)『Making Palindrome』[この記事では解説しません]
- ダイクストラ法らしいです。
$D$ が1より大きい場合、どうやっても止まれない座標が存在します。具体的には、初期座標$X$から、$D$の倍数を足すか引くかした座標以外には止まれません。
同じところを往復することで、元の場所にいながら偶数回移動を消費できます。逆に、奇数回の移動では、どうやっても元の場所にとどまることはできません。
絶対値が最小の座標は、$0$ に止まれる場合は $0$ で、そうでない場合は $0$ に一番近いプラス側かマイナス側のどちらかです。
絶対値が2番目に小さい座標は、$0$ に止まれる場合は $0\pm{D}$ 、そうでない場合は、$0$ に周辺の絶対値最小でないほうです。
A問題『Rainy Season』
問題ページ：A - Rainy Season
実装
$8$ 通り全部書きだしてもいいですが、forループで"R","RR","RRR"を作って、文字列に含まれるかinで判定することにしましょう。
コード
s = input()
ans = 0
for i in range(1, 4):
p = "R" * i
if p in s:
ans = i
print(ans)
B問題『Making Triangle』
問題ページ：B - Making Triangle
考察：
3つの整数の選び方
まず、3つの整数 $0\le{i}\lt{j}\lt{k}\le{N-1}$ をどうやってすべて列挙するかを考えましょう。（問題文では1から始まりますが、添字は0から始まるので、そちらに合わせたほうがやりやすいです）
これは、下のような3重forループを書くとできます。
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
# なにかする
$j$ は $i$ より大きくなってほしいので、$j$ は最小で $i+1$ になるように指定します。
$k$ も同様に、$j$ より大きくなってほしいので、$k$ は最小で $j+1$ になるように指定します。
1つ目の条件：すべての辺の長さが異なるか
次に、問題文に書いてあるとおり、選んだ $L_i, L_j, L_k$ がすべて異なるかどうかを判定します。これは、if文を使えばいいです。
2つ目の条件：三角形を作れるかどうか
最後に、問題文には書いてありませんが、$3$ つの棒から三角形が作れるかどうかの条件があります、一番長い棒の長さが、他の2つの棒の和よりも短いことです。
この条件も満たすなら、答えに $1$ 足します。
そんなことはもう忘れたという方も多いと思います。そういうときは、グーグル検索をするといいです。
実装
最後の三角形の条件で、棒を選ぶたびに毎回どれが一番長いか判定するのは面倒なので、先に配列をソートしてしまいます。
コード
5重にネストしてて若干見づらい気もしますが、複雑なことはしていないので、関数に分けるよりもいいと思います。
n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if l[i] != l[j] != l[k]:
if l[i] + l[j] > l[k]:
ans += 1
print(ans)
C問題『Walking Takahashi』
問題ページ：C - Walking Takahashi
やる気があればあとで図を書くかもしれない（たぶん書かない）
考察：
移動の性質
はじめに、この移動の性質について考えてみます。
とりあえず0に近づく
最初の座標 $X$ が負の場合、正の場合と反対の動きをすれば同じことになるので、絶対値を取って正にしてしまって構いません。こうすると、場合分けがなくなって楽になります。
とりあえず、$0$ に近いほうがうれしいので、できるだけ $0$ に近づくことにします。$0$を通り過ぎるまでは、一直線に$0$に向かって進めばいいです。
$0$ を通り過ぎる場合はややこしそうなので後で考えることにして、「 $0$ を通りすぎない絶対値最小の座標」=「0以上で絶対値が最小の座標」に移動してみます。
$K$ が非常に大きいので、forループでシミュレートはできません。算数で求める必要があります。
これは、「最初の座標 $|X|$ を $D$ で割った商（余りが出る割り算の答え）」だけ移動すればいいです。ただし $K$ がそれより小さいと、その前に移動回数がなくなることに気をつけてください。
残りの移動回数が偶数か奇数かで答えが決まる
この移動をしたあとの座標を $Y$ とします。残りの移動回数が $0$ なら $Y$ が答えです。まだ移動回数が残っている場合を考えます。
結論から言うと、「残り回数が偶数なら $Y$ で、残り回数が奇数ならさらにマイナス側に $1$ 回進んだ $|Y-D|$ 」になります。
残り回数が偶数のとき、同じところを往復することで、元の場所にとどまることができます。しかし、どうやっても1つ隣の場所に止まることはできません。
残り回数が奇数のときは、同じところを往復すると残り1回のとき元の場所にいるので、どうやっても元の場所の1つ隣にしか止まれません。
${|Y - D|} \le {Y + D}$ なので、残り回数が奇数の場合、プラス側ではなく、マイナス側に1回移動するほうがいいです。（外側に移動するより、内側に移動したほうがいい的なイメージ）
コード
x, k, d = map(int, input().split())
cur = abs(x) # 座標を正にしてしまいます
rem = k # 残りの移動回数です
cnt = min(cur // d, k) # 0に向かって移動する回数です
cur -= d * cnt
rem -= cnt
# 0 % 2 = 0なので、残り回数の場合分けをする必要はないのですが、一応
if rem > 0:
if rem % 2 == 1:
cur = cur - d
ans = abs(cur) # 絶対値を出力することに気をつけてください
print(ans)