読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CodeChef: Subtree swapping

codechef の practice ってあまり使わないので知らなかったんですが、コンテストから practice に問題が公開されるまで大分時間がかかるんですね。復習しづらい。 https://www.codechef.com/problems/SBSWAP オイラーツアーの切り貼りは、以下の記事で説明し…

CodeChef October Challenge 2016

Chef and Keyboard Chef and Three Dogs 証明 Chef and Two String Fenwick Iterations Big Queries Power Sums Bear and Shuffled Points Sereja and Stones Tree Balancing

CodeChef September Challenge 2016

Chef and digits of a number Faded Palindromes Chef and calculation Chef and Friends Dividing Machine JosephLand The New Restaurant Chef and Cut Chef has a Spaghetti Garden(解けず)

CodeChef August Challenge 2016

700点でした。

CodeChef July Challenge 2016: Chef and Polyhedron

https://www.codechef.com/JULY16/problems/CHEFPOL 問題 すべての面が正多面体であるような凸多面体が与えられる。この凸多面体を C 色で塗る方法は何通りあるか。ただし回転や鏡像反転によって同じになるものは同一視する。 4≦N≦25 1≦C≦109

CodeChef July Challenge: Defend the Recipe

解法 各線分による領域の共通部分を取ればよい。これは直線を使って凸包を作る問題となる。

CodeChef July Challenge 2016: Evaluate the polynomial

https://www.codechef.com/JULY16/problems/POLYEVAL 問題 多項式が与えられるので、x[i] での値を mod 786433 で求めよ。 1≦N, Q≦250,000

CodeChef July Challenge 2016

Andrash and Stipendium Chef and Electricity Chef and Tetris Chef and Robots Competition Chef and Segments Chef and special numbers

CodeChef SnackDown Online elimination round

https://www.codechef.com/SNCKEL16

CodeChef June Challenge 2016: Misha and Geometry

https://www.codechef.com/JUNE16/problems/MGCHGEOM 問題 以下の 2 種類のクエリが与えられる。 点(x, y) を追加する 点(x, y) を削除する クエリを順に処理し、処理するたびに凸包の面積を出力せよ。 クエリ数の合計は 105 以下

CodeChef June Challenge 2016: Chef and Sad Pairs

https://www.codechef.com/JUNE16/problems/SADPAIRS 問題 グラフが与えられる。各頂点は値 G[v] を持っている。頂点 v に接続している辺を削除したグラフにおいて、G[u]=G[v] かつ u と v が異なる連結成分に属するようなペアの数を数えよ。

CodeChef June Challenge 2016: 1問目から7問目

Devu and Array 明らかに最小値と最大値の間の数しか作れない。 最小値と最大値の間の数は実際に作れる。 gist.github.com Chef and Coins Game 実験すると n mod 6≠0 なら先手必勝で、そうでないなら後手必勝。 n mod 6≠0 からはn mod 6=0 に持ち込める n m…

SnackDown Online Pre-elimination round A

https://www.codechef.com/SNCKPA16

SnackDown Online Qualifier 2016

https://www.codechef.com/SNCKQL16

CodeChef May Challgenge 2016: Roads in Stars

Easy Queries よりは簡単だった。 https://www.codechef.com/MAY16/problems/STARROAD 問題 N 頂点 M 辺のグラフが与えられる。(i→j に向かう K ステップ以下の経路数)mod X 本だけ i-j 間に辺を張ったグラフを構築する。そのグラフ上での全域木は何通りあ…

CodeChef May Challgenge 2016: Easy Queries

https://www.codechef.com/MAY16/problems/DISTNUM2 問題 整数列 An が与えられる。A[l..r] から重複要素を無視して k 番目に小さい値を出力するというクエリを Q 個処理せよ。 1≦n≦105 1≦Q≦105 オンラインクエリ

CodeChef May Challgenge 2016: 1-7問目

https://www.codechef.com/MAY16/problems/LADDU https://www.codechef.com/MAY16/problems/CHBLLS https://www.codechef.com/MAY16/problems/FORESTGA https://www.codechef.com/MAY16/problems/CHEFSOC2 https://www.codechef.com/MAY16/problems/CHEFMATH…

Codechef April Challenge 2016

解法の概要だけ書いておきます。詳しい解説は書きません。