https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_h 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5195896基本方針は19999や299のように、 なるべく桁数を少なくするために9でまとめる 余りは先頭に置く として作っていけ…

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_g 前提知識 動的計画法 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5195581DPで解く。 dp[i][m] := i日目に好意をほのめかし、今までm回好意をほのめかしているときの…

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_f 前提知識 素因数分解 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5194885数列を見てみると、因数分解をしている感じになっている。 さて、どこから始めようか。 まず…

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_e 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5195243デートを行う記念日には競プロはできないので、記念日間でできる日数を数える。 各記念日間では独立に考えること…

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_d 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5194591高橋君と青木くんが順番にレスラーを取っていくが、 戦闘力が高いレスラーから先に選ぶのが、戦略としては最善な…

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_c 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5194348問題で要求されていることをそのまま実装しよう。 差分dを-7から0までforで回して答えていく。 int N; //--------…

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_b 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5194416操作をK回施しても間に合うので、施そう。 dequeを使って、先頭から取り出して末尾に追加するをK回行う。 あとは…

https://atcoder.jp/contests/iroha2019-day1/tasks/iroha2019_day1_a 解説 https://atcoder.jp/contests/iroha2019-day1/submissions/5194042先頭文字をとってくればいいので、C++ならばsubstrを使えばいい。 string S; //--------------------------------…

N個のマッチの山がある。 ここから以下の操作を順番に繰り返す。1. マッチが1つもないなら負け 2. 1つの山を選び、1つ以上とる 3. 取ったマッチ1つにつき、1つの山を全て燃やすことができる（取った山を燃やしてもいい） 4. 使わなかった取ったマッチは捨て…

C匹のムカデがいる。 各ムカデはF本の足がある。 あるムカデには同じ色の靴下を履かせたい。N種類の靴下があり、それぞれ数がわかっている。 全て1つの瓶に入っていて、ランダムに取り出していく。 全てのムカデに同色の靴下を履かせるときに、取り出す靴下…

https://codeforces.com/contest/1149/problem/BN文字の文字列Sがある。 3つの文字列スタックがある。 これに対してQ回以下のクエリを行う。1. 「+ i c」i番目の文字列キューの末尾にcを入れる 2. 「- i」i番目の文字列キューの末尾をpopする各クエリ後に以…

https://codeforces.com/contest/1149/problem/A1と2からなるN要素の配列Aがある。 これを並び替える操作をする。 操作後に、B[i] = A[0] + A[1] + ... + A[i]である累積和配列Bを作る。 適切に操作をして、配列Bに含まれる素数の数が最大である配列Aを答え…

https://leetcode.com/contest/weekly-contest-134/problems/escape-a-large-maze/2次元グリッドがある。 縦も横も10^6である。 通れないマスの集合blockedが与えられる。 始点sourceから終点targetへ隣接するマスを移動して、到達可能か判定せよ。0≦blocked…

https://leetcode.com/contest/weekly-contest-134/problems/uncrossed-lines/2つの配列A,Bがある。 各配列の要素を横一列に並べる。 A[a]=B[b]となっている要素を直線で結ぶ。 直線が公差しないように結んだときの直線の最大数は？1≦配列サイズ≦500 1≦A[i],…

https://leetcode.com/contest/weekly-contest-134/problems/coloring-a-border/2次元グリッドがある。 各要素には数が書いてある。 同じ数で隣接している要素は連結成分になる。 ある要素(r0,c0)に色colorを使って数を変更する。 (r0,c0)と連結な成分の要素…

https://leetcode.com/contest/weekly-contest-134/problems/moving-stones-until-consecutive/数直線の上に3つの石がある。 3つの石がa,b,cの位置にある。 以下の操作を任意回できる。 「石がx＜y＜zの位置にあるときに、x,zの石をxとzの間の空いている位置…

https://yukicoder.me/problems/no/823 前提知識 二項係数mod素数 解説 こういう系に初めて取り掛かる人はどこから手をつけていいか分からないと思うが、 まずは弱そうな条件を探してみる。 見ると、入力がN≦10^5となっている。 しかも、得点の計算方法がマ…

