【祝】AtCoderでレーティング1000を達成/やったこと振り返り

どうもーー

さて、タイトルの通りレーティングがようやく1000にのりました！

ABC140
ついにratingが1000に!!
めちゃくちゃ嬉しいんですけどぉ〜!!

Guam行ったら思考力向上したw pic.twitter.com/T1b5Mtg9Zb

— teramex🇲🇽/エンジニア (@mktrdbg) 2019年9月7日

まあ普通の人にとっては大したことではないのかもしれないけど、
自分にとってはなかなかに嬉しいことです！

特に最近は停滞（プラスマイナス5とか）が多かっただけに、
ABC139とABC140で自分なりの好成績が出せたのがより嬉しい！

ということで感想を書きつつ、一応どんなことをやってきたのかを書いときます。
成田エクスプレス内でコーディングし、渋谷駅で仕上げ＆提出したのでコードのひどさはご愛嬌ということで。
一発ACじゃなかったら恐ろしいことになってた。ローリスクハイリターン。
しかしリスクを取らずに何が面白い。

ABC140
A: N**3。焦っていたので(N-1)**3を一回試した。
B: なにげにむずい。どれがどれか把握
C: Maximal Value

A = [None] * N
while any(a == None for a in A):
    min_idx = B.index(min(B))
    if A[min_idx] is None:
        A[min_idx] = B[min_idx]
    if A[min_idx+1] is None:
        A[min_idx+1] = B[min_idx]
    B[min_idx] = inf
print(sum(A))

まずAを[None, None, ... None]と長さNの配列に。
Bの各要素は、Ai, Ai+1の大きい方となる。
Bの中でも小さい値から見ていき、Aの各要素を確定させていくことですべてのAの要素を確定することができる。

6
0 153 10 10 23

なら
0のところに対応するAの要素は絶対に0になるので確定する
この時点で
[0, 0, None, None, None, None]
次に小さい10の部分のAを確定させると
[0, 0, 10, 10, None, None]
もう1つの10も確定させて
[0, 0, 10, 10, 10, None]
23の部分を確定させて
[0, 0, 10, 10, 10, 23]
となり、合計53となる

D: Face Produces Unhappiness
顔面が不幸を生み出す

tmp = 1
l = []
for i in range(N-1):
    if S[i] == S[i+1]:
        if i == N - 2:
            tmp += 1
            l.append(tmp)
        else:
            tmp += 1
    else:
        if i == N - 2:
            l.append(tmp)
            l.append(1)
        else:
            l.append(tmp)
            tmp = 1

len_l = len(l)
len_l -= 2 * K
if len_l <= 1:
    print(N - 1)
elif len_l <= 2:
    print(N - 2)
else:
    ans = N - len_l
    print(ans)

前半の部分で、塊の長さをリストに入れます。
例えば
RLRRLRLL
なら、つながっている部分をカウントして
1, 1, 2, 1, 1, 2
というようなリストを作ります

この時点で、全体の幸福数は
2のところの1人と、もう1つのところの2のところの1人のあわせて2人です。

K回できる操作をしていくと、どこを回転させても
4, 1, 1, 2なら3+1=4
1, 4, 1, 2なら3+1=4
1, 1, 2, 4なら1+3=4
と、端だけ回転させる以外のどんな操作をしても幸福人数は同じになります。
結果、
N-1が最高点(LLLの場合は2になる)ということを考えると
(N-1) - 塊の数
が求める答えということが言えます。
RLRなど1のところは、幸福数が0です。

塊の数を数えると
最初
1, 1, 2, 1, 1, 2
で6個でした
次に
4, 1, 1, 2
で4つに
さらに
6, 2
で2つになりました。

一回の操作で、塊を2つ減らすことができます。
ということは、幸福数が2増えますね。
こうすると、K回操作して塊が1つになるならN-1
塊が2つになるならN-2
塊がi個になるならN-1 - i
といえます。
最終的な塊の数は
最初の塊の数 - 2*K
で求められるので、答えが出せるのではないでしょうか。

