yukicoder No.420 mod2漸化式
最近はyukicoderの低難易度埋めてます.
その中でもおもしろいと思ったものを書き留めます.
解法
まず漸化式
がそもそも何を表しているか考えます.
ためしにいろいろ入れてみると,
...
となります. のべきがとなっているところや, 数字の増え方をみると, この漸化式は(というより関数としてみると)あるを進数表現したときの立つ1の数, または各桁の和であると推測することができます. その観点を持って漸化式を見ると, たしかにそれらしいことがわかります.
問題に戻ります. 問題では, あるが与えられ,
- となるようなの数
- それを満たすの和
の2つを求める必要があります. 上の考察より, 前者は31ビット分の中に1を個立てる場合の数を求めればよいです. これは, で求まります.
後者は少し考察が必要です. 上で求めたの中で, 番目のビットにが立つ場合の数はいくらか?を考えます. この数は, ビット目に1を立てておいて他の場所に個1を立てたときの場合の数に対応するので, に対応します.
よって, ビット目に1が立つものは 個あり, このを1から30について計算するので,
となります. コンビネーションの部分は外に出せ,
となり, さらに簡略化すると,
となり, これが和の方の答えです.
しかし, が0のときだけ場合分けが必要なので注意です.
感想
漸化式の意味を理解すると大きく計算量を減らすことができる面白い問題だと思いました.
ARC 102 C - Triangular Relationship
解法
コンテスト中は, ひたすらを固定しての数を数える方法を探していた.
まず, 問題文を式に表してみると,
を固定してみたときとりあえずは
表すことができる. また,
より
が成り立ちます.
また, 条件から各について
より
について
が成り立ち, についても対称性から同じものが成り立ちます. これを変形すると, について
となり, についても
が成り立つ必要があります.
いま, を固定しているため, 不等式からとが取りうる値の数を求め, 掛けあわせれば場合の数を求めることができます(同じ式の形なので, 片方を求めて二乗すればよい).
しかし, 式
はを固定することにより得ているので正しいが,
は, との値によっては成り立たない場合があります.
がの倍数でないときはこの式を満たすことはできません. 逆に, がの倍数のときは, 両辺をで割り, を導出することができるため, がで割り切れることは, この式を満たす必要十分条件となっています.
よってその場合のみ数を数えないことにします.
これをについて行い, すべての場合の数を足しこむと答えが得られます.
SoundHound Programming Contest 2018 Masters Tournament 本線 B - Neutralize
解法
貪欲ができないか考えます.
ある薬品を0にしたいときはK個を巻き込む必要があります. また, 個以上の区間を0にしたいときはこれを繰り返すことで実現することができます.
しかし, サンプルケースを見てみるとこれは厳しそうであることがわかります.
最適解が貪欲に求まりそうにないので, 最適解を仮定してDPをすることになります.
DPをするにあたって必要な保持状態は、まず
- 見ている薬の番号(1からN)
が必要です. 他に必要なものは,
- 見ているインデックスを右端としてK個選び, 0にしたかどうか(True or False)
です.
この2つを規定すると,
基底
感想
なかなかに大きい制約なので DPはなかなか発想できません.
No.672 最長AB列
解法
まず愚直解を考えます.
左端を決めて左から文字列を見ていき, A, B,の数を数えながら右に行き, AとBの数が同一になったら最大値を更新します.
この解法はでTLEです. この解法を詰めていきましょう.
まず,ABの数が同一ということはAを1, Bを-1とすると和が0となるということです. これの累積和をとっておき, 区間が与えられたらでその区間のABの数が同一かどうかを答えられるようにしておきます.
ある2つの区間の端を選ぶと, 対応する累積和があります. その累積和の差が0であると, その 区間のABの数は同一ということになります.
上の考察から, ある区間の左側を決めたときに, それに対応する累積和と同一のものが右側に存在するか?を考えればいいことがわかります.
このときに選ぶ右端は, できる限り右側のものを選ぶと, 区間が大きくなります.
よって, 累積和をとるときにある累積和の数値をとったもので最大の添字を持つものを一緒に保存しておけばいいことがわかります.
mapで上を実装すると, 計算量はで抑えられます.
感想
はじめは累積和をとって二分探索するものかと思いましたが, 単調性の反例が見つかり断念.
こういった問題は愚直解から詰めていかないと考察が難しいですね...
類題としてAGCのZero Sum Rangeなんかが挙げられます.
区間の左側を決めた時に最適な右側を高速で導出するのは結構典型ですね.
yukicoder No.390 最長の数列
解法
DPをします.
としておきます. 遷移は,
です. 右のを固定して配るDPにすると,
計算量はなります.
左を固定すると約数の列挙にかかるためとなり, ギリギリ間に合います.
感想
難しかったです.
No.462 6日知らずのコンピュータ
解法
まず, がであるときを考えます
このとき, 〜 桁のビットまで, ビットを立てる順番の場合の数がそのまま場合の数になります. 一度立てたビットは元に戻さないため, これらの数列たちはすべて異なるものになり, 答えはとなります.
のときを考えます.
目的の数列は, それぞれの要素を2進数で表したときのビットが立っている数でソートし, 立っているビットの数をみると , となり, ビットの数にかぶりはありません.
また, ビットの立て方から, この立っているビットの数でソートした数列(とします)の性質として, が成り立っている必要があります. (ここではビットごとの論理和)
言い方を変えると, ある要素より1つ大きな添字を持つものは, ビットを要素としてみたときに左の要素を部分集合として持っている必要があります. これらの性質を与えられたが満たしていないならば, 数列を作ることはできません. また, 立っているビット数が等しいものが存在しないことも必要ですが, (等しいとき, 両方の数を数列内に入れることはできない), これはすでに上の必要条件となっています, これらの制限をクリアできないものは0を出力します.
条件を満たした数列の場合の数は, 各の間のビットの埋め方の積となります. のハミング距離の階乗を順次かけていくと答えです.
感想
ビットシフトをする際, (1<< N) -1 と書くと, 1がint型として認識され, Nがint型を超えるような値となっていると望み通りの計算結果が得られないことがわかった. 次のように記述するとうまくいく.
(1LL << N) - 1
また, MODのとり忘れに気をつけたい.
yukicoder No.491 10^9+1と回文
解答
の性質に着目します. にたとえば123456をかけると, になります. ほかの数値に対しても, 数値が左側と右側にコピーされているような感じになります. これに着目すると, が回文となる場合は, 回文を掛け算した場合のみであることがわかります.
与えられたに対して (小数点切捨)
としたが, までのの倍数の数となります.
『以下の自然数であって回文であるようなものの数』が答えとなります.
回文の数を手元で概算すると, それほど多くないことに気づいたのですべてを列挙してソートし, 二分探索で数を数えることにしました.
回文の列挙は,
1桁, 2桁は自明
K桁目は, K-2,K-4,..(1 or 2)桁の回文を真ん中に置いて両サイドに1~9を置くことで生成することができます.
詳しいことは提出を見てください.