AtCoder Beginner Contest 262 メモ(A-D)

今回の結果

2AC

C問題が難易度が低いのに解けないのは痛い。
通らないテストケースの原因をいかに見つけられるかが課題。

A - World Cup

https://atcoder.jp/contests/abc262/tasks/abc262_a

Difficulty: 8

問題文

あるスポーツ大会は西暦年を $4$ で割った余りが $2$ である年の $6$ 月に開催されます。
現在が西暦 $Y$ 年の $1$ 月である時、このスポーツ大会が次に開催されるのは西暦何年になるかを求めてください。

制約

• $2000≤Y≤3000$
• $Y$ は整数

入力

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

$Y$

出力

答えを出力せよ。

入出力例

入力例 1

2022

出力例 1

2022

入力例 2

2023

出力例 2

2026

入力例 3

3000

出力例 3

3002

参加中に考えたこと

$Y mod 4$ の値で分岐させる。

• $Y \space mod \space 4 = 0 \longrightarrow Y+2$
• $Y \space mod \space 4 = 1 \longrightarrow Y+1$
• $Y \space mod \space 4 = 2 \longrightarrow Y$
• $Y \space mod \space 4 = 3 \longrightarrow Y+3$

これを1行で書けるのか分からないが、複雑な式になりそうなので素直に分岐を４つ書いて完了。

考察・感想

他の人の回答を見て1行で解いている人の式を見たけど、かなりややこしかったのでここまでやる必要はないかな。
解き方としてif文一択でしか考えてなかったけど、while文を使う方法（ $Y \enspace mod \enspace 2 = 0$ になるまで $Y$ をインクリメントしていく ）で解いている人が結構多かった。

B - Triangle (Easier)

https://atcoder.jp/contests/abc262/tasks/abc262_b

Difficulty: 220

問題文

$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。頂点には $1,\dots,N$ の番号が付けられており、$i(1≤i≤M)$ 番目の辺は頂点 $U_i$ と頂点 $V_i$ を結んでいます。
以下の条件を全て満たす整数 $a,b,c$ の組の総数を求めてください。

• $1≤a<b<c≤N$
• 頂点 $a$ と頂点 $b$ を結ぶ辺が存在する。
• 頂点 $b$ と頂点 $c$ を結ぶ辺が存在する。
• 頂点 $c$ と頂点 $a$ を結ぶ辺が存在する。

制約

• $3 \leq N \leq 100$
• $1 \leq M \leq \frac{N(N - 1)}{2}$
• $1 \leq U_i \lt V_i \leq N \, (1 \leq i \leq M)$
• $(U_i, V_i) \neq (U_j, V_j) \, (i \neq j)$
• 入力は全て整数

入力

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

$N$ $M$
$U_1$ $V_1$
$\vdots$
$U_M$ $V_M$

出力

答えを出力せよ。

入出力例

入力例 1

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

出力例 1

2

入力例 2

3 1
1 2

出力例 2

0

入力例 3

7 10
1 7
5 7
2 5
3 6
4 7
1 5
2 4
1 3
1 6
2 7

出力例 3

4

参加中に考えたこと

この問題を読み替えると、グラフの中に三角形はいくつあるかを求めるのと同じことのよう。

$N \le 100$ なので $a,b,c$ の組み合わせを探すのは全探索でいけそう。
但し、この3重ループの中で条件にある3辺の存在を調べるのに更にループを使ってしまうとTLEする可能性があると思ったのと、あとあんまり綺麗ではない。
最初に辺の情報を $N \times N$ の二次元配列で持っておくようにして、ループの中ではこの配列の値だけを見て判定するようにすればよい。

考察・感想

組み合わせを数え間違えないようにするためにする必要があるが、方法としては2通り思いついた。