説明が鬼下手。

疲れたので終わらせに行きます。

今までにしたこと

atcoder problemsでC埋め
最近のDであれば前のよりは簡単なのでちょっと手を出したり

A, Bは本当に初めたばかりの時以外はやっても時間の無駄かと思い手をつけておりません。
とりあえず緑安定させたかったので、Cを重点的に。
水色になりたいのですが、Dをやらないと厳しそう
Cを全埋めする合理性はあまりなさそうですが、意地があるので一旦埋めてからDをもう少し手をつけようかと思っております。

疲れたので終わります。

ABC 137 pythonのプライオリティキューを使おう

どうもーーー

近頃はアプリ開発したり、ハッカソン参加したりしてます。

昨日はABC137に参加したのですが惨敗してしまいました。

A,B,Cの3完で、Cで9ペナを出して90分ぐらいになりました（泣）
めちゃくちゃ悔やまれますが、気を取り直してやっていきたいと思います。

以下レーティング推移

伸び悩み。

さて、D問題は解けなかったのですが、考え方は合ってて、Priority Queueを使っていれば通せてました。
完全に頭の中から抜けていた。。。

過去にも何回かPriority Queueの問題に出くわしたことはあったのですが、なんか面倒で勉強せず放置しておきました。

今後はそのような惨事を防ぐため、ここで復習しておきたいと思います。

とりあえずDの解答から（メイン部分のみ）

N, M = LI()
AB = [LI() for _ in range(N)]
# 日付ごとに報酬をまとめる
AB_dict = {}
for ab in AB:
    if ab[0] not in AB_dict.keys():
        AB_dict[ab[0]] = [ab[1]]
    else:
        AB_dict[ab[0]].append(ab[1])

ans = 0
pq = queue.PriorityQueue()
keys = AB_dict.keys()
for i in range(1, M+1):
    # 残りi日
    if i in keys:
        for ab in AB_dict[i]:
            # 最大値から取り出したいので以下のように入れていく
            pq.put((-ab, ab))
    if pq.empty():
        continue
    ans += pq.get()[1]
print(ans)

1日目からM日後までに稼げる報酬の最大値を求める問題です。
普通は1日目に何を選ぶかを考えるのですが、そうすると、最適な報酬が選べません。
例えば、報酬の高いものから選ぶようにすると、
3 10
2 1
1 15
のときに、
初日に15の報酬がもらえる仕事から選んでしまい、最適な戦略から外れてしまいます。

そこで逆の発想です（これはD問題とかに多いのでサクッと思いつきました）
M日目にする仕事は、1日後に報酬がもらえる仕事で報酬が最大のものを選ぶのが絶対最適です。
そうすると、M-1日目には、2日後、1日後に報酬がもらえる仕事の中で、
M日目に選ばなかった仕事のなかで報酬が最大の仕事を選ぶのが最適です。

このように考えると、必然的に1日目に選ぶ仕事が決められます。

これを実行するために、まずは報酬発生日時で仕事を分けていきます。

それを今回はdictに入れましたが、これはリストでも良いと思います。
その後、1日前、2日前、・・・とM日前までシミュレーションしていきます。

その際、dictから1日前の仕事の報酬をPriority Queueに入れていきます。
報酬最大の仕事を取り出したいので、(-(入れたい値), 入れたい値)という値をqueueに入れていきます。
priority queueは、要素を昇順にソートし、最小値から取り出すことができます。
ですので、-(入れたい値)を格納することで、最大の値が最初に出てくるようになります。

今回は、普通にforループを回してqueueに入れていきました。

あとはそれを取り出して解答に反映していくだけです。

このやり方でいつも使えるかはわかりませんが、一旦基礎的な使い方はこれで良いと思います。

以上

python/競プロでローカルでテストしてから提出する場合のテンプレを作りました。

どうもーー

久しぶりに更新します。
ここ3ヶ月間ぐらい色々ありました。

