28か月前公開・28か月前更新・0 pv・14 min read

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

Python競技プログラミングABCAtCoderアルゴリズム

https://cdn.magicode.io/media/notebox/blob_y4Du004

AtCoder Beginner Contest 261

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

戦績

あああああああああ3完ンンンん！！！！！！！（発狂）
緑Diffが…解けない…椅子がお尻でぽっかぽかに暖まりました！！！もちろんレートは冷えました。
ううん…いや、まぁ…１週間無精進なら、正直、致し方なし…うう…。
Cまでは、するするっとスムーズに流せたのになぁ…。
10分でCまで解けたのは…中々…自分の中では優秀…（かと思ったけど他の方々もさくさく解いてるのでそうでもないかもしれない…）
灰灰灰緑水だったので、diff的には…5完も、あった…はず…つらい….

次こそ！5完！したい！(N回目定期)

全体のざっくり解説

A : 数式でザクッと or 雑にシミュレーション
B : 全部チェックしよ
C : 辞書で数管理
D : DはDPのD
E : bit毎に独立して数える！

A - Intersection

問題要約

数直線があり、高橋君はこれを赤色と青色で次のように塗りました。

$X=L_1$ から $X=R_1$ までを全て赤色で塗る
$X=L_2$ から $X=R_2$ までを全て青色で塗る数直線のうち、赤色と青色の療法で塗られている部分の長さを求めて下さい。

制約

$0 \leq L_1 < R_1 \leq 100$
$0 \leq L_2 < R_2 \leq 100$
入力は全て整数

考察

$R_1$ が $L_2$ 以下、もしくは $R_2$ が $L_1$ 以下の時…共通区間が無いから0で…
それ以外…えーと…条件分けて…内包してる時も考えて…
- このあたりで考えるのを止めました。
どうせ100までの数直線なんだから、実際に塗ってみよう！（雑にシミュレーション)
- 多分数学的に場合分けし初めたら、とても面倒くさい沼にはまり込んで、内包してる場合とか状態分けでケース見落としとか合ったと思うので、愚直シミュレーションが通るなら愚直シミュレーションは正解だったと思います…（泥臭くて格好わるいけど）

# 入力
L1, R1, L2, R2 = map(int, input().split())

# ちょっと眺めの数直線を用意して
L = [0] * 110

# L1からR1までを塗り塗り…
for i in range(L1, R1):
    L[i] += 1
# L2からR2までを塗り塗り…
for i in range(L2, R2):
    L[i] += 1

# 2回塗られてる部分の数を求めたら、ハイ終わり！
print(L.count(2))

一応場合分けする場合…
$L_1 <= L_2$ とする
- そうじゃなかったらスワップして、 $L_1$ を小さくする
もし $R_1 <= L_2$ なら、
- 0:共通区間無し！
もし、 $R_1 <= R_2$ なら、
- $R_1 - L_2$ :　共通区間有り！
それ以外（ $R_1 > R_2$ )の場合（＝ $L_2,R_2$ の区間が、 $L_1,R_1$ に内包されている場合)
- $R_1 - R_2$ : 共通区間有り（内包）

# 入力
L1, R1, L2, R2 = map(int, input().split())

# スワップ部分
# ここで、L1<=L1が保証される
if L1 > L2:
    L1, R1, L2, R2 = L2, R2, L1, R1

# R1>L2じゃないと公差しないからね
if R1 <= L2:
    print(0)
# 普通に公差してる場合
elif R1 <= R2:
    print(R1 - L2)
# 内包されてる形の場合
else:
    print(R2 - L2)

B - Tournament Result

問題要約

N

人の人が総当たり戦をしました。

N

行

N

列からなる試合の結果表

A

が与えられます。

$A_{i,j}$ がWの時、人 $i$ が人 $j$ に勝った
$A_{i,j}$ がLの時、人 $i$ が人 $j$ に負けた
$A_{i,j}$ がDの時、人 $i$ が人 $j$ に引き分けた
$A_{i,j}$ が-の時、 $i=j$

