ABC042を解いてみた
A問題
入力をソートして5, 5, 7になっていればYES, なっていなければNOを出力しました。
a = [int(i) for i in input().split()]
a.sort()
if a[0] == 5 and a[1] == 5 and a[2] == 7:
print("YES")
else:
print("NO")
B問題
ソート関数で辞書順に並べて出力しました。
n, l = map(int, input().split())
s = [[i for i in input()] for j in range(n)]
s.sort()
for i in range(n):
s[i] = "".join(s[i])
s = "".join(s)
print(s)
C問題
桁を増やす必要があるかどうか、Nをすでに超えているかどうかなどの場合分けをおこない1桁ずつ決めていきました。1～10Nまで全探索すればよいなんてやり方に気がつかないなんて…という感じです。
n, k = map(int, input().split())
d = [int(i) for i in input().split()]
ablenum = [int(i) for i in range(10)]
lis_n = str(n)
lis_n = list(lis_n)
# 使用可能な数一覧
for i in d:
ablenum.remove(i)
flag_bigdigit = -1
# max(ablenum)より大きい桁があるかどうか
for i in range(len(lis_n)):
_i = len(lis_n) - i - 1
if(int(lis_n[_i]) > max(ablenum)):
flag_bigdigit = _i
break
# max(ablenum)より大きい桁があれば
if(flag_bigdigit != -1):
flag_increaseDights = 1
# 桁を増やす必要があるかどうか確認
for i in range(flag_bigdigit-1, 0):
# nの桁より大きい数字がablenumに存在していれば桁を増やす必要はない
if(int(lis_n[i]) < max(ablenum)):
flag_increaseDights = 0
break
else:
flag_increaseDights = 0
ans = ""
# 桁を増やす必要があるならば
if(flag_increaseDights == 1):
for i in range(len(lis_n)+1):
# 一桁目は0以外の最も小さな数
if(i == 0):
mnum = min(ablenum)
if(mnum == 0):
mnum = ablenum[1]
ans += str(mnum)
# 2桁目以降は最も小さい数
else:
mnum = min(ablenum)
ans += str(mnum)
# 桁を増やす必要がなければ、各桁の数字以上の最も小さい数を使う
else:
flag_over = 0
for i in range(len(lis_n)):
if(flag_over == 0):
mnum = min(ablenum)
# その桁以上の数になるまで大きくする
j = 0
while mnum < int(lis_n[i]):
j += 1
mnum = ablenum[j]
# n以上となることが確定すれば
if(mnum > int(lis_n[i])):
flag_over = 1
ans += str(mnum)
# n以上となることが確定していれば使える中で最も小さい数を使う
else:
mnum = min(ablenum)
ans += str(mnum)
print(ans)
D問題
最短経路数はコンビネーションを使って計算できるので、nCr(mod m)を高速で求める方法を使って実装しました。逆元を予め求めておくことでコンビネーションはO(1)で計算できます。フェルマーの小定理から逆元はmod mのときx^m-2で求められます。二分累乗法でx^nはO(logn)で計算できるので逆元の列はO(nlogn)で計算可能です。
Pythonでh=w=10^5のケースを試してみたところ、明らかに2秒以内に計算できていなかったのでいろいろ試してみたんですが実行時間を減らすことができずC++で書き直しました。オーバーフローを気にしなくてもよかったりPythonは好きですが、競プロで使う分にはC++のほうがよさそうだと思えてきました。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
ll fact[200000], ifact[200000], dp[100000];
int h, w, a, b;
//二分累乗法
ll binpow(ll x, ll e)
{
ll a = 1;
ll p = x;
while(e > 0)
{
if(e%2 == 0) {p = (p*p) % MOD; e /= 2;}
else {a = (a*p) % MOD; e--;}
}
return a;
}
int main(void)
{
fact[0] = 1;
ifact[0] = 1;
scanf("%d %d %d %d", &h, &w, &a, &b);
//逆元の列を計算
for(int i = 1; i < h+w; i++)
{
fact[i] = fact[i-1] * i % MOD;
ifact[i] = binpow(fact[i], MOD-2);
}
// (b-1, 0) から (b-1, h-a-1) までの経路数を計算
for(int i = 0; i < h-a; i++)
dp[i] = ((fact[b-1+i]*ifact[b-1]%MOD)*ifact[i]%MOD);
// (b-1, 0) から (b-1, h-a-1) から右下までの経路数を計算
ll ans = 0LL;
for(int i = 0; i < h-a; i++)
ans = (ans + ((dp[i]*fact[h+w-b-i-2]%MOD)*ifact[h-i-1]%MOD)*ifact[w-b-1]%MOD) % MOD;
printf("%lld\n", ans);
return 0;
}