ハッカソンに参加して、小さいですけども優勝することもできました。
そちらについても気が向いたら書こうと思います。

今日は、競プロの環境についてちょっと書いておきたいなと思います。

もう今日プロに参加しはじめて半年以上たちます。

4月5月6月は事情により参加できなかったのですが、最近少し参加しています。
レート推移はこんな感じ。

レート推移

今日は、アルゴリズムがどうこうよりも、競プロのテンプレ的なメモです。

いつもみなさんはテストケースなどはどのように試していますか？
試していない猛者はおいておくとして、僕はvimでコードを書いているので、ローカルでpythonを実行して、入力を貼り付けしてテストしていました。

しかし、これだいぶ効率悪いなと今更ながらに気づき、改めることとなりました。

要件としては、
1. 入力を一回貼り付けたらそれですむようにしたい
2. 外部ファイルにするのが面倒なので、ソースコード内にinputを置いておきたい
3. 提出時はスルーされるように
の3点を満たすように考えました。

色々と説明する前に、一旦完成形を載せます。

import os

def main(N, A):
    # 処理を書く
    return N 


if __name__ == '__main__':
    if 'LOCAL' in os.environ:
        # ローカル実行時のみ通る処理
        # テストしたい入力を入れておく
        input_values = [
                """3
7 6 8
3
                """.strip(),
                """3
12 15 18
6
                """.strip()
                ]
        for input_value in input_values:
            input_value = input_value.split('\n')
            N = int(input_value[0])
            A = list(map(int, input_value[1].split()))
            ans = main(N, A)
            expected_value = int(input_value[2])
            assert ans == expected_value, 'failed: ans: {ans}, exp: {exp}'.format(ans=ans, exp=expected_value)
    else:
        # 実際に提出したときの処理
        N = 'some_input'
        A = 'some_input'
        print(main(N, A))

ポイントとしては、環境変数を利用して、ローカル実行時と、提出時の処理を変えています。
LOCALという環境変数があれば、ローカル実行となります。
これは

LOCAL='なんらかの値 ' python my_code.py

のように実行すると、LOCALというキーで環境変数が設定されるので、最初のif文の中の処理を実行できます。
提出時はLOCALには値がセットされていないので、elseの中の処理が実行されます。

input_valuesに入力値を貼り付けた後、リスト化、数値化などの処理は問題によりけりですが、基本的にはリストの中に入力をstringとして突っ込んで、1つ1つ取り出して上手くやるという感じです。
今回は実際にAtCoderの入力をそのまま貼り付けています
空白とか無駄なものがついてくるので、一応今回はstrip()しています。

最後に、assertを利用してやることで、失敗ケースで止めるようにしました。
その際、""" """内に入力した入力値の1行下に、正解の値を入れるのが良いと思います。
お好みで。

以上、ローカルでpythonで競プロに参加する場合のちょっとしたテンプレでした。

かんたんな問題では利用する必要はあまりありませんが、何回もテストしてから提出するぐらいの問題であれば使えるのかなと思います。

ABC124ただの感想

どうもーーー

さて、懲りずにABC参加。

結果はABC3完(57m)
普通に爆死。

つらい。
でもABCに限って言えば、今回ほど出来が悪い回は無いという感触なので、もう大丈夫だと思う。

今回の最大の敗因。
それはB問題。

条件を取り違えていた。

これ、H1 <= Hi、かつH2 <= Hi、かつ、Hi-i <= Hiであれば良いという条件と間違えた。
本来は前にあるどの山よりも大きいという条件なのに。

しかも不運なことに、これに気づかなかったばかりか、質問を見てみたら改行の問題でWAになってましたみたいな。

ああー、これ俺のこと？？

と思って放置してCを解き始める。

C解けたからB見たけどまだ直ってないなー。

まあD考えよう。

あー、rejudgeされてる？？
B見たけど直ってない？？？

これは俺のミス

ってなってあわてて上の条件を何回も何回も見直しました。

