Ccmmutty logo
Commutty IT
2
・0 pv・16 min read

5完できない芸人の緑コーダーがABC262のA~Eまで

ABCAtCoderアルゴリズム競技プログラミングPython
https://cdn.magicode.io/media/notebox/blob_YfsmUNo

第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262）

ABC262のA~Eに関する解説(という名の自分用メモ書き）です。

戦績

4完でした！!!!!
今回、Dがハイパー超絶崖っぷちでしたね…。
Dの崖っぷち感、Eを解くのに必要なスキルを考えると、黒ココアさんの実力ではDまでが限界だったようです。
何か方向性も若干特殊編成っぽかったようですし（言い訳）、最近DPを練習してたので、なんとかDも解けましたし（言い訳）
今回は満足です！!
次こそ！5完！したい！(N回目定期)

全体のざっくり解説

  • A : 数式でザクッと or 雑にシミュレーション
  • B : 全地点全探索
  • C : 同じものまとめようね
  • D : 無限DP編
  • E : お絵かきテストで法則見つけてnCr！

A - World Cup

問題要約

あるスポーツ大会が西暦年を4で割った余りが2である年の6月に開催されます。
今は西暦YY年の1月です。
次に大会が開催されるのは西暦何年ですか？

制約

  • 2000<=Y<=30002000 <= Y <= 3000
  • YYは全て整数

考察

  • 余りは周期的なものなので、毎年0,1,2,3,0,1,2,3,…が続く。
  • 簡単に条件分けするのなら…
  • Y年を4で割った余りで判定
    • 0なら、Y+2年
    • 1なら、Y+1年
    • 2なら、Y年
    • 3なら、Y+3年
  • 余りが2になるまで毎年毎年愚直シミュレーションが頭を使わずに楽かもしれない…
    • どうせ４年間の間に１回は来るので。ちゃんと止めてあげれば無限ループも問題ないですね
  • 上級者の人達は、計算一発系でやっちゃうらしいです…。
    • (Y+1)//4 * 4 + 2
      • えーと…翌年を、４で割る（切り捨て）
      • その後で、４書けて…この時点で４の倍数になるので…余りは、０…
      • そこに+2…あー、たしかに…
    • 黒ココアさん、これは本番A問題で堂々と出せない…コーナーケースとか色々怖くて時間かけて確かめたくなります…
    • 例えば…2000年なら…
      • 2001//4→５００
      • 500*4 →　２０００
      • 2000+2 = 2002
    • 2001年なら…
      • 2002//4 →５００
      • 以下略
    • 2002なら…？
      • 2003//4→５００
    • 2003なら…！境界値！
      • (2003+1)//4→501
      • 501*4=2004
      • 2004+2=2006
    • おお…ちゃんと動いてる…すごい…！
python
# 条件分けVer

# 入力
Y = int(input())

# 余り
mod = Y % 4

L = [2,1,0,3] # 余りの値によって、次の開催年までに足りない年数を記録
print(Y + L[mod])
python
# 愚直シミュレーションVer

# 入力
Y = int(input())

# ４で割った余りが２になる年になるまで一生続ける…！
while True:
    # もし４で割った余りが２なら、その年で終わり！
    if Y % 4 == 2:
        print(Y)
        exit()
    # 開催されませんでした。来年また判定しましょう。
    Y += 1
python
# 上級者向け計算一発Ver

# 入力
Y = int(input())

# 計算一発パート
ans = (Y+1)//4*4+2

# 出力
print(ans)

B - Triangle (Easier)

問題要約

NN頂点MM辺の単純無向グラフが与えられます。
頂点には、1,…,N1,…,Nの番号が付けられています。 i(1≤i≤M)i(1 \leq i \leq M)番目の辺は、頂点UiU_iと頂点ViV_iを結んでいます。
以下の条件を全て満たす整数a,b,ca,b,cの組の総数を求めて下さい。
  • 1≤a<b<c≤N1 \leq a < b < c \leq N
  • 頂点aaと頂点bbを結ぶ辺が存在する
  • 頂点bbと頂点ccを結ぶ辺が存在する
  • 頂点ccと頂点aaを結ぶ辺が存在する

制約

  • 3≤N≤1003 \leq N \leq 100
  • 1≤M≤N(N−1)21 \leq M \leq \frac{N(N-1)}{2}
  • 1≤Ui<Vi≤N(1≤i≤M)1 \leq U_i < V_i \leq N ( 1 \leq i \leq M)
  • (Ui,Vi)≠(Uj,Vj)(i≠j)(U_i,V_i) \neq (U_j,V_j) ( i \neq j )
  • 入力はすべて整数

考察

  • B問題でグラフ…！若干怯えましたが、制約までよく見ると何のことはなかった
  • Nが最大100なので、100個の頂点から３箇所を取り出す組み合わせを全部出せたら済む量
    • 数としては、n=100n=100,r=3r=3のnCr=161700nCr = 161700通り。余裕で全探索できそうですね
  • 組み合わせじゃなくて愚直に全部出したとしても、1003=106100^3 = 10^6なので、全然間に合いそう
    • itertools.combinationsを使うととても便利ですね
    • combinations(list,n) := listからn個取り出した組み合わせを作ってくれるすごいやつだよ！
  • 後はグラフを情報としての持ち方
    • 隣接行列、隣接グラフなんかがあると思いますが、今回は隣接行列で持ったほうが後々スムーズ、かなー…？
    • edge_L[i][j] := iからjへの辺が張られているなら1、張られてないなら0
  • この２点だけ超えたら、後は愚直に実装するだけ…！
python
from itertools import combinations

# 入力
N, M = map(int, input().split())

# 辺を貼る隣接行列をここに作ります！
edge_L = [[0] * N for _ in range(N)]

# 辺の入力をM本分受け取っていきますー。
for i in range(M):
    u, v = map(int, input().split())
    
    # 0-indexedに戻して…
    u -= 1
    v -= 1
    
    # u→vに辺が張られてるので、１
    edge_L[u][v] = 1
    # v→uにも辺が張られてるので、１
    edge_L[v][u] = 1
    
# 答えを足していくよ！
ans = 0

# combinationsでa,b,cを一気に出す…！
for a, b, c in combinations(range(N), 3):
    
    # aからbに辺がある、bからcに辺がある、cからaに辺があるなら、三角形成立！+1！
    if edge_L[a][b] and edge_L[b][c] and edge_L[c][a]:
        ans += 1

# できた三角形の数を出力しておわり！
print(ans)

C - Min Max Pair

問題要約

11以上NN以下の整数からなる、長さNNの数列a=(a1,…,aN)a=(a_1,…,a_N)が与えられます。
以下の条件をすbれて満たす整数i,ji,jの組の総数を求めて下さい。
  • 1≤i<j≤N 1 \leq i < j \leq N
  • min(ai,aj)=imin(a_i,a_j) = i
  • max(ai,aj)=jmax(a_i,a_j) = j

制約

  • 2≤N≤5×105 2 \leq N \leq 5 \times 10^5
  • 1≤ai≤N(1≤i≤N) 1 \leq a_i \leq N(1 \leq i \leq N)
  • 入力はすべて整数

考察

  • とりあえず愚直を一旦考える。
    • i,ji,jを全部…N^2で、まぁ無理ですよねー。知ってた。
  • 気持ちとして、iiかjjのどっちかを固定したい…とりあえず小さい方のiiを固定する気持ちで色々実験。入力例2を見たりする。
  • とりあえず、１０個程度なら全部列挙できるので…実験コード書いて愚直解でどんな組み合わせが８個出てるのか見てみよ。手を動かす…！
    • (1,5),(2,8),(6,7),(6,9),(6,10),(7,9),(7,10),(9,10)
    • これらのi,jペアが正解の８つ。どういうのだろう…。
    • (1,5)が、1番目の数字=５、５番目の数字=１の組み合わせ！
    • (2,8)も、２番目の数字=8,8番目の数字=2の組み合わせ！
      • インデックスと値が入れ替わってる組み合わせはセットになるのね
    • (6,7)~(6,10)は…?
      • 6番目の数字=6,7番目の数字=7,9番目の数字=9,10番目の数字=10
      • インデックスと値が同じ数字の組み合わせ！
  • インデックスと値が同じ数字の組み合わせの個数は、
    • n * (n - 1) // 2で出てきますね。
  • インデックスと値が違う数字は…
    • 値が入れ違ってる所のインデックスが合ってるなら、+1！
  • これを1〜Nまで、順番に見ていけば、大丈夫！かな！多分！
python
# 入力
N = int(input())
A_L = list(map(int, input().split()))

same_cnt = 0 # インデックスと要素が同じものの個数
diff_cnt = 0 # インデックスと要素が異なるもので、入れ違いペアが同じになるものの個数

# 1-indexedで要素を見ていくよ！
for i, a in enumerate(A_L, 1):
    # もしindexと値が一緒なら、カウント
    if i == a:
        same_cnt += 1
    # もしindexと値が違うけど…→a番目の値がiになるものの数をカウント
    elif A_L[a - 1] == i:
            diff_cnt += 1

# same_cntは、n*(n-1)//2、同じものは2回重複して数えられているので//2したものが答え！
ans = diff_cnt // 2
ans += (same_cnt*(same_cnt-1))//2

# 答え出力しておわり！
print(ans)

D - I Hate Non-integer Number

問題要約

項数がNNの正整数A=(a1,…,aN)A = (a_1,…,a_N)が与えられます。 AAの項を１個以上選ぶ方法は2N−12^N-1通りあります。 そのうち、選んだ項の平均値が整数であるものが何通りかを、998244353で割った余りを求めて下さい。

制約

  • 1≤N≤1001 \leq N \leq 100
  • 1≤ai≤1091 \leq a_i \leq 10^9
  • 入力は全て整数

考察

  • 2^N-1通り、全部列挙できるならそれで良い話ですね…
    • Nが最大１００なので…うん、無理。知ってます。どうしたらいいのかな…？
      • そうだ、DPしよう。
      • DはDPのD！！！(ABC261以来２回目）
  • DPにすると方針建てて…次は定義、初期値、遷移を考える。
  • DPの定義…えー、と…パラメータに入りそうな要素を色々列挙してみる
    • 何個目まで見たよ！　←これは割と鉄板っぽいね
    • 何個選んだよ！　←これもよくありがち
    • 何通りあるよ！　←これはdpテーブルの値になりそう…よね。ずっと累計で取っていくイメージ。
    • 合計値は○○だよ！　 ← これをパラメータとして持つと、10^9*100の配列ができちゃうから、ダメー。
    • 平均値は○○だよ！ ←　これも配列サイズが10^9になっちゃうから、ダメー。
  • えー…平均値 = 総和 / 個数で…この中の２つは欲しいん、だけど、なぁ。
  • ちょっと式を変形したりごちゃごちゃ。
  • 平均値 * 個数 = 総和
  • 個数 = 総和 / 平均値
    • 総和が、個数の倍数になれば、平均値は、整数…！？！？！？！？　← ひらめきその１
      • 全部足したら３６でした。要素の数は９でした。→平均は４！
      • あ、なんかこれでいけそう。
    • 倍数判定なら、個数のmodが０になればいいね。
      • 個数のmodで取っていくなら、要素数は個数個しかできないので、なんとか、いけそう…！
  • ここまでの情報を元に、dpテーブルを作ってみる。
    • dp[i][j][k][l] := 先頭i項目から、j個の項を選んだ時、選んだ個数の総和をkで割った余りがlとなるようなものの個数
    • ちょ、ちょっとごちゃごちゃしすぎてて何もわからないので…色々落ち着いて考えてみる…。
  • 最終的に、AAの中から1個選ぶ場合…
  • 最終的に、AAの中から２個選ぶ場合…
  • 最終的に、AAの中から３個選ぶ場合…
    • これそれぞれの場合が独立してるので、外側でループ回したら良いのでは…？ ←ひらめきその２
    • 本番実装はこのあたりでゴリ押し実装したので、とても重かった…(70分)
    • 計算量としては、O(100^4)で厳しそうにも見えるけど、
    • 1個選ぶ、２個選ぶあたりの計算がとても速いことや、中身自体は軽いこと、制限時間が2.5sec等々でまぁ普通に通りました…！！！
*　ここからは、まさぁぁ先生の教えを元にもうちょっと楽に考えてみる
  • 「i番目の要素まで見たよ！i+1の要素目を考えるよ!」の遷移しかない場合、inlineにできる(埋め込める)よ！とのことなので…
    • i+1番目の要素を考えるよ！も一旦無視して、dpテーブルを考える。
    • dp[i][j]dp[i][j] := i個選んで、mod(最終的に選んだ数) がjになるのは○通りだよ！
      • これで考えると、遷移も減るし、次数も減るし、とても見通しが良い…！！！素晴らしい…！！！
    • んー…これ考えると、何か今までのDP問題も次元落とせたりする、のかなー。DPテクとしてちゃんと習得したいなぁ。
  • 追記：
    • しの先生より、「inlineにできる ≠\neq 埋め込める」との指摘を頂きました。黒ココアさんのinlineに対する理解が浅かったのが原因です。
    • 下記コード19行目：「# パラメータとして「今何番目まで見てるよ！」をinline：埋め込んじゃったので！」は、inlineの理解が浅く黒ココアさんの誤解ですので、一旦見なかったことにして下さい（コードブロックが編集できない…ううう…）
python
# 入力
N = int(input())
A_L = list(map(int, input().split()))

mod = 998244353
ans = 0

# 最終的に何個選ぶの？
for finally_cnt in range(1, N + 1):

    # dpテーブルを毎回作り直すよ！
    dp = [[0] * (finally_cnt + 5) for _ in range(finally_cnt + 5)]
    # 0個選んで、「総和%最終的に選ぶ個数」が0になるのは1通り。当たり前！
    dp[0][0] = 1

    # aの要素を左から順に見ていくよ！
    for a in A_L:
        # 今いくつ取ってる？これは遷移したら2→3になっちゃうので、大きい方から取る！
        # パラメータとして「今何番目まで見てるよ！」をinline：埋め込んじゃったので！
        for already_get_cnt in range(finally_cnt - 1, -1, -1):
            # 総和を最終的に選ぶ数で割った余りはいくつ？
            for mod_num in range(finally_cnt):
                # 選ぶ方だけ遷移！
                dp[already_get_cnt + 1][(mod_num + a) % finally_cnt] += dp[already_get_cnt][mod_num]
                dp[already_get_cnt + 1][(mod_num + a) % finally_cnt] %= mod
                # 選ばない方はそのままでOK！
                # パラメータとして「今何番目まで見てるよ！」をinline：埋め込んじゃったので！

    # 最終的に選ぶ個数だけ選んだ状態で、mod0になったものの数を答えに足していくよ！
    ans += dp[finally_cnt][0]
    ans %= mod

# 答えを出力して終わり！
print(ans)

E - Red and Blue Graph

問題要約

NN頂点MM辺の単純無向グラフが与えられます。
頂点には、1,…,N1,…,Nの番号が付けられています。 i(1≤i≤M)i(1 \leq i \leq M)番目の辺は、頂点UiU_iと頂点ViV_iを結んでいます。
それぞれの頂点を赤または青で塗る方法は、全部で2N2^N通りあります。
これらのうち、以下の条件を全て満たすものの総数を、998244353で割った余りを求めて下さい。
  • 赤く塗られた頂点がちょうどKK個ある
  • 異なる色で塗られた頂点を結ぶ辺の本数は偶数である

制約

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤M≤2×1051 \leq M \leq 2 \times 10^5
  • 0≤K≤N0 \leq K \leq N
  • 1≤Ui<Vi≤N(1≤i≤M)1 \leq U_i < V_i \leq N(1 \leq i \leq M)
  • (Ui,Vi)≠(Uj,Vj)(i≠j)(U_i,V_i) \neq (U_j,V_j) ( i \neq j )
  • 入力は全て整数

考察

  • 本番で全く考える時間がなかったので、改めてじっくり考えてみる
  • えーと…数え上げたい…全部で2N2^N通りだけど、Nの上限的にそれは無理…これもDPのパターンですね…！
  • dp[i][j][k]:=dp[i][j][k] := i番目の頂点まで見て、j個の点を赤く塗った時に、異なる色で塗られた頂点を結ぶ辺の本数はk本であるような塗り方は○通り！
  • ん、んー…k、いらないね…？偶数である本数がわかれば…いい、気がするので…？
  • dp[i][j]:=dp[i][j] := i番目の頂点まで見て、j個の点を赤く塗った時に、異なる色で塗られた頂点を結ぶ辺の本数が偶数本であるような塗り方は○通り！
  • あれ…えー…これで、何か、雰囲気は、いけそう…？？？
  • …えー…iが、N頂点で…jが、K個塗りたいわけで…あれー…O(NK)O(NK)は通らないぞ…何が悪い…のだ…
  • このあたりで考察をギブ、解説を見に行ったり、twitterでアドバイス求めて色々手を動かしてみたり…。
  • 簡単なグラフを書いて、赤で塗ってみたり青で塗ってみたりしよう。
  • 一旦全部青で塗って…この状態で、1つずつ赤にしてみる。(K=1の想定)
  • 頂点1を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、2本（偶)
  • 頂点2を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、2本（偶)
  • 頂点3を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、3本（奇)
  • 頂点4を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、1本（奇)
  • 次は,K=2で考えてみる。
  • 頂点1が赤(=異なる色で塗られた頂点を結ぶ辺の本数は2本）の時に…
    • 頂点2を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、1本減って、1本増える＝2-1+1=2（偶)
    • 頂点3を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、1本減って、2本増える＝2-1+2=3（奇)
    • 頂点4を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、0本減って、1本増える＝2-0+1=3（奇)
  • 頂点2が赤(=異なる色で塗られた頂点を結ぶ辺の本数は2本）の時に…
    • 頂点1を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、1本減って、1本増える＝2-1+1=2（偶)
    • 頂点3を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、1本減って、2本増える＝2-1+2=3（奇)
    • 頂点4を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、0本減って、1本増える＝2-0+1=3（奇)
  • 頂点3が赤(=異なる色で塗られた頂点を結ぶ辺の本数は3本）の時に…
    • 頂点1を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、1本減って、1本増える＝3-1+1=3（奇)
    • 頂点2を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、1本減って、2本増える＝3-1+1=3（奇)
    • 頂点4を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、0本減って、1本増える＝3-0+1=4（偶)
  • 頂点4が赤(=異なる色で塗られた頂点を結ぶ辺の本数は1本）の時に…
    • 頂点1を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、0本減って、2本増える＝1-0+2=3（奇)
    • 頂点2を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、0本減って、2本増える＝1-0+2=3（奇)
    • 頂点4を赤にすると…異なる色で塗られた頂点を結ぶ辺の本数は、1本減って、2本増える＝1-1+2=2（偶)
  • この辺から、頂点に繋がってる辺の本数（次数）の偶奇が関わってくるのかなー、とエスパー。
  • 次数が偶数の頂点(2)が赤の時…異なる色で塗られた頂点を結ぶ辺の本数＝偶数
    • ここで、もう1つ次数が偶数の頂点(1)を赤に塗ると…1本減って1本増えるので、異なる色で塗られた頂点を結ぶ辺の本数＝偶数のまま。
    • 逆に、次数が奇数の頂点(3)を赤に塗ると…1本減って2本増えるので、異なる色で塗られた頂点を結ぶ辺の本数＝奇数
  • 次数が奇数の頂点(3)が赤の時…異なる色で塗られた頂点を結ぶ辺の本数＝奇数
    • ここで、次数が偶数の頂点(1)を赤に塗ると…1本減って1本増えるので、異なる色で塗られた頂点を結ぶ辺の本数＝奇数のまま
    • 逆に、次数が奇数の頂点(4)を赤に塗ると…1本減って0本増えるので、異なる色で塗られた頂点を結ぶ辺の本数＝偶数
  • 次数が奇数の数と、次数が偶数の数が大事っぽい
    • 次数が偶数の頂点を1個赤に塗っても、2個赤に塗っても、異なる色で塗られた頂点を結ぶ辺の本数は、常に偶数
    • 次数が奇数の頂点を奇数個赤に塗ると、異（略）辺の本数は奇数、
    • 次数が奇数の頂点を偶数個赤に塗ると、異（略）辺の本数は偶数
  • 次数を奇数/偶数のグループに分けてカウントした上で、奇数グループのうち何個を赤に塗る？偶数グループのうち何個を赤に塗る？の組み合わせでとけそう…！（ここまでで第一段階）
  • K個の頂点を赤に塗りたいので…K個のうち、いくつを奇数グループで塗るかを全探索してみる
    • 次数奇数のグループからは、偶数個選びたいね
      • 次数奇数の頂点数から、偶数個選ぶ組み合わせ！
    • 次数偶数のグループからは、いくつでもいいから残りの分を選びたいね
      • 次数偶数の頂点数から、残りの分を選ぶ組み合わせ！
  • 後は、組み合わせをnCrで求めたら、解ける…！！！！！（TLE）
  • 組み合わせnCrを、フェルマーの小定理やら逆元やらを使って高速化するお話。
    • この辺りはちょっと黒ココアさんが正確に理解していないので、気になる方は別途調べてもらうとして…
    • もしくはライブラリとか色々拾ってきたりしてみて下さい…！！！
