naoya_t@hatenablog

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

AtCoder Regular Contest 102

9/1(土) 21:00-22:40
1完…506位パフォ1373でレートちょい落ち(1776→1739)

C - Triangular Relationship (300)

場合分け(以下、a\lt b\lt cとする)

  • aaa型
    • 2aがKの倍数、ってことはaは任意のK/2の倍数(Kが奇数ならKの倍数)の個数。
  • aab型
    • 2aがKの倍数になるようなaを総当たり
    • a+aもa+bもKの倍数、ってことはb-aはKの倍数なので、aが決まっているならa+K, a+2K,... をb(b≦n)として取れるのでその個数を求める
    • 順列3通りを掛ける
  • abb型
    • 2bがKの倍数になるようなbを総当たり
    • b+bもa+bもKの倍数、ってことはb-aはKの倍数なので、bが決まっているならb-K, b-2K,... をa(a≧1)として取れるのでその個数を求める
    • 順列3通りを掛ける
  • abc型
    • a+bもb+cもKの倍数ってことはa+2b+cはKの倍数
    • a+cもKの倍数、なので2bはKの倍数
    • 同様なことがa,cにも言えて、2a,2b,2cはKの倍数
      • さらに、b-a, c-b, c-a がKの倍数という制約あり
    • 2aがKの倍数になるようなaを総当たり
    • bもcもa+iKの形のはず。a+Kが何通りあるか数え、r通りあるとしたらrC2通りのb,cの選び方がある
    • 順列6通りを掛ける

→AC
https://beta.atcoder.jp/contests/arc102/submissions/3115032

解説読んだ

説明これ大雑把じゃない?(前段がなぜ成り立つのかが自明に見えない)

D - All Your Paths are Different Lengths (700)

すこし考えて
2^20なのに20ノードしか使えないのきつい
何か別の切り口で考えないとダメだ
フィボナッチとか考えたけどあれは次の項が前の項の2倍より小さいからダメだ

一旦飛ばしてEへ

戻ってきて

n通りのパスを作るには?
ていうか、そもそもノードがN個あってノード間に高々1本エッジを引いていい場合、何通りのパスが存在する?
1+1+2+4+8+... みたいに増えていくから2^{N-2}通りか
20ノードでは2^{18}通りしか作れないからこれではダメだ
ノード間にエッジを2本ずつ引いてみたら?
1+2+6+18+...みたいに増える、ってことは3^{N-1}通りか

あれ?3進法で考えるといいのか?
f:id:n4_t:20180902095101p:plain

みたいな三択の繰り返しで、合計がいくつになるパスでも作れそうだ。

端数をどう処理する?
Lを3進表現して、例えばL=22なら211(=2*9 + 1*3 + 1*1)なので、18個(0〜17)・3個(18〜20)・1個(21)に分けてしまえば良い?

という辺りまで考えて時間切れ

終了後

分けて作るのを1の位からやり直していたらノード数を消費しすぎてしまう。下位の桁は共有しよう。

L(例えば22としよう)を3進法で表現するとK桁(211なので3桁)になるとき、
まずノードをK個用意して、
f:id:n4_t:20180902095333p:plain
のように隣接ノードを3本ずつのエッジで繋いでいく。
ここまでで、【1】-【3】の間でパスが9通りあって、0〜8までの数が表現できている。
これで
18個(0〜17)・3個(18〜20)・1個(21)に分けてパスを実現するにはノードをもう1つ追加(終点になる)して*1

  • 【3】【4】間に {0|9} の2エッジを引く
  • 【2】【4】間に {18} の1エッジを引く→ {0|1|2} + 18
  • 【1】【4】間に {21} の1エッジを引く

f:id:n4_t:20180902095635p:plain
ノード【K+1】へのエッジの本数は、Lの3進表現(211)と対応している。
3の累乗に分解するとこんな感じ。
f:id:n4_t:20180902100054p:plain

196 (3進数で21021) ならこんな感じ。
f:id:n4_t:20180902101913p:plain
3の累乗に分解すると
f:id:n4_t:20180902101939p:plain

この方式なら1000000までのLを問題なくカバーできる*2
f:id:n4_t:20180902100228p:plain

→AC
https://beta.atcoder.jp/contests/arc102/submissions/3122131

解説読んだ

2進法でやってる…2進法で20ノードで表現できる2^{19}まで作って、端数を追加のエッジで8,4,2,1,...みたいに必要なビットだけ繋いでいくことで高々19*3本のエッジで2^{20}-1までの数が作れるってことか
ってこれ自分の解法の3進法を2進法にしただけか…2^20-1=1048575までなら20ノードで間に合うのね。
(解説が0ベースだったり1ベースだったりしてない?)
f:id:n4_t:20180902101750p:plain

ちなみに、20ノード60エッジで最も大きな数がカバーできるのは3進法でやった場合の1417174だった。

20ノード60エッジで足りなくなる最初の数は

base L #nodes #edges
2 1048576 21 40
3 1417175 14 61
4 393215 10 61
5 124999 8 61
6 54431 7 61
7 24009 6 61
8 11775 6 61
9 8018 5 61
10 4999 5 61

おまけ:自分の解法に出てきた例 (L=22) を2進法、3進法、4進法、5進法、10進法でやったものの比較

10進数で考えると何をやってるのか分かりやすいかも

2進法 (10110)

f:id:n4_t:20180902102729p:plain

3進法 (211)

f:id:n4_t:20180902102736p:plain

4進法 (112)

f:id:n4_t:20180902102744p:plain

5進法 (42)

f:id:n4_t:20180902102752p:plain

10進法 (22)

f:id:n4_t:20180902102758p:plain

E - Stop. Otherwise... (700)

問題読んだ
こっちの方が解けるかなと思って暫く考えたんだけど
なんかみんなD解いてるしDに戻った

F - Revenge of BBuBBBlesort! (1200)

見てない

*1:3進数表現の最上位が1の時はK番目のノードを終点にすれば良いので追加は不要になる。底を変えても同じことが言えて、例えば2進数なら最上位は必ず1なので追加ノードは不要。(このことは解説解で20ノードで2^20-1まで表現できてしまう伏線となる。)

*2:1417174まで行ける