さすがに自分を殺したくなった。

A:
普通にアホみたいに実直に問題文を再現した。

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

A, B = LI()

ans = 0
for i in range(2):
    if A >= B:
        ans += A
        A -= 1
    else:
        ans += B
        B -= 1

print(ans)

B:
死んだ。
ある山の前にある全ての山が低いか同じ高さであることを証明。
てか2個目のifいらんやん。
焦りが見える。

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N = _I()
H = LI()
ans = 1
for i in range(1, N):
    if all(H[j] <= H[i] for j in range(0,i)):
        if H[i-1] <= H[i]:
            ans += 1
print(ans)

C:
ここ最近の傾向として、AtCoderのそもそもの人気もそうだけど、受験が終わって強い若者が続々参入してきて、明らかに
パフォーマンスが出にくい。
強いひとたち早くABC卒業してほしいいい。

あと、最近のCが簡単すぎるっていうのもある？？
Dとの差が大きい感じ。

問題のほうは、交互に塗る0101010か、101010101
しかないので、最初を0にする場合と、最初を1にする場合でどちらが手数が少ないかを比べるだけ。

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

S = input()
# 2通り試せばいい
# 最初を0にするか1にするか
current = '0'
ans1 = 0
for s in S:
    if s == current:
        if current == '0':
            current = '1'
        else:
            current = '0'
    else:
        # 塗り直し
        if current == '0':
            current = '1'
        else:
            current = '0'
        ans1 += 1

current = '1'
ans2 = 0

for s in S:
    if s == current:
        if current == '0':
            current = '1'
        else:
            current = '0'
    else:
        # 塗り直し
        if current == '0':
            current = '1'
        else:
            current = '0'
        ans2 += 1

print(min(ans1, ans2))

D:

Dの中では簡単な方だったのではないか。
実際通した人も多かった模様。

自分も考察は合ってたが、焦ってたのもあって実装ミス。

0の区間をリストアップ。
011001100
なら
0~1, 3~5, 7~9
みたいな。
0~1と7~9だけ反転しても意味がないので、隣り合った区間を同時に反転させる。
これは左から右に区間をスライドしていけばよい。

0~1、3~5反転
3~5、7~9反転
というように。

その際、始点と終点だけ考えれば良いので実際に反転させる必要はない。

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, K = LI()
S = input()

positions = []
idx = 0
keep = None
while idx < N:
    if S[idx] == '0':
        if keep == None:
            keep = idx
    else:
        # 1の場合は無視
        if keep != None:
            positions.append([keep, idx])
            keep = None
        else:
            # keepしない場合
            keep = None
    idx += 1
else:
    if keep != None:
        positions.append([keep, keep+1])
#  print(positions)
if len(positions) == 0:
    print(N)
    exit()
elif len(positions) <= K:
    print(N)
    exit()

ans = 0

for idx in range(len(positions)):
    if idx + K - 1 > len(positions) - 1:
        break
    if idx == 0:
        left = 0
    else:
        left = positions[idx-1][1]

    if idx + K - 1 == len(positions)-1:
        end = N
    else:
        end = positions[idx+K-1+1][0]
    #  print(end, left)
    ans = max(ans, end - left)
print(ans)

最近の精進は、彼女がメキシコから来たのでずっと家で書くわけにもいかず、基本は移動時間にスマホで
投稿するというスタイルが多い。

こんな感じ。

誰かモバイルの良いpython editorあれば教えてください。

python3 ideは日本語入ってると落ちるのでやめました。

AtCoderエクサウィザーズコンテスト参加録/一応緑になった話

どうもーーー

昨日はエクサコンに参加しました。

結果から言うとAB2完でした。
ただクッソ早く解いたので、（ABだけの速度なら80位だったのを確認した）、レートはめちゃ上がりました。

2分で2完で緑になったｗ
普通にうれしーー#AtCoder pic.twitter.com/6mXtHFp1ko

— 寺.py (@mktrdbg) 2019年3月30日

