AtCoder Beginner Contest 263 メモ(A-D)

今回の結果

3AC

C問題、苦戦したけどなんとかACできた。
D問題を解けるようになるよりも、安定かつ高速にC問題を解けるようにするほうが目先のRatingは上げやすいのかも。

A - Full House

https://atcoder.jp/contests/abc263/tasks/abc263_a

Difficulty: 27

問題文

$5$ 枚のカードがあり、それぞれのカードには整数 $A,B,C,D,E$ が書かれています。
この $5$ 枚組は以下の条件を満たすとき、またそのときに限って、フルハウスであると呼ばれます。

• 同じ数が書かれたカード $3$ 枚と、別の同じ数が書かれたカード $2$ 枚からなる。

$5$ 枚組がフルハウスであるか判定してください。

制約

• $1 \leq A,B,C,D,E\leq 13$
• $A,B,C,D,E$ 全てが同じ値ではない
• 入力は全て整数

入力

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

$A$ $B$ $C$ $D$ $E$

出力

フルハウスである場合 Yes を、そうでないとき No を出力せよ。

入力例 1

1 2 1 2 1

出力例 1

Yes

入力例 2

12 12 11 1 2

出力例 2

No

参加中に考えたこと

入力が５つもあるのか。
変数のままだと並び替えが面倒だし、配列に入れてソートしてしまおう。
そして、フルハウスの条件を満たしているかの判定をすればOK、と思ったがWA出してしまった。
3:2と2:3の2パターンあるのが漏れてた。。

考察・感想

ソート済であれば同じ数が3枚のほうは真ん中は見る必要はないですね。

B - Ancestor

https://atcoder.jp/contests/abc263/tasks/abc263_b

Difficulty: 136

問題文

$N$ 人の人がいます。$N$ 人の人には人 $1,$ 人 $2,\dots,$ 人 $N$ と番号がついています。
人 $i(2 \le i \le N)$ の親は人 $P_i$ です。ここで、$P_i < i$ が保証されます。
人 $1$ が人 $N$ の何代前か求めてください。

制約

• $2 \le N \le 50$
• $1 \le P_i < i(2 \le i \le N)$
• 入力は全て整数。

入力

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

$N$
$P_2$ $P_3$ $\dots$ $P_N$

出力

答えを整数として出力せよ。

入力例 1

3
1 2

出力例 1

2

入力例 2

10
1 2 3 4 5 6 7 8 9

出力例 2

9

参加中に考えたこと

自分の親がどれかの配列を持たせて、あとは人 $N$ から始めて自分の親を順に見ていって $1$ になるまで辿っていけば、辿った回数が答えになる。

考察・感想

解説にDP使う解法とかあるけど、B問題では難しすぎないかな。。

C - Monotonically Increasing

https://atcoder.jp/contests/abc263/tasks/abc263_c

Difficulty: 298

問題文

長さ $N$ かつ全ての要素が $1$ 以上 $M$ 以下である整数列のうち、狭義単調増加であるものを全て辞書順に出力してください。

注記

ある $2$ 個の異なる長さの等しい整数列 $A_1,A_2,\dots,A_N$ と $B_1,B_2,\dots,B_N$ が以下を満たすとき、またその時に限り辞書順で $A$ が $B$ より早いと定義されます。

• ある整数 $i(1 \le i \le N)$ が存在し、$1 \le j < i$ である全ての整数 $j$ に対し $A_j=B_j$ が成り立ち、かつ $A_i < B_i$ が成り立つ。

ある整数列 $A_1,A_2,\dots,A_N$ は以下を満たすとき、またその時に限り狭義単調増加です。

• 全ての整数 $i(1 \le i \le N-1)$ に対し $A_i < A_{i+1}$ が成り立つ。

制約

• $1 \le N \le M \le 10$
• 入力は全て整数。

入力

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

$N$ $M$

出力

条件を満たす整数列を一行に一つずつ、辞書順に出力せよ（出力例を参考にせよ）。

入力例 1

2 3

出力例 1

1 2 
1 3 
2 3 

入力例 2

3 5

出力例 2

1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5 

参加中に考えたこと

$N < 10$ だから再帰関数でいけそう。
方針は早々に決まったものの、作成する関数のベースケースと再帰の部分の組み方に苦戦した。
時間をかなり費やして焦りもあったがなんとか解けて安堵。

考察・感想

