ヘッダファイルを含めて実行する

忘れないように。
簡単のため、関数などを書いたソースファイル及びヘッダファイルを

source.c source.h

、この関数を使ったソースファイルを

main.c

とする。

これをコンパイルして、

main.exe

と名付ける。

次をやればよい。

gcc -o main.exe source.c main.c

AGC028 B問題

AtCoder Grand Contest 028のB問題を解いた。
時間内には解けなかったし、解説もよくわからなかった。
問題はこれ
B - Removing Blocks。
解説はこれ
https://img.atcoder.jp/agc028/editorial.pdf。
参考にしたのはこれ
AGC028 B問題 Removing Blocks - banbooooのブログ。

解説

解説でよく使われる確率を理解できたことが殆どなかった。
今回もそれ。
いろいろ調べてたら上の参考サイトを見つけた。
解説などに置ける、同様に確からしい確率は確率を表しているわけでなく、
背反な事象でそれぞれの個数が等しいもののことを言っているということがわかった。
数学っぽく言うと、数え上げ測度の等しい disjoint な可測集合たちのことを言っていることがわかった。
とはいえ、確率の気持ちで理解するのは大事っぽい。
同様に確からしいっぽい気持ちで考える問題もよく見る。

解説をします。
i番目のブロックを取り除いたとき、j番目のブロックの値が加算されるとする。
i番目からj番目までのブロックがどれも除かれておらず、その中で、i番目のブロックが初めに取り除かれる場合の数を求めれば良い。

が成り立つ。
互いに排反なので、

となる。
また、（同様に確からしいの部分だが、）各に対して、

は等しい。
従って、どのに対しても、

となる。
特に、今はの場合である。
あとは、色んなサイト書いてあるように、累積和とかmodにおける逆元とか頑張ればできる。
プログラムは次のやつ。

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

from itertools import accumulate
N = int( input())
A = list( map( int, input().split()))
Q = 10**9 + 7
fact = [1]*(N+1)
invs = getInv(N)
accI = [0]*(N+1)
for i in range(N):
    fact[i+1] = fact[i]*(i+1)%Q
    accI[i+1] = (accI[i]+invs[i+1])%Q
factN = fact[-1]
ans = 0
for i in range(N):
    C = factN*(accI[i+1] + accI[N-i]-1)*(A[i]%Q)%Q
    ans += C
    ans %= Q
print(ans)

ARC094/ABC093 D問題を解いた

めっちゃ調べて、なるほどって言いながら解いた。
解いた問題はこれ
D - Worst Case。
解説がこれ
https://img.atcoder.jp/arc094/editorial.pdf。
解説はよくわからなかったので、これ
AtCoder ARC 094 D - Worst Case (700 点) - けんちょんの競プロ精進記録
を参考にして解いた。
これを読むと、元の解説でなんであんなことをしているかも理解できる。

解説

最大となる組み合わせは、1,2,...,xと1,2,...,xという頂点を逆順で組み合わせることで得られることが分かる。
途中に存在するであろうA, Bを飛ばす必要があるため、解答はx-1である。

1, 2, ..., x-1, x
x, x-1, ..., 2, 1

このとき、この最大値は

(x+1)//x * (x+1 - ((x+1)//2))

である。
感覚的に

x//2 * (x - x//2)

だと思っていたので、めっちゃ混乱した。

ここで、B = A + nであるとすると、最大はA*(A+(n-1))以上になることが分かる。
n >= 1であれば、（AとBが異なることに注意すると）積の最大値はA.Bを飛ばしても実現されることが分かる。

A=Bのときはよくわからない。
というわけで、そこは別で扱うことにする。

