CodeChef

CodeChef: Chef and Array

問題 https://www.codechef.com/problems/CHEFLKJ要素数 N の数列が与えられ、Q 個のクエリが来る。クエリは以下の2種類である。 x 番目の数字を y に変更する。 l 番目から r 番目までの部分列の中で、過半数は同じ数であるか判定する。 解法 2次元BITを構…

CodeChef: Chef and Land

問題 https://www.codechef.com/problems/CHEFIHGN x M の 2 次元平面のマップが与えられる。マップには道 '.' と壁 '*' と首都 'C' がある。ロボットがあり、ロボットに U, R, L, D のコマンドを与えることで上下左右に動かすことが出来る。全ての道にロボ…

CodeChef Snackdown 2016 : Online Elimination Round - Jealous Numbers

問題 1000 以下の数が N 個与えられるので、部分集合の中の任意の2つが互いに素になるように部分集合を作るとき、最大の部分集合の数を答えよ。 解法 NUMSET - Editorial - CodeChef Discuss uwiさんに聞いた。すべての数は 31 以下の素数と、32以上の素数 0…

CodeChef Snackdown 2016 : Online Elimination Round - Alliances

問題 Contest Page | CodeChef頂点数 N のツリーが与えられる。 K 個のギャングがいて、各ギャングはツリー上のある頂点集合を支配している。 クエリが Q 個くる。各クエリはある頂点 v と、ギャングのリストが含まれている。 リスト中のギャングが支配して…

CodeChef Snackdown 2016 : Online Elimination Round - Cube Towers

問題 Contest Page | CodeChefN 個の空文字列と M 個の単語が与えられる。Q 個のクエリに応答せよ。クエリは以下の 3 種類からなる。 文字列 X の先頭に文字 C を挿入する。 L〜R 番目の文字列の中で単語 P を含むものがいくつあるか出力する。 L〜R 番目の…

CodeChef SnackDown Online Pre-elimination round A - Longest Increasing Subsequences

問題 Contest Page | CodeChef100 以下の自然数を使ってLISがちょうどK個存在する数列を作れ。同じ数字は1度しか使えない。 解法 MAKELIS - Editorial - CodeChef Discuss{ 2 1 4 3 }で 2*2 通りのLISが含まれる数列を作れる。ここの左側に {5 6} をつけると…

CodeChef Snackdown 2015 : Online Elimination Round - Chef and Trees

問題 Contest Page | CodeChefツリーが与えられる。1本辺を足して閉路を作るとき、直径を小さくすることが可能か判定せよ。 解法 MAXDIST - Editorial - CodeChef Discussツリーの直径を求める。ツリーの直径が偶数の時、中心となる頂点は1つだけである。中…

SnackDown Online Qualifier 2016 - Floor Division Game

問題 https://www.codechef.com/SNCKQL16/problems/FDIVGAME 解法 grundy 数に規則性がある (のを uwi さんに教えてもらった) ので、それを先に作っておいて、参照しながら求めると良い。 コード #include <bits/stdc++.h> using namespace std; int main() { cin.tie(0); i</bits/stdc++.h>…