AtCoder Regular Contest 102 参加記

今回僕が解けたCとDは解法を言われるとそれはそうとなるので,ACまでの試行錯誤を書いておく

C問題 Triangular Relationship

考察

  • よくわからんけど愚直はもちろんTLE.O(N\log N)までしかだめ
  • 1つ決めると他2つが決まるとか?
  • そういう訳ではなさそう…?
  • 数えたいものの特徴は?
  • \bmod kが同じやつ同士っぽい
  • ただ何でもいいわけじゃなくて,2倍してmod k取ると0になるやつだけ
  • mod決めちゃえばそれの個数は求まるし,重複OKなので3乗するだけ
  • 実装(こんがらがってて1WAした)

むずかしかった

解法

2x\equiv 0\pmod Kとなるすべてのxについて,[1,N]に何個存在するか求めその3乗を答えに足す.

D問題 All Your Paths are Different Lengths

考察

  • とりあえず実験
  • 適当に辺を足していってもある程度作れそうだけど,頂点と辺の制約的に賢いことしないとダメそう
  • 無駄な枝分かれは意味がないので基本は1本道にしたい.
  • 多重辺
  • 2進数とか良くね????
  • 実験するとL=2^nn+1頂点と2(N-1)辺で表現できる

f:id:SugarDragon5:20180901234759j:plain

  • このままだと2の累乗しか表現できないし最大で21頂点必要になってダメそう
  • n頂点でL=2^nできないの?
  • できた

f:id:SugarDragon5:20180901235151j:plain

  • 1つ頂点が減らせた.2進数で考える+αのこの方針で20頂点に収めることは可能そうだし,もう少し考察してみよう
  • 2の累乗以外を表現できるように辺を足す方法を考える
  • とりあえず2個目のやつよくわからんし1個目のやついじろう
  • Lを2進数で見たときに1の桁に対して操作が必要
  • 辺の制約的に追加できるのは各桁1本
  • それぞれの操作で増やしたいパスの個数を満たすところはどこだ
  • 桁の回数行ったところから辺を引くと欲しい数だけ増えそう
  • 他に影響してほしくないのでゴールに直接つなごう
  • 重みはいい感じの数が出るようにしてみる
  • できた

f:id:SugarDragon5:20180902000514j:plain

  • 頂点数[\log_{2}L]+1で表現できた
  • 2^{20}未満なので20個でできそう
  • うまくいきそうなので実装する(きびしい)
  • AC

解法

[\log_{2}L]+1点の2進グラフ(画像1枚目のやつ)に適切な辺を適切な数値で足していく

結果

f:id:SugarDragon5:20180902001054p:plain
71分2完1ペナで201位
f:id:SugarDragon5:20180902001156p:plain
まあまず水色に落ちないところ(パフォ663で水)まで上がったので嬉しい.
2回連続で700を通せたのが良かった.