AtCoder Beginner Contest 252 メモ(A-D)

今回の結果

2AC

B問題ではまって時間取られたし、C問題もそんなに難しい問題じゃないのにACできなかったのが痛かった。

A - ASCII code

https://atcoder.jp/contests/abc252/tasks/abc252_a

Difficulty: 7

問題文

英小文字 a, b, …, z の ASCII 文字コードはこの順に $97,98,…,122$ です。

$97$ 以上 $122$ 以下の整数 $N$ が与えられるので、ASCII 文字コードが $N$ であるような英小文字を出力してください。

制約

• $N$ は $97$ 以上 $122$ 以下の整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

答えを出力せよ。

入出力例

入力例 1

97

出力例 1

a

入力例 2

122

出力例 2

z

参加中に考えたこと

ASCIIコードに合わせて数値型を文字に変換して出力するだけ。

B - Takahashi's Failure

https://atcoder.jp/contests/abc252/tasks/abc252_b

Difficulty: 42

問題文

高橋君の家には $N$ 個の食品があり、$i$ 番目の食品のおいしさは $A_i$ です。
また、高橋君には嫌いな食品が $K$ 個あり、具体的には $i=1,2,…,K$ について、$B_i$ 番目の食品が嫌いです。

高橋君は $N$ 個の食品のうち、おいしさが最大の食品から $1$ つを選んで食べようと考えています。 高橋君が嫌いな食品を食べる可能性があるならば Yes を、食べる可能性が無いならば No を出力してください。

制約

• $1≤K≤N≤100$
• $1≤A_i≤100$
• $1≤B_i≤N$
• $B_i$ はすべて相異なる
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$
$A_1$ $A_2$ ​$\cdots$ $A_N$
$B_1$ $B_2$ ​$\cdots$ $B_K$

出力

高橋君が嫌いな食品を食べる可能性があるならば Yes を、無いならば No を出力せよ。

入出力例

入力例 1

5 3
6 8 10 7 10
2 3 4

出力例 1

Yes

入力例 2

5 2
100 100 100 1 1
5 4

出力例 2

No

参加中に考えたこと

やるべきことを順に整理すると、以下の2ステップでいける

1. $A$ の中から最大のおいしさを求める（ $Amax$ とする）
2. $Ai = Amax$ の食品の中に $B$ が含まれているかを調べる

食品数は最大で100なので、多重ループでも計算量は気にしなくて大丈夫。

C - Slot Strategy

https://atcoder.jp/contests/abc252/tasks/abc252_c

Difficulty: 441

問題文

$N$ 個のリールからなるスロットがあります。
$i$ 番目のリールの配列は文字列 $S_i$ によって表されます。 ここで、$S_i$ は $0, 1, …, 9$ がちょうど $1$ 回ずつ現れる長さ $10$ の文字列です。

それぞれのリールには対応するボタンがついており、高橋君は各非負整数 $t$ について、 スロットが回り始めてからちょうど $t$ 秒後にボタンを $1$ つ選んで押す（または何もしない）ことができます。
スロットが回り始めてから $t$ 秒後に $i$ 番目のリールに対応するボタンを押すと、 $i$ 番目のリールは $S_i$ の $(t \enspace mod \enspace 10)+1$ 文字目を表示して止まります。
ただし、$t \enspace mod \enspace 10$ で $t$ を $10$ で割ったあまりを表します。

高橋君は全てのリールを止めた上で、表示されている文字が全て同じであるようにしたいです。
高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを求めてください。

制約

• $2≤N≤100$
• $N$ は整数
• $S_i$ は $0, 1, …, 9$ がちょうど $1$ 回ずつ現れる長さ $10$ の文字列

入力

入力は以下の形式で標準入力から与えられる。

$N$
$S_1$
​$S_2$
$\vdots$​
$S_N$

出力

高橋君が目標を達成できるように全てのリールを止めるまでに、スロットが回り始めてから最小で何秒かかるかを出力せよ。

入出力例

入力例 1

3
1937458062
8124690357
2385760149

出力例 1

6

入力例 2

5
0123456789
0123456789
0123456789
0123456789
0123456789

出力例 2

40

参加中に考えたこと

