Tenka1 Programmer Contest 2019 E Polynomial Divisors

面白かったので。
解けてもおかしくなかった。めっちゃ苦戦したけど。

問題はこれ
E - Polynomial Divisors

ポイントはフェルマーの小定理と、N 次方程式の根の個数。

解説の準備

フェルマーの小定理

 p素数とする。任意の  p の倍数でない整数 x に対して、

 x^p = 1\, mod\, p

となる。

以下、 \mathbb{Z}/p\mathbb{Z} = \{0 \, mod\, p , \ldots, p-1\, mod\, p\} とかく。

群論を使った簡単な証明:

 |\mathbb{Z}/p\mathbb{Z}| = p-1 と「有限群の各元の位数は、その群の位数の約数」から従う。

 N 次方程式の根は高々  N 個以下

整域ならよい。つまり、普通に思いつくものはだいたいよい。

解説

 p素数とする。
 f(x) = \sum_{i=0}^N a_i x^i とする。
ただし、 a_N \neq 0 とする。

 p \geq N+1 のとき

任意の  i に対して、 A[i%p = 0] であればよい。

というのも、N 次方程式は、 \mathbb{Z}/p\mathbb{Z} 内に高々  N 個しか根を持たないが、
  \mathbb{Z}/p\mathbb{Z} の元の個数は、 p 個なので、
 f は、恒等的に  0 でなければならない。

今回は、 a_N 0 でないことを使って、その約数を見ることにする。

 p \leq N のとき

上の場合の条件でも、もちろん成立する。
今からの議論はその場合も含む。

まず、
 f x を因子に持たないといけないので、
 a_0 = 0\, mod \, p でなければならない。

というわけで、 a_0 = 0\, mod \, p の場合のみを考えれば良い。
つまり、残りの  mod\, p 0 でない整数 x だけ調べれば良い。

フェルマーの小定理を思い出す。
すると、 x^{p-1} = 1 になるので、
 f は次のように言い換えて良い。

 0 \neq x \in \mathbb{Z}/p\mathbb{Z} p の倍数でない整数  x )に対して、

 f(x) = \sum_{i=0}^N a_i x^{i\, mod\, (p-1)} =: g(x)

となる。

これは、 (p-2) 次方程式なので、根を高々  (p-2) 個しか持たない。
 f 0, 1, \ldots, p-1 を根に持たなければならない。
 0 は除外して考えているので、
まとめると、
 g は根を少なくとも  (p-1) 個持たなければならない。

そういうものは、恒等的に  0 であるようなものしか存在しない。
というのも、根の数を見れば、矛盾が見える。

ちなみに、
 a_00 でなければ a_0 の素因数だけを見ればよいが、
めんどくさいので、 N 以下の素数全てを調べている。

解答

def factors(z):
    ret = []
    for i in range(2, int(z**(1/2))+1):
        if z%i == 0:
            ret.append(i)
            while z%i == 0:
                z //= i
    if z != 1:
        ret.append(z)
    return ret

def eratosththenes(N):
    if N == 0:
        return [0]
    work = [True] * (N+1)
    work[0] = False
    work[1] = False
    for i in range(N+1):
        if work[i]:
            for j in range(2* i, N+1, i):
                work[j] = False
    return work


N = int( input())
A = [ int( input()) for _ in range(N+1)]
E = eratosththenes(N)
Primes = [ i for i in range(N+1) if E[i] == 1]
ANS = []
F = factors( abs(A[0]))
for f in F:
    if f >= N+1:
        Primes.append(f)
for p in Primes:
    if p >= N+1:
        check = 1
        for i in range(N+1): # f が恒等的に 0 であるかどうかのチェック
            if A[i]%p != 0:
                check = 0
                break
        if check == 1:
            ANS.append(p)
    else:
        poly = [0]*(p-1)
        for i in range(N+1): # フェルマーの小定理
            poly[(N-i)%(p-1)] = (poly[(N-i)%(p-1)] + A[i])%p
        check = 0
        if sum(poly) == 0 and A[N]%p == 0: # a_0 が 0 かつ、g が恒等的に 0 であることをチェックしている
            check = 1
        if check == 1:
            ANS.append(p)
