2021-02-17

AtCoder 東京海上日動プログラミングコンテスト2020 E - O(rand)

問題解説

atcoder.jp 公式解説がわかりにくかったので自分なりに書いてみます。

問題概要

$A_1,A_2,...,A_N$ が与えられます。
ここから重複なく $1$ ～ $K$ 個選び、下記の条件を満たす方法は何通りあるか求めよ。
・選んだ数の論理積が $S$
・選んだ数の論理和が $T$

制約

$1 \leq K \leq N \leq 50 \\ 0 \leq A_i, S, T < 2^{18} \\ A_i \neq Aj$

方針

$S,T$ に関する問題の単純化
数え上げ方針の検討
数え上げの実装

1. $S,T$ に関する問題の単純化

まず $S,T$ について観察します。
各ビットごとに見たとき、 $S$ の $i$ 桁目が $S_i$ 、 $T$ の $i$ 桁目が $T_i$ だったとします。
すると、下記の場合分けができます。
① $(S_i,T_i) = (0,0)$
→　選んだ数は全て $i$ 桁目が0でなくてはならない。

② $(S_i,T_i) = (0,1)$
→　選んだ数の $i$ 桁目に0,1両方が混ざっている必要がある。

③ $(S_i,T_i) = (1,0)$
→　このような選び方は存在しない。
　　→　この組み合わせがあった場合は答えが0通りで確定

④ $(S_i,T_i) = (1,1)$
→　選んだ数は全て $i$ 桁目が1でなくてはならない。

③はなかったものとして、①と④を考えると、
$i$ 桁目の数字に着目することで選ぶことのできない数字を取り除くことができます。

例えば入力例2を見ると、これは1桁目が④、2,3桁目が②、4桁目以降が①になっている例です。

$S = 1 \\ T = 7 \\ A = \{3,4,9,1,5\}$

よって、1桁目が1ではない $A_2 = 4$ は使うことができません。
同様に、4桁目が0ではない $A_3 = 9$ も使うことができません。
逆にいうと、それ以外の数字を使えば1,4桁目の条件はいつでも満たすことができます。

以上のことから、使える数字だけを選定し、②以外の桁を右に詰めてしまうことにしましょう。
先の入力例2は下記のように変わります。

$S = 0 \\ T = 3 \\ A = \{1,,,0,2\}$

このような前処理をすることで、問題を下記のように言い換えることができました。

$S=0,T=2^ L-1,0 \leq A_i \leq 2^ L$ として、1～ $K$ 個の数を選ぶ。
各桁ごとに選んだ数のビットが0か1かをカウントしたとき、全ての桁で0,1両方が1回以上出現しているような選び方は何通りか
※ $L$ は②を満たす桁の数

2. 数え上げ方針の検討

ここからが難しいです。
結論から言うと、桁ごとが満たすべき条件に着目し、包除原理を使って解きます。

まず、「全ての桁で0,1両方が1回以上出現しているような選び方」ですが、これは各桁ごとに独立な事象の重ね合わせです。つまり、下記で表現できます。

「1桁目で0,1両方が1回以上出現しているような選び方」
$\cup$ 「2桁目で0,1両方が1回以上出現しているような選び方」
$\cup ...$
$\cup$ 「 $L$ 桁目で0,1両方が1回以上出現しているような選び方」

また、「0,1両方が1回以上出現しているような選び方」は扱いづらいです。
「0だけ」「1だけ」「両方」の3状態を考えないといけないので状態量が $3^ L$ になってしまいます。

ここで、余事象を考えると扱いやすくなります（後述）。
言語化すると「"0だけが出現している"or"1だけが出現している"ような選び方」になります。

すると求める答えは下記に言い換えられます。

「1桁目で"0だけが出現している"or"1だけが出現している"ような選び方」
$\cap$ 「2桁目で"0だけが出現している"or"1だけが出現している"ような選び方」
$\cap ...$
$\cap$ 「 $L$ 桁目で"0だけが出現している"or"1だけが出現している"ような選び方」
の余事象

