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

R XOR操作が出てくるので i を２進数表示したときの n 桁目を (i>>n)&1 であらわす。 全探索は行ごとでするのに、総和は列ごとに数えるのが面倒くさい。 numpy を使って転置するか、A.sum(axis=0) で列ごとに和を取っていくとよい。 np.count_nonzero(A,axis…

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も最初から因数分解…

b より大きく、a 以下の数字の積の約数の数の個数を求めればいいのだけれど、b,a が大きすぎてそのまま掛け算をするとオーバーフローする。 なので一つずつ素因数分解して、個数分だけ素数をリストに入れていって、あとで collections.Counter で数えた。 a,…

C - Align数列を並び替えて隣り合う２数の差の最大値を求める問題。 直観的に一番小さいものと一番大きいものが隣り合うように、出来るだけ真ん中に置くように並べるのがいいと予想できるが、単にそれを実装するのではなく、 隣り合う２数の差 = 大きいもの…

今回の反省と学び 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 に入れる。時間を増やす要因が通過時間と通貨を交換する時間の二つ（疲れているのでダジャレみたいになっている）あるので、交換するか、移動するかで分けて考える。移動…

拡張ダイクストラの簡単な問題ということで、まず解いてみました。通常のダイクストラと何が違うかというと、例えば、頂点が3つなら最小距離を保存するリスト d も d = [float("inf")] * 3 とかで十分でしたが、今回の問題のように、総距離が４の倍数になる…

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…

二分探索で最小値を探すやつ。蟻本３－１－３ 二分探索は値の探索をするだけなので、最小回数で動作終わるようにするための必要十分な動作方法を、主に貪欲法で見つけてくる方に難易度が関わってくる。 今回は左端 ( X0 ) から順に arg回で、それより左側の…

二分探索２つめ。 答えを n と仮定したときに n が条件を満たすかどうかは (a, b) = (x, 1)*k + (1, y) * (n - k) とおいたときに、R >= a かつ B >= b を満たす 0以上 n以下の整数 k が存在することと同値である。 （厳密にはさらに n これを正負に注意して…

二分探索の問題。二分探索はここのサイトがとても参考になった。 めぐる式二分探索 コピペで使える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の約数…

素数についての謎の知識を二つ得た 1. p が素数のとき、x^n % p = x^(n%(p-1)) % p 2. p-1 > c > 1 のとき、x^n+y^n≡c (mod p) を満たす個数は０または x^n+y^n≡1 (mod p) を満たす個数に等しい。 証明はここをみてください。 フェルマー方程式/Fermat(JOI20…

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

C - Next Letter 先頭から a に変えれそうなら a に変える、最後尾までみたときにまだ k が残っているなら k が０になるまで最後尾の文字を変える s[ i ] を ' a ' にするときに毎回 s = s [ : i ] + ' a ' + s [ i + 1 : ] としているのは何とかならないの…

D - HarlequinAtCorder Problems でおすすめされていたので解いた 実験していくうちに、A1,A2,..,A(n-1),An と A1,A2,...,A(n-1),An+2 A1,A2,..,A(n-1),An,２ との勝者が同じではと気づいた よってA の中に奇数が一つでもあれば first になり、すべて奇数な…

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