与えられた結果表

A

に矛盾があるかどうかを判定して下さい。

制約

$2 \leq N \leq 1000$
$A_{i,i}$ は-である
$i \neq j$ の時、 $A_{i,j}$ はW,L,Dのいずれかである

考察

$N$ の制約が小さいため、全探索余裕っぽい
- 全部チェックして矛盾が無いか確認しようね
この手の勝敗確認とか、じゃんけんの判定とか、割と実装に癖というかコツがある気がする…
- 今回の場合だと、W:L,L:W,D:Dみたいな辞書実装とか…
- Wを+1,Lを-1に変換して、最終結果が0になるかどうか、とか…
- 類題だったり人のソースコード見てみると、色々ワンポイント技あり実装が学べて良いかもですね！

# 入力
N = int(input())
L = []
for i in range(N):
    L.append(input())

# 表に矛盾が無いかどうかを示すフラグ
ans_flg = True

# iとjを全探索して…
for i in range(N):
    for j in range(i + 1, N):

        # 其々の場合で矛盾となる状態を抽出
        # もし矛盾があった場合、フラグで管理
        if L[i][j] == 'W' and L[j][i] != 'L':
            ans_flg = False
        if L[i][j] == 'L' and L[j][i] != 'W':
            ans_flg = False
        if L[i][j] == 'D' and L[j][i] != 'D':
            ans_flg = False

# 矛盾が合ったかどうかで判定出力！おわり！
if ans_flg:
    print('correct')
else:
    print('incorrect')

C - NewFolder(1)

問題要約

N

個の文字列

S_1,S_2,…,S_N

が与えられます。

i=1,…,N

の順に、次の指示に従って加工して出力してください。

$S_1,…,S_{i-1}$ の中に、 $S_i$ と同じ文字列が存在しないならば、 $S_i$ を出力する
$S_1,…,S_{i-1}$ の中に、 $S_i$ と同じ文字列が $X個$ 存在するならば、 $X$ を文字列として扱って $S_i + ( + X + )$ を出力する

制約

$1 \leq N \leq 2 \times 10^5$
$S_i$ は英小文字のみからなる長さ1以上10以下の文字列

考察

A、B問題と比べてちょっとだけ制約が大きくなった。
- 毎回、「何回出てきたか」を数えるとTLEしちゃいそう…
Sの入力を読みつつ、カウントしていけばいい！かな！
- こういう時にdefaultdictさんがとても優秀。defaultdictは木の葉にて最強。

from collections import defaultdict

# 入力
N = int(input())

# カウント用defaultdict準備
d = defaultdict(int)

for i in range(N):
    # Sを受け取って…
    S = input()
    
    # もしSが過去に出てきたなら、"()"を付けて個数も出力！
    if d[S]:
        print(S + '(' + str(d[S]) + ')')
    else:
    # Sが初めて出てきたなら、そのまま出力！
        print(S)
        
    # Sの個数に+1
    d[S] += 1

D - Flipping and Bonus

問題要約

高橋君が

N

回コイントスを行います。
また、高橋君はカウンタを持っており、最初カウンタの数値は

0

です。

i

回目のコイントスで表/裏のどちらが出たかによって、次の事が起こります。

表が出た時：カウンタの数値を1増やし、 $X_i$ 円もらう
裏が出た時：カウンタの数値を0に戻すまた、 $M$ 種類の連続ボーナスがあります。
$i$ 種類目の連続ボーナスでは、カウンタの数値が $C_i$ になるたびに $Y_i$ 円貰うことができます。
高橋くんは最大で何円もらうことができるかを求めて下さい。

制約

$1 \leq M \leq N \leq 5000$
$1 \leq X_i \leq 10^9$
$1 \leq C_i \leq N$
$1 \leq Y_i \leq 10^9$
$C_1,C_2,…,C_M$ は全て異なる
入力は全て整数

考察