これで包除原理が使えるような形に持ち込むことができました。

$i$ 桁目が「"0だけが出現している"or"1だけが出現している"ような選び方」を満たしているとき、 $X_i = 1$ 、満たしていてもいなくてもどちらでも良いとき $X_i = 0$ とします。
$X := \{ X_1,...X_L \} | (X_i =0,1)$ を一つ決めたときに、
そのような条件を満たす数の選び方を $f(X)$ で定めます。
$X$ の $2^ L$ 通りの選び方全体を $Y$ とすると、
（包除原理については詳しい説明は省きますが、）答えは下記で求めることができます。

$\Large \Sigma_{X \in Y} \{(-1)^{\Sigma X_i} * f(X) \}$

あとは、 $f(X)$ が求められれば良いです。

3. 数え上げの実装

余事象を考えると扱いやすくなる、と先ほど述べたポイントです。
$X := \{ X_1,...X_L \} | (X_i =0,1)$ を、 $i$ 桁目が $X_i$ の2進数だと考えます。

例えば $X = \{ 0,1,0,1 \}$ は1010です。
このケースだと、「2桁目で"0だけが出現している"or"1だけが出現している"ような選び方」かつ「4桁目で"0だけが出現している"or"1だけが出現している"ような選び方」の数が $f(X)$ になります。

具体例を見てみましょう。
$f(X)$ は下記の場合分けの合計になります。
・(2桁目,4桁目) = (0,0)
0000,0001,0100,0101 などからいくつか選ぶ方法
→　 $A_i \; and \; 1010 = 0000$ となるような数 $A_i$ からいくつか選ぶ

・(2桁目,4桁目) = (0,1)
1000,1001,1100,1101 などからいくつか選ぶ方法
→　 $A_i\; and \; 1010 = 0010$ となるような数 $A_i$ からいくつか選ぶ

・(2桁目,4桁目) = (1,0)
0010,0011,0110,0111 などからいくつか選ぶ方法
→　 $A_i\; and \; 1010 = 1000$ となるような数 $A_i$ からいくつか選ぶ

・(2桁目,4桁目) = (1,1)
1010,1011,1110,1111 などからいくつか選ぶ方法
→　 $A_i \; and \; 1010 = 1010$ となるような数 $A_i$ からいくつか選ぶ

このようにみると、 $X$ をビットマスクと捉えて、
$A_i$ をマスク処理した後に同値になるグループのサイズがわかれば、 $f(X)$ が計算できることがわかります。
（いくつか選ぶ＝1~K個選ぶ方法の数は二項係数の和で計算できます。）

よって、ビットマスクの値を一つ固定し、 $N$ 個の $A_i$ にそれぞれマスク処理をして、同値になるグループごとに選び方を計算する、という処理をすることでこの問題を解くことができます。

ビットマスクの数が $2^ L$ 、
マスク処理の回数が $N$
1回のマスク処理で $L$ 桁処理する（※）ので、
これらは $O(2^ LLN) \approx O(2.4*10^ 8)$ で計算できます。
※　この処理はbit演算で速い、かつ桁数も少ないので致命的にはならなそう
※※　二項係数の和は $O(N^ 2)$ で事前計算しておきます。（TLE1回）

n,k,s,t = map(int,input().split())
a = list(map(int,input().split()))

# 二項係数の事前計算
fac = [1] * (n+1)
for i in range(1,n+1):
    fac[i] = fac[i-1] * i
com = [[0] * (n+1) for _ in range(n+1)]
for i in range(n+1):
    for j in range(i+1):
        com[i][j] = fac[i] // (fac[j] * fac[i-j])

com_n = [0] * (n+1)
for i in range(n+1):
    for j in range(1,k+1):
        com_n[i] += com[i][j]

# 要らない数、桁の圧縮
use = [-1] * 18
for i in range(18):
    si = (s >> i) & 1
    ti = (t >> i) & 1
    if si == 0 and ti == 0:
        use[i] = 0
    elif si == 0 and ti == 1:
        use[i] = 2
    elif si == 1 and ti == 0:
        print(0)
        exit()
    else:
        use[i] = 1

