読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC042を解いてみた

abc042.contest.atcoder.jp

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;
}