#ぼやき
最近はやりのAtCoder、僕も初めてみたんです。
それでね、先週ABC191から初参戦してみたわけですよ。
もうね無理、文章の理解すらできない。
ギリギリ頑張って調べながらABだけできたけど、それ以降は何聞かれているかもわからない。
それで、もう初めて１回目で限界を感じてしまい、それでもあきらめきれず過去問に手を出し始めるわけですよ。
やっぱりABC190のCが解けない（泣
解説動画見たらC++とかいう古の言語で書かれててなにがかいてあるかもよーわからんしもう俺無理だ数学の教養ない俺は一生灰色止まりの底辺プログラマにしかなれないんだよ...
せめてpythonとか初心者がプログラミング入門で触りやすいわかりやすい奴で書いてよぉ...
そんな人いっぱいいるでしょ。いるよね？
僕みたいに中学からスポーツだけやってて算数と英語は昔から2ばっかりで受験戦争も一度も経験せず勉強さぼりにさぼって推薦で文系Fラン大学を卒業してIT就職した人いるよね。
いや、ここまで教養底辺の人はいないと思う。
だって俺が数学で最後にやった記憶があるの解の公式とかだよ？いや、ぎりぎりlogは触った気がするけどあきらめて授業全部寝てた気がするくらいよ？
はい、そんな僕がですね、先週の休日全部使って今日も有給使ってやっとABC190のCを解いたのよ。
いや、正確にはその中間に「シティーハンター（フランス映画版）」「舟を編む」をみたりヒトカラしたりABC191に参加したりしていたから本当に三日かかったわけではないんだけど、まぁもうだいたい3日よ、3日かかって知り合いの緑コーダーや青コーダーに聞いて強そうな人の解答もみてやっと理解できたから、解説しますよ！
もうね、本当に数学力0の僕が1から調べてやっとどういう思考で解けるのかというのを理解したので、きっと誰でも理解できると思う！僕の日本語が読めれば！理解できなかったらそれは僕の責任だ！ごめん！
理系のつよつよコーダー諸君は、糞雑魚文系がきたらこれくらい全部解説してあげないとだめなんだなということを理解して引き続き糞雑魚文系の指導に当たってほしいと思う。
ぼやき、以上
解説
この解説は問題と本記事のコード・コメントを見ながら読んでもらう想定です。
まず問題を読み、どういう内容かを理解してから以下のコード・コメントを読んでもらうとよいと思います。
問題
https://atcoder.jp/contests/abc190/tasks/abc190_c
僕の解答（コメント抜き）
https://atcoder.jp/contests/abc190/submissions/20057912
資料（２進数と１０進数の変換サイト）
https://hogehoge.tk/tool/number.html
#（このあたりのとっかかりは大体解説動画の受け売り）
#ぱっと見上手いやり方が見つからないので、多項計算（係数を含まない）ではなく、何らかの係数を使うと考える。
#その場合、Kが最大16と非常に小さいので、これを使って全パターン検索を行うことをめざす。
#つまり、それぞれの人間K人がCとDどちらを選んでボールを置いたかというパターンを１つずつすべて検証し、それぞれがいくつ条件を満たすかをカウントする。
#K人がCとDどちらを選んでボールを置いたかというパターンの数は2のK乗（2^K）個存在する。
#2択の検証であれば0or1で判断できるので、ビット全探索という手法を使う。
#まず変数を受け取る。
#受け取り方は自分が使いやすい形でよい。
N, M = map(int, input().split())
AB = [map(int, input().split()) for _ in range(M)]
A, B = [list(i) for i in zip(*AB)] #A=[A1,A2....] B=[B1,B2...]
K = int(input())
CD = [list(map(int, input().split())) for _ in range(K)] #[[C,D],[C,D]...]
ans = 0 #出力すべき答え
#とにもかくにも、まずは全探索するために全パターン回数まわるループを作成する。（今回は2^K回）
#2進数1をK回左シフト(右側に0を足して桁数を増やす)することで、2^Kを表現することができる。
#このループ１回につき１パターンを検証して毎回組み合わせの数を取り出し、最終的に答えとなる組み合わせの最大値を出力すればよい。
for S in range(1<<K):
#皿の状態を初期化する。
#１ループごとに１パターンの検証を行うため、皿の状態はループ内で初期化する。
#要素の値が0ならボール無、1以上ならボールありとする。
dish = [0] * N
#皿の初期化が終わったので、KとCDを使ってボールを皿の上においていく。
#ここで表現したいのは、2^Kパターン中の１パターンだけである。
#このとき、毎ループごとに重複せずにボールを置いていきたいので、ボールを置く処理にループごとに違う値となるSを取り入れる必要がある。
#人間が一つずつボールを置いていくので、１パターンを生成するために必要なループはKとなる。
#【1】へ飛んでください（処理を上から追うのではなく、思考の順番に追う）
for i in range(K):
#【2-1】※詳細な解説が不要な場合、2-2へ飛んでください。
#では、i人目の人間がCとDどちらを選ぶかという処理を考える
#bit全探索は、1パターンを010101のように2進数であらわし、ある桁が1か0かでその要素の状態を判断する手法である。(状態が２種類じゃないと使えない)
#つまりK人の人間がそれぞれどんな判断を下したかの集合を1パターンとしたとき、「Kの数」と「検証すべき2進数の桁数」は一致する必要がある。
#例としてK=5の時に検証すべき2進数は5桁となり、あるパターンを５桁で00001と表現したとき、1~4人目はCを選んだが、5人目はDを選んだというように判定できる。
#こうすることで、00000~11111をすべて見れば、人間が全員Cを選んだところから、全員Dを選んだところまですべて検証を行うことができる。
#そして、そのパターンの総数が2^K、つまり例でいえば2^5=32個であるということなのだ。
#
#上記の説明にあるように、例えばKが5だった場合、検証すべき桁数は5桁になる。00000→11111（0から31まで）
#そして、この検証すべき数字はSを2進数に変換することで表現できる。
#その理由を解説する。
#Sはループ回数を十進数であらわしたものであり0~2^Kまで増加するが、K=5のときSの最大値は2^5=32となる。
#これを2進数に変換すると100000となるため検証したい範囲11111よりも1つ多くなってしまう。
#しかし、ループのカウントは0からはじまるため00000からはじまり、32の一つ前の11111で全パターンを検証し終わる。（0から31までで32パターンの検索が終わる。）
#そのため、S=0~31を2進数にして、0で桁数を埋めると00000~11111となり、検証したい2進数と一致するのである
#
#【2-2】
#ここまでの話を踏まえると、参照すべき2進数は「全パターン数-1」で表すことができ、これはSをそのまま２進数にすればよく、
#１パターンの検証につきi人目は「2進数化したSのi桁目」を参照することで、2^K回ループを回せば全パターンを検証することができるといえる。
#そしてボールを置く対象一覧であるCDリストは[[C,D],[C,D]...]の集合体であるため、CDリストのi番目を取り出し、インデックス0or1を取り出し、
#そのインデックスに対応する値をxに代入すればボールを置くべきお皿の番号がわかるのである。
#
#この後の処理を見てもらったときにKi が一番怪しいと思うので解説する。
#Kiはi番目の人間がCDのどちらを選ぶかという処理なので、0か1かどちらかになる。
#この処理は結局はK桁を0埋めした2進数S(S=0のときは0ではなく00000...となっていなければならない)からi桁目を取り出すという処理である
#最終的に必要な値はintなので、まずint()で囲っている。
#i桁目を取り出すには文字列に変換しなければならないので、中身をstr()[i]とする。
#Sを２進数に変換したいのでformat(S, 'b')となるが、
#K桁を0埋めしなければならず、これはstrにしか指定できないので、２進数の表現をstr(format(S, 'b')).zfill(K)としている
Ki = int(str(format(S, 'b')).zfill(K)[i])
#お皿のインデックスは0から始まるので、CDの値も-1しないとlist index out of rangeになる。
#ここまで追えたら【3】に飛ぶ
x = CD[i][Ki]-1
#【1】
#ボールを乗せる処理をかく。
#i人目の人間はi番目のCDセットからCorDの皿どちらかを選んでボールをおく
#なので、どこにボールを置くかをxとし、これにCかDの値を代入すれば対応するインデックスのお皿にボールを乗せることができる。
#【2-1】へ飛んでください
dish[x] += 1
#【3】ここまででお皿の状態dishを1パターン分埋めることができたので、
#あとは個のお皿の状態でいくつの条件を満たせるかカウントするだけでよい
cnt = 0
for i in range(M) :
#条件に対応したdishを参照する必要があるが、indexは0から始まるので-1しないとlist index out of rangeになる。
if dish[A[i]-1] and dish[B[i]-1] : cnt += 1
if ans < cnt : ans = cnt
print(ans)
#あとがき
どうでしょうか。
数学糞雑魚ナメクジAtCoder初心者の方の役に立ったでしょうか。
そうであったらうれしいです。
僕は思います。
せっかくやる気出してAtCoderを始めたはいいものの、数学の知識が無さ過ぎて数学の勉強するにもどこからやっていいかわからないし、過去問とこうにも解説がもう理解できないとか、強そうな人のコード見てもなんでこういう書き方になるか理解できないという理由でストレスがたまり、成長するにできない。
この理解できないという辛さこそがモチベーションを削ぐ最大の敵であると。
しかしどうでしょう。
我々人類、こと伝えるという分野においては５万年を超える歴史をもつわけでございます。
今の人間、どんな難しい概念も、あらゆる手を尽くしてやってわかれないことはありません。
####「そんな言葉は綺麗ごと」であります
今回、僕は初めてAtCoderを触り、初コンテストで絶望し、初過去問解きで絶望し、それでも周りの友人のおかげでやっとこさ１問理解、いや理解したと思える程度にはなりました。
いろんな方からのアドバイスやサイトやコードをみて、前提とされている内容の不明な点を紐解き、前提知識ほぼ無しの状態からC問題を解くのにとても多くの労力が必要でした。
そして、僕程度の知識でC問題を理解するのにこれだけの粒度の解説が必要であることを実感しました。
泣きそうです。
やってやれないことはありませんが、こんなに毎回つらいならやりたくありません。
しかし１問、されど１問。
たった１問の過去問を解くだけでどれだけの学びがあったことでしょうか。
そう振り返ってみると、これもまた悪くないなと思えるわけです。
何といっても数学大っ嫌いで趣味でプログラミング触りたいとも思っていなかった自分が、休日三日を注ぎ込めるくらいのモチベーションを発揮できたわけですから、競技プログラミングというのはおかしな魅力があるものだなぁとおもうわけです。
まぁ、今の僕には競技の場と認識するにはあまりに遠すぎるものではありますが。
しかしてはたまた思うのです。
もうちょっと楽にキャッチアップできないかなぁと。
かつて青コーダーの友人にききました。
「どうすればそれだけのコーディングができるようになるんだい」
####「東京大学大学院数理科を卒業されてください」
流石に無理じゃ！！！！
それは無理なんじゃ！！！
そんなわけで、このようなアホ糞ながったらしくそこらの僕よりつよつよなプログラマにとってはアホ糞冗長な解説記事を上げることにしたわけです。
前回のABCでは8000人中7000位くらいでした。
この記事がAtCoderを触るような世の中のやる気勢の12%くらいにしか価値のないものだとは重々承知の上ではございますが、やはり、僕のような人間はいるはずです。
そんな方々のために、そして未来の自分のために、このような記事をこれからも上げていきたいと思う次第でございます。
僕のやる気が続く限りは...!!!!
#追記
Kiの出力方法ですが、よりスマートな表現としてここでもビット演算を使うことで高速化かつよりスマートに書くことができるそうです。
なお、シフトで計算する場合は、文字列とは違ってi=0の時１の位がの対象になる（右から見る）ことに注意してください。
Ki = (S>>i) &1
&はビット演算子というもので、この記号は論理積、aもbも同じ位のビットが1の場合1を返します。
b=1なので、要は下一桁が1なら1を返すよということですね。
Sを右シフトすると勝手に２進数扱いになるので、例えば00001であれば、00001,0000,000,00,0とiごとにシフトして１の位を入れ替えることができますから、これだけで動いちゃうわけです。
うーんスマート。