a2 = []
for ai in a:
    new = 0
    for j in range(17,-1,-1):
        x = (ai >> j) & 1
        if use[j] == 0 and x == 1:
            break
        if use[j] == 1 and x == 0:
            break
        if use[j] == 2:
            new = new*2 + x
    else:
        a2.append(new)

# 包除原理で数え上げ
l = use.count(2) # 圧縮後の桁数
ans = 0
for mask in range(2**l):
    group_cnt = dict()
    for ai in a2:
        masked = ai & mask
        if masked in group_cnt:
            group_cnt[masked] += 1
        else:
            group_cnt[masked] = 1

    pc = bin(mask).count('1')    
    for j in group_cnt.values():
        ans += (-1) ** pc * com_n[j]

print(ans)

感想

余事象に言い換えるところが全く発想になく、 $3^ L$ の世界で悩み続けていました。
もし言い換えができたとしても、包除原理できることに気づく、ビットマスクを使うと $f(X)$ が数え上げられる、なども発想の飛躍があり厳しいです。

ちなみに、公式解説だと計算量 $O(2^ LN)$ となっており、 $L$ を外せるらしいのですが、そこの工夫はよくわかっていません。
余事象に言い換えるところはmaspyさんのブログを参考にしました。

2021-01-27

pythonでatcoderで黄色になりました

はじめまして、くまざきといいます。

いきなりで恐縮ですが、先日atcoderで黄色になりました。

いわゆる色変記事というものを書こうと思います。

f:id:qumazaki:20210126170559p:plain — rate

お品書きです。

自己紹介・バックボーン
黄色になるまで
ライブラリ
その他ポエム

自己紹介・バックボーン

1989年生まれ
2019年8月、競プロ初参加
主にpython,pypyでコンテストに参加
→　numpy,numba,cythonなどは使っていません。
中学受験勢
→　中学受験当時、算数はかなりできる方でした。が、その後の数学は適当です。
　　特に大学以降の数学はサボっていたのでほとんどわかっていません。
パズルや謎解きが好き
→　二コリ系パズルで暇をつぶす日々を過ごしていたのですが、
　　それなら競プロのほうが有意義なのでは？と思ったのが、
　　競プロを始めたきっかけの一つです。
頻度高くないが、一応仕事でプログラミングすることもある
→　データ分析チックな仕事をすることがあり、
　　その際pandasやscikit-learnなどを使ったりしていました。
　　じゃあpythonは完璧かというとそういうわけでもなく、
　　list型とかdict型とかの仕様はあまりよくわかっていなかったです。
始めた時点で競プロ知識はほぼ０

黄色になるまで

f:id:qumazaki:20210126180715p:plain — 推移

初期（～2019年12月）
Twitterの謎解きクラスタでatcoderの話をしている方がおり、
プログラミング＋数学＋パズルみたいなものなら得意分野かなと思って始めました。
得意分野だという読みは外れてはいなかったのですが、世の中にはもっと上がいるのだということにすぐ気づくことになります。

入出力だけのお作法だけ勉強して、特に過去問を解くわけでもなくABC137に出たのが初回で、2完灰パフォでした。
C問題とD問題にも手を出していますが、どちらもTLEしており、この時点では計算量の概念がなかったことが伺い知れます。

その後もうすこし勉強して、数回コンテストに出ています。
この時緑～水パフォでしたので、初期能力はこれくらいだったようです。
2019年は年末にかけて忙しい時期だったため、10~12月はコンテストに参加していません。
水色まで（2020年1~3月）
本格的に競プロ活動を再開し、これ以降ほぼ週1ペースでコンテストに参加しています。
2月からは200日程度streakをつないでいました。

精進内容ですが、そこまでの経験でDPに苦手意識があったので、ひとまずEDPCをやれるとこまでやりました。
atcoder.jp