ようやく念願の緑。
これで当分気持ちよく寝ることができそうです。

そして解けなかったものの、Cもそこまで悪くはなかったかなと。
ちゃんと左端に落ちるやつで一番右にいるやつと、右端に落ちるやつで一番左にいるやつを求めればというところまでは
考察できましたが、二分法を使えば良いというのが湧いてきませんでした。
これは普通に精進不足。でも次からは二分法の問題出たら絶対解けると思う。
整数でsortされてたものにはいつもbisectを使ってたのですが、自分で書くとなるとなかなかできないですね。

ちゃんと翌日Cを解きました。
別解である逆順で見ていく方法も、他の方のコードを眺めて理解だけはしました。賢い。

一応書き直したつもりの提出
なかなかひどいコードですが、二分法、慣れていこうと思います。

https://atcoder.jp/contests/exawizards2019/submissions/4786891

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
s = input()
TD = []
T, D = [], []
for i in range(Q):
    t,d = LS()
    TD.append([t,d])

def get_mid(lb, ub):
    if lb + ub < 0:
        return 0
    else:
        return (lb + ub) // 2
# 左から落ちるものの探索
# 2回midが同じならやめる
def find_left_dropped():
    lb, ub = -1, N
    while True:
        if lb + ub < 0:
            mid = 0
        else:
            mid = (lb + ub) // 2
        original_mid = mid
        for td in TD:
            if td[0] == s[mid]:
                if td[1] == "L":
                    mid -= 1
                else:
                    mid += 1

                if mid == -1:
                    # 左に落ちた
                    lb = original_mid
                    if get_mid(lb, ub) == original_mid:
                        return original_mid+1
                    break
                
                if mid == N:
                    # 右に落ちた
                    ub = original_mid
                    if get_mid(lb, ub) == original_mid:
                        return original_mid
                    break
        else:
            # 落ちなかった
            ub = original_mid
            if get_mid(lb, ub) == original_mid:
                return original_mid

def find_right_dropped():
    lb, ub = -1, N
    while True:
        if lb + ub < 0:
            mid = 0
        else:
            mid = (lb + ub) // 2
        original_mid = mid
        for td in TD:
            if td[0] != s[mid]:
                continue

            if td[1] == "L":
                mid -= 1
            else:
                mid += 1

            if mid == -1:
                # 左に落ちた
                lb = original_mid
                if get_mid(lb, ub) == original_mid:
                    return original_mid+1
            
            if mid == N:
                # 右に落ちた
                ub = original_mid
                if get_mid(lb, ub) == original_mid:
                    return original_mid
                break
        else:
            # 落ちなかった
            lb = original_mid
            if get_mid(lb, ub) == original_mid:
                return original_mid + 1

left_survived = find_left_dropped()
#  print(left_survived)
right_survived = find_right_dropped()
#  print(right_survived)

result = right_survived - left_survived
print(result)

初めてのコンテスト参加が1/13で、約2ヶ月半で緑になれたのは良かった！

一応歴代成績はこんな感じ。

最初のレーティング4ですw

精進はこんな感じでCばっかやってます。

疲れるのでストリークとかは一切気にせずやってます。

純粋なABCのCだけで言えば36問解いてるので、そろそろD問題もちょいちょいやっていこうと思ってます！

あとtwitterでもちょこっと書きましたが、メキシコ人の彼女が日本に来ます。
なのでコンテストあんま参加できなくなるかもーという懸念があるのですが、それとは別に
緩募な感じで、獣医のニーズがあるか知りたいです！

スペック
日本にもうすぐ住む予定
メキシコ国立自治大学で獣医資格持ち
日本語は割と知ってるけど、これからもっと勉強
英語はまあいけます
（スペ語ネイティブ)
26歳

私としては、スタートアップとかで動物系があればアツいなーと思ってるのですが、、、
まあとにかく今後仕事探すことになるので、何か知ってれば教えてほしいです！

AtCoder ABC121のただの感想

