8/24にAtCoderで第一回日本最強プログラマー学生選手権-予選-が開催された。学生以外も参加できてレーティングが変化するとのことだったので参加したが、Aしか解けなかった...

A問題

問題

1〜M月、1〜D日から構成される高橋暦の中で積の日が何日あるかをカウントする問題。

m月d日としてときの
$d _ {10}$ はdの10の位
$d _ 1$ はdの1の位
とすると、積の日の条件は

$d _ 1 >= 2$
$d _ {10} >= 10$
$d _ 1 \times d _ {10} =m$

となる。

ループして上記条件に該当する日が何日あるかをカウントすればいいだけ。

自分の回答

M,D=map(int, input().split())
 
seki=0
for m in range(1,M+1):
    for d in range(1,D+1):
        str_d = str(d)
        if len(str_d)==2:
            d10 = int(str_d[0])
            d1  = int(str_d[1])
            if d10 >= 2 and d1 >= 2 and d10*d1 == m:
                seki+=1
print(seki)

他の人の回答みて勉強になったこと

10の位と1の位を分割するのにstrで文字列に変換する必要はなく、以下の書き方で変換できる。

d10 = d % 10 # dの10の位
d1 = d // 10 # dの1の位

また組み込み関数divmod()を使うと一行で書ける。

d10, d1 = divmod(d, 10) # (dの10の位, dの1の位)

divmod()を使うと下記のように書き直せる。

M, D = map(int, input().split())
seki = 0
for m in range(1, M + 1):
    for d in range(1, D + 1):
        d10, d1 = divmod(d, 10)
        if d10 >= 2 and d1 >= 2 and d10 * d1 == m:
            seki += 1
print(seki)

B問題

問題

数列AをK回繰り返しものを数列Bとしたとき、数列Bの中に転倒数はいくつあるか。(答えは $10 ^ 9 + 7$ で割った余りで表示する。)

転倒 (数学) - Wikipedia

B問題は時間内に解くことはできなかった... 数列Aの中で発生する転倒数と、繰り返される数列A間で発生する転倒数がありこれらを別々に考えて計算する必要があった。

数列Aの中で発生する転倒数をtento1とすると、
$tento _ 1 \times K$
となり、

2つの数列A間で発生する転倒数をtento2とすると、
$tento _ 2 \times (K \times (K-1)) \div 2$
とすることができる。
$(K \times (K-1)) \div 2$ は組み合わせの公式。K個の中から2つ選んだときの組み合わせ数を求めている。

上記２つの結果を足したものがが答えとなる。 ( $tento _ 1$ と $tento _ 2$ はループなどで数える。 )

(時間外の)自分の回答

N,K=list(map(int, input().split()))
A=list(map(int, input().split()))
 
MOD=10**9+7
 
def count(A,N):
    arr=[0]*N
    for i, ai in enumerate(A[:-1]):
        cnt=0
        for aj in A[i+1:]:
            if ai > aj:
                cnt+=1
        arr[i]=cnt
    return arr
 
s1=sum(count(A,N))
s2=sum(count(sorted(A,reverse=True),N))
v=K*(K-1)//2
print((s1*K+v*s2)%MOD)