Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

Codeforces

D. Make Them Equal (Educational Codeforces Round 122 Div. 2)

問題 https://codeforces.com/contest/1633/problem/D 問題概要 長さnですべての要素が1の配列 a が与えられる。配列aの要素に対して、a_i = a_i + a_i / x (x > 0) という操作が最大 k 回実行可能である。 長さnの配列bとcがあり、上記の操作で a_i == b_i …

C. And Matching (Codeforces Round #768 Div. 2)

問題 https://codeforces.com/contest/1631/problem/C 問題概要 2の累乗である整数nと0 <= k <= n - 1である整数kが与えられる。 n/2個のペアを以下の条件を満たすように作れ。 各ペアには0からn-1までの整数が一つずつ含まれている ペア毎にbitwise ANDを取…

B. Swaps (Codeforces Round #743 (Div. 2))

問題 https://codeforces.com/contest/1573/problem/B 問題概要 長さnの2つの数列aとbが与えられる。aは2n以下のそれぞれ異なる奇数が、bは2n以下のそれぞれ異なる偶数が任意の順に格納されている。 これらの数列に対して以下の操作を行うことができる。 aま…

C. Product 1 Modulo N (Codeforces Round #716 (Div. 2))

問題 https://codeforces.com/contest/1514/problem/C 問題概要 整数nが与えられる。[1, 2, ..., n-1]の部分列で要素の積をnで割ったあまりが1となるもののうちで最長のものを求めよ。 考察 nと互いに素でない数は含めることができません。gcdが1でないため…

B. AND 0, Sum Big (Codeforces Round #716 (Div. 2))

問題 https://codeforces.com/contest/1514/problem/B 問題概要 整数nとkが与えられる。以下の条件をすべて満たすような長さnの配列がいくつあるか答えよ。 すべての要素は0から2k-1までの整数である すべての要素のビットごとのANDは0である すべての要素の…

A. Perfectly Imperfect Array (Codeforces Round #716 (Div. 2))

問題 https://codeforces.com/contest/1514/problem/A 問題概要 長さnの配列aが与えられる。aの空でない部分配列をbとするとき、すべての要素の積が平方数にならないようなbが存在するかどうかを答えよ。 考察 aの中で、1つでも平方数でないものが含まれてい…

C. Add One (Divide by Zero 2021 and Codeforces Round #714 (Div. 2))

問題 https://codeforces.com/contest/1513/problem/C 問題概要 整数nとmが与えられる。nの各桁の数に1を加えたものを並べた列を新しいnに置き換える操作をm回繰り返したとき、nが何桁になっているか答えよ。 考察 とりあえず0からスタートしてどうなるか見…

AtCoderで黄パフォをとるまでにやったこと

TL;DR AtCoderでは飽き足らずCodeforcesにも積極的に参加します Codeforcesでギャグセンスを磨きます なんとAGCにこどふぉギャグが出題されました 大勝利 ちょっと真面目に たくさん問題を解けば解くほど、パターン認識でこなせる(いわゆる「やるだけ」)問…

D. AB Graph (Codeforces Round #699 Div. 2)

問題 https://codeforces.com/contest/1481/problem/D 問題概要 完全有向グラフが与えられる。各辺にはaまたはbの文字が付与されている。(辺(u, v)と辺(v, u)は独立して考えるため、同じ文字が付与されているとは限らない) このグラフ上の長さmのパスで、…

A. Kids Seating (Codeforces Round #681 Div. 2)

これはこどふぉDiv. 2のAにありがちなギャグではなく、制約の意味を考えるいい問題なのではと思いました。 問題 https://codeforces.com/contest/1443/problem/A 問題概要 整数nが与えられる。1から4nまでの数を一つずつ持った集合の部分集合として、要素をn…

A. Reorder (Codeforces Round #678 Div. 2)

この問題に1時間かけてしまったばっかりに、青から水に落ちました・・・。 問題 https://codeforces.com/contest/1436/problem/A 問題概要 整数が含まれる長さnの配列aと、別に整数mが与えられる。 配列aの中身を任意に並べ替えることで が、mと等しくなるよ…

B. Putting Bricks in the Wall (Codeforces Round #676 Div. 2)

見た目に騙されました・・・。こどふぉギャグでした・・・。 問題 https://codeforces.com/contest/1421/problem/B 問題概要 のグリッドがあり、(1,1)と(n,n)以外のすべてのマスには0または1の値が与えられている。 隣接するセル(上下左右)のうち、0のセル…

C. Palindromifier (Codeforces Round #676 Div. 2)

What is Programming!? 問題 https://codeforces.com/contest/1421/problem/C 問題概要 英小文字からなる文字列Sが与えられる。文字列に対して以下の操作を繰り返し行うことができる。 を指定して、その左にあるのi-1文字を反転させた文字列を、Sの左に連結…

B. Belted Rooms (Codeforces Raif Round 1 Div. 1 + Div. 2)

というわけで、Cより難しかった?B問題です。 問題 https://codeforces.com/contest/1428/problem/B 問題概要 n個の部屋があり0からn-1の番号が振られている。各部屋はn個のコンベアで環状に繋がれている。それぞれのコンベアは、部屋番号の正方向に進む(n-…

C. ABBB (Codeforces Raif Round 1 Div. 1 + Div. 2)

Bでもよさそうな問題だと思いましたが、実際Bより正答者が多かった模様。 問題 https://codeforces.com/contest/1428/problem/C 問題概要 AとBからなる文字列が与えられる。文字列中に"AB"または"BB"があればそれを消去することができる。 消去した結果とし…

C2. Pokémon Army (hard version) (Codeforces Round #672 Div. 2)

問題 https://codeforces.com/contest/1420/problem/C2 問題概要 長さnの配列aが与えられる。この配列の部分列を、その要素を左から順に加算減算加算減算・・・したときの演算結果が最大になるように取りたい。最大値はいくつになるか。(ここまでC1) また…

E. Directing Edges (Codeforces Round #656 Div. 3)

問題 https://codeforces.com/contest/1385/problem/E 問題概要 n個の頂点とm個の辺で構成されたグラフが与えられる。いくつかの辺が有向辺でいくつかの辺は無向辺である。 すべての無向辺に、グラフが循環しないように方向をつけよ。構築が不可能ならその旨…

D. a-Good String (Codeforces Round #656 Div. 3)

個人的に超お気に入りの問題でした。(スター押した) 問題 https://codeforces.com/contest/1385/problem/D 問題概要 長さn=2^k (k >= 0)の文字列sについて、以下の条件を少なくとも一つでも満たすものをc-goodな文字列を呼ぶことにする。 n=1のとき、それ…

B. Restore the Permutation by Merger (Codeforces Round #656 Div. 3)

問題 https://codeforces.com/contest/1385/problem/B 問題概要 長さnの順列2つを、それぞれの順番が壊れないようにマージさせた長さ2nの数列が与えられる。 たとえば元の順列が[3, 1, 2]のとき、[3, 1, 2, 3, 1, 2]、[3, 3, 1, 1, 2, 2]そして[3, 1, 3, 1, …

A. Three Pairwise Maximums (Codeforces Round #656 Div. 3)

このセットの解けた問題の中で、結果的には一番苦戦したという・・・。 問題 https://codeforces.com/contest/1385/problem/A 問題概要 正の整数x, y, zが与えられる。x = max(a, b), y = max(a, c), z = max(b, c)となるような正の整数a, b, cを一つ示せ。…

C. Omkar and Baseball (Codeforces Round #655 Div. 2)

問題 https://codeforces.com/contest/1372/problem/C 問題概要 長さnの順列が与えられる。この順列を昇順にソートしたい。以下の条件で並べ替えを実行する時、最小の並べ替え回数は何回か? 連続した部分配列を指定する 指定された部分配列の中で要素を入れ…

B. Omkar and Last Class of Math (Codeforces Round #655 Div. 2)

問題 https://codeforces.com/contest/1372/problem/B 問題概要 正数nが与えられる。以下の条件を満たす正数の組{a, b}を答えよ a + b = n 上記の条件を満たすa, bのうちでlcm(a, b)が最も小さい 考察(証明) あるn未満の正数kをとってきて、a=k, b=n-kとお…

A. Omkar and Completion (Codeforces Round #655 Div. 2)

This is the GAG of Codeforces! 問題 https://codeforces.com/contest/1372/problem/A 問題概要 正数nが与えられる。長さnの配列を以下の条件を満たすように構築せよ。 各項は1000を超えない正数である に対してを満たす(ただしx,y,zは重複が許される) 考…

D. Replace by MEX

こどふぉってちょいちょいMEXが出てきますね。 問題 https://codeforces.com/contest/1375/problem/D 問題概要 長さnの配列が与えられる。各項の値は0からnの間の整数である。 あなたは、配列の任意の項を選択し、その時点での配列のMEXで置き換えることがで…

C. Element Extermination (Codeforces Global Round 9)

考察で迷走したあげく、ギャグ問であったことを知ったときの衝撃たるや・・・ 問題 https://codeforces.com/contest/1375/problem/C 問題概要 長さnの順列が与えられる。あなたは順列中のとなるようなiについて、とのいずれかを除去することができる。 上記…

B. Neighbor Grid (Codeforces Global Round 9)

問題 https://codeforces.com/contest/1375/problem/B 問題概要 n行m列のグリッドが与えられる。各セルには非負正数が書き込まれている。あなたは各セルの数値を自由に増加させることができる。 ここで、すべてのセルについて、そこに書き込まれている数値が…

A. Sign Flipping (Codeforces Global Round 9)

こういう問題、苦手です・・・。 問題 https://codeforces.com/contest/1375/problem/A 問題概要 長さnの数列が与えられる。あなたは各項の符号を自由に変えることができる。 符号を変えることで、与えられた数列を以下の条件を満たす数列に変形せよ。 とな…

C. Ehab and Prefix MEXs (Codeforces Round #649 Div. 2)

問題 https://codeforces.com/contest/1364/problem/C 問題概要 長さnの配列aが与えられる。1 <= i <= nの各iについてを満たすような配列bを構築せよ。 考察 について、に含まれる数字を使うことはできません。先に使ってしまうと、jのときのMEXがになりえな…

B. Most socially-distanced subsequence (Codeforces Round #649 Div. 2)

問題 https://codeforces.com/contest/1364/problem/B 問題概要 長さnの順列が与えられる。以下の条件を満たす長さkの配列を構築せよ。 を順列pから作れるsのうちで最大にする 上記の条件を満たす配列sのうち、kの大きさを最小にする 考察 一番目の条件を満…

A. XXXXX (Codeforces Round #649 Div. 2)

問題はちゃんと読みましょう。問題はちゃんと読みましょう。 問題 https://codeforces.com/contest/1364/problem/A 問題概要 配列aと非負整数xが与えられる。aの部分列で(ここでaの部分列とはaの先頭と末尾からいくつかの(0やすべてを含む)要素を取り除い…