http://abc056.contest.atcoder.jp
http://arc070.contest.atcoder.jp
以下、解説
続きを読むCodeforces Round #404 問題と解説
http://codeforces.com/contest/785
A. Anton and Polyhedrons
http://codeforces.com/contest/785/problem/A
"Tetrahedron"なら4面体, "Cube"なら6面体, "Octahedron"なら8面体, "Dodecahedron"なら12面体, "Icosahedron"なら20面体である。
N個の上の5つの内の立体の種類が与えられるとき、全ての立体の面数の総和は？
B. Anton and Classes
http://codeforces.com/contest/785/problem/B
N個のチェスの授業、M個のプログラミングの授業がある。
各授業で開始時間と終了時間が決まっている。
チェスとプログラミングの授業を1つずつとる時、2つの授業の間の休み時間の最大値は？
（必ずかぶる場合は0とする）
C. Anton and Fairy Tale
http://codeforces.com/contest/785/problem/C
N個収容できる倉庫がある（最初はN個入っている）。
以下の行動が毎日繰り返される時、何日目で終了するか。
（i日目とする）
1. 倉庫からi個取り出す（取り出し切れないor空っぽから終了）
2. M個倉庫に入れる（N個を超える時は満杯のN個が倉庫に入った状態にする）
D. Anton and School - 2
http://codeforces.com/contest/785/problem/D
文字列Sの（非連続OKの）部分列のうち、RSBSである部分列は何通りあるか(mod10^9+7)。
※ RSBS: (),(()),((())), (((()))), ... みたいな文字列
E. Anton and Permutation
http://codeforces.com/contest/785/problem/E
N個の数列があり、中身は{1,2,3, ... ,N}である。
これについてQ個の以下のクエリを処理する。
1. L[i]番目とR[i]番目の要素をスワップする
2. 数列全体について反転数を答える
競技プログラミングにおける連立方程式問題まとめ
連立方程式を使った解法について
- とりあえず、けんちょんさんの最強記事を読もう
- 一次連立方程式を解く
- ガウスの消去法（掃き出し法,O(N^3)）, 反復法（誤差に注意）のどちらでも解ける
- 反復法でやるときは行列累乗を使って2^20くらい回すといいかも
- 漸化式を作った時にDP更新とは違ってループしているようなものは連立方程式を解くかも
- 素晴らしい資料
- ライツアウト系に特化した問題集
- ガウスの消去法の良い教科書
- ガウスの除去法はK重対角行列であれば、O(N^2K)に削減できる 問題1 問題2（非想定解）
- mod2上でのカウスの消去法もよく出題される
問題
反復法
ガウスの消去法
- CF425 Vasya and Shifts 解説
- AOJ Find the Outlier 解説1 解説2 解説3
- yukicoder No.195 フィボナッチ数列の理解(2) 解説
- AOJ Strange Couple 解説1 解説2
わからない
Codeforces Round #403 問題と解説
http://codeforces.com/contest/782
A. Andryusha and Socks
http://codeforces.com/contest/782/problem/A
1～N番のN組の靴下がある。
左右合わせて2N個の靴下をある順番で受け取る。
もう片方の靴下を受け取るまで机の上にもう片方の靴下を置いておき、もう片方が来たらどちらも片付ける。
机の上に最大何個の靴下が置かれることになるか。
B. The Meeting Place Cannot Be Changed
http://codeforces.com/contest/782/problem/B
N人いる。
それぞれ位置X[i]で歩く速さはV[i] m/秒である。
どこか一箇所に集まる時に最短何秒かかるか。
C. Andrysha and Colored Balloons
http://codeforces.com/contest/782/problem/C
N頂点の木がある。
各頂点に色をつけるが、a - b - cと連結している場合はa,b,cは違う色で塗る必要がある。
つまり、2頂点先までで同じ色があるとダメ。
必要な色数の最小数と、その場合の塗り方を答えよ。
D. Innokenty and a Foodball League
http://codeforces.com/contest/782/problem/D
N個のクラブ名（三文字）と町の名前の組がある。
以下のルールで全ての組に対して三文字の名前を決めることができるかを判定せよ。
できるならば、そのパターンを示せ。
1. 「全てクラブ名にする」か「クラブ名の先頭2文字と町の名前の先頭1文字を合わせる」
2. クラブ名が同じ他のクラブが存在する場合は「全てクラブ名にする」ことで命名ができない
E. Underground Lab
http://codeforces.com/contest/782/problem/E
N頂点M辺の無向グラフがある。
長さfloor(2N/K)以下のパスをK本用意することで全ての頂点を通るようにする。
そのパスの構成を答えよ。
F. Axel and Marston in Bitland
http://codeforces.com/contest/782/problem/F
N頂点M辺の有向グラフがあり、辺には0か1が書かれている。
これに対しPとBから成るパターン文字列を考える。
S[0] = P
S[i] = S[i - 1] + inv(S[i - 1])
inv関数はPとBを反転させる関数
つまり、S = {P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP}
Pは0にBは1に対応している。
頂点1からスタートしてパターン文字列に沿って頂点を移動していく時、移動できる距離の最大値を答えよ。
もし、移動距離が10^18を越える場合は-1と出力せよ。
