競プロリハビリ開始とバチャ反省
競技プログラミングを再開しますという話
AtCoderのコンテストに最後に出たのが2020/5/31なのですが、そろそろ一年経つので6月になると同時に(つまり、ぴったり一年経つと同時に)コンテストに復帰することにしました。5月中をかけてゆっくりリハビリしていきます。
バチャリンク
https://kenkoooo.com/atcoder/#/contest/show/a1ca2d09-73b4-4248-9f1b-879cd95bd2b3
解説
1. 仲良しうさぎ
概要
各ウサギが好きなのは一匹なので、あるウサギについて2ペア以上組んでいることはあり得ません。よってそのウサギが好きなウサギと両想いかを確認していけばよく、求まる数が「両想い属性を持つウサギの数」なので、最後に2で割るとペアの数になります。
実装
自分が好きなウサギの好きなウサギが自分であるかどうかを見ればよいです
N = int(input()) alist = list(map(int, input().split())) ans = 0 for i in range(N): if alist[alist[i]-1] - 1 == i: ans += 1 print(ans//2)
2. Good Sequence
概要
元の数列のうち、いい数列の要素になりえる数の条件は「自分自身より個数が多い」数です。3が5個あれば2個減らすことで3-3になりますが、3が2個しかなければいい数列の要素として残せません。ある数KがV個ある時、K<=VならばV-K個削り、K>VならばV個全て削る、という操作をすべての要素に行うことで最小手数でいい数列が求まります。
実装
個数を数えるにはCounterが便利です
from collections import Counter N = int(input()) alist = list(map(int, input().split())) ac = Counter(alist) ans = 0 for k, v in ac.items(): if v < k: ans += v else: ans += (v-k) print(ans)
3. ∵∴∵
概要
OとEを交互に足していきます。終わりです
実装
listに変換するとpopが使えてうれしいです
O = list(input()) E = list(input()) ans = "" while O: ans += O.pop(0) if E: ans += E.pop(0) print(ans)
4. 100 to 105
概要
商品は最低100円なので、どのように買っても X // 100個は買えます。そうすると端数がX % 100円発生するので、その端数を作り出せるかが問題となります。1桁目を見ると1~5円があるので、一番大きい5円を最大限使った場合が表せる最大の数になります。よって(X // 100)*5が(X%100)を上回っていれば、可能です。
実装
上の話を実装するだけです
from math import ceil X = int(input()) can_buy_num = X // 100 mod = X % 100 if mod <= 5 * can_buy_num: print(1) else: print(0)
5. Choose Integers
概要
何を足してもいいと言っていますがAの倍数縛りがあるので、結局和もAの倍数です。 よって「A*N % B == CとなるNがあるか？」を探索すればよいです。
実装
よくわからなかったのでN=1000まで回しました
A, B, C = map(int, input().split()) for i in range(1, 1000): if (A*i) % B == C: print("YES") break else: print("NO")
6. To 3
概要
3の倍数の性質として、「各桁の和が3の倍数になっている」というのがあります。よって、和が3の倍数になるかだけをみたいので、すべての数をmod 3で考えてよいです。
与えられた数列 mod 3をSとして、Sの総和のmod 3をとったものをXとします。Xが0なら最初の時点でOKです。Xが1の場合はSの1を一つ、あるいは2を二つ消すことでXが0になります。Xが2の場合も同様で、Sの2を一つか、1を二つ消すことで実現できます。逆に、これ以外の場合は実現できません。
実装
from collections import Counter N = input() def int_and_mod3(c): return int(c) % 3 Nlist = list(map(int_and_mod3, list(N))) ln = len(N) sn = sum(Nlist) nc = Counter(Nlist) if sn % 3 == 0: print(0) elif sn % 3 == 1: if nc[1] >= 1 and ln > 1: print(1) elif nc[2] >= 2 and ln > 2: print(2) else: print(-1) else: if nc[2] >= 1 and ln > 1: print(1) elif nc[1] >= 2 and ln > 2: print(2) else: print(-1)
7. Minimization
概要
全部同じ値になっているとき、それは最初の数列の最小値になっていることが明らかにわかる。なぜなら、最小値以外をすべて同じにして[2, 2, 2, 2, 2, 1, 2, 2, 2]という風にしても、結局すべて同じになるためには1を含んだ範囲を操作しなければならないからである。
長さKの範囲を操作するとき、最小値を含むことを考えると「新たにK-1の範囲を更新する」と言い換えられる。素直に考えると、最小値を左端に含んで右に動かしていく、右端に含んで左に動かしていく、の二つをすることで全てが1になることがわかる。ここで、端で少しあまることがあるのでそれを反対側に移譲することで最小手数で達成できる。
実装
from math import ceil N, K = map(int, input().split()) Alist = list(map(int, input().split())) min_num_index = Alist.index(min(Alist)) left = min_num_index right = N - 1 - min_num_index extra = (K-1) - (left % (K-1)) if (left % (K-1)) else 0 # print(left, right, extra) right -= extra print(ceil(left/(K-1)) + ceil(right/(K-1)))
8. Ice Tea Store
概要
まず、求められるNが整数なのでQとHはそれぞれ4倍、2倍して1Lの値段に換算して良い。そうすると1Lが三種類出てくるので、その中の最安値を1Lの値段として設定できる。
その最安値の2倍がDより安い場合、すべてそれで買えばよい。Dの方が安い場合、可能な限りDで買い、余った分をできるだけ安く買いたいが、問題より「ちょうどN[L]」という制約があるので、余った場合は先に述べた1Lの最安値で買うほかない。
実装
Q, H, S, D = map(int, input().split()) N = int(input()) Q *= 4 H *= 2 best_price_of_QHS = min(Q, H, S) if 2*best_price_of_QHS <= D: print(best_price_of_QHS*N) else: print((D * (N//2)) + (best_price_of_QHS * (N%2)))
9. ModSum
概要
左に一個ずつずらすと、1~(N-1)に2~Nが割り振られ、「(N-1)%N=N-1」より、そこまでの余りの総和は1~(N-1)の総和になる。最後だけが「N%1=0」になるため、結局1~(N-1)の和を求めればよい。
実装
N = int(input()) a = N - 1 print((a*(a+1))//2)
10. A+...+B Problem
概要
あり得ない場合の場合分けが面倒ですが、あり得る場合は「AとBは最低一回ずつ使う」という条件を用いて、A+BにA*(N-2), B(N-2)を足した範囲が答えの範囲になります。
実装
あり得ない場合の判定が面倒でした
N, A, B = map(int, input().split()) if A > B or (A != B and N == 1): print(0) exit() if A == B: print(1) exit() N_ = N-2 deka = A + B + B * (N-2) tubi = A + B + A * (N-2) print(deka-tubi+1)
感想
案外解けましたが、時間が足りず緑まで行きませんでした。まぁ週2, 3くらいのペースでバチャしてリハビリしていけたらと思います。
