atcoder.jp 考察 まずは愚直解を考えます。を全探索してみます。明るさをからに変更するときの操作回数は、を明るさをからに変更するときの操作回数の最小値として、です。はで計算できるので、全体の計算量はです。 #include<bits/stdc++.h> using namespace std; using li</bits/stdc++.h>…
以下の問題を解いていたときに考えたことです。 atcoder.jp この問題はbitwise orとしてありうるものを数える問題ですが、今回は最小値と最大値を求めることを考えます。 問題 整数が与えられます。以上以下の整数から1個以上選んで、それらのbitwise orを取…
atcoder.jp 問題 整数が与えられます。以上以下の整数から個以上選んで、それらのbitwise orを取ってできる整数としてありうるものが何通りあるかを求めてください。 制約 考察 の場合は通りなので、の場合を考えます。 が上位桁まで一致していたとします。…
codeforces.com 問題 要素数の数列が与えられます。としてあり得る値の最小値を求めてください。 制約 考察 とします。の先頭桁がなるべく小さくなるようにするのがよいので、を先頭桁から決めていきます。 今桁目を見ているとして、次の3つの場合があります…
取り組み方(自分向け) コンテスト中 なるべく全部の問題に目を通します。問題分が簡潔なものから読んで、できそうだったら考えます。時間がかかりそうor無理そうだったら次の問題に移ります。 コンテスト後 コンテスト中に解けるのは大体0問か1問です。現在…
codeforces.com 問題 整数が与えられます。長さの順列のスコアを を満たすような組の個数 とします。長さの全ての順列のスコアの合計をで求めてください。 制約 は素数 考察 という条件について 部分列の長さを、最小値をとおきます。この部分列が条件を満た…
codeforces.com 問題 長さの数列が与えられます。これは長さの順列の一部が欠けたもので、欠けたところはになっています。 が順列になるように復元したときの、の複雑さの最小値を求めてください。ここでの複雑さとは、隣接要素のペアであって、偶奇が異なる…
codeforces.com 問題 整数が与えられます。長さの数列のペアであって、次の条件を満たすものの個数を求めてください。 制約 考察 条件を図にすると、赤の□で囲んだ部分の不等号が無くても十分だと分かります。 よって、以下の条件を満たすの個数を数えれば良…
yukicoder.me A.じゃんけん 表を書くとあいこになるのは のときだと分かります。 B.数列変換マシン より なので、を求めれば良いです。ここで例えばのとき、 $$ y_{1}=\dfrac{x_{2}+x_{3}}{2},\ y_{2}=\dfrac{x_{1}+x_{3}}{2},\ y_{3}=\dfrac{x_{1}+x_{2}}{2…
2019年を軽く振り返ろうと思います。 1月~3月 受験があったらしいです。この時期が今年だったと感じられないくらい昔に感じます。センター試験が終わった頃に、何かやりたいなぁと思って、競技プログラミングを再開することにしました。競技プログラミングは…
atcoder.jp 考察 うさぎがジャンプする前後の座標の期待値の変化を考えます()。うさぎのジャンプ前後のうさぎの座標をそれぞれとします(これらは確率変数です)。 (1) のとき(うさぎがジャンプする場合) 点の点に関して対象な点の座標をで表すとすると、 \beg…
atcoder.jp 1679->1673(-6) 厳しいですね C. Snack を求めればよいです。より、です。はC++であれば__gcd(組み込み関数?)を使って求められます。 #include<bits/stdc++.h> using namespace std; using Lint=long long; Lint lcm(int a,int b) { return (Lint)a*b/__gcd(a,b)</bits/stdc++.h>…
codeforces.com 1733->1841(+108) 証明: ACをしました A. Equation 問題 整数が与えられます。を満たすような合成数を求めてください。 制約 考察 とを出力すれば良いです。これらは合成数で、制約を満たします。 B. Modulo Equality 問題 要素の数列が与え…
atcoder.jp 問題 頂点の木が与えられます。各頂点に整数を1つ書き込んで、隣接する頂点に書き込まれている数字の差がになるようにしたいです。すでに個の頂点に数字が書き込まれているとき、条件を満たすように数字を書き込むことができるか判定してください…
問題 atcoder.jp 考察 操作によって生じるコストを、生じる場所によって別々に考えてみることにします。そうすると、操作によってかかるコストの総和の下界がであることが分かります1。これが達成可能かどうかを考えてみます。 列に対する操作を整数で表すこ…
atcoder.jp 問題 のマス目が与えられます。各マスは黒か白で塗られています。このマス目に含まれる'N'の大きさの最大値を求めてください。ここで'N'とは、正方形状のマス目であって、両端の列のマス目と、左上から右下にかけての対角線上のマス目が黒で塗ら…
前書き 運良く予選を通過することができたので(190位くらい)、本戦に参加してきました。オンサイト決勝は初参加です。 移動 東京駅には何度か行ったことがありますが、一人で行くのは初めてでした。迷子になったときのために早めに出ました。会場の最寄り駅(…
atcoder.jp 問題 要素数の数列に対して、以下の操作を行う。 操作: 以下の正の整数を選び、初めて以上になるような要素からを引く。ただしこの操作によって要素がになってはいけない。 この操作を最大で何回行えるか。 制約 解法の概要 前から順番に操作を行…
次に進むために4月から現在(9月)までの約5ヶ月間を振り返って反省をしました。年末にまた振り返ろうと思います。誰の役にも立ちませんが、とりあえず公開しておきます。 月ごとに振り返る 4月 5月 6月 7月 8月 9月(今日は9/11) 反省点はどこか? 競プロを続け…