python
# 入力
N, M, K = map(int, input().split())
mod = 998244353

# 次数カウンター用配列
deg_L = [0] * N

# とりあえず前準備として、階乗を事前計算…ここでmod取って良いのが良き。
kaijo = [1]
gyaku = [1]
for i in range(1, 2 * (10 ** 5) + 10):
    kaijo.append(kaijo[-1] * i % mod)
    gyaku.append(pow(kaijo[i], mod - 2, mod))

# nCrを、事前にmod取った値で計算してる&階乗も逆元もメモ化的に事前計算してるので、速い！
def comb(n, r):
    if r < 0:
        return 0
    if n < r:
        return 0
    return kaijo[n] * gyaku[r] * gyaku[n - r] % mod


for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    deg_L[u] ^= 1
    deg_L[v] ^= 1

odd_node_cnt = deg_L.count(1)  # 次数が奇数の頂点の数
even_node_cnt = N - odd_node_cnt  # 次数が偶数の頂点の数

ans = 0
# 次数が奇数の頂点をいくつ塗る？を全探索していくよ
for odd_paint_cnt in range(0, K + 1, 2):
    # 奇数個塗っちゃうと異色辺が奇数本になるのでダメー
    if odd_paint_cnt % 2 == 1:
        continue

    # 赤の頂点に足りない分は、次数が偶数の頂点を塗るよ
    even_paint_cnt = K - odd_paint_cnt

    # 次数が奇数の頂点の中から、赤く塗る個数を選ぶ組み合わせ
    odd_comb = comb(odd_node_cnt, odd_paint_cnt)
    # 次数が偶数の頂点の中から、赤く塗る個数を選ぶ組み合わせ
    even_comb = comb(even_node_cnt, even_paint_cnt)

    # 組み合わせ同士を書けたものを足して…mod取ってあげる
    ans += odd_comb * even_comb % mod
    ans %= mod
print(ans)

Discussion

コメントにはログインが必要です。