ワーシャルフロイド法を二回使うらしい。思いつけるのか？ 解説読んで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 で高速化 値の変更がなくても …

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

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

i = 1 ~ 2**10-1 まで bit 全探索する問題。 与えられた F を 2 進数としてみると、i ＆ F =１となっている桁の個数でどの P になるかが決まる。 '10' をそのまま 2 進数として扱いたいときは int( '10', 2 ) としてやる。 （ print すると 10 進数表記の 2 …

B - Buildings are Colorful! 制約が小さいのでビルの選び方を n-1Ck-1 通り全探索して間に合う 選んでないビルもビルの最大値に関わることがあることに注意 n,k = [int(i) for i in input().split()] a = [int(i) for i in input().split()] if k == 1: pri…

25分で d まで順調に解けたが e,f がどうにもできず終了。５完の道は遠い。 解説を読んで dp で実装してみたがなかなか手ごわかった。Unrated なので難易度がはっきりしないが本来なら青diff になっているかも。 dp[ i ][ j ] を （An の大きいものから i 番…

Code Jam - Google’s Coding CompetitionsAしか解けず５点差で通過できず。C何とかして部分点取りたかった。インタラクティブはまだ入力の仕方がわからないので諦め。 Aは４方向に i 回目に 2**(i-1) 移動でき、(x,y) = (0,0) から、最終的に目的の座標に到…

maspy さんの解説をひたすら読んだ [AtCoder 参加感想] 2019/12/08:ABC 147 | maspyのHP XOR関連の共通した着目点は、各桁ごとのbit 演算は独立して計算できるということ i を2進数表示したときの n 桁目は ( i >> n ) & 1 で表せる ある桁のXORのｎ個の総和…

ダイクストラ法の問題 この問題は道路を片方向にしか通れないので、１からｋまでの最短路とｋから1までの最短路は別に求める必要がある。 import sys input = sys.stdin.readline n,m,t = map(int,input().split()) a = list(map(int,input().split())) a = …

ワーシャルフロイド法で解く問題 街の通り方は順列で全探索した 計算量は最大(200**3 + 8!) くらいで pypy3 で 330ms def warshall_floyd(d): #d[i][j]: iからjへの最短距離 for k in range(n): for i in range(n): for j in range(n): d[i][j] = min(d[i][j…

素直に問題文を言いかえせずに解いたら解けるという変わったパターンだった。 制約が最大５０＊５０なことを重視するべきだった。 辺を一つ減らして毎回 Union-find をして一つの木でなかったら (大きさが N でなかったら）ans += 1 するという方針 n, m = m…

ほかっておいた蟻本の2-5章を進め始めた 蟻本がC+で書かれていても、先人の方々が python のコードをまとめてくださっているので独学でもなんとか耐えている 神サイト 蟻本 初級編 python カテゴリーの記事一覧 - じゅっぴーダイアリー今回はワーシャルフロ…

Union-find の練習 何回でもスワップできるので、結局 i と p[i]-1 が同じ木にいるかどうかで求まる。 import sys input = sys.stdin.readline n,m = [int(i) for i in input().split()] p = [int(i) for i in input().split()] p = tuple(p) chk = [[set(),…

a から b までのXORの累乗和を計算する問題 1から１５までのXORの累乗和を順に求めていくと、 １、１１、０、１００、１、１１１、０、１０００、１、１０１１、０、 １１００、１、１１１１、０ となっていき、3 (mod4)のときに０になることがわかる また、…

Union-find木 の練習 Union-find のライブラリーはじゅっぴーさんのをそのまま使わせていただいております。 蟻本 python Union-Find木 競技プログラミング - じゅっぴーダイアリーUnion-find はつなげることしかできないので、入力を逆向き (append でなく …

N = 8 なら順列を小さい順にすべて列挙して p, q と一致するものがあるか調べても余裕で間に合う (８！ = 40320) list の == は中身の順番まで完全に一致していると True を返すおまけ set の == は順番は関係なく中身の種類さえ合っていれば True を返す [1…