考えたこと： ・愚直解として以下のようなものがある。 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 考えたこと： （これやったことあるんだけど忘れたので、もう一度解く・・・） ・再帰でいじる。 ー＞ダメ。計算が間に合わない。 ・貪欲 ー＞前から順番に消せるなら消していく方…

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