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 件のコメント:
ラベル:

2021年12月12日日曜日

Codeforces Round #758 (Div.1 + Div. 2)

 Dまで四完。

コンテスト後のツイート



　Eも解くべきな気もするけど、やらない気もするので公開。
時刻: 0 件のコメント:
ラベル:

2021年12月9日木曜日

AtCoder Regular Contest 131

　ABCEの四完でした。

コンテスト後のツイート

D - AtArcher

　解説放送を見てAC。
　ポイントを挙げると、

・全ての幅がDちょうどだと思って良い
・N本の中心が原点あたりに来るようにした方が良い。なので、そこから0～Dずれているものを全て調べれば良い。
・一回ごとの矢の打ち方を考えるのではなく、「0～Dずれているものたち」をまとめて考えることができる。x本目の矢が刺さる位置はDしかずれないので、累積和を使える

　という感じか。
　一点目はコンテスト中分かっていた（というか、誤読してそういう問題だと思っていた気がする）。二点目も、そんなに深く考えなかったけど当たり前。

　さらに累積和を使いそう……とは想像がついたが、その使い方が分からず解説を見た。つい、一回ごとの点数を考えたくなる（Dおきで累積和を取ろうなどと思ったが上手くいかなかった）が、まとめてやれば累積和を使えるというのが重要ですね。

　これも主客転倒系の発想の転換か。
　

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

2021年12月8日水曜日

AtCoder Regular Contest 130

　Bまで二完で終了。Bまで解いた後Fに行った判断が正解だったかどうか。

コンテスト後のツイート

C - Digit Sum Minimization

　公式解説は見ずにACしましたが、「繰り上がりの回数を増やせば良い」という本質情報を誰かのツイートで見た後でAC。
　「繰り上がりの回数を増やせば良い」ということが分かれば、まあ解ける。Pythonだと多倍長があるので、実際に数字を足して確かめることができるので楽ですね。

　コンテスト中は、桁DPかな、と思ったところで飛ばしてしまいました。
　「繰り上がりの回数を増やせば良い」は実験したら気付けた気がするので、この問題に集中していたら解けていた気もするけど、本当に実験コードを書こうと思ったかは分からないからなぁ……。
　

D - Zigzag Tree

　解説、解説放送を参照しつつAC。

　制約から二乗の木DPは考えたくなる。
　二乗の木DPは、「あるノードがルートだったとき、その部分木についての（何らかの）数」を持つDP。そのことが頭にあれば、「自分より小さい数が何個あるか？」を持ってDPすることが思いつける。これで（実際に実装しようとすると頭がこんがらがるけど、ちゃんとやれば）木DPは書ける。

　が、これを普通に書くと二乗にならず、累積和による計算量削減が必要になる。これは、式を見て冷静に考えれば分かるのだが、私はかなり悩んでしまった。

　木DPパートも計算量削減パートも典型といえば典型で、分かってしまえば難しいものではないし、解かなきゃいけない問題だとは思うけれど、実際にACまでもっていくのは結構困難に感じた。

F - Replace by Average

　コンテスト中に、a, $x_1$, $x_2$, ..., b（各$x_i$はaやbより大きい）という列に操作を行った最終結果がどうなるかは分かっていた。
　aの方が小さいとし、この列がn+1項とすると、(b-a)/nずつ等差数列のように大きくなっていく。余りはどうなるか？　というと、1ずつbに近い方へと分配される。

　たとえば、
・3, 1000, 1000, 1000, 1000, 20
　に操作を行うと、
・3, 6, 9, 12, 16, 20
　のように、途中までは差が3、それ以降は差が4になって20へたどりつく。

　これは実験すれば分かった。
　公式解説ではこの証明に分量を割いていて、なかなか難しいが、問題を解くだけならこの結果を導くことができればOKだろう。

　こうしてできた結果が凸になることにはコンテスト中に気付いた。が、それを生かすことができず、値の小さい区間に対してこの操作を行う……みたいな方針へ走ってしまった。

