abcのC問

難易度のメモ

難易度をメモする。自分はC問の壁を感じるのでちゃんと一覧を作っておきたかった。

C問が解けるか解けないかが緑になる境目な気もするので、そこらへんで右往左往してて、これから練習する人のためにもなればいいなと思う。

難易度は主観が多く、

• 簡単（abの延長で解ける）
• 普通（ちゃんと考える、ちょっと工夫すれば解ける）
• 難しい（アルゴリズムを適用したり、10進の数値計算以外を使う）

という具合で決めている。

やった問題から順次載せるので、更新は非常に遅い…

簡単

• abc127c　l,rの範囲の指定。累積和じゃない問題を扱いたいときにいいかも
• abc132c　中央値みたいに求める

普通

• abc126c　確率を一つずつ求める問題。扱う変数が少し多くなるので頭がパンクしがちな人には効く問題
• abc137c　文字数カウントと組み合わせの数

難しい

• abc128c　bitFlag（二進数でT/F判断）
• abc129c　配るdpを使う。想像力があれば普通レベル

abc127cのノート

漫画

昨日読んだhush hushという漫画が良かった。

リスとコヨーテのほのぼの漫画だった。

別にhashとは何の関係もない。

abc127c

atcoder.jp

結構簡単に感じた。

多分l,r別にforを回しても間に合うと思う。

l,rの入力が

1,3

2,4

だと、一つ目で1~3なので

| 1 2 3 | 4　=> 3枚のIDカード[1,2,3]

二つ目で2~4なので

1 | 2 3 4 | => 3枚のIDカード[2,3,4]

が通ることが可能。したがって両方に含まれる2,3のIDカードの二枚が答えとなる。

また、と連続しているので穴抜けはない。

書いたコード

n,m = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(m)]

l_max,r_min = 0,10**5
for l,r in src:
    l_max = max(l_max,l)
    r_min = min(r_min,r)
else:
    if r_min-l_max < 0:
        print(0)
    else:
        print(r_min-l_max+1)

入力の際にl,rを分けておけばmin関数,max関数にそれぞれリストを入れるだけなのでそっちの方が書き方的には早かったと思う。

また、今回だったらこれで作っても

def ret(list_object, index):
   return [i[index] for i in list_object]

すぐに返ってくるのでいいかもしれない。

最良なのは入力を変えることだとは思うけれど。

反省

簡単だったけど、ans<0の時を書き忘れでWAしてしまった。

ちゃんと考えないとね。

abc128cのノート

概要

今までbitFlagをしたり普通に計算として二進数を扱う問題が数多くあったが今まで解けずじまいだった。

ここで練習したので、次に生かしたい。

今回は先人のコードを読み解いたというメモ。

二進数の演算について

今回使ったのがアンド演算子。 出力は普通の掛け算となる。

bitFlagは、組み合わせの全列挙を行う際に掛け合わせの金型として使うと丁度良い。

今回の問題だとオンを1、オフを0として扱うとスイッチsの組み合わせを各桁で表すことが可能になる。

桁の繰り上げは左シフトが適当で、二進数のbitFlagの作り方もこれで二進数で桁数指定でき簡単になる。

入力のnがスイッチの数すなわちn桁分bitFlagを用意すれば十分なので

range(1<<n)

とすると、2ⁿ-1の数(11111 11111)までを指定できる。

abc128c

atcoder.jp

解説にある通り、全列挙をすると計算量がO(mn*2ⁿ)となるので2¹⁰を大分多く見積もって概算10⁴としてもオーダー全体で10⁶で間に合う（らしい）

パクったコード

今回は完全にパクりコード。

毎度読みやすくて理解がしやすい。

一番深いインデントのアンド計算の左シフトでs-1としているのは、スイッチの番号が1から始まるのに対して桁数の表現が2⁰から始まりシフトの必要性がないのでその整合のためである。

# original_author prd_xxx

N,M = map(int,input().split())
src = [tuple(map(int,input().split())) for i in range(M)]
P = list(map(int,input().split()))