これで灰Diffなんですね。再帰とか茶Diffかと思ってたので少し驚いた。
Pythonだと関数使って一発らしい。

D - Left Right Operation

https://atcoder.jp/contests/abc263/tasks/abc263_d

Difficulty: 1016

問題文

長さ $N$ の整数列 $A=(A_1,A_2,\ldots,A_N)$ が与えられます。
あなたは以下の連続する操作をちょうど一度だけ行います。

• 整数 $x\ (0\leq x \leq N)$ を選ぶ。$x$ として $0$ を選んだ場合何もしない。 $x$ として $1$ 以上の整数を選んだ場合、$A_1,A_2,\ldots,A_x$ をそれぞれ $L$ で置き換える。
• 整数 $y\ (0\leq y \leq N)$ を選ぶ。$y$ として $0$ を選んだ場合何もしない。 $y$ として $1$ 以上の整数を選んだ場合、$A_{N},A_{N-1},\ldots,A_{N-y+1}$ をそれぞれ $R$ で置き換える。

操作後の $A$ の要素の総和として考えられる最小値を求めてください。

制約

• $1 \leq N \leq 2\times 10^5$
• $-10^9 \leq L, R\leq 10^9$
• $-10^9 \leq A_i\leq 10^9$
• 入力は全て整数

入力

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

$N$ $L$ $R$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを出力せよ。

入力例 1

5 4 3
5 5 0 6 3

出力例 1

14

入力例 2

4 10 10
1 2 3 4

出力例 2

10

入力例 3

10 -5 -3
9 -6 10 -1 2 10 -1 7 -15 5

出力例 3

-58

参加中に考えたこと

$L$ と $R$ それぞれ置き換える操作の計算量は $O(N)$ になるはず。
$x$ と $y$ をどう探すかだけど、左からないし右から順に調べて値が最小となるものを選べばいいのかと思ってコードを書いて提出するが、数ケースでWAになってしまう。
エラーになるケースが分からずタイムアップ。

考察・感想

時間を置いて再度解いてもACできなかったので解説を読み、再度考えなおして解いた。

まず連続する操作の片方のみであれば、$L$ のほうであれば関数 $f$ を用いると $f(i) = min(f(i-1)+a(i), L \times (i+1))$ 、 $R$ の場合同様に関数 $g$ を用いると $g(i-1) = min(g(n-i-1), R \times (n-i-1) ) $ で求められる。
なお、 $R$ はそのまま処理すると途中の値を間違える恐れがあるので、一旦逆順にしてLと同じようにしたうえで、再度逆順にするのでもいい。

では $x$ と $y$ の2つの処理を行う場合の最小はどうするかを考える。
$f$ も $g$ も最小値なのだから、双方の最小値の和になる $f(i) + g(N-i)$ が最小になるものが答えになる。

入力例の1と2を表にすると以下のようになる。

入力例1

$i$	0	1	2	3	4
$A(i)$	5	5	0	6	3
$f(i)$	4	8	8	14	17
$g(i)$	15	11	6	6	3
$f(i) + g(i+1)$	15	14	14	17	17

この表より、最小値の14が答えになる。

入力例2

$i$	0	1	2	3
$A$	1	2	3	4
$f(i)$	1	3	6	10
$g(i)$	10	9	7	4
$f(i) + g(i+1)$	10	10	10	10

この表より、$f(i) + g(i+1)$ の値は全て10となっているがこれが答えになる。

但し、上の表において $i$ が $0$ または $N$ の時の場合（= 全てLまたはRに置き換える）が最小になる場合もあるので、

• $f(i) + g(i+1) \enspace [0<i<N-1]$
• $f(N-1)$
• $g(0)$

以上3つのうちの最小値が答えになる。

3つのパターンに分ける代わりに $N+2$ 個の配列を用意して $A[1]～A[N]$ に $A(i)$ の値を入れて同様の処理をすることで、$f(i) + g(i+1) \enspace [0 \le i \le N]$ だけで最小値を求めることもできる。

これを入力例1を使って表すと以下のようになり、やはり答えは14になる。

$i$	0	1	2	3	4	5	6
$A(i)$	0	5	5	0	6	3	0
$f(i)$	0	4	8	8	14	17	0
$g(i)$	0	15	11	6	6	3	0
$f(i) + g(i+1)$	15	15	14	14	17	17	17

こっちのほうが場合分けの処理が減るのでコードは少しすっきりする。