1. 二次元配列の中に漏れがないように $(U_i,V_i), (V_i,U_i)$ の両方に値を入れ、重複して数えないように $0 \le i < N-2, \enspace i+1 \le j < N-1, \enspace j+1 \le k < N$ の範囲でループさせる
2. 二次元配列には $(U_i,V_i)$ のみ値を入れ、 $(i,j), (j,k),\color{#FF0000}(i,k)$ の3つの値があるものを数え上げる

2は $U_i<V_i$ の制約があるのでこういう方法もできる。if文の中はシンプルだが、あまり一般的ではないので1の方法で解くのが主流かと思う。

C - Min Max Pair

https://atcoder.jp/contests/abc262/tasks/abc262_c

Difficulty: 362

問題文

$1$ 以上 $N$ 以下の整数からなる長さ $N$ の数列 $a=(a_1 ,\dots,a_N)$ が与えられます。
以下の条件を全て満たす整数 $i,j$ の組の総数を求めてください。

• $1 \leq i \lt j \leq N$
• $\min(a_i, a_j) = i$
• $\max(a_i, a_j) = j$

制約

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq a_i \leq N \, (1 \leq i \leq N)$
• 入力は全て整数

入力

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

$N$
$a_1$ $a_2$ $\dots$​ $a_N$

出力

答えを出力せよ。

入出力例

入力例 1

4
1 3 2 4

出力例 1

2

入力例 2

10
5 8 2 2 1 6 7 2 9 10

出力例 2

8

参加中に考えたこと

Nの値が大きいので計算量が $O(N^2)$ より少ない方法を考える必要がある。
入力例2の答えが8つなので洗い出してみると、$(1,5), (2,8), (6,7), (6,9), (6,10), (7,9), (7,10), (9,10)$ の8つである。
ここから規則性を考えると、条件を満たすものとして2パターンがあることに気づいた。

$i$	1	2	3	4	5	6	7	8	9	10
$A_i$	5	8	2	2	1	6	7	2	9	10
$P(i)$	△	△			△	〇	〇	△	〇	〇

1. $P(i) = 〇 \longleftarrow i = A_i$
2. $P(i) = △ \longleftarrow i = A_j$ かつ $j=A_i$

2の△において、i,jで対になるので数は必ず偶数個になり、 $i<j$ の条件により $\dfrac{△}{2}$ 個の組が存在する。
1の〇は、〇の中から任意の2つを選んだものは全て条件を満たすので、組の数としては $_nC_2$ 個ある。

この２つのパターンで数えた組の和が答えになる、と考えた。
この例の場合だと $_4C_2 = 8$ となり答えが合う。

が、通らないケースがあってACできない。
漏れているケースが分からずACできず。

考察・感想

上のテキストを書いた後に改めてコードを書いたらすんなりACした。。
△の数え方をミスってた。
落ち着いて解けば全然できる問題なのに時間に迫られるとこういうミスをしてしまうなぁ。

D - I Hate Non-integer Number

https://atcoder.jp/contests/abc262/tasks/abc262_d

Difficulty: 1213

問題文

項数が $N$ の正整数列 $A=(a_1 ,…,a_N)$ が与えられます。
$A$ の項を $1$ 個以上選ぶ方法は $2^N−1$ 通りありますが、そのうち選んだ項の平均値が整数であるものが何通りかを $998244353$ で割った余りを求めてください。

制約

• $1≤N≤100$
• $1≤a_i≤10^9$
• 入力はすべて整数

入力

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

$N$
$a_1$ $a_2$ $\dots$​ $a_N$

出力

答えを出力せよ。

入出力例

入力例 1

3
2 6 2

出力例 1

6

入力例 2

5
5 5 5 5 5

出力例 2

31

参加中に考えたこと

そのまま計算すると $(2^N)$ でTLEするので、工夫が必要。
全然解き方が分からない。

考察・感想

解説を読んでも3次元DP？が全然分からず、今の自分では解けない問題。
というか、解説があまりに短くて、これで分かる人はACしてるんじゃないかと思う。。
DPは基本的はものしかやってないから、AtCoderにあるDP練習用を進めて幅を広げていきたい。