ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

技術室奥プログラミングコンテスト #3 参加記録(H問題のみ)

技術室奥プログラミングコンテスト #3 - AtCoder

筑波大学附属駒場中学校・高等学校の皆さんによるコンテスト。

部分点がたくさんあるので順位表も複雑ですが、6完+部分点で16位でした。

f:id:betrue12:20180715082653p:plain

普段なら各問題の解説を書くのですが…今回公式解説がすごく丁寧で、解説を書こうとしてもこれを丸写ししたような内容になってしまうため、1問だけ。

Hの510点を解説と違うやり方で取ったので、それについて書いていきます。

H - 新入生歓迎数列 - Hard

H - 新入生歓迎数列 - Hard

基本アイデアは解説の最初の方に出てくる「2進数の各桁を分配する」です。

f:id:betrue12:20180715094741p:plain

このように  A_{1} を起点にして2進数の各桁を分配することでそれぞれの値を作ります。

分配されるそれぞれの値は  2^{30}-1 以下なので、2進数で30桁。 N がおよそ  550000/30 = 18333.33... 以下であればこの方法でいけます。これで280点。

 N \le 25000 で+230点もらえるので何か方法はないか考えたところ、「階差数列を使う」というアイデアが出ました。

f:id:betrue12:20180715100300p:plain

作りたい数列をソートし、その階差数列を取ります。そうすると、最小値が1、最大値が  2^{30}-1 なので、階差数列の総和 2^{30} - 2 以下となります。

「各項が  2^{30} 程度」と「総和が  2^{30} 程度」の違いは大きくて、 N = 25000 としてざっくり計算すると1つ1つの値の平均は 2^{30} / 25000 = 42949.672... くらいになります。これは16bitで作れるので、最後の数列復元に各1回使うことを加味しても  17 \times 25000 = 425000 回程度で完了します。

これを実装して510点を取ったのが以下のコードです。

510点コード:Submission #2839764 - 技術室奥プログラミングコンテスト #3

この方法だとここから発展性がないのでこれ以上の点数は望めませんが、510点までであれば公式解説の4進数よりも思いつきやすいのかな…?と個人的には思いました。