SRM 672

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

するめ、オエイス回っぽいし出れなくてよかった説ある

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

今度解いてみよ

hogeover30 @hogeover30

才能談義っぽいのがあったのか

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

オエイス使って問題解いたことなし

kuuso @kuuso1

あさめ、いっそAM5時とかからやってくれ。

nmnmnmnmnmnmnm @enuemuenuemuenu

SRMのeasyなのだけれど逆シミュレーションを10000000000からやると時間が足りないので下から200000くらいまでやっていく。というのはすぐ思いついたけどサンプル2がいつまでたってもあわなかった。

nmnmnmnmnmnmnm @enuemuenuemuenu

n=20の答えがいつまでたっても21になってしまうのはなぜか？

nmnmnmnmnmnmnm @enuemuenuemuenu

22から3で21になって、最後21から2で20になる過程が飛んでしまっている。おかしい。

パーポーフルート @ParpooFruit

こんな手が twitter.com/kenkoooo/statu…

宇宙ツイッタラーX @kenkoooo

はてなブログに投稿しました #はてなブログ TopCoder SRM 672 Div1 Easy: Procrastination - 宇宙ツイッタラーXの憂鬱 kenkoooo.hatenablog.com/entry/2015/10/…

2015-10-21 11:50:00

パーポーフルート @ParpooFruit

約数をソートして最小のをとるx2回で3900ms、そこから約数を昇順で取る変更中に糸冬了。。kinabaさんみたく2通り一度に列挙してソート、なら実行時間的に間に合ったのか。

パーポーフルート @ParpooFruit

ということで約数列挙ライブラリが地味に昇順対応された。

hotpepsi @hotpepsi

@masashinakata 更新しました competitiveprogramming.info/topcoder/srm/r…

kmjp @kmjp_pc

今日のDiv1 Easy1発ACならず。今回出なくて助かったな…。今回のEasy正答率も平均スコアも低目だし、結構考察難しい…？

nico_shindannin（診断人） @nico_shindannin

帰宅じゃ。体だるかったけど、まぁなんとか…。今日もできるだけ早く寝たいところじゃ…。

nico_shindannin（診断人） @nico_shindannin

今朝のSRM672 Div1 Easyについての感想だけ、書くのじゃ。

nico_shindannin（診断人） @nico_shindannin

わしはシミュレーション解で、x/h=a余り0or1になるようなaを、hを2から増やしていく。ただhを2→nまでループさせると、nは100億で間に合わないので、hを2→√nまでループさせて、その後x/a=h余り0or1でもあるから、aを√n+1→2までループさせたのじゃ。O(√n)

nico_shindannin（診断人） @nico_shindannin

こういう問題で何もアイディアが思いつかないときは、まずは計算時間を無視したシミュレーション解を書いて良いと思うのじゃ。計算が間に合わなくても、ログを出力すれば、良いアイディアに気づくチャンスが増えるのじゃ。特にこの問題は、nを気にしなければシミュレーションは3分もあればかけるので

nico_shindannin（診断人） @nico_shindannin

また、計算時間が間に合わないシミュレーション解と、高速化した提出解を比較することで、ポカミスで落ちることも防ぐことができるのじゃ。nは10000ぐらいまで全部テストすれば、まぁ落ちることはないでしょう。シミュレーションを書いた時間分のロスの元は取れると思うのじゃ。

nico_shindannin（診断人） @nico_shindannin

さらに、仮に高速化解が思いつかないとか、間違えてたとしても、それはそれで、どういうケースでダメだったかが分かるので、チャレンジ時に強力なテストケースになりうるのじゃ。まだチャンスが残る。

nico_shindannin（診断人） @nico_shindannin

競技プログラミングに限らず、一般のプログラミングでも、絶対正しいテストケースがあると、いろいろ使える。こういうことは、心がけしだいですぐ改善できるとこなので、おすすめ。

nico_shindannin（診断人） @nico_shindannin

ま、そんなとこじゃ。あと、「素数のところを越えてタスクが移動することがない」を生かした別解（というか想定解?）が多くて、けっこう意外でした。

hogeover30 @hogeover30

「とりあえず速度は気にせず愚直解を書いてみよう」 → 「書けぬ」 → Coding Phase has ended.

hogeover30 @hogeover30

あまりにもよくある

nico_shindannin（診断人） @nico_shindannin

じじい、養生します。さよならー

nico_shindannin（診断人） @nico_shindannin

さっきのツイートaを√n+1→2ではなく√n-1→2ですね…。テストシミュ解を書けば、こ、こういうポカにも気づくことができるのじゃ！（開き直り）