for ans in ANS:
    print(ans)

おまけ

計算量の話。
エラトステネスは  O(N \log(\log(N))) です。
調べる素数の個数と、fg に整理するときの  N の積だけ必要で、
これが支配的です。
というわけで、計算量は

 O(N \log(N) + N (N \mbox{以下の素数の数})) = O(N^2/\log(N))

になる。等号は素数定理
ほんで、 10^4 以下の素数の個数は、 1229 個。

つまり、
 10^7 くらい。

python だと間に合わなくて、pypy で間に合った。

Tenka1 Programmer Contest 2019 D Three Colors

Tenka1 Programmer Contest 2019 に参加した。

C しか解けなかった。
D の Three Colors が解けそうで解けなかったので、その解説。
問題はこれ
D - Three Colors

解説

ほぼほぼ公式解説の通りだけどね。
 S = \sum_{i=1}^N a_i とする。
三角形の最長の辺が S/2 以上だと、正の面積を持つ三角形にならない。
そうでないものが求めるもの。
R が最長辺と仮定して良い。
そうすると、その 3 倍が求めたいものです。
ここで、2 辺が S/2 に等しい場合をダブルカウントしてしまっていることに注意。
細かいことはプログラムの中に書く。
ちなみに、pypy じゃないと通らなかった。

解答

Q = 998244353
N = int( input())
A = [ int( input()) for _ in range(N)]
S = sum(A)
H = (S+1)//2
dp = [0]*(S+1)
dp[0] = 1
for a in A:
    for s in range(S, a-1, -1):
        dp[s] = (dp[s]*2 + dp[s-a])%Q #dp[s]*2 はR以外においた場合の数。GとBに置く2通りがある。
    for s in range(a-1,-1,-1):
        dp[s] = dp[s]*2%Q
ans = (pow(3, N, Q) - sum(dp[H:])%Q*3%Q)%Q
if S%2 == 0:#R=G=S/2となる場合を数える。
    dp = [0]*(S+1)
    dp[0] = 1
    for a in A:
        for s in range(S,a-1,-1):
            dp[s] = (dp[s] + dp[s-a])%Q
    ans += dp[H]*3 #R=G=S/2, R=B=S/2, B=G=S/2の3通りがあるので
    ans %= Q
print(ans)

yukicoder No.811 約数の個数の最大化

yukicoder contest 210 に参加した。
A、Bしか解けなかった。
Cは面白い問題だと思ったけど、解けなかった。
というわけで、C の問題はこれ。
No.811 約数の個数の最大化 - yukicoder
解答を見て、なるほどってなったので解説を書く。

解説

ポイントは、自然数  N 以下の自然数全ての約数と素因数の個数を求めるのは、高々  O(N\log(\log(N))) でできるってこと。
エラトステネスの篩の要領でやればうまくいく。
言われると書けるけど、思いつかない。
簡単に解説。
まず、N-1 以下の自然数を格納したリスト  Ints := [0, 1, 2, \cdots, N-1]を用意する。
これを前から見ていきながら次の操作をする。
ところで、先に 2.1 を見ると方がわかりやすい。
 i に対して、
1.  Ints[i] 0 であれば、これは合成数である。

 i合成数であるとは、i より小さい素数の積で表される、つまり、
i より小さい素数たちで割り切れる、ということである。

2.  Ints[i] 0 でなければ、これは素数である。
 i素数とは、より小さい素数で割り切れない、ということである。
2.1. 素数  i の倍数 i \times j i で割れるだけ割る。
すると、 i \times j がいくつの  i を素因数に持つかがわかる。
解答中だと、 t-1 がそれにあたる。
更に、これを用いれば、約数の個数も分かる。

あとは、各  N 以下の自然数  i との最大公約数を見て、
その素因数の個数が  K 個以上か見て、その後、約数の個数を見れば良い。

解答

