[ABC262]第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262） A～C問題Python解説

A問題

A - World Cup

Y = int(input())

if Y%4 == 0:
    print(Y + 2)
elif Y%4 == 1:
    print(Y + 1)
elif Y%4 == 2:
    print(Y)
else:
    print(Y + 3)

4で割った余りなので、0,1,2,3の4択ですね。
余りが0の時は2年後に開催されるのでY+2を出力。
余りが1の時は1年後に開催されるのでY+1を出力。
余りが2の時はその年に開催されるのでYを出力。
余りが3の時は3年後に開催されるのでY+3を出力。

B問題

B - Triangle (Easier)

N, M = map(int, input().split())
uv = [[False for __ in range(N)] for _ in range(N)]

for i in range(M):
    U, V = map(int, input().split())
    uv[U-1][V-1] = True
    uv[V-1][U-1] = True

# print(uv)
c = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            if uv[i][j] and uv[j][k] and uv[k][i]:
                c += 1
print(c)

B問題にしては少し難しい質問でした。
キーワードは「2次元リスト」と「総当たり」です。

まず、2元リストuvを作ります。
このリストをどう使うかというと、
まずは全部に初期値として、Falseを与え、
線でつながっている点の番号を格納します。
例えば、uv[1][2] = Trueであれば、点1と点2が繋がっています。
uv[2][3] = Falseであれば、点2と点3は繋がっていません。
ここで1つ注意点ですが、uv[x][y] = Trueであれば、
uv[y][x] = Trueです。
繋がっていることを示すので、点xと点yが繋がっているということと、点yと点xが繋がっているということは同意だからです。

それではリストuvを使って数えていきましょう。
このリストの準備が理解できたら、あとは問題ないでしょう。
if uv[i][j] and uv[j][k] and uv[k][i]:
で、点iと点jと点kが繋がっているのか確認します。
繋がっていたらカウンターを+1して、
最後に繋がっている点の組み合わせの数を出力します。

C問題

C - Min Max Pair

N = int(input())
A = list(map(int, input().split()))
ans = 0

#a[i] = i,a[j] = jの時
c = 0
for i in range(N):
    if A[i] == i+1:
        c += 1
ans += c*(c - 1)//2

#a[i] = j,a[j] = iの時
for i in range(N):
    if A[i]>i+1 and A[A[i]-1] == i+1:
        ans += 1
print(ans)

制約も多いですし、総数なので、全探索は無理ですね。
条件を整理していきましょう。

問題文の以下の部分に注目してください。

min(ai,aj) = i　　①
max(ai,aj) = j　  ②

minというのは最小値を求める関数、
maxというのは最大値を求める関数ですね。
つまり、①はaiとaj小さいほうがi、
②はaiとajの大きいほうがj
という意味になります。

例えば、
ai<ajの時、
①よりai = i、②よりaj = jが分かります。
同様に、ai>ajの時、
①よりaj = i、②よりai = jが分かります。

つまり、整数i,jの組としては
(1)ai = i , aj = j
と
(2)ai = j , aj = i
の2通りしかないということなのです。
これを実装していけばいいわけですね。

(1)について：
数列aの中から、インデックス番号iとそれに対応する要素a[i]が
等しいものを探します。
a[i] = iで探すことができますね。
もしa[i] = iを満たすような整数が2個以上あれば、
(1)の条件を満たします。
では、総数はいくらになるでしょうか？
答えは、nC2です。
条件を満たす整数のうち2個を使いますので、上記のような式になります。
nC2 = n*(n-1)//2として、
プログラムを書きましょう。

(2)について：
for i in range(n):
   for j in range(n):
としたいところですが、これではTLEとなります。
if A[i]>i+1 and A[A[i]-1] == i+1:
の条件分岐でa[i]a[j]をそれぞれ求めることができます。

最後に(1)と(2)それぞれを足した答えを出力します。