自力AC。解説とは若干違った。むしろ解説がよく分からん。 ぱっと見で01ナップザック問題じゃんとなり、dpするだけなのかと普通の (N*T) の二次元dp を実装したらサンプル３が合わず考えると、T-1 秒までなら T 秒を超えても注文ができるのが原因だと分かる…

自力AC。差の絶対値の総和を求める。 こういうときは | n - m | = max(n,m) - min(n,m) なので、a より小さいものの数、大きいものの数を x 座標と y 座標で別々に求めたらよい。これの一次元版を解いたことある気がする。 1 そして X座標が x となる頂点の…

XOR の知識 1．a^a = 0, a^b^a = a^a^b = b（交換法則） 2．n%4 = 1 のとき 1^2^...^n = 1, n%4 = 3 のとき 1^2^...^n = 0 (ABC121 D)2. から 1^2^...^2**m-1 = 0 となり、1. から k 1^2^,...,^k-1^k+1^,...,^2**m-1 = k となる。 考察はできたが実装が手こ…

i 文字目を A にした時の文字列の作り方の総数を f(i,0) = dp[i-1][0] として f(n) = sum(dp[n-1]) を求める。 例えば７文字の作り方の総数 f(7) を考えるときは新たに条件を満たさなくなるのは、 ○○○○AGC、○○○○GAC、○○○○ACG、○○○A○GC、○○○AG○C、 となるもの…

a[p]+b[q]+c[r] の最大値を k 個求める問題。 取り合えず逆順でソートすれば、最大値は a[0]+b[0]+c[0] になるのは確定で、その次に最大になるのが、a[1]+b[0]+c[0], a[0]+b[1]+c[0], a[0]+b[0]+c[1] のどれかだと分かれば後は heap で k 回ぶん回すだけ。気…

100分フルに消費して4完。レート微増。参加者のレベルも上がっている気がする？自分の成長速度があまり感じられない。二連続ぐらいで水パフォ取れると安定しそうだけどなぁ ｃは2回続けて全探索に殺されてたので流石にできた。c は numpy で行ごとに足せれる…