どうもーーーーー

懲りずにまたABCに参加。

結果は初の全完。

今回は全完がいつもより多いみたい！
ラッキー

それでは適当に感想

A:
B,Cよりも悩みました笑
(Aなのに5:27もかかった。)

H, W = LI()
h, w = LI()
 
print((H-h)*(W-w))

もともとの幅-黒い部分の行数
と
もともとの高さ-黒い部分の列数
を
かけあわせると白い部分の四角の面積が求まる！

■■■□□
■■■□□
■■■□□
■■■■■
■■■■■

これなら5-3と5-2をかけると、白い部分が出ます。

もっとはやく解けるべきである。

B:
素直に問題文の条件をコードに落とすだけ。
気をつけることはない。

N, M, C = LI()
B = LI()
A = []
for i in range(N):
    A.append(LI())

res = 0  
for i in range(N):
    x = sum([A[i][j] * B[j] for j in range(M)]) + C
    if x > 0: res += 1
print(res)

普通に格納されたAの各行に対して、BをかけたものとCを足して、0より大きいかを比べて大きければresultに1を足していくだけ。

C:
貪欲。数少ない私の知るアルゴリズム。
pythonだと普通にソートするだけでいいから楽。

N, M = LI()
 
AB = []
for i in range(N):
    a,b = LI()
    AB.append([a, b])
 
# ただ安い店から買い叩いていくだけの話
AB = sorted(AB, key=lambda x:x[0])
 
count = 0
idx = 0
cost = 0
while count < M:
    if AB[idx][1] > M - count:
        # この店で終わりの場合
        cost += (M-count)*AB[idx][0]
        count = M
        break
    else:
        # 全部買う
        cost += AB[idx][0] * AB[idx][1]
        count += AB[idx][1]
    idx += 1
 
print(cost)

sortのところでkeyを指定してるけど、いらなかったな。
てかこれ、せめて価格と本数の入力を逆順にするべきだったのでは？？

最後のループは変数が多くて気持ち悪い感じになってしまいましたが、今まで買った本数をcount, それまでにかかったコストをcost,訪れる店の番号をidxで管理しました。

訪れた店のレッドブルを全部買うべきなら、その店の値段と本数をかけたものをプラス。
訪れた店の在庫のほうが、足りない本数より多い場合は、その店で買って買い物終了なので、足りない本数×その店の値段を足して終了。

D:

初Dをリアルタイムで通せた。
しかし、正直理解してません。
気合で通しました。
競プロは気合が命。
気合があればDも通る。

A, B = LI()
if B % 4 == 0:
    # 0になるのが1つ前
    pass
elif B % 4 == 1:
    # 0 になるのが2つ前
    B = B^(B-1)
elif B % 4 == 2:
    # 0になるのが３つ前
    B = B^(B-1)^(B-2)
elif B%4 == 3:
    B = 0
    
A = A - 1
if A % 4 == 0:
    pass
elif A % 4 == 1:
    A = A ^ (A-1)
elif A % 4 == 2:
    A = A ^ (A - 1) ^ (A - 2)
else:
    A = 0
 
print(A^B)

この解答を見ると気合のほどが伝わってくるのではないでしょうか。。

まあ思考の過程をたどると、まず値がかなりでかい。10**12て。
これは計算させる気はないなと思いました。
DPなどもさすがにこの桁数になると関係ないだろうーと思って。

ということであんまりXX法的な話では無いかなーと思い。とりあえず0~8までを紙に２進数で書き出して、
いろいろxorを取ってみました。

そうすると、このように0-3-7-11といったように、４個ごとにxorが0になるという規則性を見出しました。
これが気合の力。
（ちなみに２個毎に１になるという規則性もあるらしい）
つまり、20は０から数えたときに21番目なので、20の2進数が0-20のxorになります。
21の場合は0から22番目なので、20と21のxorになります。