あとは、仕事で毎週泊りがけの出張をしていた時期があり、
夜ご飯を食べると何もすることがなかったので、ひたすら令和ABCのバチャをやっていたり、蟻本の初級編あたりを読んでみたり。

コンテストでは水パフォが安定するようになっていたので、
しばらく続ければ水色にはなれそうだな、と思っていました。
この辺で「とりあえず黄色」を当面の目標にしようと決めたような気がします。

（水色になったタイミングのatcoder problemsスクショ）

（当時は今よりもだいぶ情報が少なかったですね。）
1800くらいまで（2020年4~5月）
競プロでも急に伸びる時期がある、みたいな話をよく聞きますが、
私もこの時期にrateが伸びました。
ABCで全完したり、黄パフォが出たり、みたいなことが急に発生したりしました。

学んできた競プロ基礎知識がある程度定着して、コンテスト中に発揮できるようになったタイミングだったかな、と思います。

精進内容としては、令和バチャが一通り終わってしまったタイミングで、JOIレベル7埋めに着手した時期です。
自分の競プロ力を見つめなおしたときに、実装力が足りないという感覚があり、下記の記事で実装力向上にJOI過去問が勧められていたので手を出した、という感じです。

qiita.com

JOIの古めの問題はpythonだとTLE,MLEが厳しいものもあり、pythonユーザにはオススメしづらいのですが、逆にそこでいろいろなテクニックを身に着けた感じもします。

あと、勢いでmaspyさん主催の組み合わせ論輪読会に参加したのもこの時期です。
私は参加者の中だとかなり数学レベルが低い方なので、めちゃくちゃ必死に準備して、それでも置いて行かれている感じです。
内容が高度過ぎて、今のところあまりrateに結びついてはいないと思われるのですが、いろいろ知識は増えています。
（ちゃんと知識定着していればrateにつながっていたであろう場面は何度か観測しています。）

（青色になったタイミングのatcoder problemsスクショ）
停滞期（2020年6～11月）
ここから半年ほどrate1700~1850の間で停滞します。
半年もあったのでいろいろな精進をしていました。

「やっぱ黄色になりたかったら黄diffを解くべきだよね」と思って黄diffで40日ほどstreakをつないでみたり、
「ABCで速度負けするし、青diff以下の速度上げよ」と思って平成ABCのバチャをしながら青diff埋めをしたり、
「いや、ARCでパフォ出せた方が強い！」と思ってARCバチャをやってみたり

今考えると迷走していますが、どの営みも悪くはなかったと思っています。
黄色まで（2020年12-2021年1月）
競プロでも急に伸びる時期がある、みたいな話をよく聞きますが、また急にrateが伸びだしたのがこの2か月です。
久々にABCで黄パフォが取れたと思ったら、翌週のARCで橙パフォが出て、これは流れに乗ったな、という感じでした。

何がよかったのかこじつけで考えてみると、下記のような感じでしょうか。
①知識の抜けが減ってきて、～青diffが少ない考察で倒せるようになってきた
→　ABCの速度負けが減り、パフォが安定
②相性の良い黄diffなら短い時間（30~60分）で処理できる力がついてきた
→　ARC級で黄パフォoverが出せるケースが発生した

停滞期は「青を安定させるか」「黄以上を解くか」で悩んでいたのですが、結局両方やればよかったということですかね。

というわけで、先日のキーエンスコンでめでたく黄色になれました。

（黄色になったタイミングのatcoder problemsスクショ）

ライブラリ

個人的に、色辺記事には持っているライブラリの情報が記載されていると嬉しいと思っており、それ故に手持ちのライブラリを書きます。
→　参加者の大半が持っているライブラリを持っていないとすれば、該当する問題が出た際にかなりのハンデとなるため、把握しておきたいという気持ちです。

うろ覚えですがざっくりの作った時期などの情報を併記します。
→　◎：水色まで　○：青まで　★：コンテスト未使用

ACL移植を除けば、決して多く持っている方ではないのでは？と思っていますがどうなのでしょうか。