N, K = map( int, input().split())
Ints = [ i for i in range(N)] #エラトステネられる数列
Primefactors = [0]*N #素因数の個数を格納する部分。
Factors = [1]*N #約数の個数を格納する部分。
for i in range(2, N):
    if Ints[i] == 1:
        continue
    for j in range(1, N):
        if i*j < N:
            t = 1
            while Ints[i*j]%i == 0:
                Ints[i*j] //= i
                Primefactors[i*j] += 1
                t += 1
            Factors[i*j] *= t
        else:
            break
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return(a)
ans = 1
nowfactors = 1
for i in range(2,N):
    if Primefactors[gcd(i,N)] >= K:
        if Factors[i] > nowfactors:
            ans = i
            nowfactors = Factors[i]
print( ans)

おまけ

計算量の話。

    for j in range(1, N):
        if i*j < N:
            t = 1
            while Ints[i*j]%i == 0:
                ...

のところの計算量。
 N を十分大きな整数とする。
 p素数とする。(別に、素数じゃなくても良い)
 N 以下の数で  p で割り切れるものは、だいたい \frac{N}{p} 個。
 N 以下の数で  p^2 で割り切れるものは、だいたい \frac{N}{p^2} 個。
・・・・・・・・
というわけで、
ここの計算量は、
 \sum_{k=1}^\infty \frac{N}{p^k} \approx \frac{N}{p-1}
くらい。
自然数の逆数の和のオーダーは  O(\log(N))
今回は素数のみでこの操作を行うことを考えれば、もう少し小さくて、
 O( \log(\log(N))) になる。
Primefactors と Factors を求める計算量は、 O( N\log(\log(N))) になる。

エクサウィザーズ 2019 E Black or White

エクサウィザーズ 2019 E Black or White の解説。

コンテスト中に解けたのが嬉しかったので、ついでに解説を書く。

問題はこれ
E - Black or White
解説はこれ
https://img.atcoder.jp/exawizards2019/editorial.pdf

解説

まず、 i 回目までに  B 個の黒が全て出る確率 b_i を求める。
これは、 k ( \leq i) 回目で最後の黒が出る確率の和になる。
k回目に、最後の黒が出る場合の数は、 k-1 回目までに黒がちょうど B-1 回出る数に等しい。
つまり、 \binom{k-1}{B-1} になる。
また、 k ( < B) 回目までで黒が全て出ることはない。
まとめると、
 b_i = \begin{cases}\sum_{k = B}^{i} \frac{\binom{k-1}{B-1}}{2^k} & (i \geq B)\\ 0 &(i < B)\end{cases}
となります。

同様に、 i 回目までに  W 個の白が全て出る確率 w_i は、
 w_i = \begin{cases}\sum_{k = W}^{i} \frac{\binom{k-1}{W-1}}{2^k} & (i \geq W)\\ 0 &(i < W) \end{cases}
で与えられます。

では、i 回目に黒が出る確率を求めます。
これは、i 回目の操作を行う前に黒と白がそれぞれ少なくとも1つあれば、
 (i-1\mbox{回目の操作の後、白と黒が少なくとも1つある確率})\times \frac{1}{2}
になります。
(i-1回目の操作の後、白と黒が少なくとも1つある確率)
は、i-1 回目の操作の後、黒または、白が出尽くしているわけではないと言い換えられるので、
1 - b_{i-1} - w_{i-1}
となります。
白または、黒しか無い場合は黒しか見る必要がないので、
 w_{i-1}
となります。これは、i-1回目までに白が全部出ていれば、残りは黒しか出ないためです。
というわけで、i 回目に黒が出る確率は、
(1 - b_{i-1} - w_{i-1})\times \frac{1}{2} + w_{i-1}
となります。
後は、頑張って実装します。

解答

Q = 10**9+7
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

B, W = map( int, input().split())
Z = getInv(B+W)
I = [1]*(B+W+1)
for i in range(1,B+W+1):
    I[i] = (I[i-1]*Z[i])%Q