問題文が長い。こういう時は入出力の例を見たほうが主旨の理解が早まる。
とはいえ少しややこしいのでちゃんと整理。

• 0秒からリールを押すことができる
• 同時に2つ以上のリールを止めることはできない

最小時間をどうやって探すかを考える。
$Si$ の長さが $10$ で、$N≤100$ しかないから、止める数字 $0$ から $9$ の全てのパターンを計算してその最小値を求める方針でも計算量は問題なさそう。
どのリールを止めるかは、ある時点において次に押せるものを探して押せばよい。

あと、整理した内容の2点目から2つのリールでともに $i$ 番目で止めたい場合、1つ目を止めてから+10秒必要ということも分かる。
入力例２がその例になる。(0+10+10+10+10=40秒)

この方法に適したデータの持たせ方は、$0,1,...,9$ がそれぞれ $S$ の何番目にあるかの個数を持っておけばよい。
0秒目からボタンが押せるので、0オリジンで持っておく。

• 入力例1: $8$ で止める場合

  • 0番目が1つ、1番目が1つ、6番目が1つ
  • この順で8を止めれば6秒

• 入力例2: $0$ で止める場合

  • 0番目が5つ
  • 0 + 10 + 10 + 10 + 10 = 40秒

ここまで考えてコードを書いたけど、WAになる。。

考察・感想

WAになる理由どこにあるのが探して自分のミスに気付いた。
間違いに気づいたのはこのパターン。

• 入力例1 0で止める場合　→　6番目が2つ、7番目が1つ
  • 誤：6+1+10=17秒
  • 正：6+10=16秒

無条件に10足したらいかんよなー。
ここも愚直にループで処理していけばよかったのか？

でも自分がやりたかった合理的な解き方は公式解説にあった。
考え方は途中まで同じだけど0~9それぞれの時間を計算する際、要は一番出現位置が多いところを基準に計算すれば簡単に求められると。なるほどね。

コンテスト中はデータはpush_backで追加してたけど、試すパターン×出現位置を10x10の2次元配列で持っておくのがやりやすかったと感じる。

D - Distinct Trio

https://atcoder.jp/contests/abc252/tasks/abc252_d

Difficulty: 884

問題文

長さ $N$ の数列 $A=(A_1 ,A_2, … ,A_N)$ が与えられます。
以下の $2$ 条件をともに満たすような整数の組 $(i,j,k)$ の個数を求めてください。

• $1≤i<j<k≤N$
• $A_i ,A_j, A_k$ は相異なる

制約

• $3≤N≤2×10^5$
• $1≤A_i≤2×10^5$
• 入力に含まれる値は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1$ $A_2$ ​$\cdots$ $A_N$

出力

答えを出力せよ。

入出力例

入力例 1

4
3 1 4 1

出力例 1

2

入力例 2

10
99999 99998 99997 99996 99995 99994 99993 99992 99991 99990

出力例 2

120

入力例 3

15
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9

出力例 3

355

考察・感想

時間内に解けなかったので後で考えてみた。
まず問題文の理解に時間を喰ったんだけど、これって一言で言えば重複しない３つを選ぶ方法は何通りあるか？ってことになる。
各要素ごとに何個あるかのマップで持っておいて、それを使って解く流れを考える。

重複組み合わせを使うのかと思ったけど計算がかなり大変になりそう。
発想を変えてみて、全パターンから重複があるパターンを引くのはどうか。
選ぶのは３つだから、重複するパターンは3つとも同じ、2つが同じの2パターンだからこっちのほうが計算しやすいのでは？と考えた。

全パターンの数は $_nC_3$ で求まる。
あとは重複するパターンを計算する。
ここで要素ごとの個数を持つマップを $m$ とする。

• 全て同じ場合：3個以上ある要素について $_{m_i}C_3$ の合計
• 2つ同じ場合：2個以上ある要素について $_{m_i}C_2 × (n-m_i)$ の合計

全パターン数から上の2つを引くと求めたい答えになる。

解く前にも思ったけど、後から解説を読むと予想通り解き方のパターンが多い問題だった。
DPでもできるかと最初思ったけど、組み合わせを使う方が自分はやりやすかったので、この方法で解いた。