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

hamayanhamayan's blog

Sorting the Coins [Codeforces Round #441 B]

http://codeforces.com/contest/875/problem/BN枚のコインがあり、最初は全部表である。 以下の手続きを1セットとして行う。 1. コインを右から左に順番に処理する 2. i番目が裏で(i+1)番目が表なら、i番目を表に(i+1)番目を裏にするp[1],p[2],...,p[N]が与…

Classroom Watch [Codeforces Round #441 A]

http://codeforces.com/contest/875/problem/ANが与えられ、X+(Xの各桁の総和)=Nを満たすXを全て答えよ。 1≦N≦10^9

Something with XOR Queries [Codeforces Round #440 B]

http://codeforces.com/contest/871/problem/Bインタラクティブ問題。 2つの0~N-1が1つずつある順列p,bが内部で決まっていて、p[b[i]]=iを満たす。 2N回以下の質問で順列pを特定せよ。 質問は「? i j」でp[i] xor b[j]を聞ける。 答えの順列pはユニークでな…

Maximum splitting [Codeforces Round #440 A]

http://codeforces.com/contest/871/problem/AQ個の以下のクエリに答える。 ある数Nが与えられるので、これを合成数(4以上の非素数)の和で表す。 何個の数で表せられるか答えよ。無理なら"-1"Q≦10^5, N≦10^9

Axis-Parallel Rectangle [AtCoder Beginner Contest 075 D]

https://beta.atcoder.jp/contests/abc075/tasks/abc075_d

Bridge [AtCoder Beginner Contest 075 C]

https://beta.atcoder.jp/contests/abc075/tasks/abc075_c

Minesweeper [AtCoder Beginner Contest 075 B]

https://beta.atcoder.jp/contests/abc075/tasks/abc075_b

One out of Three [AtCoder Beginner Contest 075 A]

https://beta.atcoder.jp/contests/abc075/tasks/abc075_a

競技プログラミングにおける数学的問題まとめ

工事中記事 数学的知識 アルゴリズム 繰り返し二乗法による累乗高速化 mod関連 フェルマーの小定理 中国人剰余定理 離散対数問題 ウィルソンの定理 ルーカスの定理 確率・期待値 期待値の線形性 整数問題公式 素数判定 O(sqrt(N))の手法 ミラーラビン素数判…

101 to 010 [CODE FESTIVAL 2017 予選B D]

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_d

3 Steps [CODE FESTIVAL 2017 予選B C]

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_c

Problem Set [CODE FESTIVAL 2017 予選B B]

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_b

XXFESTIVAL [CODE FESTIVAL 2017 予選B A]

http://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_a

n! / m / m / m... [yukicoder No.575]

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

正多面体サイコロ [yukicoder No.574]

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

妖精の演奏 [yukicoder No.572]

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

a^2[i] = a[i] [yukicoder No.573]

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

3人兄弟(その2) [yukicoder No.571]

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

3人兄弟(その1) [yukicoder No.570]

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

Wrong Brackets [CSAcademy #51 E]

https://csacademy.com/contest/round-51/task/wrong-brackets/ 問題概要 2*N文字で'('がN文字で')'がN文字の括弧列のうち、辞書順でK番目に正しくない括弧列を求めよ。 N≦30

Manhattan Distances [CSAcademy #51 C]

https://csacademy.com/contest/round-51/task/manhattan-distances/ 概要 T(≦10^4)個のクエリが与えられる。 3つの頂点のマンハッタン距離だけ与えられるので、頂点を復元せよ。 もしありえないなら"-1"

競技プログラミングにおける連結DP問題まとめ

連結DP 造語なのだが、連結性を状態として持つDP フロンティア法とかとも言う 問題 TDPC マス目 解説1 解説2 解説3 yukicoder No.541 3 x N グリッド上のサイクルの個数 解説1 解説2 解説3 yukicoder No.569 3 x N グリッドのパスの数 解説 ICPC模擬国内予選…

競技プログラミングにおける挿入DP問題まとめ

挿入DP 順列などに挿入することで遷移を進めていくDP 問題 HR Permutation Happiness SRM694 Div2 Hard UpDownNess 解説 CSA Restricted Permutations TDPC 文字列 解説1 解説2 解説3 CF429 On the Bench yukicoder No.93 ペガサス 解説1 解説2 http://kmjp.…

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

UnionFind 連結成分を管理するデータ構造 (解説) 最小全域木の構成でも使われる 連結時に成分に入っている情報を併合することもある(要素数とか) incremental(併合はできるが、分離はできない) (発展だが)永続UnionFindもある 問題 AtCoder Union Find 連結…

競技プログラミングにおけるマンハッタン距離問題まとめ

マンハッタン距離 マンハッタン距離(wiki) 最強のマンハッタン距離解説記事 問題では45度回転はほぼやってる 問題 yukicoder No.131 マンハッタン距離 (WA出まくったら飛ばしてもいい) AtCoder Four Coloring ARC047 同一円周上 ARC065 へんなコンパス 差の…

4/N [Tenka1 Programmer Contest C]

http://tenka1-2017.contest.atcoder.jp/tasks/tenka1_2017_c

Min Swaps [CSAcademy #50 E]

https://csacademy.com/contest/round-50/task/min-swaps/ 概要 N要素の順列Pがある。 この順列の要素を任意回スワップすることで隣接する要素の差の総和を最大化したい。 最大化するときにスワップする回数の最小値は? Nは偶数で2

GraphAndPairs [SRM721 Div1 Med]

問題概要 以下の条件を満たす無向グラフを作れ 1. グラフはシンプル 2. 3~1000頂点 3. 辺は2~1000本 4. 良いペア(最短距離がd)が丁度k通りある 2 1

Palindromic Matrix [CODE FESTIVAL 2017 予選A C]

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_c

fLIP [CODE FESTIVAL 2017 予選A B]

http://code-festival-2017-quala.contest.atcoder.jp/tasks/code_festival_2017_quala_b