XOR っぽいけど本質はそこじゃない感じの問題。 本質は s = 0011100... と並んでいたら、s[0 : ], s[2 : ], s[5 : ] で操作する回数が異なっている必要があるということ。 なので s[2], s[5] で区切る必要があり、これを満たす最大の長さは min( max(2,len(s…

女子の選びだけ itertool で nCp 通り全列挙して男子の選び方を貪欲に選んでいく。 collection.Counter で most_common(q) とかして選んでいたら TLE したので普通にリストに入れていって上から q 番目まで取ったらいけた。 import sys input = sys.stdin.re…

a として実装した。 import sys input = sys.stdin.readline n,m = map(int,input().split()) chk = [] for i in range(n): a,b = map(int,input().split()) if a <= m: chk.append((a,b)) from heapq import heappop, heappush from operator import itemge…

数列を前から見ていって、二分探索でその数字が今の数字の色の種類のどれに上書きできるかをを探して、上書きできる奴で、一番数が大きいものにその数字を上書きする。 貪欲法の練習問題で箱を入れていくやつと同じ考え方。 D - プレゼント0 なら色の種類を …

文字列をアルファベットのリストに入れていって二分探索したらいいやつ。 s = contest, t = cc みたいなときに 一つ目の c と二つ目の c が同じ答えにならないように 見ている t の位置が更新するたびに ans += 1 してデバッグするのに 15 分ほどで気づけた…

abc で冷えた後なのでこういう問題は冷静に瞬殺できる。 明らかに全探索するわけがなく、数学的要素が強そうなので素晴らしい。 x,y に至るまで (+1,+2) を i 回、(+2,+1) を j 回したとすると、 x = i + 2*j, y = 2*i + j となって 答えが０でないためには …

３完。負け。いつも愚直に全探索するだけの問題を難しく考えすぎてそこで詰まる。 全探索するかとは一回は思うのだけど、今いち全探索しても間に合う制約なのかどうかが全く分からず結局他の方法を考える→時間切れみたいになっている。 Dも最初から因数分解…

今回の反省と学び 19C10 ≒ 46000 くらいの全探索が通ること。（総数が19C10 なのは分かっていた） 重複組み合わせの itertools が用意されていること。 itertools 使うときは順列の要素がデフォルト時は 0 から始まるので注意 次は5完する。 import sys inpu…

サンプル２が結構ヒントになった。 まず m が最大値の時に条件を満たせばいいとわかる。 そして、初めの割り当ての２数 ( a, b ) の差(a 一周すると (1,b+n-a+1) となるから、 n = 奇数のときは一周すると偶奇が変わる、n = 偶数のときは偶奇が変わらないと…

a,b,d,e の４完。cは 19C10 の全探索が間に合うとは思えず敗戦。 その代わり青diff の数列の問題をかじっていたおかげで e を解くことができた。考え方自体にはあんまりないけど、この前解いた abc 094 d-Worst Case に印象は似ていた。 d は、x//b が一定の…

尺取り法：数列の連続した部分列にあてはまる条件を O(n) で求めてくれる優れもの。 XOR四天王の二人目を倒しました。(弱さも多分2番目) 個人的な尺取り法の実装については、条件を満たさなくなった瞬間に（部分列の長さ - 1）を使って求めたいものを求めて…

青diff 初の自力AC 解説はX = (ak/2) ∗ (2p + 1) を X が 2 で割り切れる回数と ak/2 が 2 で割り切れる回数が同じ と言い換えててあたま良すぎかとなった a のなかにひとつでも ( aj / ai )% 2 == 0 となるものがあれば答えが 0 になって、そうでないなら答…

最大マッチング問題というらしい。 解説を読んだら理解はしたけど n= (a*b)**0.5 d = int(n) if n.is_integer(): d -= 1 ans = d*2-1 と c= int((a*b-1)**0.5) chk = 2*c-1 が同じものになると思っていたので、間違え続けた。（例えば、(a, b) = 134576397, …

ワーシャルフロイド法を二回使うらしい。思いつけるのか？ 解説読んで5分くらい考えて解説が正しいことを理解した。 python だと from scipy.sparse import csr_matrix from scipy.sparse.csgraph import floyd_warshall で簡単にワーシャルフロイド法ができ…

拡張ダイクストラで解く。総時間、頂点に加えて今持っている銀貨の数を追加して heap に入れる。時間を増やす要因が通過時間と通貨を交換する時間の二つ（疲れているのでダジャレみたいになっている）あるので、交換するか、移動するかで分けて考える。移動…

158 E を解いたことがあるのに関わらず、d が解けずに敗戦。a の羊を半分と誤読し続けたせいでパフォも最悪でした。失敗を二つもしたらそうなる。 考え方は int( s[ i: j+1 ] ) が2019の倍数 ⇔ int( s[ i : ] ) - int( s[ j : ] ) %2019= 0 (2019と10が互い…

f (t) = a * t + b * sin( c * t * pi ) として、 f (t) - 100 中間値の定理から、f (left) - 100 0 (left f (t) - 100 0 なら、t = (t + left)/2 として探索範囲を狭めていけば答えに効率的にたどり着く。 a,b,c = map(int,input().split()) import math de…

二分探索の問題。二分探索はここのサイトがとても参考になった。 めぐる式二分探索 コピペで使えるPython実装 - 学習する天然ニューラルネット 答えを arg と仮定した場合にそれが条件をみたすなら、arg+1についてもまた調べる、満たさないなら、arg//2 につ…

文字列 s から作られる部分列の中で辞書順で k 番目に小さいものを求める問題。 k import sys input = sys.stdin.readline s = input().rstrip() l = len(s) k = int(input()) chk = set() for i in range(26): for j in range(l): if s[j] == chr(i+97): fo…

題名からして素因数分解するのは間違いないとして、約数の積が何通り作れるかを考えるのだが… 頭が固くて自力では解けなかった。解説AC 例えば n=4 , m=360 (2^3*3^2*5^1) とすると答えとなるものは A1*A2*A3*A4 = 360 となるものであるが、 A1 は 360の約数…

10**5までの素数のリストをどう作るのが早いかという話。 とりあえず python 素数判定 高速 でググってこれをコピペしてみた。ミラーテストというらしい。 Pythonを使って高速素数判定をしてみる - Pashango’s Blog k = 13 のときで 1700ms だった。 4**13分…

A の小さいものを Ci のうち一番大きいものに変えていくのが一番大きくなるなあと考えた。 大きいものから変えていくので、N枚変える or Aの最小値が現在の Ci 以上になったらそこで終了してよい。 最小値を取り出すのを heapq で高速化 値の変更がなくても …

最近緑diff をすんなり解けるようになって成長を感じる。上達というよりは緑diff 程度の問題なら考えることはこのくらいかな～みたいな頭の動かし方に慣れてきたんだと思う。今回は数列の隣り合う２数の正負を好きなようにして最大値を求める問題。 負の数が…

直観的に一回の動作で、１と１との間にある０を全て１にする、 次の動作では、前１にしたところより１つ右にある０の塊を全て１にする… という動作をｋ回繰り返したものの中から連続して１が並ぶ最大値が作れるとわかる Sのなかに０が連続していくつあるか、…