はまやんはまやんはまやん

hamayanhamayan's blog

2018-02-01から1ヶ月間の記事一覧

競技プログラミングにおける幾何問題まとめ

幾何問題 概要 幾何の知識というか幾何ライブラリを求められる問題がある 実装 参考 反転幾何 テク一覧 全ての座標が異なるx,y座標が10^5くらいの場合は、x^2+y^2が同じ座標が144個くらいしかない 問題 偏角ソート 単純な偏角ソート コドフォでの実装記事(…

Sleepy Game [Codeforces Round #467 (Div. 1) B]

http://codeforces.com/contest/936/problem/BN頂点M辺の有向グラフがある。 最初に頂点Sに石を置いて、順番に石を辺に沿って動かしていく。 動かせなくなったら負け。 10^6回動かすとその時点であいこになる。 「両者が最適に動くとは限らない」とき、先攻…

Save Energy! [Codeforces Round #467 (Div. 1) A]

http://codeforces.com/contest/936/problem/A1度スイッチを入れるとK分間稼働するストーブがある。 自分はD分毎に部屋の様子を見に来る。 もしストーブが切れていたらストーブを着け直す。 料理をするが、ストーブが全ての時間でついていればT分、ストーブ…

E869120 and Good Triangles [yukicoder No.655]

https://yukicoder.me/problems/no/655

Air E869120 [yukicoder No.654]

https://yukicoder.me/problems/no/654

Reversed LCS [AtCoder Grand Contest 021 D]

https://agc021.contest.atcoder.jp/tasks/agc021_d

Tiling [AtCoder Grand Contest 021 C]

https://agc021.contest.atcoder.jp/tasks/agc021_c

Holes [AtCoder Grand Contest 021 B]

https://agc021.contest.atcoder.jp/tasks/agc021_b

Digit Sum 2 [AtCoder Grand Contest 021 A]

https://agc021.contest.atcoder.jp/tasks/agc021_a

E869120 and Lucky Numbers [yukicoder No.653]

https://yukicoder.me/problems/no/653

E869120 and TimeZone [yukicoder No.652]

https://yukicoder.me/problems/no/652

E869120 and Driving [yukicoder No.651]

https://yukicoder.me/problems/no/651

Squared Ends [CSAcademy #70 E]

https://csacademy.com/contest/round-70/task/squared-ends/N要素の配列Aがある。 これをKグループに分ける。 各グループ[A[l], A[l+1], ..., A[r]]について(A[l] - A[r])^2のコストがかかる時、コストの総和の最小値は?

Distribute Candies [CSAcademy #70 D]

https://csacademy.com/contest/round-70/task/distribute-candies/N個をK箱に分けるが以下のルールで分ける 隣接する箱の数は異なっている 箱には最低1個は入っている 箱の中に入っている数の最大値と最小値の差が最小化されている 作るのが不可能なら"-1"

Min Distances [CSAcademy #70 C]

https://csacademy.com/contest/round-70/task/min-distances/以下の条件を満たすN頂点の重み付き無向グラフを構築せよ。 M本の「頂点aと頂点bの最短距離がc」という情報をすべて満たす 無向グラフはシンプルで連結である

Right Down Path [CSAcademy #70 B]

https://csacademy.com/contest/round-70/task/right-down-path/縦N,横Mのバイナリ行列がある。 ここから ある1つのセルを決める そこから最低1セル右に進む そこから更に最低1セル下に進む のように移動する。 移動できるのは1のマスだけであるとき、作れる…

Digit Holes [CSAcademy #70 A]

https://csacademy.com/contest/round-70/task/digit-holes/数0,6,9は穴が1つ、数8は穴が2つあるとする。 [A,B]の数の中で穴の数が最大の数を答えよ。

Subgraphs [SRM730 Div1 Med]

https://community.topcoder.com/stat?c=problem_statement&pm=14817ある数Kが与えられる。 以下の条件を満たすようにグラフを生成する。 頂点数Nは46個以下 自己辺、多重辺無し x=[0,K*(K-1)/2]について、N個からK個取ってきた頂点集合の中の辺がx本である…

StonesOnATree [SRM730 Div1 Easy]

https://community.topcoder.com/stat?c=problem_statement&pm=14811頂点0を根とする木が与えられる。 木の各頂点は最大2個の子を含む。 頂点iには重みW[i]がある。 以下のルールに従って石を置く。 頂点0に石を置くための最大の瞬間重み総和は? 子供(孫は…

Fafa and Ancient Mathematics [Codeforces Round #465 E]

http://codeforces.com/contest/935/problem/E以下のルールの文字列がある。 dは1桁の自然数であり、dのみでアーメス式 E1,E2がアーメス式なら(E1 op E2)もアーメス式。opは+か- アーメス式のopの部分が全て?となっている式Eがある。 この?に+をP個、-をM個…

Fafa and Ancient Alphabet [Codeforces Round #465 D]

http://codeforces.com/contest/935/problem/DM種類の文字があり、文字1~文字Mである。 N文字の文字列AとBがある。 この2つの文字列は一部文字が欠けており、その部分は0となっている。 0となっている部分がk個ある場合には文字の入り方次第でM^k通り考えら…

Fifa and Fafa [Codeforces Round #465 C]

http://codeforces.com/contest/935/problem/C半径R, 中心(x1,y1)の円Cと(円の外かもしれない)頂点P(x2,y2)がある。 これについて以下の条件を満たす円C'の半径と中心を答えよ。 円C'は円Cの内部にある 円C'は頂点Pを含まない 円C'は上の2条件を満たす中で…

Fafa and the Gates [Codeforces Round #465 B]

http://codeforces.com/contest/935/problem/BN文字の命令列がある。 'U' -> (x,y)から(x,y+1)へ移動 'R' -> (x,y)から(x+1,y)へ移動 y=xのグラフの直線の左側と右側で国が分かれている。 頂点(0,0)から命令に従って移動していく時に国を何回またいだかを答…

Fafa and his Company [Codeforces Round #465 A]

http://codeforces.com/contest/935/problem/AN人いる。 リーダーの人数を決めて、各リーダーに均等に人を振り分ける。 均等に振り分けることの出来るリーダーの人数は何通りあるか。 各リーダーに1人も人がいない状況はダメ

Grid Repainting [AtCoder Beginner Contest 088 D]

https://abc088.contest.atcoder.jp/tasks/abc088_d

Takahashi's Information [AtCoder Beginner Contest 088 C]

https://abc088.contest.atcoder.jp/tasks/abc088_c

Card Game for Two [AtCoder Beginner Contest 088 B]

https://abc088.contest.atcoder.jp/tasks/abc088_b

Infinite Coins [AtCoder Beginner Contest 088 A]

https://abc088.contest.atcoder.jp/tasks/abc088_a

Permutation Cycle [ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) C]

http://codeforces.com/contest/932/problem/Cf(i,j) := P[i] (j=1) f(i,j) := f(P[i], j-1) (otherwise) と定義される関数fがある。 関数g(i)をf(i,j)=iとなる最小のjと定義する。 g(1), g(2), ..., g(N)の値がAかBのいずれかになるように順列Pを構築せよ。…

Recursive Queries [ICM Technex 2018 and Codeforces Round #463 (Div. 1 + Div. 2, combined) B]

http://codeforces.com/contest/932/problem/Bf(n) := nの非ゼロの桁の総積 g(n) := n (n < 10) g(n) := g(f(n)) と定義する。 Q個の以下のクエリを処理せよ。 「x=[L,R]の中でg(x)=Kとなる個数を求めよ」