2021年12月30日木曜日

Codeforces Round #763 (Div. 2)

　Dまで四完。

コンテスト後のツイート

　とりあえずEは放置します。
時刻: 0 件のコメント:
ラベル:

Educational Codeforces Round 120 (Rated for Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Math Test

　解説AC。

　abs(x) = max(x, -x)で変形するという典型だが、この式を使おうという発想が全く出なかったのはまずい。これにより、N人を、予想より高い点を取ったか、低い点を取ったか、で分けてbit 全探索する。

　PyPyだとTLEにも悩まされた。

　bit 全探索して、実際にきちんとスコアを求めているとTLEしてしまう。そうではなくて、プラス側に割り振った場合 x - r点を、マイナス側に割り振った場合 r - x点を取ったとして計算してしまっても最大値は変わらない（xを実際の点、rを予想の点としています）。それを利用すると定数倍改善されてACできる。

　今回は定数倍の改善に過ぎないけど、これを利用して計算量を改善することもあると思うので、後半のテクニックも頭に入れておきたい。


時刻: 0 件のコメント:
ラベル:

2021年12月26日日曜日

Codeforces Global Round 18

　pretest三完で終了。
　Eは実質できていて、最後に間違いに気付き書き換えたものが間に合っていたら通っていました。うーん悔しい。

コンテスト後のツイート

D. X(or)-mas Tree

　解説AC。
　考察が足りていなかった上、誤読もしていた。

　木のpathに関する問題ということで（あと、STATUSを見たらPyPyでTLEが多く出ていたこともあり）、オイラーツアーとか、HL分解のようなことを考えてしまっていた。ちょっと苦手意識があるせいなのかね、こういう方面しか考えられなかったというのは。

　が、そんなことは必要なかった。pathのxorだけを考えたいので、1～頂点xまでの累積xorをNODE[x]とすると、path u～v間のxorはNODE[u]^NODE[v]となる。これを使えば、エルフの条件も、uとvの間に辺を張ったものと解釈できる。
　なので、後は、pathの距離が-1になっているものを後回しにしてDFS（つまり、01BFSみたいにする）していけば良い。

　なお、誤読というのは、エルフに与えられるのが「距離を二進法にしたときの1の個数の2で割った余り」ではなく、単純に「距離を2で割った余り」だと思っていた、というものです。

　これ、本番中実装してWAが出ていたら気付けなかった気がする……。
時刻: 0 件のコメント:
ラベル:

2021年12月21日火曜日

Codeforces Round #761 (Div. 2)

　D1まで。

コンテスト後のツイート

D2. Too Many Impostors (hard version)

　D1のように隣接三項を聞いていく方針でも、0や1の個数が(n/3, 2*n/3)ということを使っているため、同じ方針でいけるのかなー、と思うとそれではダメ。

　さらに3/nということを強く利用するため、全体を3個ずつに分けるのがポイントだった。3個ずつの組のn/3個あると見て、その三つずつを全部聞くと、0や1の個数が(n/3, 2*n/3)なためその返答に0も1も含まれる。
　そして、その組についてもう6回くらい聞くと、0や1を少なくとも一つ以上確定できる。

　後はそれを利用するのだが、最初に聞いた3個組が0か1かを利用すると、各組二回ずつ聞いて答えを求めることができる。

E. Christmas Chocolates

　解説AC。

　操作により、xからxより小さい数へ遷移するのは一通り。それにより作られる木の直径が答え。シンプルだが、そのような頂点・辺からなるグラフだけ考えれば良い、というのが難しい。
　ただ、思いつくのは難しくても、実験すれば気付けたような気もする。何も思い浮かばない時は実験するのが大事。
時刻: 0 件のコメント:
ラベル:

2021年12月15日水曜日

Codeforces Round #760 (Div. 3)

　pretestは全完。このまま全問通るといいなー→システムテスト全完でした！　Div. 3とはいえ、全完は久しぶりで嬉しい。

コンテスト後のツイート



 　

時刻: 0 件のコメント:
ラベル:

2021年12月14日火曜日

AtCoder Beginner Contest 230

　Fまで六完。

コンテストへのリンク
コンテスト後のツイート


G - GCD Permutation

　解説放送を見てAC。

　gcdが0でないということは、何かの倍数になっているということ。なので、2の倍数の項たち、3の倍数の項たち、4の倍数の項たち、5の倍数の項たち、6の倍数の項たち、……それぞれについて答えを求めることを考える。
　この際、4の倍数の項たちは2の倍数の項たちを計算するときに既に足されているし、6の倍数の項たちは、2の倍数の項たち及び、3の倍数の項たちを計算するときに既に足されている。
　なので、答えを求めた後、適切な係数を掛ける必要がある。
　これは、エラトステネスの篩風にやれば求めることができる（なお、この係数をメビウス関数と呼ぶらしい）

　次に、Pの方を見よう。2の倍数の項たちP[2], P[4], ...について、gcdが0でないものが何組あるか数えたい。
　これも同じ方法を使えばできる。

　……と書くと、まあそうか、という感じなのだが、コンテスト中はこの二回目も同じ方法が使えるということが思いつかなかった。
　前半パートと後半パートで同じ方法を使う自然な問題なんだけど、なぜか逆に盲点になってしまった。

　約数を扱う問題で斬新な手法を問われることはあまりなくて、いかに高速化（特に、エラトステネスの篩を使うことが多い）できるかが重要、というのが最近感じている印象です。
時刻: 0 件のコメント:
ラベル: ,

2021年12月13日月曜日

Codeforces Round #759 (Div. 2, based on Technocup 2022 Elimination Round 3)

　ABCDFの五完。順位は良かったけど、Fが既出だっただけなので。

コンテスト後のツイート

E. Frequency Queries

　クエリ先読みして、オイラーツアーしながら情報を集めておくやつ。
　実装大変だけど、一応実装したらTLE。

　C++での最速が1000msくらいなので、PyPyでも上手くやれば通せそうな気もするけど、諦めます。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)