Codeforces Round #669 (div2) 参加記録
久々の更新です。Codeforces Round #669 (div2) に参加しました。
A~Cの3完でレートは少し下がりました。Eがギリギリ間に合わなかった（1分遅れ...）のが悔しいです...
A Ahahahahahahahaha
1と0のみからなるリスト（リスト長は偶数）からn/2こ除去してa1-a2+a3...=0にする方法を見つける問題です。（n<103） Aにしては難しく多くの人が時間がかかっていたようです。 1と0の少ない方全部除去すれば大体OK。111000のように同数の時は0の方を消して、1110みたいに1が奇数のこる場合はもう１つ1を消せばOK。
B Big Vova
簡単枠です。a1...anが与えられるので並び替えてb1..bnを作る問題。ただし、ci=gcd(b1,b2..bi)としたときにCが辞書順最大にならないといけない。（n<103）
貪欲にgcdが大きくなるのを選んでいけばです。n2で解けます。（雑）
C Chocolate Bunny
インタラクティブ問題です。 リストP は1..Nを並びかえたもの。クエリは"? i j"の形で聞ける。Pi%Pjの値が帰ってくる。Pを復元する問題。クエリは2*N回可能。
i=1, j=2とi=2, j=1を投げます。それぞれの答えをa, bとします。P1>P2ならb=P2%P1=P2になり、またa=P1%P2<P2です。P1<P2ならその逆です。 なので、a, bのうち大きい方がP1, P2の小さい方と一致します。P1, P2のどちらかは決まるので決まっていない方とP3について同じことをします。 これをPnまで順にやれば完成です。
実装とテストに詰まりました。
D Discrete Centrifugal Jumps
わかりませんでした。終了後、以下を参考にACしました。
ある塔から飛べる次のタワーは4箇所以下になるということです。 AC時には上記コードから少し変えてbfsしました。本質的には同じです。
E Egor in the Republic of Dagestan
問題文がはじめ理解できず苦しみました。考えると結構すぐ（数分くらい？）で解法がわかりました。Dの後ということと読みにくい問題文のせいで回答者が少なかった気がします。
NノードM辺の有向グラフが与えられます。辺には0, 1のラベルが付いています。 各ノードに0, 1のラベルを貼る問題です。 あるノードに0を貼るとそのノードから出るラベル0の辺は通れなくなります。 1の場合も同じです。 上手くノードに0or1を付けてノード1からノードNまでの最短距離を最大化する問題です。
後ろからbfs（有向辺を逆向きとしてみる）して訪れるノードのラベルが決まってなかったらそのリンクを使えないようにノードのラベルを設定すればいいです。訪れたノードのラベルが既に決まっている場合はその道のラベルと一致していないなら無視、一致していればそこから先も探索って感じでOKです。 ちなみに本番ではN=1のときに最短距離無限となってしまうコードを書きWAしました。N>=2にして欲しかった。