ans = 0
# 2^Nまでrange探索を行う。
for b in range(1<<N):
    for i in range(M):
        c = 0
        for s in src[i][1:]:
            if b&(1<<(s-1)):
                c += 1
        # 最後に条件スイッチの条件と合致しているか検証
        # 合わなければelseに飛ばずbの次を検証しに行く
        if c%2 != P[i]: break
    else:
        ans += 1
print(ans)

abc132cのノート

abc132c

ひとりでとけた。

書いたコード

n = int(input())
d = list(map(int,input().split()))

d.sort()

if n%2==0:
    print(d[n//2]-d[n//2-1])
else:
    print(0)

気持ちが中央値だった。

中央値だと(d[n//2]+d[n//2-1]) / 2。

今回は以上、未満の境になることが可能な数の個数なので単純に(以上にすべき数)-(未満にすべき数)の2数の区間の計算で求めた。

指定した2数が同じ値であった時には以上・未満の境を決めることができない、ということなので出力そのままの0でよい。

abc137cのノート

近況

前回から一か月近く経った。

一か月ほど帰省している。

本を数冊読んだ。競プロから離れていたし、コンテストにも出ていなかった。なるべくコンテストにはい。

ディープラーニングがわかる数学入門を一応読み終えた。数学に関してあまり明るくないので、かなり躓き苦しみながら読んだが、どうにか糧にできたと思いたい。

abc137c

某ゴリラ競プロerを解答を参考にした。abcでpython書きでほぼ毎回最速acをもぎ取っているので見習いたい…

今回の学びとして、Counter()について先に述べる。

dict型とcollections.Counter()

collections型は以下の公式ドキュメントを参照した

docs.python.org

今回使用したのはdict型でのバグを減らす目的である。

当たり前だが、バグるコード。

d = {}
d["k"] += 1

dict型なので勿論怒られる。

「"k"なんてkey見つかんないんだけどっ！」ってpythonちゃんにたしなめられてしまう。

しかし、

from collections import Counter
c = Counter()

c["k"] += 1

このようにCounter()を用いると辞書型風にカウントしてくれて、さらに怒られない。 名前の通り、そのまま単語のカウンターとして機能してくれる。

また、標準ライブラリなのでどこでも使える。

パクったコード

わからなかったのでパクった。

# original_author prd_xxx
from collections import Counter

N = int(input())
S = [input() for i in range(N)]

# collections.Counter()を使うと0回目の時にバグらないのでelseを省略可能
# ctr = Counter()
ctr = {}
ans = 0

for s in S:
    a = ''.join(sorted(list(s)))

    if a in ctr:
        ans += ctr[a]
    else:
        ctr[a] = 0

    ctr[a] += 1

print(ans)

ソート済み文字列が以前に存在していたら、答えに前回の合計値を加算する。

もし仮に同様の文字列（ここでは1文字）が処理されたらansは1回目..0加算(合計0) 2..+1(1) 3..+2(3) 4..+3(6) 5..+4(10)の増加になる。

更新手順について、自分の考えていたのは最後に出現回数をそれぞれで計算し、 その個数分をそれぞれ算出しようと思っていたが解法をみて要らない手間だと感じた。 （アナグラムが同様のグループに含まれる個数が同じものについては計算できるからそれを優先しようと思考していた）

丸パクリだと何となく嫌なので、辞書型に組み替えた。

abc129cのノート

abc129c

階段飛ばしの問題。

先輩に「配るdp」での解き方を教わった。

atcoder.jp

いい感じに理解できたので、それを残す。

配るdpについて

本問題において配るdpは「その配列要素に辿りつくまでに何通りがあるか」を保存し、それを利用する。

問題中で高橋君は1または2段飛ばしの動きをする。これをもとに穴なしで2段目にたどり着く通り数を考えると、

「最初の場所(0段目)のi通りから2段飛ばし」による1通りと、

「1段目から、1段上がる」操作による1通り

の合計2通りがある。

3段目も同様に穴なしで考えると1段目からの2段飛ばしと、2段目からの1段上がる2通りである。

通り数を保存すると、この問題だと「今のindexの2つ前の要素の和」で次の要素の通り数が決まる。

ただし、穴についてはこの処理を行わないことによって整合性をもたせることができる。

3段穴なしで考えると、0段目も含めるので

[1,1,1,1]

の配列を用意して2からforを回す。(2からでないと参照ができないし、indexの0,1に関しては一通りしかないので1,1のままで良いから)

index 2を考えると前2要素の和なので2となる。

index 3を考えると同様に3となる。

したがって、[1,1,2,3]の配列に変形される。

基本的にはこれを続けていくことで求めたいもの-1のindexまで求められる。

書いたコード

n,m = map(int,input().split())
l = [1]*(n+1)
# This is [Kubaru_dp]

for i in range(m):
    a = int(input())
    l[a] = 0

for i in range(2,n+1):
    if l[i]==0:
        continue
    l[i] = (l[i-1]+l[i-2])%(10**9+7)
else:
    print(l[-1])

基本的入力は省略する。
l(エル)について一つ多く配列を取っているが、答えを簡単に出力したいためにこのようにした。単純にnまで出力したいがn個だとindexが0~(n-1)までしか出ないからである。

一度目の入力を受け取るfor文内でl[a] = 0がありこれは穴である。

二度目のforで配るdpの操作をしている。lが0であったら、今穴の上に高橋くんがいることを仮定しているのでこれは捨てるべき操作になる。したがってこれを無視する。
なんとなくここで、値が足りなくなる気がするが、穴を飛び越える時点で穴を通る通りが0通りであることを考えるとわかりやすいかもしれない。
また、0が二回くる時にここで途切れ以降が0埋めされる。したがって答えが0の際もちゃんと出力される。

lの要素の更新だが、制約どおり(10**9+7)で出力するので更新時点でこれを行う。確かフェルマーの小定理。

いもす法についてのノート

いもす法

累積和のアルゴリズム。

想定される使用方法としては「任意の配列オブジェクトの幅指定を何度も受け取る」ものに対して用いる。 これで生成されるのは「受け取った際の合計の配列」である。

ここでは１次元０次について解説する。

参考。

imoz.jp

アルゴリズムについて

幅指定の入力において重複が多かったindexの最大値を求める問題を想定する。

幅指定

まず「幅指定で受け取る」というものを説明する。

例として長さ10で幅指定を受け取るとする。

index:

0,1,2,3,4,5,6,7,8,9

value:

0,0,0,1,1,1,1,1,1,0(*)

0,1,1,1,0,0,0,0,0,0

これを幅指定で受け取ると、

１つ目:index(3~8) だから、3,8

２つ目:index(1~3) だから、1,8

となる。

したがって0,9とすれば1で埋められた入力を受け取ることになる。

(*)再度参照

計算

「重複の数」を計算する。

これは単純に各valueの合計を取ればよいだけなので、例の合計は

index:

0,1,2,3,4,5,6,7,8,9

value:

0,1,1,2,1,1,1,1,1,0

したがってindex:3の2が最大値となる。

いもす法の実践

幅指定での計算を累積和的に工夫する。

幅指定に対して「帯」をイメージし、指定indexの終端まで伸びているとする。

ここで、指定indexの終端+1のindexのvalueを-1とする。

この配列を１つ目(3,8)で考えると、

index:

0,1,2,3,4,5,6,7,8, 9

value:

0,0,0,1,0,0,0,0,0,-1

index:3が1でindex:9が-1となっている。

これを累積和で考えると、index:3からindex:8までが1で埋められ、index:9において-1されることによりその地点が0となる。これで整合性がとれることが理解される。

すなわち、一番最初のvalueの例(*)と同じ情報を持っている。

また、１つ目と２つ目の幅指定を受け取った後のいもすのvalueは

0,1,0,1,-1,0,0,0,0,-1

となる。

計算量削減のイメージ

普通、一つ一つ要素を改めなければならないので（（指定回数+1）*配列の長さ）分の計算が必要だが、いもす法だと（指定回数*2+配列の長さ）となる。

配列要素の変更がindex指定の二回分しか行われないので、非常に計算が軽くなる。

感想

天才の発想。一生思いつかんわ…