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

hamayanhamayan's blog

競技プログラミング

Count Arrays [CSAcademy #65 D]

https://csacademy.com/contest/round-65/task/count-arrays/Q個の区間がある。 i番目の区間は[L[i],R[i]]の区間に少なくとも1つは0が含まれるという条件。 全ての区間の条件をみたす長さNのバイナリ列は何通りあるか。 ※バイナリ列 : 0と1からなる文字列

Count 4-cycles [CSAcademy #65 B]

https://csacademy.com/contest/round-65/task/count-4-cycles/2つのN頂点の木がある。 それぞれの木の同じ頂点間に辺を追加で張り、2つの木を合成する。 この無向グラフの中で長さ4のサイクルの個数を答えよ。

Parititon the numbers [CodeChef January Challenge 2018 E]

https://www.codechef.com/JAN18/problems/PRTITION1~Nの数が1つずつある。 この中でxだけ除外する。 残った数を2グループに分け、各グループの総和が等しくなるように出来るか求めよ。 等しく出来ないならImpossible、出来るなら、どのように分けるかを示…

String Merging [CodeChef January Challenge 2018 D]

https://www.codechef.com/JAN18/problems/STRMRGN要素の文字列A、M要素の文字列Bがある。 これをマージして文字列Cを作る。 マージルール AとBから全ての文字を使う Aの文字列の順番、Bの文字列の順番は崩さすマージする 関数Fを用意する F(S) := 文字列Sの…

K-Concatenation [CodeChef January Challenge 2018 C]

https://www.codechef.com/JAN18/problems/KCONN要素の配列Aがある。 これをK個繋げたNK要素の配列をBとする。 配列Bの連続部分列の中での総和の最大値は?

Maximum Score [CodeChef January Challenge 2018 B]

https://www.codechef.com/JAN18/problems/MAXSCN*N要素の行列Aがある。 各行から数を1つずつ選んで数列Eを作る。 数列Eを狭義単調増加するように選ぶとき、数列Eの総和の最大値は何か。 もし、狭義単調増加するように取れないなら-1を出力する。

Rectangle [CodeChef January Challenge 2018 A]

https://www.codechef.com/JAN18/problems/RECTANGL 長さa,b,c,dが与えられる。 この長さを全て使って長方形が作れるか判定せよ。

Median Sum [AtCoder Grand Contest 020 C]

https://beta.atcoder.jp/contests/agc020/tasks/agc020_c

Ice Rink Game [AtCoder Grand Contest 020 B]

https://beta.atcoder.jp/contests/agc020/tasks/agc020_b

Move and Win [AtCoder Grand Contest 020 A]

https://beta.atcoder.jp/contests/agc020/tasks/agc020_a

Kill/Death [第4回 ドワンゴからの挑戦状 予選 C]

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_c

2525文字列分解 [第4回 ドワンゴからの挑戦状 予選 B]

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_b

ニコニコ文字列判定 [第4回 ドワンゴからの挑戦状 予選 A]

https://dwacon2018-prelims.contest.atcoder.jp/tasks/dwacon2018_prelims_a

競技プログラミングにおけるインタラクティブ問題まとめ

インタラクティブ問題への取り組み方 最適戦略がある 二分探索・三分探索 ビット毎に聞く 問題 最適戦略がある CF440 Something with XOR Queries 解説 CSA64 Prime Factors CSA64 Limited Moves 二分探索 yukicoder No.246 質問と回答 yukicoder No.253 ロ…

競技プログラミングにおける最近点対問題まとめ

最近点対 N点あるなかで最も近い距離にある2点の距離を求める問題 分割統治で解ける 実装 問題 AOJ Closest Pair AOJ Neartest Two Points 解法 CF245 Tricky Function 解説1 解説2 ABC022 Big Bang 解説1 解説2 AOJ Directional Resemblance(超難)解説

Katana Thrower [AtCoder Beginner Contest 085 D]

https://abc085.contest.atcoder.jp/tasks/abc085_d

Otoshidama [AtCoder Beginner Contest 085 C]

https://abc085.contest.atcoder.jp/tasks/abc085_c

Kagami Mochi [AtCoder Beginner Contest 085 B]

https://abc085.contest.atcoder.jp/tasks/abc085_b

Already 2018 [AtCoder Beginner Contest 085 A]

https://abc085.contest.atcoder.jp/tasks/abc085_a

競技プログラミングにおける半分全列挙問題まとめ

半分全列挙 O(2^N)は間に合わないがO(2^(N/2))は間に合うときの解法 2グループに分けて全列挙をして、1つのグループは全探索し、もう一方のグループに関しては二分探索などで高速に処理する 最大クリーク・最大独立集合問題を解くのに使う 問題 ECR32 Maximu…

New Year's Eve [Codeforces Round #456 B]

http://codeforces.com/contest/912/problem/B1,2,3,...,Nのように[1,N]の数が1つずつ用意されている。 ここからK個以下の数を取ってきてxorを取る。 最大値は?

Tricky Alchemy [Codeforces Round #456 A]

http://codeforces.com/contest/912/problem/Aボールを作るが、以下のルールで作れる 黄ボールは黄素材2つ 緑ボールは黄素材1つと青素材1つ 青ボールは青素材3つ 手元に黄素材がA個、青素材がB個ある。 黄ボールをx個、緑ボールをy個、青ボールをz個作りたい…

Noelちゃんと電車旅行 [yukicoder No.631]

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

門松グラフ [yukicoder No.630]

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

グラフの中に眠る門松列 [yukicoder No.629]

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

Tagの勢い [yukicoder No.628]

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

ランダムウォークの軌跡 [yukicoder No.627]

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

Graph Game [CSAcademy #63 D]

https://csacademy.com/contest/round-63/task/graph-game/N頂点M辺の無向グラフがある。 AlexとBobが戦う。 Alexが先攻。 次数が偶数の頂点とそれにつながる辺を消す操作を行う。 操作が行えなくなったほうが負け。 どちらも適切に動いた時の勝者はどちらか…

Find Remainder [CSAcademy #63 C]

https://csacademy.com/contest/round-63/task/find-remainder/N要素の配列A,Bがある。 この時B[i] = A[i] % Kとなるような最小の自然数Kを求めよ。 もし、存在しないならば-1と答えよ。 ※ 問題文では「B[i] = A[i] mod K」とあるが合同式ではないので注意

Maximize Profit [CSAcademy #63 B]

https://csacademy.com/contest/round-63/task/maximize-profit/S円のお金とQ個の確率を持っている。 確率を適切に入れ替えて順番に使っていくことを考える。 i番目の確率を使う場合は2つの選択が選べる。 1. 確率を使ってお金をP[i]%上昇させる 2. 確率を捨…