ACL（Atcoder Library）以外
■データ構造系
◎　UnionFind木
◎　segment tree（最小値・最大値のみ）

BITはACL移植をするまで持っていませんでした。先にセグ木を履修すると要らないと思ってしまいます。
最近はセグ木はACL移植のものを使っています。抽象化は慣れるまで大変ですが、慣れるとかなり便利に感じます。

■グラフ系
◎　ダイクストラ
◎　ベルマンフォード（★）
◎　ワーシャルフロイド
◎　rerooting
○　LCA（★）

BSF,DSFはいろいろな場面・用途で使うのでライブラリにしておらず、その場で都合の良いものを書いています。
LCAも毎回書いていたのですが、さすがに面倒だと思って最近ライブラリにしました。が、その後利用場面に出くわしていません。

rerootingは一時期ABCで出ていたイメージがあり、都度書くのはつらかったのでライブラリにしました。が、ここ半年以上見かけていない気がします。

グラフは入力から様々な関数を一つにまとめた汎用関数・クラスを作って持っている方もいるそうなのですが、そこまで手を出していません。
また、グラフ系は、pythonユーザの場合networkxを使うのも十分選択肢だと思います。が、私はpypyメインなので使っていません。

■素数・素因数など
◎　素因数分解
◎　約数列挙
◎　エラストテネスの篩（奇数だけ見て高速化）
◎　エラストテネスの篩（区間l-rの間の素数を列挙するもの）（★）

■その他
◎　bitDPでの部分集合列挙
◎　二項係数算出（前処理o(N), クエリO(1)）
〇　転倒数算出（★）

二項係数の計算は頻出で、無いと戦えないので、ACLにも含まれていてよいのでは？と思っています。
また、以上の他に、入力とよく使うパッケージのimport文については、すぐコピペできるようにまとめてあります。
ACL移植
全部青になった以降の作成です。
セグ木以外は使ってないです。

〇　convolution（★）
〇　fenwicktree(BIT)（★）
〇　segtree / lazysegtree
〇　scc（★）
〇　twosat（★）
〇　string（★）
〇　maxflow（★）
〇　math（★）

コンテストではほとんど使えてないですが、「万が一出たときに持っていないと著しく不利になる」「アルゴリズム読むと勉強になる」の観点から、pythonユーザの方は積極的に移植したらいいと思っています。

ちなみに、進行形で細々と移植作業を進めていて、残りの大物はmincostflowぐらいになっています。一方、現時点で「pypy向け」＆「完了済」の公開移植PJが無いようなので、移植完了後、需要があれば公開するかもしれません。

その他ポエム

かなり長文になってきたので簡潔に。今後の目標など書きます。

黄色になったタイミングでコンテストを卒業する案もあったのですが、もう少しくらいはrateが伸ばせそうな感触があるので、当面は2200を目標にARC・AGCに参加していこうと思います。

それとは別に、python,pypyユーザ向けのtipsなどを発信できるといいのかな、と考えています。（今回ブログを作ったのもその辺が目的だったりします。）

https://atcoder-circles.herokuapp.com/circles/pythonista

上記のサイトによればpython,pypy使いで現在（2021年1月27日時点）黄色以上になっている人数は36人しかいません。
言語を絞らなければ黄色overは1000人以上いるので、全体の1/30程度だということになります。

一方、これより低いrate帯だと、相対的なpythonユーザはもっと多いです。
元々競プロガチ勢はC++を選択するのでしょうがない傾向ではあるのですが、C++以外の教材・情報が少ないこともこの一因かと思っています。

一昔前は「pythonだと〇色は無理」みたいな発言もあったようですが、最近ではmaspyさんがその反証をどんどん進めてくださっていますし、python界隈を盛り上げるために私もなんらか貢献できるといいな、という感じです。

qumazakiのブログ

pythonで競プロをしています。

AtCoder 東京海上日動プログラミングコンテスト2020 E - O(rand)

問題概要

制約

方針

1. $S,T$ に関する問題の単純化

2. 数え上げ方針の検討

3. 数え上げの実装

感想