F = [1]*(B+W+1)
for i in range(1,B+W+1):
    F[i] = F[i-1]*i%Q
w = 0
b = 0
for i in range(1,B+W+1):
    if i - 1 < B and i - 1 < W:
        print(I[2])
    elif i - 1 >= W and i - 1< B: #i > B
        w += F[i-2]*I[i-1-W]%Q*I[W-1]%Q*pow(I[2],i-1,Q)%Q
        w %= Q
        print(((1 -  w)%Q*I[2]%Q + w)%Q)
    elif i - 1 >= B and i - 1 < W: #i > W
        b += F[i-2]*I[i-1-B]%Q*I[B-1]%Q*pow(I[2],i-1,Q)%Q
        b %= Q
        print((1-b)%Q*I[2]%Q)
    else:
        w += F[i-2]*I[i-1-W]%Q*I[W-1]%Q*pow(I[2],i-1,Q)%Q
        w %= Q
        b += F[i-2]*I[i-1-B]%Q*I[B-1]%Q*pow(I[2],i-1,Q)%Q
        b %= Q
        print(((1 -  w - b)%Q*I[2]%Q + w)%Q)
おまけ

mod の逆元を求める記事書いたと思ったけど、書いてなかった。

Go 入門前

golangdebian にインストールした。

version

1.12.1 linux-amd64

手順

wget https://dl.google.com/go/go1.12.1.linux-amd64.tar.gz
tar -xvf go1.12.1.linux-amd64.tar.gz
sudo mv go /usr/local

次を、~/.bashrc に追記する。

# golang
export GOROOT=/usr/local/go
export GOPATH=$HOME/go
export PATH=$PATH:/usr/local/go/bin

トポロジカルソート

トポロジカルソートの勉強をした。

もともとの目的は EDPC ( Educatiocal DP contest ) の G. Longest Path を解くためにやった。

これ
G - Longest Path

トポロジカルソートとは

いい感じに有向グラフの頂点の番号付けを変える操作。
いい感じっていうのは、前から後ろに自然に流れているみたいな。
wikipedia を見てほしい。これ
トポロジカルソート - Wikipedia

実装する

参考になったのは、
上に書いた wikipedia と、
トポロジカルソート - Thoth Children
Kahn の方法ってやつで書いたつもり。

有向非巡回グラフの場合にやる。
一言で言うと、
入力辺の無い頂点と、それに付随する辺を除く、ことを繰り返す
ということ。

S を deque とします。
python なら list で十分です。
C++ なら deque 使わないとやりにくい気がする。
S には入力辺が無い頂点を格納する。

T を空リストとする。
最終的にこれがトポロジカルソートの結果を格納する。

1. V を  V[i] := \sharp\{\mbox{入力辺の本数}\} というリストを作る。

2. 入力辺の無い頂点を S に格納する。

3. 次の操作 4--6 を繰り返す。

4. S の前方から 頂点 s を一つ取り出し、T の後方に格納する。

5. 次の操作 6 を繰り返す。

6. s から出ている辺を除く。これに伴い、V の値が更新される。これが 0 になった頂点を新たに、S に追加する。

実装 ( python )

AOJ のトポロジカルソートへの解答の形で書いてある。
これ
トポロジカルソート | グラフ | Aizu Online Judge

def topologicalsort(N,E):
    V = [0]*N
    for i in range(N):
        for y in E[i]:
            V[y] += 1
    S = [ i for i in range(N) if V[i] == 0]
    SORTED = []
    while S:
        s = S.pop(0)
        SORTED.append(s)
        for t in E[s]:
            V[t] -= 1
            if V[t] == 0:
                S.append(t)
    return SORTED
    
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
for _ in range(M):
    x, y = map( int, input().split())
    # x, y = x-1, y-1
    E[x].append(y)
ANS = topologicalsort(N, E)
for i in range(N):
    print(ANS[i])

EDPC G

python

これ python は通るけど、pypy は TLE する。
ナンデ???

