SRM 690
-
masashinakata
- 2317
- 0
- 0
- 0
-
- いいね！0
nmnmnmnmnmnmnm
@enuemuenuemuenu
今日のSRM690div1easyですが、私が見つけたわけではないのですが、N=40、K=1のとき{0}が通るようです。
2016-05-04 15:16:12
koyumeishi
@koyumeishi_
k^N全部試すの、 for で 0...k^N までk進法的に見ると O(k^N * N) になるけど、枝狩りとかメモ化は難しいし、普通の再帰とかと比べると応用の幅は狭そう
2016-05-04 16:02:09
kmjp
@kmjp_pc
はてなブログに投稿しました #はてなブログ TopCoder SRM 690 Div1 Easy WolfCardGame - kmjp's blog kmjp.hatenablog.jp/entry/2016/05/…
2016-05-05 00:07:20
kmjp
@kmjp_pc
はてなブログに投稿しました #はてなブログ TopCoder SRM 690 Div1 Medium TreeWalker - kmjp's blog kmjp.hatenablog.jp/entry/2016/05/…
2016-05-05 00:24:08
kmjp
@kmjp_pc
はてなブログに投稿しました #はてなブログ TopCoder SRM 690 Div1 Hard WolfHockeyTeamHard、Div2 Hard WolfHockeyTeamEasy - kmjp's blog kmjp.hatenablog.jp/entry/2016/05/…
2016-05-05 00:47:20
agw
@masashinakata
ウェブがしっちゃかめっちゃかの間はSRMの例の質問(知人に勧めるか)は一貫してNoと答えると決めているのだが、やはり良問が多いので早くYesを押せるようになりたい
2016-05-05 02:24:20
agw
@masashinakata
ところで@torus711さんのDiv 1 Easyの解説読んでるんだけど、「Nが零元にならない適当なmod」って「N ≡ 0(mod p)とならないp」という解釈でよいのだろうか twitter.com/torus711/statu…
2016-05-05 02:44:46
とーらす🌸📦🌕✨🍀
@torus711
やったこと D1-300: N が零元にならない適当な mod をとって，零元だけ集めてくる．N = 60, K = 15 で 105 が出てきて死ぬので 1 に差し替える
2016-05-04 11:36:31
とーらす🌸📦🌕✨🍀
@torus711
@masashinakata あっそうです（最近講義で代数学をやってたので語句がアレになってしまいました）．「適当な」をちゃんと言うと「条件を満たす法のうち最小のもの」です．零元（法の倍数）からはどうやっても法の倍数しか出ないので，0 と合同にならないようにすれば絶対に作れません
2016-05-05 02:52:16
agw
@masashinakata
@torus711 ありです! 後半の零元だけ集めてくる、というのはそうやって決めたpで決めることができる「x ≡ 0(mod p)となるようなx」という感じで解釈してよいのかしら...?
2016-05-05 02:55:27
とーらす🌸📦🌕✨🍀
@torus711
@masashinakata です．mod m だとすると km (k>0) と書ける整数です．これらを足したり引いたりしても m の倍数なので，m が N を割りきらなければ valid です（ただし 60 はやばい）
2016-05-05 03:00:17
agw
@masashinakata
@torus711 をー、解りやすい。ありがとうございます。60の存在は面白かったすなあ。部屋内で写経しただけでも(60, 15)で落とせる実装が4つあったような気がしました(そういえば同部屋でしたね)
2016-05-05 03:03:18
とーらす🌸📦🌕✨🍀
@torus711
@masashinakata いい感じに法を取れるか直感では分からなくてテストコードを書いたんですけど，そのおかげでチェックできたので命拾いしました．60 とか 360 あたりが約数多いのは有名な話っぽい（時刻・ 角度の文脈）ので，事前に気付きたかった気もします
2016-05-05 03:07:55