https://yukicoder.me/problems/no/822 解説 https://yukicoder.me/submissions/343382よくよく考えると、(x,y)のペアは全探索ができる量である。 まず、xは[0,2^17)の範囲で考えればいい。 これは、2^17=131072であり、2進数表記すると1000000000000となる…

https://yukicoder.me/problems/no/821 解説 https://yukicoder.me/submissions/343365☆の割には難しい問題に見える。順位表を見てみると、プロが5分とかで解いている。 ここから導けるのは、エスパーが必要であるということである。 プロが一瞬で思いついた…

https://yukicoder.me/problems/no/820 解説 https://yukicoder.me/submissions/343360パット見難しそうに見えると思う。 例えば、Nが3のときは、 1 2 3 4 5 6 7 8 となり、Kが2のときは、 4 8 となって、2が答え。 これは最大が8で4で割り切れる個数なので…

https://atcoder.jp/contests/abc125/tasks/abc125_d 解説 https://atcoder.jp/contests/abc125/submissions/5169416ときにはエスパー力も必要であると教えてくれる問題。 （証明の仕方を知らないので、エスパーと表現してるだけだけど） だいぶ自明っぽいエ…

https://atcoder.jp/contests/abc125/tasks/abc125_c 解説 追記: GCDの計算をO(1)で計上して書いてありますが、実際はO(log10^9)が最終的な計算量に追加されます。 今回はそんなに問題にならないですが、たまに事前計算とかでこの計算量も削る必要のある問題…

https://atcoder.jp/contests/abc125/tasks/abc125_b 解説 今回の問題は解法が2つあるので、どちらも紹介する。 解法2の方が計算量が軽くておすすめだが、 解法1の全探索もやり方としては必ず覚えておく必要がある。 解法1 : 全探索 https://atcoder.jp/cont…

https://atcoder.jp/contests/abc125/tasks/abc125_a 解説 https://atcoder.jp/contests/abc125/submissions/5169262何回ビスケットが生成されるかというのを考えると、T/A回になる。 実際は切り捨てなのだが、C++ではint/intは切り捨てしてくれるので、これ…

https://yukicoder.me/problems/no/818 前提知識 動的計画法 解説 https://yukicoder.me/submissions/341024A[i],B[i]や産ませる鶏肉にするという部分が少しむずかしいのでなんとかする。 あるニワトリiについてj回操作を行えるとすると、美味しさの総和の最…

https://yukicoder.me/problems/no/817 前提知識 二分探索 解説 https://yukicoder.me/submissions/340743N回操作して、手元にある硬貨を昇順ソートしたときのK番目はなにかという問題。 二分探索の典型テクとして、 【「ある条件でソートしたときのK番目の…

https://yukicoder.me/problems/no/816 前提知識 O(sqrt(N))で約数全列挙 解説 https://yukicoder.me/submissions/340724答えのCを全列挙する。 そのまま全列挙すると10^18個あって無理なので、候補を絞る。 条件２「どの 2 つの自然数を足しても、残った 1 …

https://yukicoder.me/problems/no/815 解説 https://yukicoder.me/submissions/340714答えはちょうど、N/2の切り上げになっている。 A/Bの切り上げは(A+B-1)/Bで計算できるので、これで計算して答え。 int N; //------------------------------------------…

https://leetcode.com/contest/weekly-contest-132/problems/recover-a-tree-from-preorder-traversal/二分木がある。 これをpreorder dfsで探索して、[深さ][頂点に書かれている数]を順番に書いてつなげた文字列が与えられる。 preorder dfsはある頂点に来…

https://leetcode.com/contest/weekly-contest-132/problems/longest-arithmetic-sequence/N要素の配列Aがある。 ここから、等差数列である連続でなくてもよい部分列を取り出すときの、長さの最大値を求めよ。N≦2000, A[i]≦10000 前提知識 動的計画法 解説 h…