よし、ここに墓を立てよう。よわよわコーダーの黒ココアさん、D問題AC通せず発狂したままここに眠る。
=====ここから黒ココアさんが陥って結局AC通せなかったダメ考察ルート=====
参考にしたところで何も良いことは無いので軽く読み飛ばして下さい
3完でレートを冷やした自分への戒めとして記す
表/裏をN個選ぶ全通りなら… $O(2^N)$ で、5000通りは当然無理…どうにか計算を楽にしたい…
状態をゆっくり見てみよう…
- とりあえず、最終回(N回目）のコイントスは、絶対表よね。そこでカウンタ0に戻しても意味無いので… $X_N$ 円取りそこねちゃうもん。
- じゃあ…後ろから見ていく…？
  - $N$ 回目が表確定だとして… $N-1$ 回目…裏…？表…？何これ、うーん…カウンタによってどっちもある、のか…
    - $C=1$ のボーナスがあるなら、裏出すパターンもある…
一旦、全部表パターン/全部裏パターン考えてみよう…
- 全部表パターンなら…全部のボーナス1回ずつと、Xの合計…
  - sum(X) + sum(Y)
- 全部裏なら、当たり前だけど0円
- じゃあ…どこで裏にする…？裏にした時に利益出るのって、どこで判断するの…？
  - やっぱりボーナスかなぁ…
ループ圧縮とかダブリングみたいなイメージで、特定ボーナスを得た段階でリセットさせたら…
- 最後の余りだけ、もう1回ループさせるのか、そのまま走らせるのか判断…？
- 実際提出してみるもWA。それはそう。反例が全然思いつく…
じゃあ… $O(N)$ で、カウンタ上限をループさせる…?
- いやこれもダメじゃん反例めっっっちゃ出てくる何事どういう事…
=====ここまで黒ココアさんが陥って結局AC通せなかったダメ考察ルート=====
ここから正解ルート
結論から言うとDP
ありえるパターン全通り探索で $O(2^N)$ が通らない…
- ここから、 $O(N^2)$ なら通る→DPを疑うのが典型パターンの様です
DPとして、どの情報を残す/どの情報を落とす/どの情報が後々に影響するかを考えてみる
- とりあえずi回目のコイントス…までは持ちたい、かなぁ。
  - 1回目のコイントスで表なら、 $X_1$ と、ボーナスがあるならボーナスも…
  - 裏なら、0円…
  - 2回目は…表なら、 $X_2$ と…ボーナスが2にあった時…貰えるかもらえないかは前回表か裏かによって変わる…
    - これだけじゃパラメータ足りない感じしますね…
- 他にパラメータになりそうなものを考えてみる
  - i回コイントスしたうちの、表を出した回数…？
    - i - 表の回数 = 裏の回数、までは分かる
    - i回のうち、どこで「裏」を出したかによってボーナス取得可否が変わるから、いまいち…
  - じゃあ…えーと…何があれば、ボーナス取得可否が分かる…？
    - 直近、連続で表が出た回数…？
    - えっ、あ、これ、ようするにカウンタの数値…？？？
- 今 $X$ 回のコイントスした！！！カウンタが $Y$ だよ！！！→この時に取得できる最大金額が分かるなら…
  - $X+1$ 回目に裏を出すと…
    - → $X$ 回目で得る最大金額がそのまま $X+1$ 、カウンタ $Y=0$ に
  - $X+1$ 回目に表を出すと…
    - → $X$ 回目に、カウンタ $Y$ の状態で得る最大金額に、 $X+1$ 回目の表で得る金額 + カウンタ $Y+1$ で得るボーナスの金額を足したもの
- 状態足りる、っぽい…ね…？
- ex)5回目のコイントスで、カウンタ2になりました。その時取得できる最大の金額は、
- 絶対に4回目のコイントスでカウンタ１の金額の最大金額を経由してる筈
- 結局、「今のカウンタ」がわかれば次のトスで表/裏が出ても正しく遷移できるし、
- そのトス以前に何回裏が出ても、どこで裏が出ても、金額には影響しないので情報として捨てて良い
後は、添字ガチャをしないように、落ち着いて実装…！！！
コンテスト後にTLで見かけた実装ポイント
- ボーナスの管理を、リストで行う
  - カウンターのボーナスが無い時は、ボーナス０として扱う
  - ボーナスがある所だけ、 $Y_i$ を入れてあげる
  - defaultdictでも良いねー？でも更新しないから、リストがシンプルでいい、かなぁ。

