結論から言うと、25 分で D までスラスラ解けたのですがその後永遠に虚無な時間を過ごしていました。
サトゥー
もくじ
ABC132 A – Fifty-Fifty
長さ \(4\) の英大文字からなる文字列 \(S\) が与えられます。 \(S\) がちょうど \(2\) 種類の文字からなり、かつ現れる各文字はちょうど \(2\) 回ずつ現れているかどうかを判定してください。
https://atcoder.jp/contests/abc132/tasks/abc132_a
コンテスト中にはすぐに楽そうな実装方法が思いつかなかったので愚直に場合分けしながら解きましたが、よく考えると文字列をソートしてしまえばラクですね。
回答案
以下のコードで Python3 で 17 ms で AC でした。
S = sorted(input())
if len(set(S)) == 2 and S[0] == S[1] and S[1] != S[2] and S[2] == S[3]:
print("Yes")
else:
print("No")サトゥー
ABC132 B – Ordinary Number
\({1, 2, …, n}\) の順列 \(p = {p_1, p_2, …, p_n} \) があります。
以下の条件を満たすような \(p_i (1 < i < n) \) がいくつあるかを出力してください。\(p_{i−1}, p_{i}, p_{i+1} \) の \(3\) つの数の中で、\(p_i\) が \(2\) 番目に小さい。
https://atcoder.jp/contests/abc132/tasks/abc132_b
条件は p[i] < p[i + 1] < p[i + 2] or p[i + 2] < p[i + 1] < p[i] と言い換えることができます。ので、コレを for ループ回して条件を満たすものをカウントすれば答えが得られますね。
回答案
以下のコードで Python3 で 17 ms で AC でした。
n = int(input())
p = list(map(int, input().split()))
ans = 0
for i in range(n - 2):
if p[i] < p[i + 1] < p[i + 2] or p[i + 2] < p[i + 1] < p[i]:
ans += 1
print(ans)ABC132 C – Divide the Problems
高橋君は、 \(N\) 個の競技プログラミング用の問題をつくりました。 それぞれの問題には \(1\) から \(N\) の番号がついており、問題 \(i\) の難易度は整数 \(d_i\) で表されます(大きいほど難しいです)。
高橋君はある整数 \(K\) を決めることで、・難易度が \(K\) 以上ならば「 ARC 用の問題」
・難易度が \(K\) 未満ならば「 ABC 用の問題」という風に、これらの問題を二種類に分類しようとしています。
https://atcoder.jp/contests/abc132/tasks/abc132_c
「 ARC 用の問題」と「 ABC 用の問題」が同じ数になるような整数 \(K\) の選び方は何通りあるでしょうか。
難易度 \(K\) の前後で分けられるので、まずは \(d_i\) をソートしておきます。すると、 d[N // 2] 以降が ARC 、d[N // 2 - 1] 以前が ABC に振り分けられるように \(K\) を設定すればいいので、\(K\) としてあり得る値は d[N // 2 - 1] + 1 から d[N // 2] までの合計 d[N // 2] - d[N // 2 - 1] 個になります。
回答案
以下のコードで Python3 で 76 ms で AC でした。
N = int(input())
d = sorted(list(map(int, input().split())))
print(d[N // 2] - d[N // 2 - 1])ABC132 D – Blue and Red Balls
\(K\) 個の青いボールと \(N − K\) 個の赤いボールがあります。同じ色のボールは区別が不可能です。すぬけ君と高橋君はこれらのボールで遊んでいます。
https://atcoder.jp/contests/abc132/tasks/abc132_d
まず、すぬけ君が、\(N\) 個のボールを左から右に一列に並べます。
次に、高橋君は、これらのうち \(K\) 個の青いボールのみを回収します。高橋君は、\(1\) 回の操作で連続して並ぶ青いボールを何個でも回収することができます。高橋君は、常に \(K\) 個の青いボールを回収するのにかかる操作の回数が最小になるように行動します。
\(K\) 個の青いボールを回収するために高橋君がちょうど \(i\) 回操作をする必要があるボールの並べ方は何通りあるでしょうか。 \(1 \leq i \leq K\) をみたす \(i\) それぞれについて答えを計算し、 \(10^9 + 7\) で割った余りを答えてください。
次のように解釈すればラクかと思います。
\(N – K\) 個の赤いボールをあらかじめ一列に並べておきます。この間（両端含めて \(N – K + 1\) 個）に青いボールを入れていきます。
このとき、青いボールは \(i\) 回の操作で回収できる必要があるので、 \(K\) 個の青いボールが \(i\) 個のグループに分けられて、連続して並ぶ必要があることに注意します。
\(K\) 個の青いボールを \(i\) 個のグループに分ける方法が \( {}_{K – 1} C_{i – 1}\) 通り、それらを赤いボールの間に入れる方法が \( {}_{N – K + 1} C_{i}\) 通りなので、コレを掛け算すれば答えが得られます。
サトゥー
二項係数 \({}_n C_r\) の求め方
二項係数 \( {}_n C_{r} \) の計算については Qiitaの記事 を参考にコードを書いてみました。
from operator import mul
from functools import reduce
def cmb(n, r):
if n < r:
return 0
r = min(n - r, r)
if r == 0:
return 1
numer = reduce(mul, range(n, n - r, -1))
denom = reduce(mul, range(1, r + 1))
return numer // denom % (10 ** 9 + 7)注意すべきは次の 2 点です。
- \( {}_{N – K + 1} C_{i}\) を計算するときに \(N – K + 1 < i\) になってしまう場合の対処
- 得られる答えの数字が大きくなりすぎるときの対処
前者は条件分岐で 0 を返すようにすれば OK です。後者については一応 \(10^9 + 7\) で割っておきました。
回答案
次のコードで Python3 で 174 ms で AC でした。
from operator import mul
from functools import reduce
def cmb(n, r):
if n < r:
return 0
r = min(n - r, r)
if r == 0:
return 1
numer = reduce(mul, range(n, n - r, -1))
denom = reduce(mul, range(1, r + 1))
return numer // denom % INF
N, K = map(int, input().split())
INF = 10 ** 9 + 7
for i in range(1, K + 1):
print(cmb(K - 1, i - 1) * cmb(N - K + 1, i) % INF)ABC132 E – Hopscotch Addict
ケンくんはけんけんぱが大好きです。今日は有向グラフ \(G\) の上でけんけんぱをすることにしました。 \(G\) は \(1\) から \(N\) で番号付けされた \(N\) 頂点および \(M\) 辺からなり、 \(i\) 番目の辺は頂点 \(u_i\) から頂点 \(v_i\) に接続しています。
https://atcoder.jp/contests/abc132/tasks/abc132_e
ケンくんははじめ頂点 \(S\) にいて、頂点 \(T\) までけんけんぱで移動したいです。 \(1\) 回のけんけんぱでは、「自分の今いる頂点から出ている辺を \(1\) つ選んで、その辺が接続する頂点に移動する」という操作をちょうど \(3\) 回連続で行います。
ケンくんが頂点 \(T\) に移動することができるか、また移動できるなら最小何回のけんけんぱで頂点 \(T\) まで移動することができるかを答えてください。 けんけんぱの操作の途中で頂点 \(T\) に訪れても、「頂点 \(T\) に移動できた」とは見なさないことに注意してください。
まだ解けてないです。とりあえず寝て明日考えます。
回答案
# まだできてないよ