しかしそれだけでは解けず。
さらなる気合を注入し、
0-5のxorを取った後、0-3のxorを取って、その2つのxorを取ったりいろいろしてたら、たまたまそれが正解だった。

こうして一切のかっこよさのない解答ができましたとさ。めでたし。

つまりこのD正答は、偽。
他のD問題等にあまり汎用性のない解き方をしてしまった感。
小手先のテクニック。

まあしかし今は良しとしよう。少しずつ伸ばしていく。

なんとかあともう少しで緑というところまできた。
まあ右肩上がりだしよしとしよう。

AGCで１完だったらレーティング下がるかな？？

参加するか悩む。
早く解けたら提出しようかな。

ま、今回はこんなところで。

ABC 120 ただの感想

どうもーーーー

花粉。この一言で終えてしまってもなんら不足ない今日この頃。

殺してくれ〜〜〜！！！

さて、AtCoderのABCに参加しました。

今回は
A:音
B:割り切れる
C:箱
D:島と橋

というテーマでした。
（だから何）

ではここからただの感想

A:
高橋くんと出てきた時点でまず問題文に集中できない。

B円で聞ける最大回数と、C回を比べて小さいほうを出力しました。

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


A, B, C = LI()

result = B // A
print(min(result, C))

B:
約数が出てきた時点で吐き気を感じました。

とりあえず愚直に書きました。
両方を割り切れる数字を下から数えていってリストに格納。
ループしきったら大きい方からK番目を取るだけ。
最近はちゃんと制限を見て、これは全探索だとかなんとか一応考えながらやるようにしてます。
（この間のC問題の件もあるし）

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

A, B, K = LI()

nums = []
for i in range(1, 101):
    if A % i == 0 and B % i == 0:
        nums.append(i)

print(nums[-K])

C:
今回のC問題は箱ではありますが一切箱を意識しない問題でしたね。

最初、確認するのが面倒で、まあN<=10**5ぐらいならいいかーと思って提出したらTLEになったのでちゃんと考えました。

幸いすぐに0と1を数えて少ない方の数の2倍だと気づけたので通せました。

面倒ですが制限をみてちゃんと時間内にできるかも確認しながら最近はやるようには心がけています。
（コメントのような感じで）

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

S = S()
#  S = ''
#  for i in range(10**5):
#      if i % 2 == 0:
#          S += '011'
#      else:
#          S += '1'

# 0と1すくない方の数になる絶対
print(min(S.count('1'), S.count('0'))*2)

D:
端から解けるとは思っていませんが、毎度チャレンジします。
今回はデータ構造とかテクニカルなことはまだ準備できていないので、とりあえず愚直に書こうと思いました。

しかし実装でぐだり、愚直実装がようやく終了10分前とかにできて、そのあとこれは後ろから見れば良いのだと気づきました。

まあしかしその程度では到底間に合わんだろうということでジ・エンド

なんらかの木構造を使いたかったのですが、Union-Findその他データ構造は蟻本で眺めたことしかないので使えません。。

もう8回も参加したのか。。。
今回はパフォ998の、レーティングプラス59でした。

そろそろ上がりづらくなってきたな〜。

来週再来週とAGCだし解けないし、一旦の目標である緑へはまだ２ヶ月ほどはかかりそうだ。

これからの方針として、C問題を重点的に対策することにしました。

AtCoderで手っ取り早く緑に到達するには、ABCのCだけを解いていけばよい、という結論に至った。
Cを確実に毎回解けるようにする。Cだけを解いていこう。蟻本は眺めるだけにする。

— 寺/django,vuejs (@mktrdbg) March 3, 2019

というのも、A問題はまずプログラミング自体はできるのであまり勉強にならないので却下。

B問題も問題文のままの実装が多いため却下。

C問題は解けないときもままあるので、勉強になります。
アルゴリズムとかもいい感じででてくるし。

Dは難しすぎて今やる意味はあまりありません。

蟻本も難しすぎてあまり本気でやる効果は薄い状態です。

２ヶ月後には緑になりたいので精進します