# 入力
N, M = map(int, input().split())
X_L = [0] + list(map(int, input().split()))

# bonus_L[i] : カウンタがiになったときのボーナス
bonus_L = [0] * (N + 10)

for i in range(M):
    C, Y = map(int, input().split())
    bonus_L[C] = Y

    
# dp配列準備!余裕みて+10で作ってみたりすると何かプロっぽい感じして良き。list index out of range出ないのも良き。
# dp[i][j]　:= i回コイントスをして、カウンターの値が[j]になるときの、最大金額！
# とりあえず「その状況があり得る？」かを判定するかなと思って、ありえない値として-1を突っ込んだけど、0でいいね…？
dp = [[-1] * (N + 10) for i in range(N + 10)]
# 0回コイントスをしました！カウンタ0です！その時にありえる最大金額は0円です！当たり前体操！
dp[0][0] = 0
# 直前のコイントスで、得られる最大金額を確保しておく
# →　次のコイントスで「裏」を出した時の金額になるよ！
max_score = 0

# コイントスした回数。1回トスするよ。N回までトスするよ。
for toss in range(1, N + 1):

    # toss回目のトスで裏を出す＝カウンタ0にする時の最大金額は、直前までのコイントスで得た最大金額
    dp[toss][0] = max_score

    # カウンターの値を考える。toss回目で、カウンターがcnt回になったときの最大金額
    for cnt in range(1, toss + 1):
        # toss-1回目、カウンタ=cnt-1の最大金額 + toss回目のX + カウンタボーナス！
        dp[toss][cnt] = dp[toss - 1][cnt - 1] + X_L[toss] + bonus_L[cnt]

    # toss回目の最大値　→　次のカウンタ0で裏を出した時に使うよ！
    max_score = max(dp[toss])

# 最後のトスが終わったときの最大金額が答え！
print(max_score)

E - Many Operations

問題要約

変数

X

と、

X

の値を変更する

N

種類の操作があります。　　操作

i

は整数の組

(T_i,A_i)

で表されます。

$T_i = 1$ : $X = X and A_i$
$T_i = 2$ : $X = X or A_i$
$T_i = 3$ : $X = X xor A_i$

変数

X

を値

C

で初期化した状態から、以下の処理を順に実行して下さい。

操作 $1$ を行い、操作後の $X$ の値を出力する
続けて、操作 $1,2$ を順に行い、操作後の $X$ を出力
続けて、操作 $1,2,3$ を順に行い…
…
続けて、操作 $1,2,…,N$ を順に…

制約

$1 \leq N \leq 2 \times 10^5$
$1 \leq T_i \leq 3$
$0 \leq A_i \leq 2^{30}$
$0 \leq C \leq 2^{30}$
入力は全て整数

考察

似たような操作の繰り返しで、数直線上でロボットが右左に行ったり来たりするような、そんな問題合ったような…うーん…累積和…？
愚直に毎回操作すると当たり前に $O(N^2)$ ですり潰されちゃう
どこをスキップしてくれようか…
bit演算の典型として、「bitごとに独立」に考えてみる。
- and,or,xorの操作は繰り上がり/繰り下がりがないのでbit毎に独立に考えて良さそう
手持ちの $X$ に操作1をして…更新された $X_1$ に、操作1と操作2をして…
- 各bitに、それぞれ操作１、操作２、…、操作 $N-1$ を行うことを考える
- bitって結局0か１しか持たないのだから、
  - 0に対して「操作１〜操作 $N-1$ を行った結果」
  - 1に対して「操作1〜操作 $N-1$ を行った結果」
  - をそれぞれ持って、毎回操作毎に更新すれば良いんじゃない？