Q = int( input())
def matching(A,B):
    #最大となる組み合わせは、1,2,...,xと1,2,...,xという頂点を逆順で組み合わせることで得られることが分かる
    #このとき、これらの積の最大値は(x+1)//2*(x+1-(x+1)//2)である
    #ここで、B = A + nであるとき、最大はA*(A+(n-1))以上になることが分かる。
    #n >= 1であれば、積の最大値はA.Bを飛ばしても実現されることが分かる。
    if A == B:
        return 2*A - 2
    S = A*B
    L, H = 0, A*B
    while H - L != 1:
        M = (L+H)//2
        if ((M+1)//2)*(M + 1 - (M+1)//2) < S:
            L = M
        else:
            H = M
    return L-1 #L-1なのは、A,Bを飛ばすため
for _ in range(Q):
    A, B = map( int, input().split())
    print( matching(A,B))

ABC056 D

写経して、通したが、そのコードに反例があったので、メモ。
pythonでやたら速いやつに対する反例。
Submission #3336978 - AtCoder Beginner Contest 056。

5 12
6 4 3 2 1

答えは0だけど、1が出力される。

ABC057 D問題を解いた。

AtCoder Beginner ContestのD問題を解いた。
問題はこれ
D - Maximum Average Sets。
解説はこれ
https://atcoder.jp/img/abc057/editorial.pdf。
今回は問題自体の話ではなく、Counterのfor文の挙動がバージョンによってかなり違うということ。
次のコードを実行してみる。

from collections import Counter
V = list( map( int, input().split()))
CV = Counter(V)
for x in CV:
    print(x)

入力はこれ。

2 1 1 3 5 4 4 4 

AtCoderで使われているpython3.4.3だと

1
2
3
4
5

ってなる。
python3.6.0以降だと、

2
1
3
5
4

ってなる。

つまり、pytho3.6.0より前だと、数字の小さい順に出てきて、python3.6.0以降だと、listに出ていた順ででてくる。
次のWandboxに同じコードで実験できるようにしている。
[Wandbox]三へ( へ՞ਊ ՞)へ ﾊｯﾊｯ。

AtCoderで通らなかったコードは次。正しいはず。

from math import factorial
from collections import Counter
def combination(a,b):
    if a < b:
        a, b = b, a
    comb = 1
    for i in range(b):
        comb *= a-i
    comb //= factorial(b)
    return comb

N, A, B = map( int, input().split())
V = list( map( int, input().split()))
V.sort( reverse = True)
print( sum(V[:A])/A)
CV = Counter(V)
ans = 0
K = CV[ max(V)]
if A <= K:
    for i in range(A, min(K, B)+1):
        ans += combination(K, i)
else:
    cnt = A
    for x in CV:
        if cnt <= CV[x]:
            ans += combination(CV[x],cnt)
            break
        else:
            cnt -= CV[x]
print(ans)

AtCoderで通るようにしたもの。Counterを使いたかった。

from math import factorial
from collections import Counter
def combination(a,b):
    if a < b:
        a, b = b, a
    comb = 1
    for i in range(b):
        comb *= a-i
    comb //= factorial(b)
    return comb

N, A, B = map( int, input().split())
V = list( map( int, input().split()))
V.sort(reverse = True)
print( sum(V[:A])/A)
S = list( set(V))
S.sort(reverse = True)
CV = Counter(V)
ans = 0
K = CV[S[0]]
if A <= K:
    for i in range(A, min(K, B)+1):
        ans += combination(K, i)
else:
    cnt = A
    for x in S:
        if cnt <= CV[x]:
            ans += combination(CV[x],cnt)
            break
        else:
            cnt -= CV[x]
print(ans)

Visual Code studioを導入して、C++の環境を整えた

タイトル通り、Visual Code Studioを導入して、拡張機能としてC/C++ ConfigurationとClang command adapter configurationを入れた。
基本設定は

C-,

で、設定できる。大体GUIでできる。

ターミナルから起動するには

code

でできて、

code ./

でカレントディレクトリをプロジェクトにして開くことができる。

code ./hoge.cpp

で、
hoge.cppを開けるらしい。

コマンドが全然わからないので、覚えていく。

C-n

で新規ファイルを開く。

C-s

で名前をつけて保存。めんどいな。

ARC036 D問題

AtCoder Regular ContestのD問題を解いた。
問題はこれ
D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder。
解説はこれ
AtCoder Regular Contest 036 解説。
書いてみたら、最後のテストケースだけREになって、なんでや！ってなって、調べた。
あった。
蟻本初級編攻略 - 2-4 Union Find木 後編 - Arantium Maestum
これによると、union-findで無限ループに陥ることがあるらしい。
この修正は、感覚的には、木treeの辺に向きがあると思って、その向きを数の大きい方が小さい方に揃えるイメージ。
そうすると、サイクルができない。

def find(A,x):
    p = A[x]
    if p == x:
        return x
    a = find(A,p)
    A[x] = a
    return a
 
def union(A, x, y):
##    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    if find(A,x) > find(A,y):
        bx, by = find(A,y), find(A,x)
    else:
        bx, by = find(A,x), find(A,y)

    bx, by = sorted([find(A,x), find(A,y)]) # bx, by = find(A,x), find(A,y)だと無限ループ。
    A[y] = bx
    A[by] = bx

N, Q = map( int, input().split())
V = [ i for i in range(2*N)]
for _ in range(Q):
    w, x, y, z = map( int, input().split())
    x, y = x-1, y-1
    if w == 1:
        if z%2 == 0:
            union(V,x,y)
            union(V,x+N,y+N)
        else:
            union(V,x,y+N)
            union(V,y,x+N)
    else:
        if find(V,x) == find(V,y):
            print('YES')
        else:
            print('NO')

おまけ

##のsortedを使うより、if文で書いたほうが倍ぐらい速かった。
関数を呼び出さないほうが速いっぽい。
defも然り。