def topologicalsort(N,E):
    V = [0]*N
    for i in range(N):
        for y in E[i]:
            V[y] += 1
    S = [ i for i in range(N) if V[i] == 0]
    SORTED = []
    while S:
        s = S.pop(0)
        SORTED.append(s)
        for t in E[s]:
            V[t] -= 1
            if V[t] == 0:
                S.append(t)
    return SORTED
    
N, M = map( int, input().split())
E = [ [] for _ in range(N)]
for _ in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    E[x].append(y)
V = topologicalsort(N, E)
ANS = [0]*N
for i in range(N):
    v = V[i]
    t = ANS[v]+1
    for e in E[v]:
        if t > ANS[e]:
            ANS[e] = t
print( max(ANS)) 
C++
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <algorithm>
#include <climits>
#include <deque>
using namespace std;
typedef long long int ll;
#define all(x) x.begin(),x.end()

int main()
{
  int N, M, x, y, s, l;
  cin >> N >> M;
  int V[N];
  vector<int> E[N], T;
  deque<int> S;
  for (int i = 0; i < N; ++i) {
    V[i] = 0;
  }
  for (int i = 0; i < M; ++i) {
    cin >> x >> y;
    x--; y--;
    E[x].push_back(y);
    V[y] += 1;
  }
  for (int i = 0; i < N; ++i) {
    if (V[i] == 0) {
      S.push_back(i);
    }
  }

  while (S.size()) {
    s = S[0];
    S.pop_front();
    T.push_back(s);
    l = E[s].size();
    for (int i = 0; i < l; ++i) {
      V[E[s][i]]--;
      if (V[E[s][i]] == 0) {
        S.push_back(E[s][i]);
      }
    }
  }
  int ANS[N];
  for (int i = 0; i < N; ++i) {
    ANS[i] = 0;
  }
  int v, t;
  for (int i = 0; i < N; ++i) {
    v = T[i];
    t = ANS[v] + 1;
    l = E[v].size();
    for (int j = 0; j < l; ++j) {
      if (t > ANS[E[v][j]]) {
        ANS[E[v][j]] = t;
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < N; ++i) {
    if (ans < ANS[i]) {
      ans = ANS[i];
    }
  }
  cout << ans << "\n";
  return 0;
}

単語帳から問題をランダムに出力する

正確に言うと、単語帳の単語をランダムに問題として出力してくれるプログラムをpythonでかいた。

strip()

が便利だった。

説明

./tangocho.org

というファイルを読むことにする。

path = "./tangocho.org"

とする。

中身は

| apple  | りんご |
| tomato | トマト |

という感じ。

fileを読む
with open(path) as f:
    X = f.readlines()

とすると、[tex: X} にファイルがリストとして入る。

split

指定した語で文字列を分割する。
何も指定しなければ、半角スペースで分割する。
例えば、

s = "| apple  | りんご |"

として

s.split("|")

とすると、

['', ' apple  ', ' りんご ', '']

と出力される。

リスト内包表記
[ i for i in range(10) if i%2 == 0]

とすると、

[0,2,4,6,8]

となる。

strip

ある文字列の改行とか空白を除去してくれる。

ここまでのまとめ
with open(path) as f:
    tangos = [ [s.strip() for s in t.split("|") if s.strip()] for t in f.readlines()]

とすると、

[["apple", "りんご"], ["tomato", "トマト"]]

となる。

まとめ

上記のようなリストが作れればあとは、random を使ってランダムに出力できるようにすればいい。

結果的に次のようなものになる。

from random import randint
print("org fileを指定してください")
path = input() #pathを指定する。例えば、tangocho.orgみたいな
with open(path) as f:
    tangos = [ [s.strip() for s in t.split("|") if s.strip()] for t in f.readlines()]
n = len(tangos)
# print(tangos)
while 1:
    eigo, nihongo = tangos[randint(0,n-1)]
    print(eigo, end = " ")
    if input(): #なにも入力しなければ、そのまま問題が出続ける。何か入力すれば終了する。
        print(nihongo)
        break
    print(nihongo)
    print("")