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)