Codeforces
問題ページ Problem - B - Codeforces 考えたこと loopが2個の8を18個並べた36個が上限に見える ループが2個の8とループが1個の4,6,9あたりを使って適当に並べればよさそう leading zeroにだけ気をつけて出すと通る AよりBの方が簡単ですが… #include <bits/stdc++.h> using</bits/stdc++.h>…
問題ページ Problem - A - Codeforces 考えたこと ソートして大きい方と小さい方だけ考えればよさそうな気がしたので投げるとpretest通る 順位表を見てると+10とかしてる人がいたので見返すとだめなパターンがある 場合分け面倒そうなのでO(nm)の全探索を書…
問題ページ Problem - J - Codeforces 概要 nCk mod m を求める。 1 <= n <= 10^18, 0 <= k <= n, 2 <= m <= 1000000 考えたこと JAG夏合宿で見た問題 パット見nCk mod m求めるいつものやつだ！と思って制約を見たら真顔になった n, kが大きすぎるのでn, kま…
問題ページ Problem - C - Codeforces 概要 長さnの数列aが与えられる。以下の操作を繰り返して数列のすべての要素を1にする最小の操作回数を求めろ。 操作: 数列aから隣接した2要素x,yを選び、その一方をgcd(x, y)と置き換える。 解法 まず、数列中に1が1つ…
問題ページ Problem - C - Codeforces 概要 赤い島がa個、青い島がb個、紫の島がc個ある。これらの島に橋をかける。橋の長さを1としたとき、同じ色の島で最短距離が3未満になるような島のペアが存在しないようにしたい。このとき、橋をかける方法が何通りあ…
問題ページ Problem - C - Codeforces 概要 q個(1<=q<=10^5)個のクエリが与えられる。各クエリでは整数n(1<=n<=10^9)が与えられる。整数nを合成数の和として表したとき、最大の合成数の個数を各クエリで答えろ。 考えたこと できるだけ小さい合成数をつかっ…
問題ページ Problem - 878A - Codeforces 概要 n個(n <= 10^5)のbit操作が書かれたプログラムが与えられる。0から1023までの数がプログラムに入力される。このとき、5個以下のbit操作で同じ操作となるプログラムを出力しろ。 解法 bit操作と言われたので2進…
問題ページ Problem - 887C - Codeforces 概要 2×2×2の立方体のルービックキューブが入力で与えられる。一回回転することで色が揃えられるなら"YES"、揃わなければ"NO"を出力する。 解法 回転のパターンは6パターンで反転で2倍で12パターン存在する。これを…
問題ページ codeforces.com 解法 まず、各ダンサーが待つ時間をスタート位置を変えるという形で処理する。(p[i], 0)からスタートするダンサーであれば(p[i], -t[i])、(0, p[i])からスタートするダンサーであれば(-t[i], p[i])からスタートすると扱うことで全…
問題ページ codeforces.com 考えたこと 構成ゲーっぽい。適当な文字列についてcostがどのように求められるのか考えてみる。 まず、異なる文字種が影響し合うことはなさそう。ある文字種がN個存在するときについて考えると、costはN(N-1)/2になりそう。いくら…
問題ページ Problem - B - Codeforces 考えたこと 頂点を二つに分類してそれぞれの頂点群が直線上に乗っていて各直線が平行であるかを判定すればよさそう。 まず、頂点1とiを2頂点として選ぶ。この2頂点を通る直線を一本目として考える。この直線上にない頂…
問題ページ Problem - A - Codeforces 考えたこと 問題を読むと普通に思い浮かばない。奇数が連続してるところで切れる（奇数個の要素になるところでしか切れないので嘘）のでその数を数えればいいという謎の思考をする。 終了30分前にhackされる。ちゃんと…
コンテスト中に考えてたことをまとめてみることにした。解法解説とはちょっとちがうかも？ 覚えてる範囲なので時間はずれてるかも？ ～00:03 Aを読むと、各文字の出現頻度を数えてKと比べればよさそう。ささっと実装したらpretest通った～00:10 Bの読解が難…
問題ページ Problem - C - Codeforces 概要 関数 F(n, k)を次のように定める。 集合{1,2,…,n}からk要素を選んだ部分集合を全て列挙する。各部分集合の値をその部分集合の最小の要素の値とするとき、この値を平均をF(n, k)とする。 \sum F(a[i], b[i]) が最大…
問題ページ Problem - A - Codeforces 概要 n個の風船をk人の子供に配る。同じ子供に同じ色の風船を二つ以上配らないように全部の風船を配ることが出来るか 解法 各色の出現数の最大がk以下ならYes, そうでないならNo
問題ページ Problem - D - Codeforces 概要 頂点1が根のn頂点の木が与えられる。q個のクエリを処理する。 クエリ1 頂点vとvの子孫の頂点の値を1にする クエリ2 頂点vとvの先祖の頂点の値を0にする クエリ3 頂点vの値を出力する 解法 部分木に関するクエリな…
問題ページ Problem - E - Codeforces 概要 n要素の根が1の木が与えられる。m個のクエリを処理しろ。 クエリ1 頂点vの部分木の頂点の色をcに変更する。 クエリ2 頂点vの部分木に含まれる色の種類を求める 解法 部分木に関するクエリを処理するのにオイラーツ…
問題ページ Problem - E - Codeforces 問題概要 数列a, bが与えられる。次の2種類のクエリを処理する。 1. b[y+q] = a[x+q] ( 0 2. b[x]を表示する 解法 区間更新の遅延セグメントツリーを使う。遅延更新用の配列に更新する配列aのインデックスとの値の差を…
問題ページ Problem - D - Codeforces 概要 数列aが与えられる。f(l,r,x) を l 解法 まず、f(1, i, a[i])を計算する。それぞれの要素の個数を数える配列を用意して順に計算していけばよいが、a[i] b[i]>c[j]となるような(i,j)の組の個数を求めればいい。BIT…
問題ページ Problem - A - Codeforces 解法 [l_i, x_i)、(x_i、r_i]の区間でまだ誰にも負けていない兵士がいればその兵士はx_iに負けたとして更新していけばよさそう。すでに負けた、負けていないを管理するのが大変そうだったのでクエリを逆に読んで、管理…
問題ページ Problem - D - Codeforces 問題概要 k-palindromeを以下のように定義する。 文字列の左半分と右半分が空文字列ではなく一致している 左半分と右半分がともに(k-1)-palindromeである 1-palindromeは通常の回文と同様である。 文字列sが与えられる…
問題ページ Problem - C - Codeforces 解法 t秒目での各星の明るさは(s[i]+t) % (c+1) で求められる。星の明るさは周期c+1で同じものが現れるのでc+1回分2次元累積和を取っておいて各クエリにO(1)で答える。同じ地点に複数の星が存在するケースがあることに…
問題ページ Problem - C - Codeforces 考えたこと 色々数字をいじっていたらそれっぽい解法が思いついて投げたら通った。 gcdを求めたあと素因数分解をしたくなったが、a、bが大きな素数のときに計算時間が怖かったのでこの方針は捨てた。 立法数判定だけな…
問題ページ Problem - B - Codeforces 解法 各文字について最初に現れるタイミングと最後に現れるタイミングを調べてimosする。
問題ページ 解法 操作には周期4の周期性があるので周期性を使って判定する。
問題A 問題概要 解法 問題B 問題概要 解法 問題C 問題概要 解法 codeforces.com 問題A 問題概要 月とその月が何曜日から開始するかが与えられる。この月で1週間ごとに列が切り替わるカレンダーを作成する際、カレンダーは何列になるか。 解法 1, 3, 5, 7, 8,…
A問題 問題概要 解法 B問題 問題概要 解法 C問題 問題概要 解法 codeforces.com A問題 問題概要 n組の靴下が袋の中に入っておりそれぞれペアごとに揃えたんすにしまいたい。袋の中から1つずつ取り出して机に並べる。そして、靴下が組になった時点でたんすに…
問題A 問題概要 解法 問題B 問題概要 解法 問題C 問題概要 解法 問題D 問題概要 解法 codeforces.com 問題A 問題概要 n人の生徒が属する2つのグループA, Bがある。各生徒は1から5の5段階の成績がつけられている。グループ間で生徒を交換することでそれぞれの…
A問題 問題概要 3個の箱の中にボールを隠しました。規則にもとづいて箱の位置を交換します。移動させた回数が奇数のときは左と真ん中の箱、偶数のときは右と真ん中の箱を入れ替えます。移動させた回数と最後にボールがあった場所から最初にボールがあった位…
