naoya_t@hatenablog

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

CADDi 2018

12/22(土) 21:00 - 23:00
atcoder.jp
キャディ株式会社主催のABC/ARC形式のプログラミングコンテスト

晩ごはん食べながら
まさかの1完でパフォ3桁…
1740→1679 (-61) レート冷え込みー
(過去問を埋めれば埋めるほどレート落ちてない?)

C - Product and GCD (300)

まずは素因数分解して
(Pが素数の場合、N=1ならP、N≠1なら1)
素因数の数がN個以上なら

違う
N個以上ある素因数が1つもなければ1
さもなければ
N個以上ある素因数(の積)を答える
→WA(1)
それはそう
2N個あったらその素数の2倍、じゃなかった2乗
3N個あったら…3乗
になるはずで
→AC
https://atcoder.jp/contests/caddi2018/submissions/3841723
Pが大きい場合の処理がおかしくてなんか無駄に時間使った

後で

1\le n\le \sqrt[N]{P}の範囲の整数nを全部試せばいいじゃん

  • 2以上を試して駄目なら1
  • (2以上の数)をN乗したやつがPを割り切れるかを整数演算でやると死ぬので、Pがその数でN回割り切れるかで見る

→再AC
https://atcoder.jp/contests/caddi2018/submissions/3852214

教訓

300は 愚直に解いた ほうがいい #n575

D - Harlequin (500)

何かごにょごにょやってGrundy数をうまく編み出してNimに持ち込む?
なんか考えてても時間溶けるだけ
飛ばした

後で

は(突然思いついた)
色の数だけテーブル(と腕)を用意してそれぞれ独立に、同時並列で戦わせればいいじゃん
で全テーブルで勝利するように考えればいい(することができるか判定すればいい)。

各テーブルでは1つずつしか取れないし、偶数に持ち込むことが勝利条件
なので、最初から全部偶数だと勝てないけど、それ以外なら勝てる
→AC
https://atcoder.jp/contests/caddi2018/submissions/3852090

なにそれ
Cより簡単じゃん

そこに至れなかったのは

  • 考え過ぎというか焦りというか
  • Grundy数 (Nim) にこだわった
  • 小規模な実験をして観察すべきだった

教訓

武器を捨て 実験しよう 焦らずに #a575

E - Negative Doubling (800)

左はどこまでが負で、右はどこからが正なのかを決めればあとはgreedyに解けるんだけど
境目をどこにすると最小値になるか?
ってのを三分探索で解こうとしてて
計算あわなくてサンプルすら合わない(三分探索ではなくgreedyの部分で)
で終了

解説読んだ

なるほど15回以上やった箇所があるとそれ以降は同じ変わり方しかしない(ので0≦x≦15のDPで行ける)…
(あとで通す)

F - Square (900)

開いてない

後で

問題は読んだ。
来年はこの辺り(900点とか)も埋めていきたい。