naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Grand Contest 017

agc017.contest.atcoder.jp
7/19 21:00-23:00
出てみた
AGCは初めてかな
1完 (o--x--)

Bの解法を思いついたときには終了まで3分切ってた
終わってすぐに通した

レーティング少し上がった(けどまだ3桁)
f:id:n4_t:20170710000653p:plain
f:id:n4_t:20170710000706p:plain

A. Biscuits

あれ?これって結構でかい数になりうるよね
面倒くさいしpython
Counterで殴って
nCkをインクリメンタルに計算しつつ
→AC
Submission #1409066 - AtCoder Grand Contest 017 | AtCoder

B. Moderate Differences

区間を1ステップずつ(とはいえ累乗で)出してた
時間かかりすぎる
skip

残り3分弱で解法思いついた
.. [C, D]
.. [C-D, D-C], [2C, 2D]
.. [C-2D, D-2C], [2C-D, 2D-C], [3C, 3D]
...
...
.. [C-(m-1)D, D-(m-1)C], ...., [(m-1)C-D, (m-1)D-C], [mC, mD]
になるんだよね (m=N-1)
C,Dの値によって重複したりしなかったりするんだけど、
それが重複してようがしてまいがいいじゃん
どれかに入ってるか計算するのってO(N)だ
→AC
Submission #1412749 - AtCoder Grand Contest 017 | AtCoder

C. Snuke and Spells

skipped

D. Game on Tree

Nimぽい
ツリーをどうXORに落とすのか
サンプルケース通るところまで頑張った
→WA
Submission #1412020 - AtCoder Grand Contest 017 | AtCoder (嘘解法)

E. Jigsaw

unopened

F. Zigzag

unopened