- 桁数は…30。N*30は余裕で間に合いそう。
後は実装実装！
以下おまけ
- きり先生のユーザ解説が、上手すぎてもう無理。
- 0から初めた時の結果と、1から始めた時の結果とを別々の変数で持ってるから正直無駄かと思いきや完全に無駄がなさ過ぎる…
- bit演算一発で落とし込んじゃったら、黒ココアさんみたいにループで桁毎に見ていく必要もないんですねー。（池上彰感）
- いやもう何これbitの魔術師ですか…？最後(16行目)のand, or, xor の畳み掛ける感じとか、何？？？
- シンプルすぎて無駄がなさすぎて見易いことこの上ないので見やすすぎて逆に見にくいまでありますわ
- 黒ココアさんの実力不足で16行目何してるのかよく分からなかったりする。正直あんまりわかってない。
  - 多分、&s1で、Xの1が立ってる所で、かつ、1からはじめて今bitが立ってる所だけ拾って…
  - ^ mで、反転させてるから…& s0で、Xの1が立ってない所で、かつ、0からはじめてbit今bitが立ってる所だけ拾って…
  - それらのorだから、ほら、ね？？？（やっぱりよくわかってない）

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

# 何故かXで与えてくれなかったので、X作成
X = C

# bit毎の直前の操作までを記録する配列。
# bit_L[i][j] :=　i桁目のbitを、j(0 or 1)から操作初めたらどうなったよ！な配列 (0 or 1)
bit_L = [[0, 1] for _ in range(30)]
 

for _ in range(N):
    # N回入力受け取って…
    T, A = map(int, input().split())
 
    # 1桁ずつ見ていくよ！
    for i in range(30):

        # and操作の時！
        if T == 1:
            
            # もしAのi桁目のbitが立ってるなら、i桁目は何も変わらない
            if (A >> i) & 1:
                pass
            # 立ってないなら、0から始めても1から始めても0になる
            else:
                bit_L[i][0] = 0
                bit_L[i][1] = 0

        # or操作の時！
        elif T == 2:
            # もしAのi桁目のbitが立ってるなら、0から始めても1から始めてもi桁目は1になる
            if (A >> i) & 1:
                bit_L[i][0] = 1
                bit_L[i][1] = 1
            # 立ってないなら、i桁目は何も変わらない
            else:
                pass

        # xor操作の時！
        else:
            # もしAのi桁目のbitが立ってるなら、直前で0なら1に、1なら0になる
            if (A >> i) & 1:
                bit_L[i][0] ^= 1
                bit_L[i][1] ^= 1
            # 立ってないなら、i桁目は何も変わらない
            else:
                pass
 
    # 出力する値を計算するパート！
    output = 0
    # 1桁ずつ見ていくよ！
    for i in range(30):
        
        # もしXのi桁目のbitが立ってるなら…
        if (X >> i) & 1:
            # i桁目のbitで、1から初めたら直前までの操作を行った時,bitは立ってる？
            # 立ってるなら、2^i乗をインクリメント
            if bit_L[i][1]:
                output += 2 ** i
                
        # もしXのi桁目のbitが立ってないなら…
        else:
            # i桁目のbitで、0から初めたら直前までの操作を行った時,bitは立ってる？
            # 立ってるなら、2^i乗をインクリメント
            if bit_L[i][0]:
                output += 2 ** i
 
    # 出力！Xの更新も忘れずに！
    print(output)
    X = output

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

AtCoder Beginner Contest 261

戦績

全体のざっくり解説

A - Intersection

問題要約

制約

考察

B - Tournament Result

問題要約

制約

考察

C - NewFolder(1)

問題要約

制約

考察

D - Flipping and Bonus

問題要約

制約

考察

E - Many Operations

問題要約

制約

考察

Discussion

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