　そこで凸包を作ろう、と思えたら良かった。
　こういうときアルゴリズムの勉強が大事ですね。凸包（convex hull trickやslope trickでも可）の具体的なアルゴリズムやイメージがちゃんと浮かべば、その方針を取れたと思う。

　凸包で得られた点たちに対して、その隣同士の点について上記の操作を行うと、かなり答えに近付く。実際、それを20回繰り返すことでACできた。（嘘解法だと思うけど、この回数がlogで抑えられそうな気もするので、もしかすると嘘解法じゃないかも？）

　正しい解法は、差が変わる点を適宜加えた（上の例だと、3と20だけでなく12も加える）凸包を作ればOK。
　1項目が3、6項目が20ならば商と余りを計算することで、「4項目が12になり、それが今作りたい凸包の候補になる」と分かる。この操作をしながら凸包を作っていけば良い。
時刻: 0 件のコメント:
ラベル: , ,

2021年12月7日火曜日

AtCoder Grand Contest 056

　A一完でした。


C - 01 Balanced

　解説AC。
　「牛ゲー」というキーワードを聞いても解法が分からず、解説を読んで図を描いてようやく理解できた。

　コンテスト中は連立方程式を解くことを中心に考えていたが、それでは計算量が落ちなそう。だったらグラフの問題なのでは？　とはちょっとだけ思った。
　しかし、そう気付いても実際にグラフに落とすのはなかなか難しい……。

　ただ、グラフにしようと思えば、頂点はN個（か、01列の最初・間・最後を考えてN+1個）だろうし、辺として考えられるのは、

・隣同士の頂点を結ぶ
・問題文の条件にある0と1の個数が同じ範囲の始点と終点を結ぶ

　くらい。あとは、辺の重みをどうにかしようという気持ちになれば、解法にたどりつくのは不可能じゃなかったかな、とは思う。


　牛ゲーに関連してこの問題を見てみたけど、大分雰囲気が違いますね。
　こちらは、「$x-y\leq w$という形の不等式（がたくさん）で表せたら牛ゲーを考えよう」という感じの問題でした。
時刻: 0 件のコメント:
ラベル: ,

2021年12月3日金曜日

Educational Codeforces Round 118 (Rated for Div. 2)

　pretestはEまで。システムテストでCが落ちていたが、これは制約で$a_i$が$10^9$までというのを見て、$h$も$10^9$までと勘違いしてしまったため。そこを修正したら通った。ratedでこういうミスしたら悔やんでも悔やみきれないので、気を付けましょう。

コンテスト後のツイート

　Fはどうしよう。とりあえず放置します。


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

2021年12月2日木曜日

NECプログラミングコンテスト2021(AtCoder Beginner Contest 229)

　Eまで五完でした。見直すと、FもGもシンプルで解けなくてはいけない問題だった。

コンテスト後のツイート

F - Make Bipartite

　解説AC。全く思いつかなかった。
　結構長い時間フローを疑っていたのが良くなかったか。実際にDPして色塗りしていこうとは思わなかった。
　一直線上だったらまずDPを疑ったと思うのだけど……。うーん、図形に引きずられたか。

・各頂点からの辺の数が少ない
・規則性があるので、1→2→3→……と順番に決められそう

　あたりを思えばDPは自然ですね。

G - Longest Y

　解説AC。
　D問題に引きずられたのか、尺取り法を使おうとして失敗。Yの位置だけを取り出し、累積和を使うと、（寄せるべき中央のindex, 左端のindex, 右端のindex）を決めたらO(1)でswapのコストが得られることまでは分かっていた。

　問題は、中央のindexが(左端+右端)/2として求められることに気付かなかったこと。それが分かれば答え決め打ち二分探索を使うのは自然だった。
　中央値というのはちょっと考えたはずなのだけど、最後実装しているときは忘れていたね……。尺取りで上手くいかない、と思ったときにもう一度解法を考え直さなくてはいけなかった。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)