考えたこと： ・愚直解として以下のようなものがある。 vectorを１つ用意する。(初めにＡｉ（i=1~N)を入れておく。） 各ｊに対して、vectorにＢｊ枚、Ｃｊを入れる。 vectorをsortする。 大きい方からＮ枚とる。 このＮ枚は明らかに最大値をとり、このような…

コンテスト中はＥに時間を全て使ってしまいました。 自分の理解した範囲で解説していくので、間違いなどありましたら指摘して頂ければ 嬉しいです。 考えたこと ・ｂは本質ではない！順番に足していけばよい！ ・絶対値の和の関数の最小値を取る座標は、傾き…

考えたこと： ・値の等しい任意のai,ajに対して題意の条件が成立するので、構築できるならば対称性がありそう。 ・もしかして、Ｋ＝＝０の場合にしか構築できないのでは？？ ー＞場合分けして提出。 ー＞そんなことなかった。 ・紙上で実験をし続けていると…

考えたこと： ・Zは定数なので、ほとんど関係ない。（ＭＯＤ ２をとって終わり） ・Ax1+Ay1のＭＯＤ ２が解っているとき、、片方の値が判明すればもう片方も判明する。（０か１しかないので） ・ＡがわかればＢもわかるという関係を連結と呼ぶならば、２つの…

考えたこと： ・二点間についてすべて考えてしまうとＯ(N^2)で間に合わなくなる。 ・距離の偶奇しか問われていないので、距離の大きさは本質ではない。 ・こういう問題は根付き木にして、根を起点にして考えるとよいことが多い。 図を書いてじっと眺めてみる…

C - GCD on Blackboard 考えたこと： ・双方向から累積gcd ・すべて素因数分解してごちゃごちゃ （バグったのでＤに行きました。ＡＣ出来ませんでした・・・） 解説： この問題を言い換えると、「Ｎ個の要素からＮ－１個選んだ時、ＧＣＤが最大になるような…

考えたこと ・010を[1,3]で反転させると101、[2,2]を反転させて 111 とできるが、 これは左の０と右の０を別々に反転させることと同じっぽい。 （１を跨いで反転させるのは無意味そう） ・連続する０を反転することだけを考えればいいのではないか？ ・（連…

考えたこと： 1)メモ化再帰 2)包除原理で解く。 -> 2は厳しそう。 -> 重複が滅茶苦茶になりそう。 メモ化再帰で実装する。 どうやって？ dp[i][a][b]：＝i番目まで見ていて、i-2番目はa,i-1番目はbの時の数列の個数。 (ここで、A=0,B=1,C=2,T=3と対応させる…

皆さま、お久しぶりです。 競プロを再開したいと思います。 C - Unification 考えたこと： （これやったことあるんだけど忘れたので、もう一度解く・・・） ・再帰でいじる。 ー＞ダメ。計算が間に合わない。 ・貪欲 ー＞前から順番に消せるなら消していく方…

考えたこと： ・メモ化再帰 ー＞重複が取り除けない・・・ ー＞偶奇で場合分けしたりするのだるすぎる・・・ ・数え上げていく ー＞これも微妙・・・ ・組み合わせの計算に持ち込む。 ー＞どうやって？ 左端上の点を固定して考えようとしていましたが、これ…

A:12/22 解法： 各桁毎にチェックしていく。 整数Ｎの１桁目はＮ％１０に等しい。 ２桁目は（Ｎ／１０）％１０に等しい。以下同様 whileで実装する。 （わからない場合は確かめてみると良い） #include <bits/stdc++.h> using namespace std; #define int long long signed </bits/stdc++.h>…

初めに思いついたこと： ・前からシミュレーション ->何往復もするのでかなりの計算量になる。（Ｎ＜＝１０＾５） ・反転数っぽい。 ー＞ＢＩＴか？ ー＞ダメ。ＡＧＣ－ＡでＢＩＴが出るわけない。（ぐっと我慢する） （もっと楽な方法があるはず） 実験を進…

初めに思いついたこと： ・Ｎ＜＝５０と小さい。 ・漸化式を用いて、ＮバーガーのＰとＢの総数と、ＮバーガーのＰの総数は表せる。 （前者をnum[N],後者をf[N]と表す。） ・後ろから数え上げればいいな。 ー＞シミュレーションか？ ー＞シミュレーションは厳…

初めに思いついたこと： ・最小値だから二分探索では？？？（条件反射） ー＞問題をよく見ると、そんな必要はない。 ・Ｎ＝１０＾５だからsortして考えて良いな。 ー＞sortしたら尺取り法の要領で求まるのでは？ ー＞Ｋが決まっているから尺を取る必要もない…

初めに思いついたこと： ・１００！を愚直に扱うのはまずい。（１５０桁くらいある） ・約数の個数なので、素因数分解した値を考えれば良さそう。 （この時、１００！を素因数分解しても、素因数の個数は（２＾１０）＾５０≒１０＾１５０よりせいぜい５００…

初めに思ったこと： ・全探索は難しそう。Ｏ（Ｎ）＝１０＾９ ・桁ＤＰかな？ ・ずるずると桁ＤＰの沼にハマる コンテスト後： bit全探索を思いつく。 具体的には、3,5,7を0,1,2に対応させてbit全探索。 計算量はＯ（１０＊１０＊３＾１０）≒１０＾６で、間…

競技プログラミングの解説ブログを書いてみることにしました。 私はプログラミングを知らない状態で競プロを始めた人間です。 なので、プログラミング未経験者の方々が競プロを始めたときに、私の軌跡を参考にできるようなブログが書けたらなと思います。 あ…