Codeforces Round #669 感想
はじめてのRated div2
https://codeforces.com/contest/1407
総括
A問題を中心になんか全体的にぼろぼろ
Problem A
長さn（偶数）の01の配列を半分以上残るように自由に削って奇数番目の要素の総和=偶数番目の要素の総和にせよ
考えたこと
- 0があったら0って吐いてそうでないなら1を2個吐けば
- 誤読じゃん 削りすぎ
- とりあえず1の個数c1と0の個数c0をカウントするのは大事そう
- [c1/2]*2個1を吐いて後c0個の0を付けるのは
- 順番の情報が落ちるから嘘
- [c1/2]*2個の1とc0個の0を出現順に合わせて出力すれば
- 総和の平衡が崩れるから嘘
- A問題なんですが…
- 0が多いなら0を使いたい 1が多いなら1を
- でもできれば0を
- 0が半分以上（半分より多いではなく半分以上）なら0だけ吐いて終了
- そうでないなら1が半分+1以上
- [c1/2]*2個1を吐けばいい（n/2ちょうどでいい気がするけど要素数が奇数になって壊れうる）
- 55分+4ペナとは
ひとこと
思いついた実装を書いては消し書いては消しを繰り返していた。落ち着け コンテスト前に見たA問題も解けなかった。A問題適正…
Problem B
数列Aを並び替えてできるBのうち、Bから作れる数列Cが辞書順で最大になるものをひとつ出力せよ 数列C Ci=GCD(B1~Bi)
考えたこと
- 累積GCD必須
- 先頭は最大要素以外ありえない
- 数列Cの各要素の値はまあ増えはしないよね
- Ci=GCD(A1~An)になったらあとはどうでもいい
- B2は先頭とのGCDを最大化する要素
- B3はGCD(B1,B2)とのGCDを最大化する要素
- 以下同じ
- 前から順に決めればいい
- 以下怪しい考察と実装
- 少なくとも序盤は全探索するしかない
- Amax小さいしどうせ累積GCDは10項もすればすぐ全体の累積GCDに一致するでしょ（嘘。Aに同一要素がないと書いてない）
- そうなったら打ち切って余ってる候補並べればいいやん計算時間がO(n2)から定数のでかいO(n)に減りそう（それは嘘…）
- 候補管理はmultisetでいいかしら
- 制約ちゃんと見たら絶対間に合うが O(n2 logなんちゃら)で
- 40分か…
ひとこと
頭動いてない＆制約変に読んだせいでちょっとよく分からん実装になった。複数テストケースなこと忘れて計算量見積もり壊しがち
Problem C
インタラクティブ。n要素の順列pがある。? x yという質問を投げるとp[x]%p[y]が得られる。2n回以内の質問で順列を復元せよ
考えたこと
- 時間がありませんが
- p[a]とp[b]の大小関係がわかる？
p[a] % p[b] > p[b] % p[a]ならp[a] < p[b]- modというか大小関係が情報として得られるので最大の要素の位置をn回の質問で特定できれば
- 残りn回で各要素を特定できるけど
- 大小関係の時点で2n回使い切るじゃん
- えー
残りの問題は守備範囲外と判断。
コンテスト中～終了直後
Hackの余裕などなし（成功した例知らないけど） システムテストは無事通過。よかった 英語力に不安が…おとなしく翻訳つかうか…？
レート
486。初めてなので低めに出ているはず。
コンテスト後Cの解法ツイなどを見て
p[a] < p[b]の時はp[a] % p[b] = p[a]p[a] > p[b]の時はp[a] % p[b] < p[b]であるが、p[a] % p[b] < p[a]でもあるp[a] % p[b]とp[b] % p[a]両方の結果からどっちか1要素は確定できる- 2n回でn要素全部特定できそう
