ferinの競プロ帳

競プロについてのメモ

ARC079 F Namori Grundy

問題ページ
F - Namori Grundy

解法

0以上a[i]未満の整数xが頂点iから辺が伸びている頂点jの値a[j]として全て使われているようなa[i]の決め方をする。
すなわち、a[i]から辺が伸びている頂点jの値として使われていない最も小さい値がa[i]の値となる。

サイクル以外の頂点の値a[i]は葉から順番に見ていくことで簡単に決められる。
サイクル上の適当な頂点を一点取ったとき、その頂点が取りうる値は、

  • その頂点に辺が入る頂点の値として使われていない最も小さい値
  • その頂点に辺が入る頂点の値として使われていない二番目に小さい値(サイクル上で頂点iに入る辺を持つ頂点jが最も小さい値を取る場合)

の2つしかありえない。

サイクル上の1頂点の値が決まればサイクル上の残りの頂点の値も順に決まっていく。この2パターンで成立するものがあれば"POSSIBLE"、なければ"IMPOSSIBLE"となる。

学んだこと

なもりグラフでサイクル外の頂点だけを探索する方法
grundy数の定義

ARC079E Decrease (Judge ver.)

問題ページ
E - Decrease (Judge ver.)

解法

a[i]がn以上であればn未満になるように引き、数列の他の要素に適切な値を加えることを繰り返した。
最初からn未満になるように操作すると途中で遷移がバグってるところがあったので一回 7*n 未満になるように操作したあと n未満になるように操作したら通った（ア
正当性の証明を一切してないすごい怪しいコードになった。

ARC079D Decrease (Contestant ver.)

競技プログラミング ARC

問題ページ
D - Decrease (Contestant ver.)

解法

n=50で考える。
k=0のとき 49 49 49 … 49 とする。
k=1のときは1回操作してこの数列になればよいので 99 48 48 … 48
k=2でも同様に 98 98 47 47 … 47
これを繰り返していくと、
k = 50 で 50 50 50 … 50
k = 100 で 51 51 51 … 51 となる。

したがって50回で周期が存在する。

speedrun001 FからL

F-見える数

読解が難しかったけど質問を見たらわかった。a[i]以前の最大の数がa[i]より小さければそのa[i]は見える。なので最大の数を保持して全てのa[i]を見ればできる。

G-あまり

10のa[i]の長さ乗を掛けたあとa[i]を足すを繰り返す。MODの取り忘れに注意。

H-LIS

LISでググってください。O(nlogn)で解ける。

I-和がNの区間

尺取り。今見ている区間の合計がn未満ならr+1, 今見ている区間の合計がnより大きければl+1する。

J-転倒数

転倒数でググってください。BITを使うとO(nlogn)で解ける。

K-辞書順で何番目？

a[i]の位置にa[i]未満の数が来るものの個数を合計すればいい。(a[i]より前で使っていないa[i]未満の数の個数) * (N-i-1)! を全てのa[i]について足し上げる。a[i]未満の数の個数はBITを使えばO(logN)で取得できる。

L-N回スワップ

1が1番目にいなかった場合、1と1番目の数を直接交換する以外1を1番目に持っていく方法はない。したがってiがi番目になければ適切な位置に持っていくのを繰り返すのが最適になる。 同じ位置について２回交換すれば元の位置関係に戻すことが出来、1回交換すると元の位置関係とは違うものになる。したがって最適な方法で交換したあとに、2の倍数回交換することができれば"YES"、そうでなければ"NO"となる。