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

2021年11月30日火曜日

AtCoder Beginner Contest 223

　Fまで六完。

コンテスト後のツイート

G - Vertex Deletion

　解説放送を見てAC。
　全方位木DPで書いたけど、理解するのにも実装にも非常に苦労してしまった。全方位木DP自体は理解しているつもりだったけど、遷移式が分かりにくいだけで非常に戸惑った。
　ライブラリとはいえないけど、一応、以前に比べると書きやすい形にまとめた。（次回、全方位木DPを書くときはここで書いたものを元にしよう）
時刻: 0 件のコメント:
ラベル: ,

2021年11月29日月曜日

Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)

　Eまで五完。Eに手間取り過ぎた……。

コンテスト後のツイート

　F以降を解かなそうな気がするので、ツイートだけだけど記事を公開。Eは類題経験が生きたといえなくはないんだけど、もっとすんなり通したかった。

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

2021年11月27日土曜日

Codeforces Round #757 (Div. 2)

　D1まで四完。

コンテスト後のツイート

D2. Divan and Kostomuksha (hard version)

　やり方はD1と同じ。（自分のツイートだけじゃ解法を理解するのは無理だろうけど、今回は省略）

　問題は約数列挙を高速にできるか？　というところ。
　エラトステネスの篩を使えば高速にできるだろう、とは思っていたけど、良い書き方が分かっておらず、一旦素因数分解してから約数を求めるという二度手間で書いていた。

　実際は、素因数分解を経由せずに書けて、その方が速い（その書き方に気付いておらず、他の方の提出を見て気付いた）。そのように書き直したらPyPyでもACできた。
時刻: 0 件のコメント:
ラベル: ,

2021年11月24日水曜日

AtCoder Beginner Contest 226

　Eまで五完。

コンテスト後のツイート

F - Score of Permutations

　解説放送を聞いてAC。

　i=P[i]となったらそこでボールが止まると誤読していた。ツイッター上で同じ誤読をしている人を散見したが、とはいえ良くない。最初誤読しても、Sample3の答えが合わなかったところで気付くべきでした。

　というわけでoeisを使うにしても、これではなく、こっちだったよう。

　ただ、本番は埋め込みしようとしていたわけなので、その後のDPによる処理が分かっていなかったのもまずい。

　DP[i][j]で、i人まで決まって、そこまでのlcmがjのときの場合の数、とする。遷移は、「まだどのグループにも属していない添え字最初の人がどのグループに入るか？」を考えることで求められる。

　これは、重複なく数え上げるときの典型手法の一つ。実験→埋め込みにいってしまったためまともに考えなかったせいもあるかもしれないが、思いつけなかったのはダメ。ちゃんと身に着けておきたい。

G - The baggage

　解説AC。Gに置かれているから難しそうだけど、CやDあたりに置かれていたらたくさん解かれていそう。
時刻: 0 件のコメント:
ラベル: ,

Codeforces Global Round 17

　Dまで四完。Eが解けなかったのは、Dで苦戦して頭が働かなかったため、という気もする。

コンテスト後のツイート


E. AmShZ and G.O.A.T.

　三個がterribleな場合に帰着されそうというのはそうなのだけど、そこから考察を進められなかった。

　badじゃない数列を構築していこう、と考えれば良かった。

　a, b, c （a<b<c）がbadじゃないとする。さらにd（>c）を付け加えたいなら、a, c, dの三つがterribleになってはいけないので、d-cがc-a以上にならなくてはいけない。なので、構築できる数列のサイズはlogで抑えられるので、計算量も大きくならない。

　これで十分条件も満たしている、というのに気付いていなかったのがマズかった。四個以上の数列がbadになるとき、terribleな三個の数列ができそうだけど、できるならどこにできるのだろう？　という考察ができていなかった。これは気付けなきゃいけなかったなぁ……。

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

2021年11月23日火曜日

AtCoder Regular Contest 129

　Cまで三完。

コンテスト後のツイート


D - -1+2-1

　解説放送を聞いてAC。
　一時間考えていたけど、累積和なんて全く思い浮かばなかった。（階差は考えたが……）

　累積和を取るということが思い浮かべば、「初項に+2」「末尾の項に+2」以外の全ての操作は、累積和を一つ後ろの項へわたすような操作と分かる。なので、

・累積和の和が0になるよう、「初項に+2」「末尾の項に+2」により調整。
・あとは、「初項に+2」と「末尾の項に+2」は同じ回数ずつ使う。実際に操作が行えるよう、これらの操作回数を二分探索で決定（解説では二分探索していないが二分探索でも解ける）

　とすれば良い。

　なので、「累積和を取る」というのをどう思いつくのかが大事だろう。これは、

・「総和は変わらない」「数列が円環じゃない場合は簡単だから端の操作を特別視できそう」

　といったあたりから気付けなくてはいけなかったのだろうと思う。

　このあたりにギャップを感じるなら、maroonさんの公式解説の方が良いのかな……。こちらだと、操作で$i$を選んだ回数を$a_i$として立式することで、まあまあ自然に解法へと辿り着いているから。とはいえ、式を見たときこの考察へたどりつくのは簡単ではないな……。
時刻: 0 件のコメント:
ラベル:

2021年11月6日土曜日

yukicoder contest 321

　ABの二完。C思いつかなかったのは大いに反省。


No.1730 GCD on Blackboard in yukicoder

　各A_iの約数を列挙できたら解けるな……と思い、エラトステネスの篩（に似た方法）で約数列挙を高速にするやつを使って通した。
　解説を見ると、エラトステネスの篩（に似た方法）を使うのは同じだが、約数列挙までする必要はなかったみたい。頭が固い。

No.1731 Product of Subsequence

　解説AC。
　Kの約数を使うだろうな、とは思ったのにDPを思いつかなかった。
　さらに、DPの遷移式を立てるとき、gcdを使うことを思いつかなかった。

　反省しかないけど、こういう、頭が働いているときなら思いつけたはず……って内容を思い付けなかったときって、具体的な反省をし辛い気がする。
時刻: 0 件のコメント:
ラベル:

2021年11月5日金曜日

技術室奥プログラミングコンテスト#6 Day2

　A一完で終わってしまった。そこそこ解かれている問題はACしたい。


B - Replace to the Other

　この前のAGCの問題の類題ということで見てみた。
　確かに類題なのだが、これを思い付くのも厳しい……。結局解説を見てしまった。

　「同じ文字達を変える」方が分かりやすいのに、その逆を考えねばならないのですね……。

C - Strange Paper

　これは実験一択でした。
　Nが8くらいまでは実験でき、それくらいまで実験したら答えに気付けそうです。ただ、N=6で解がないのがちょっと意外か。全探索じゃなくて、乱択で答えを求める実装をしたため、解がない場合に気付かずちょっと困りました。

D - NG Word Game

　解説を読んでもよく分からなかったけれど、このツイートを見てAC。"01"*Nは考えたんだけど、端から調べていってOKっていうのがパッと分からずつまった。
時刻: 0 件のコメント:
ラベル:

2021年11月4日木曜日

AtCoder Regular Contest 126

　AB二完で終了。悲しい。


C - Maximize GCD

　解説AC。

　Aの要素全てをmax(A)に揃えられるほどKが大きいときはOK。
　問題は、そうできないとき。
　普通に考えると、gcdをxにできるかどうか、の判定にはO(N)かかる。なので、gcdの候補をどうやって絞っていくかが問題。だけど、どう絞れば良いのだろう……？

　……と考えてハマってしまった。

　実際は、「gcdをxにできるかどうかの判定」の計算量を減らせる。

　あるxに対して、kxより大きく(k+1)x以下の範囲にあるものは全て(k+1)xにする。なので、「その範囲に何個あるか」「その範囲の総和」が分かれば良い。
　それらを予め求めておくことで、各xについて、O(max(N)/x)になり、（調和級数の）logの計算量で求められる。

　コンテスト中、「gcdをxにできるかどうかの判定」の計算量が本当にO(N)必要なのか？　を疑問に思った時間は確かにあった。だけど、gcdの候補の方が絞れそうな気がしたので、真面目に考えずに終わってしまった。

　候補を絞るのが難しそうと思ったときに計算量を減らせないか検討すべきだったんだろうけど、飛ばしてDへ行こうと思ってしまった（飛ばしたこと自体は悪いことではないけど）。
　まあ確かに、max(A)とかから候補を絞るのはいかにも嘘っぽいので、計算量削減を考える方が筋は良いんですよね。

D - Pure Straight

　（解説通りの方法ではないけど）解説AC。

　解説の「使う項と部分列の位置を固定した場合」の部分が非常に重要だと思う。コンテスト中、一応正しいことを考えてはいたようだけれど、答えは「転倒数＋何か」になるはずとは思ったけれど、「何か」の部分があやふやだった。

　あとは、区切り位置を決め、「その前の部分からどの数字を取ってきて、その後ろの部分からどの数字を取ってくるか？」をbit全探索すれば計算量は悪いが答えが求まる。自分の書き方だと定数倍がきついため、bit全探索の部分を枝狩り（区切りの直前の数字は必ず前におく、など）してAC。
時刻: 0 件のコメント:
ラベル:

2021年11月3日水曜日

AtCoder Regular Contest 127

　AB二完でレートを落とす。

　コンテスト終盤、Eのサンプルが合い、舞い上がって提出したときREが二個返ってきて、焦りに焦ってしまった（指が震え、汗がたくさん）。そのせいで結局通せず。
　こういう時間ギリギリのやつは、最終的にはACできていたことが多いのに、今回は失敗してしまった。まあ、最初二問で時間かかってしまったのもまずいんだけど……。


C - Binary Strings

　解説AC。

　大体、Xが全体の半分以上か以下かで、最初の文字が分かりそうだなー、とは思う。
　その解法であっているのだけど、詰めるのはなかなか大変。
　特に、Xが2進法で与えられるということを活用する部分は難しい。

　実装にも苦労した。
　解説通りに実装したつもりだったが、X=0になったかどうかの判定の仕方が分からず困ってしまった。
　立っているbitの個数を持つという方法に気付きどうにかAC。

D - Sum of Min of Xor

　解説AC。
　なかなか解説が理解できず苦労したが分かってしまえば単純だった。

　xorの問題だし、制約を見ても、桁ごとに考えるのが良さそう。
　最上位の桁について、ABそれぞれのbitが立っている/立っていないの四通りで場合分けできる。それを00、01、10、11の四つで表すことにする。たとえば、Aでビットが立っていて、Bで立っていない場合10で表す。

　この四通りの、何と何でxorを取るかで場合分けして考える。

　この桁で決着がつかないのは、00^00、00^11、11^11、01^01、01^10、10^10のとき。このときは、一つ下の桁を見る再帰を使いたい。このままだと再帰できないようだが、公式解説のように、S=00+11、T=01+10とすると、S内、T内で再帰することができる。

　それ以外、この桁で決着がついた場合は、一番下の桁からこの桁まで、それぞれの桁についてbitが立っているものの個数を調べておけばよい。
　たとえば、01^11ならAの方がBより小さいので、（01のもののうちk桁でAのbitが立っているものの個数）*（01のもののうちk桁でAのbitが立っていないものの個数）+（01のもののうちk桁でAのbitが立っていないものの個数）*（01のもののうちk桁でAのbitが立っているものの個数）に1<<kをかけたもののを加えれば良い。

　個人的には、この、「ある桁で決着がついた場合の処理」では全部の桁を見るというのが分かりづらかった。確かに、そうしても計算量は間に合うのだけど、他では再帰で一桁ずつ見ていくのにこっちでは下の全桁を見て処理するというのは分かりにくい気がする。
時刻: 0 件のコメント:
ラベル:

2021年11月2日火曜日

AtCoder Grand Contest 055

　一問もACできず終了。残り30分ほどでBの解法が分かり、実装、提出してみたがTLE。その後、TLE解消方法に気付くも実装でミスってWAのまま終了。レートは落ちたけど、noSubしなかったのは良かったかなぁ……。


A - ABC Identity

　解法ツイートなどは見たけど、概ね自力でAC。

　文字列を三つに分ける、という解法はコンテスト中から考えていた。最初の1/3のうち、文字数が一番多いものを取ったらどうだろう……いや、それはできないか、などと考えていた。

　大体の気持ちはそれで良いのだが、「一ヶ所の文字数を0にしよう」と考えるのがポイント。

　三か所に分けていて、一ヶ所にAとBとCが含まれるので、計９個消さなくてはいけないが、ある箇所の文字数が0個になったとき、他の二か所も同じ文字数ずつ減ることを考えると、一ヶ所が一文字のみになったとき、他の二か所はその文字以外の二文字以下になっており、あとは二回で全て消せる。
　そこまでは高々四回（＊）で消せるので、これで六回以下になる。

　……ところで、実験するとこれで五回になっているみたい。
　確かにそうなりそうだけれど、証明できない。

B - ABC Supremacy

　ABCを0, 1, 2で置き換え、(S[i] - i) mod 3で考えれば分かりやすい！　と思いついたのは、コンテスト二時間以上経過してから。それも、この問題（類題かと思って見にいったがあまり似ていなかった）の解説の一行目に、「まず入力から1を引きます」と書いてあったため思いつけた模様。

　その後、同じ数字三つ（つまり、元の問題の"ABC", "BCA", "CAB"）は自由に移動できると気付き、残ったものが一致するかどうかで判定すれば良いと気付いたのが30分前あたり。

　そこからコードを書き、ランダムテストし、提出した……が、TLE。

　ちゃんと計算量を見積もっていなかったのですね。焦っていたせいか、なぜか計算量は大丈夫という気持ちになっていました。
　定数倍効率化するコードをいくつか投げ、その後ようやくどういうとき二乗になるかに気付く。これはdequeを使えば計算量改善できる、と気付いたのは終了五分ちょっと前。

　時間が足りないか、と思いつつ書き直して提出したがWA。直せず終了。

　同じ処理を二回やっていたのだけど、二回目のところで初期化忘れをしていたためWAが出ていた……と気付いたのはコンテスト終了後に冷静になってからでした。
時刻: 0 件のコメント:
ラベル:

2021年10月31日日曜日

AtCoder Grand Contest 052

　A一完で、そのAも未証明でした。


A - Long Common Subsequence

　"0"をN個、"1"をN個並べる解法は、問題を見た当初考えた。それで、どんなS+Sに対しても、前半部分から"0"N個を、後半部分から"1"N個を抽出できる。

　その最初や最後に"0"や"1"をつけるという方法も考えたのだけど……。
　S="111000"のときS+S="111000111000"で、
　ANS="0"+"111000"とすると、
　前半で三つの"1"を使ったら、その前に"0"が置けないので無理！　と思ってしまった。が、実は後半で"111000"全て消費できるので、部分列になっていた。

　これに気付かず迷走。Sを元に作る解法を考えてWAを出した後、
　最終的には、"0"*N+"1"*Nの前後に"0"や"1"を付け加えたもの全てに対して、実際に部分列になっているかどうか確かめるコードを書き、なっていたら答えとするものを書いてACした。

　未証明だったけど、長さ2*Nで、部分列になっているものは作れているのだから、2*N+1もそれに近いもののはず！　と、信じられたのは良かったか。

　そこそこ正しそうな方針を思い付いたら、その方針を元に考えた方が良いことが多いと思うので。（全然間違ってたってこともあるんだけど。まあ、そのときは仕方ない）

B - Tree Edges XOR

　解説AC。

　辺に関する条件は扱いにくいので、頂点に関する条件に読み替えられないか？　と考えるのがポイント。

　その後も難しいけど、読み替えができたならいけそう。難しい問題だと、なんとか別の問題に言い換えられないかと考えるのは重要ですね。


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

2021年10月30日土曜日

Codeforces Round #748 (Div. 3)

　pretestは全完。

コンテスト後のツイート



　システムテスト全部通っていたら、ツイート貼り付けただけで記事書かなくても良いかなー、とか思っていたら、D2はWA、FはTLEと二問も落ちてしまった。


　Fは累乗を前計算したらOK。

　D2は、解の上限を見誤っていたためダメで、そこを直したらTLE。約数全列挙で解を絞るという方法でAC。
　ツイートした解法でも速い言語ならいけるかもしれないけど、良い解法ではなかった。
時刻: 0 件のコメント:
ラベル:

Educational Codeforces Round 116 (Rated for Div. 2)

 　Cまで三完。


E. Arena

　ツイッターでDPの定義を見てAC。

・DP[i][j]=残りi人で、残った一人の最大値がjのとき一人だけが勝つ場合の数、とする。

　答えは、DP[n][1...x]を全体から引いたもの。

　遷移は、最大値がi-1だけ減るので、そのとき何人いなくなるかで場合分け。k人いなくなるなら、pow(i-1, k)*Combi(i, k)を掛ける。

　計算量は三乗だと思うけど、定数倍が小さくなるのでOK。

　DPを疑うのは自然だし、分かってしまえばDPの定義も自然に思えるけど、思いつけなかったね……。
時刻: 0 件のコメント:
ラベル:

2021年10月29日金曜日

技術室奥プログラミングコンテスト#6 Day1

 　EまでとH、Jの七完。

F - Frog and Tadpole

　自力AC。

　xマスにいたカエルがyマスへジャンプするとする。このとき、x+1～y-1にあるマスは、白マスでも黒マスでも良い。

　なので、マスiまでたどりつく場合の数をDP[i]とする（つまりDP[N]が答え）と、

・DP[y]=DP[y-1]+2*DP[y-2]+...2^(y-x-1)*DP[x]

　となる。
　このままだと二乗の計算量だが、累積和を使って高速化すると間に合う。

G - At Most Two

　最長共通部分列 (LCS)は二次元DPにより求められる（たとえば、この解説）。
　だが、実質的に値が変わるのは、A[i]とB[j]で同じ値が含まれる箇所のみ。

　B[j]と一致するのがA[k]とA[l]のとき、
　DP[k][j]=DP[k-1][j-1]+1, DP[k][l]=DP[k-1][l-1]+1
　と変更されうるのは二か所のみ。

　他のxについて、DP[x][j]は、DP[x][j-1]と一致している。
　なので、区間最大値を取得できるセグメント木を使ったDPで更新していける。

　……と、文字で書くとこんな感じだけど、二次元の絵を描かないと分からないと思う。LCSは二次元DPだから、今回もとりあえずその絵を描いてみる、というのが重要。

I - 1<->k

　解説AC。
　コンテスト中なら、実験エスパーを目指すのが最善だろうけど、なぜか実験していなかったよう。

　解説二行目、「中国剰余定理よりf(n)は乗法的関数」というところがなかなか理解できなかったので、そこを埋めておきます。

　中国剰余定理（参考）は、

　p, qを互いに素な生整数としたとき、任意のa, bについて、

・x=a (mod p)
・x=b (mod q)

　を満たす整数xが[0, p*q)　にただ一つ存在する。

　というもの。

　この定理で、a=b=1の場合を考えると、x=1は「x=1 (mod p), x=1(mod q)」を満たすので、

・x=1 (mod p), x=1(mod q)　を満たすのはmod p*qでは x=1 のみ（*）

　と分かります。

　ここで、

・y^2=1 (mod p)
・z^2=1 (mod q)

　となるy, zを考えます。中国剰余定理を使うと、

・x=y (mod p)
・x=z (mod q)

　となるxが[0, p*q)　にただ一つ存在しますが、x^2=1 (mod p)、x^2=1 (mod q)なので、（*）より、x^2=1 (mod p*q)　と分かります。

　長くなってしまったけど、こんな感じで良いはず。ここを乗り越えれば、その後の解説は追えるはずです。

K - Dial Key

　解説AC。

　自分では、

　各要素について、「区間に+1/-1」した後、「ある要素に+1/-1」を用いて調整するしかない。ので、一つ前の要素について「区間に+1/-1」でいくつへ変更したか？　を持ってDPすれば良い。

　……みたいなことを考えていたが、これではダメ。先の方まで区間を使った後、前の部分を処理することがある。

　正しくは、「区間へ+1する処理」→「区間の前と後の二か所で差が変わる」と考えるのがポイント。これは典型の一つなのに思いつかなかった。反省。
　ただ、その後貪欲にやって良いというのもピンと来なかったので、自力ACは結構遠かったかな。
時刻: 0 件のコメント:
ラベル:

2021年10月27日水曜日

サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）

　Eまで五完。


F - Cleaning Robot

　解説放送を聞いてAC。
　方針が思いつけなかったけど、

　文字列一回で移動する量(x, y)が重要そう　→　(x, y)の何回かの移動で一致するものをひとまとめにして考えよう

　というのは結構自然に思える。

　理解できた後も、「どうしてこんな解法思いつくんだろう？」みたいな問題は仕方ないけど、分かってしまえば簡単、のような問題には食らいつきたいね。

G - Propagation

　平方分割と言われれば解ける。
　しかし、平方分割に気付けなかったのは問題。類題経験もあったのに。
時刻: 0 件のコメント:
ラベル: ,

2021年10月22日金曜日

AtCoder Beginner Contest 221

　Fまで六完でした。


G - Jumping sequence

　解説放送を聞いてAC。

　45度回転すればx軸、y軸を独立に考えることができ、部分和問題に帰着できる。

　マンハッタン距離を扱うときに45度回転はよく登場するけれど、こういう風に使うことがあるとは知らなかった。

　bitset高速化の方針でACしたけれど、MLEなども気を付けねばならず結構大変だった。

　解説放送後半にある、部分和問題のもっと計算量の良い解法はこれから理解したい。→解法は一応理解したけど、実装が大変そうなので放置します。

H - Count Multiset

　解説放送を聞いてAC。

　ヤング図形との対応に気付けばDPへ持ち込むことはそれほど難しくなさそう。
　また、分割数と似ていると思えれば、（分割数の求め方を知っていれば）ヤング図形との対応を考えるのは自然だった。

　というわけで、「写像12相」をちゃんと理解していれば解ける問題、と言えそうだけど、ちゃんと理解するのは結構大変。

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

2021年10月18日月曜日

大和証券プログラミングコンテスト2021（AtCoder Regular Contest 128）

　Cまで三完。橙パフォで2100復帰。ただ、Cまでがたまたま速く見えただけで、一時間以上残せたのにD以降の難しい問題に手が届いていないのは悲しい。

コンテスト後のツイート


D - Neq Neq

　解説AC。
　前半の考察部分と、後半、それをDPにする部分、どちらもすごく難しいというわけではないのだけど、結構考えにくい。
　コンテスト中、一時間以上時間を使ったけど、考察も正確ではなかった。

　まず、

・「1 1 1」のように同じ数字が連続する場合は全部残すしかない。

　ことには気付く。そして、

・「1 2 1 2 1 2 1 2」のように二つの数字が繰り返される場合、その間二個の数字を両方消すことはできない

　かと思ったが、それは間違い。「1 2 1 2 1 2 3」なら、右から順番に消していけば「1 3」まで消すことができる。
　とは気付いたのだけど、二番目の内容を正確に記述することができなかった。
　公式解説の通りで、

・種類数が2で長さが4以上のとき、両端を残して間を消すことはできない

　と記述できる。
　言われればなるほど、という感じだけど、正しく分かっていたかは疑問……。


　さて、それをDPに直すところも難しい。私は、公式解説のdp[i]の定義が分からず困ってしまった。
　ここでは、

・DP0[i]=i番目のボールを残したときの（i番目までの）場合の数
・DP1[i]=i番目のボールを除いたときの（i番目までの）場合の数

　とする。
　一番初めのボールは残すしかないので、DP0[0]=1、DP1[0]=0。
　また、特に制約がなく、残すことも除くこともできる場合は、DP0[i]=DP1[i]=DP0[i-1]+DP1[i-1]となる。また、同じ数字が連続する部分では、DP1[i]=0となる。

　あとは、「種類数が2で長さが4以上」の条件について考える。

　たとえば、

・A=[1, 2, 1, 2, 1, 2, 1]

　のとき、

DP0=[1, 1, 2, 3, 5, 8, 13]
DP1=[0, 1, 2, 4, 7, 12, 20]

　となる。
　これは、DP0[i]=DP0[i-1]+DP1[i-1]から、ダメな場合を除く、と考えると求められる。

　たとえば、DP0[3]=3は、DP0[2]+DP1[2]=4からDP0[0]を除いている。このとき除いているのは、「1, _, _, 2」と、間にある二つを取り除いた場合だ。

　同様に、DP0[4]=5は、DP0[4]+DP1[4]=7から、DP0[0]とDP0[1]を除いている。それぞれ「1, _, _, _, 2」と、「?, 2, _, _ ,1」に対応している。
　DP0[5]=8は、DP0[5]+DP1[5]=12から、DP0[0]とDP0[1]とDP0[2]を除いている。

　こんな感じでDP0とDP1を求められる。
　あとは、DP0に関する累積和を考えると、O(N)になる。
時刻: 0 件のコメント:
ラベル:

2021年10月16日土曜日

yukicoder contest 318

　A一問解いて、Bを考えているうちに意識が……。


No.1708 Quality of Contest

　コンテスト後、自力AC。
　思いついてしまえば当たり前に思える解法なのに、なかなか思いつけなかった。

　ただソートするだけの解法を考えて、それと比較すれば正しい解法が分かった。

No.1709 Indistinguishable by MEX

　解説（というか、解法ツイートを見て）AC。
　mexの値を小さい方から見る、というのは自然ですね。
　これを思い付けなかったのは良くない。
時刻: 0 件のコメント:
ラベル:

2021年10月9日土曜日

yukicoder contest 317

　ABCEGの五完で終了。
　今回は簡単だったようで、もっと解かなきゃいけなかったみたいだけど、問題文がちょっと分かりにくかったせいもあって厳しかった。（Eが分かりにくいという声が多いみたいだけど、私にはDの方が分からなかった）


No.1702 count good string

　結局読解できなかった。

　正しく読み解くと、

・Sの部分列で、"yukicoder", "?ukicoder", "y?kicoder", ..., "yukicode?"のいずれかとなるものが何個あるか？

　という問題だった。
　一旦分かってしまえば、確かに問題文もそう読めるのだけど、私は「良い部分列のうち Tに含まれる部分列」というのが解釈できなくて止まってしまった。

　サンプルの説明は書いて欲しかったなぁ……。と思うけど、コンテスト中に90人くらいに解かれているのだから、自分の読解力がまずいのでしょう。（とはいえ、読解力ってどうすれば鍛えられるか分かりにくいんだよねぇ）

　題意が読み取れればDPで解けます。

No.1704 Many Bus Stops (easy)

　これは誤読していた。
　1.5秒かけて別のバス停に到着したらまたすぐ動き出すものと思い（ただし、同じバス停に残ったものは1秒後に動き出すのかと考えていた。不思議）、行列累乗だとは思ったものの、遷移を書くのが難しいな……と考えていた。

　うーん、質問の「iは整数」というのも読んだはずなのに、こんな誤読をするのは良くない。

　行列累乗と分かれば、
・バス停xにいるか
・バス停xに向かう途中か
という6状態を考えて行列累乗すればOK。

　さらに、バス停A以外を区別する必要はなく、Aとそれ以外にだけ分ければOKと気付けば（これに気付かず、一回MLEなコードを投げてしまった）、hardの方も解ける。
時刻: 0 件のコメント:
ラベル:

Kotlin Heroes: Episode 8

　Eまで五完で終了。Kotlin Heroes以外ではほとんど書いてはいないけど、Kotlinはそこそこ書けるつもり。なのに、前半の問題で解くスピードがかなり遅いのは、書き慣れていないということなのかなぁ。
　このコンテストで50位以内に入ることは目標の一つなのだけど、今回は掠りもしなかった。


F. Kotlinforces

　制約が本質の問題。

　$t_i$が1か2ということに気付かないと始まらないが、コンテスト中はそこまでに結構時間がかかってしまった。

　$t_i$が1のやつは端から詰めれば良いので、$t_i$が2のやつについて考える。

　$t_i$が2のやつは、
・偶数番目の端から詰める
・奇数番目の端から詰める
　の二通り考えなくてはいけない。どちらかが最適となる。

　これは、二次元DPでDP[i][j]で、偶数番目が残りi個、奇数番目は残りj個、とやればできるが、これだとTLE。（コンテスト中、ここまで考えた）

　だが、よく考えると高速化できる。
　それまで何文字使ったかは分かるので、偶数番目が残りi個のとき、奇数番目が何個使ったかは、「奇数番目の個数 - 偶数番目に今まで使った個数」で求めることができるのだ。
　これで一次元のDPになり、計算量は二乗になる。

　そして、DPした後、DPの復元を行うことで答えが求められる。

　DPの復元パートもあるし、そこそこ実装が面倒で、コンテスト後ACするまでには結構時間がかかってしまったけど、もっと楽に書く方法はあるんだろうか。

　


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

2021年10月2日土曜日

yukicoder contest 316

　（途中で休憩してしまったけど）Bまで二完で終了。


No.1694 ZerOne

　解説AC。

　01と10を入れ替える問題になることには気付いたが、そこから進まなかった。一つの01, 10は一回しか動かないのかな？　と思ってDPを書いたけど、そんなことはない。

　01と10が入れ替わるということは、片方の1のindexが1増え、もう片方は1減る、ということなので、各1のindexの和の合計が不変量になるのがポイント。

　これは気付きたかったね……。
時刻: 0 件のコメント:
ラベル:

2021年9月29日水曜日

Codeforces Round #744 (Div. 3)

 　pretestはFまで。Gを考えていたら睡魔に襲われてしまった。


コンテスト後のツイート







 

　今更ながらツイートの埋め込み機能を使ってみたけど、見やすいか？　というとどうなんだろう……。

　Eは、E1とE2で別の問題です、と書かれているのに、同じ解法で貪欲に辿り着くというのが面白かった。
　Gは考え方は間違ってなくて、bitsetを使ったら通った。bitset、最近使ってなかったから忘れていた。

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

2021年9月28日火曜日

AtCoder Beginner Contest 220

　Fまで六完。Fは全方位木DPのライブラリを用意していなかったのが良くなかったか。Eは面倒な解法を選んでしまったかと思ったが、良い解法と大差なかったのかな。

コンテストへのリンク

G - Isosceles Trapezium

　解法ツイートを見てAC。
　ポイントは、

・等脚台形は上底と下底の垂直二等分線が一致する。

　ということ。
　思いついても良かった内容ではあるけれど、時間もなかったし仕方ないかなぁ。

　なお、自分は、垂直二等分線を「方向ベクトルとx切片」で表そうとしたが、PythonのFractionモジュールを使ったところ重くなってしまいTLE。
　分数を、mod 10^9+7で表してACした。

　これだと、異なる二つが一致する可能性があるので良くないんだけど、どういう実装が良いのかなぁ。gcdを使うのが普通なのかな。

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

2021年9月25日土曜日

yukicoder contest 314

　最初の二問を見て、30分以上は考えていたはずだけど、分からず眠気に負けてしまった。


No.1680 Sum and Difference

　解説見てもちょっと悩んだけど、解説の方針でAC。

　とりあえず、二変数の問題なんだから、xy平面に描いて考えるべきだった、というのが反省。しかし、それでも解けるようだけど結構難しい。

　解説のように置換して45度回転しても、X=x+y, Y=x-yの偶奇が一致するときにx, yが整数になるというのがそれほど自明に思えなかった。
　偶奇が一致すると分かれば、共に偶数、共に奇数で場合分けして数え上げれば良い。

No.1681 +-*

　解説AC。
　+とｰが打ち消すことは気付いたけど、その後が分からなかった（A[l:r]*係数みたいな形になりそうな気がして、それだと二乗かからない？　とか思っていた）。
　言われてみればという感じではあるけど、結構難しい。


（解かれている人数を見るとDまではACすべきなんだけど……）
時刻: 0 件のコメント:
ラベル:

yukicoder contest 315

　コンテスト中はCまでしか終わらず、コンテスト後に自力でEまで。　
　最初Bが分からなくなってぼーっとしてしまったせいなんだけど、CDEは典型なんだからそっちを見るべきだったよね。こういう感じでやる気をなくすのは良くない。


No.1689 Set Cards

　bit DPが自然だと思う。
　ただ、想定解法は包除原理だった。

　以前も、bit DPで解ける問題の想定が包除原理だった問題を見たことがあったと思う。どちらも部分集合を扱うから当然といえば当然なのかもしれないけど、この二つが結構似ているというのは頭に入れておきたい。
時刻: 0 件のコメント:
ラベル: , ,

2021年9月21日火曜日

Educational Codeforces Round 114 (Rated for Div. 2)

　pretestはDまで。コンテスト終了間際にEの大体の考察はできた。
　システムテストでDがMLEで落ちたけど、setに突っ込むものをtupleからhash(tuple)に変えて通した。（衝突させるテストケースは作れるだろうけど）


E. Coloring

　良い行列の作り方は、

・一行目を決定→n行目はn-1行目の反転
・一列目を決定→n列目はn-1列目の反転

　で全てを網羅できる。また、その方法で作ったものは全て良い行列になる。
　ただし、それだと市松模様が重複するので、その場合を引かないとダメ。

　実装は結構大変なものになってしまった。

・x=3, y=3で1
・x=x, y=5で0

　とかがあると、「一列目を決定→……」の操作では矛盾するので作れないのだけど、そういう、「この操作でやろうとすると矛盾」というのを管理するため、「一列目が1のときと矛盾しないものが何個で、0と矛盾しないもの何個か」を管理する。

　それが矛盾しないときにだけ計算する、という感じでやった。
時刻: 0 件のコメント:
ラベル:

2021年9月15日水曜日

AtCoder Beginner Contest 218

 　Fまで六完。



G - Game on Tree 2

　しばらく解説を見ても理解できなかったが、落ち着いて考えたら理解でき、AC。

　コンテスト中は、中央値を求めるのだから答え二分探索だろう！　と、飛びついてしまったのがダメだった。この方針（x以上のものを1, それ以外を-1として木DP）だと「答えがA[i]以上になるか？」という判定はできるが、(A[i]+A[j])/2となる場合の処理が上手くいかない（と思う、多分。）

　なので、考え方を変える。

　木の葉それぞれについて、「そこにたどりついたときの中央値」が求まれば、後は木DPで答えを求められる。
　で、実はこれはオイラーツアー（DFS順）みたいなことをしながらBIT上の二分探索をすることで求めることはできる。


　なお、$10^5$回くらいなら間に合うだろうとDFS部分を再帰で書いたら、PyPyだとTLEして、PythonでACできました。やっぱりPyPyの再帰は遅いなぁ。

H - Red and Blue Lamps

　解説AC。

　凸性を理解するため勉強しようと思って解説を見たのに、貪欲で解けるということでそれでACしてしまった。
　（貪欲解は）難しいけどなるほど、という感じ。
時刻: 0 件のコメント:
ラベル:

2021年9月9日木曜日

Educational Codeforces Round 113 (Rated for Div. 2)

　Dまで四完でした。


E. Playoff Restoration

　半分全列挙。
　半分全列挙は疑ったのに、半分に分けても混ぜることができない気がしてしまった。

　実際は、$\sum{ i \cdot A^{p_i}}$　がハッシュなので、各$A^{p_i}$ごとにindexの総和さえ分かればよく、それならぐっと数が減るので半分全列挙が機能します。

　……と、納得してツイートしたらmaspyさんに不要だと指摘されました。（指摘ありがとうございます）

　Sample1で考えてみます。
　決勝で勝つか負けるかは考えずに半分全列挙をし、勝った場合負けた場合、それぞれについてハッシュ値を求めると、前半については、

・[5, 3, 5, 2]のときのハッシュ値
・[5, 3, 5, 1]のときのハッシュ値

　が分かっています。（こうやって列挙する数は$k=5$のとき、$2^15$個）

　この、[5, 3, 5, 2]に対応する後半のハッシュがあるかを調べるためには、

・h（問題文で与えられたハッシュ値）- [5, 3, 5, 2]のときのハッシュ値

　なるハッシュ値を取るものが後半の列挙した中で、かつ二位ではなく一位を使うものの中に存在すれば良いです。

　これ、ハッシュが和として定義されているから、半分のハッシュの和が分かれば残り半分は全体から引くことで求められる……と、当たり前なのだけれど、半分全列挙で上手くできるのはこの性質のおかげで、私が躓いたのはこの部分だったかと思う。

　そして、前半と同じように後半も列挙・調査しておけば、これが[1, 5, 5, 3]に対応しているということが分かります。

　シンプルな半分全列挙で、ナップザック問題の半分全列挙のように、ソートして二分探索（もしくは尺取り）というようなことも必要ない。

　半分全列挙というキーワードを思い付いたのなら、解けなくてはいけない問題でした。反省。
時刻: 0 件のコメント:
ラベル: ,

2021年9月4日土曜日

yukicoder contest 312

　Cまで三完でした。


No.1665 quotient replace

　Grundy数を求めてACしたが、素因数の個数を考えることでNIMに帰着できたのね。なるほど。

No.1666 累乗数

　解説AC。
　二つ目の方法でやりました。二乗の個数が他の累乗の個数より多いことには気付いていたのに、こういう方法に思いつかなかったのはまずい。

　約数包除での方法も理解しました。コンテスト中は、素数ベキに絞ってやることを考えていた。そこから約数包除は遠いような近いような。

No.1667 Forest

　解説AC。
　コンテスト中あまり考えなかったため解けなかったのは仕方ないけど、解説を見てすぐピンと来ないのは良くない。

・重複を除くため、残っている頂点のうち一番小さいものを何と組み合わせるかを考える
・ケイリーの公式

　この二つをちゃんと理解していれば解けたはずだし、どちらもそれほど特別な手法ではなかった。


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

2021年9月3日金曜日

CodeCraft-21 and Codeforces Round #711 (Div. 2)

 　Eまで五完。時間ギリギリで通ったのは嬉しい！


F. Christmas Game

　解説AC。

　公式解説が分かりやすかった。
　こういう問題だとNIMに帰着するのは定石とはいえ、なかなか面白かった。

　が、解説では実装がよく分からず、全方位木DPだよね？　と思ったらそう書いているツイートを見つけた。

　今回は逆元がある全方位木DPということで、実装はそれほど大変ではなかった。
　が、全方位木DPで得た配列の添え字のどこからどこまでを使うかで混乱、結局時間がかかってしまった。

　上手く書けたら全方位木DPのライブラリにしようと思って書き始めたのだけど、（まあまあ上手く書けた方かとは思うものの）結局遷移式とか添え字とかを考えるところが大変だからライブラリ化してもなぁ、という気持ちになったのでライブラリ化は見送りかなぁ。

　全方位木DPは二回DFSをやることになるわけだけど、一回目のDFSを書いたら二回目は書かなくていいようにライブラリ化したい。
　今回みたいに、DP配列の中身が配列の場合にも対応できるようにライブラリ化できるはずだよね。また今度やります。（先送りして良いのだろうか）
時刻: 0 件のコメント:
ラベル: ,

2021年9月2日木曜日

灘中入試コンテストday2

　Cまで三完でした。


No.1353 Limited Sequence

　解説AC。

　まず三つ目の条件を正しく理解することが重要。

・各ｉ( 1 <=ｉ<= N ) について、i が（A_i＋１）個以上連続してはいけない

　という意味です。（コンテスト中はこれを解釈できずに飛ばしてしまった記憶が……）

　これさえ分かれば、

・同じ数字を付け加えるときは一気に付け加えれば良さそう

　と思えるので、それを利用してDPできます。
　問題を正しく理解できれば、そこまで難しくなかったか……。

No.1354 Sambo's Treasure

　fairly_lettuceさんの解説が分かりやすかった。
　考察が難しい問題ではないけど、包除原理のとき何を除けばいいかというあたりで混乱してしまった。順番が確定しているので、包除原理といっても$(-1)^N$をかけたりする必要がない、というのがポイントか。

　というわけで、理解したので実装してみようか、と思って書いたらかなり苦戦した。こういうのをさくっと実装できるようになるにあどうしたら良いのかなぁ。

No.1355 AND OR GAME

　解説AC。

　後ろから見るという発想はあったが、Pが分かっても、操作前のYが一意に決まらないためダメだと思ってしまった。分からないbitは分からないままにして計算すれば良かったのか。
時刻: 0 件のコメント:
ラベル:

2021年9月1日水曜日

AtCoder Beginner Contest 214

 　Fまで六完でした。GとHは解法にかすりもしていなかった。要復習。


G - Three Permutations

　snukeさんの解説放送を見てAC。
　えー、難し過ぎませんか？　ステップ数が多いし、一つ一つのステップが重い。今は理解できているけど、もう一度まっさらな状態から解けと言われると結構厳しい気がしてしまう……。

　以下、（提出コードにも書いたけおｄ）snukeさんの解説放送を聞いたメモ。
 
　順列→グラフの問題と考える。
　二つの順列から、サイクルの集合と考える。
　各辺について、両端の頂点以外のものを書き込むと考える。
 
　辺を、
・〇（両端以外を書き込むもの）
・×（両端のいずれかを書き込むもの）
・？（上記どちらでも良い）
　の三つに分ける。
 
　〇は扱いにくいので、包除原理を使う。
 
　2^N通りのうち、×の箇所を決め打つと、
　各連結成分について考えることで答えを求めることができる。
 
　×の個数でDPする。
　DP[i][j] = iまで見て×がj個のときの場合の数　とする。
 
　各サイクルごとにDPする。
　辺を順々に見ていき、「直前の頂点を使ったか？」をflagに持つ。
　サイクルなので、最初の辺については二通り試す。

H - Collecting

　解説放送を聞いてAC。
　問題を見ても全くフローに思えなかったのでどうしようもないが、最小費用流と言われればなるほど、と思えた。Kが小さいのも、「フローを流す回数が小さい」と考えれば確かに、と。

　ただ、
・コストが負の辺があるので、それを解消する工夫が必要
・自分のフローライブラリが遅い

　ため、その後も非常に苦労した。
　一点目については、snukeさんの記事も理解しておきたいが、なかなか難しい……。

　二点目については、毎回距離を初期化して一からダイクストラしているのがまずい気がする。使い回せるところは使い回と高速化できそうな気がするが、よく分かっていない。
時刻: 0 件のコメント:
ラベル: ,

2021年8月28日土曜日

yukicoder contest 311

　AB二完で終了。Cを考えていたら睡魔に誘われてしまった。


No.1658 Product / Sum

　解説AC。
　1でない個数を二個にして式変形してみると、解ける。

　解法を理解してから見ると、サンプル1が良い誘導になっているのが分かる。二変数にすれば良いんだ、と。

　コンテスト中は、一変数にしなくては厳しい気がして悩んでいた。
　サンプル1で、10*10 / (2*10) = 5 という式が見えてしまったのが良くなかったか。一般にはN = 2でA1 = A2のとき上手くいくとは限らないのは分かったけど、この式から変形してどうにかするのか、と。
　詰まったら別の方針を考えないとね。

No.1659 Product of Divisors

　コンテスト後、自力で解けた。
　が、公式解説で二項係数でやっているところを思いつかず、DP＋行列累乗で解いてしまった。

・DP[i] = pに関する指数が残りi個のときの場合の数

　として、そこから各dに何個振り分けるか？　というのをK回行った。

　まあNが小さいからこの解法で問題ないけど、最初二項係数でできるのでは？　と疑ったのに、解法を思い付けなかったのは良くない。
時刻: 0 件のコメント:
ラベル:

2021年8月27日金曜日

Codeforces Round #741 (Div. 2)

　途中寝かけたせいもあり、D1まででした。 


D2. Two Hundred Twenty One (hard version)

　D1で、さらに取り除くindexを指定するもの。
　D1で（証明しなかったけど）偶奇さえあっていれば答えが得られた。ということは、ある区間の長さが奇数ならば、一つ削除することで全体を0にすることができる。なので、区間が偶数で0でない場合は、どこでも一つ削除してから考えて良い。

　あとは、立式することが重要。区間[l : r]からxを削除するとすると、Sを累積和として、

・S[l : x-1]+S[x]+S[x+1 : r]＝S[l : r]=kとする
・S[l : x-1]-S[x+1 : r]=0

　となれば良いので、計算すると、

・A[x]=1のときS[l : x]=k/2+1
・A[x]=-1のときS[l : x]=k/2-1

　となれば良いと分かる。

　なので、Sが条件を満たすもののうち、区間[l, r]に含まれるものを探せば良い。これは二分探索を使えばOK。


　なお、コンテスト終了間際に大体この考察には至っていたのだけど、その後ずっとACできなかったのは、「区間[l, r]に含まれるものを探す」という条件を忘れていたせいでした。[l, r]に含まれないものを出力して、なんでWAなんだろう……とずっと考えていた。ひどい。
時刻: 0 件のコメント:
ラベル: ,

2021年8月25日水曜日

Codeforces Round #740 (Div. 1, based on VK Cup 2021 - Final (Engine))

　ACの二完でした。Bは惜しくなかった。Dの方が惜しかったのかも？（ACしていないのではっきりしたことは言えないが）


B. Up the Strip

　DP[x]がどこから足されるかを考える。
　引き算については、DP[1]～DP[x-1]の和を足し込めば良い。これは累積和でOK。

　割り算について。まず思いつくのは、$\sqrt{x}$で分ける方法だと思う。

　DP[x/1], DP[x/2], ... , DP[x/$\sqrt{x}$]はそのまま計算、$\sqrt{x}$より大きい数で割る場合は、それぞれの商について何個ずつかを求める。

　コンテスト中はこの方法しか思いつかなかった。
　これで、Div. 2の部分点はもらえるが、Div. 1では点数にならない。

　約数に注目するのが重要。

・(x-1)/yとx/yの整数部分の値が変わるのは、x/yが割り切れるとき

　ということに注目する。これを考えると、xの約数についてだけ、変化分がどれだけ増加するかを調べていけば良い、と分かる。
　が、これでも間に合わない（MLEになるはず）。

　そこで、発想の逆転。約数を考えていたところを倍数で処理できないか考える。
　DP[x-1]だった増加量がDP[x]に増えるのは、xの倍数のところである。それを利用し、xの倍数のところに、その増加量の変化を書き込んでいく。これなら、MLEを回避できる。
時刻: 0 件のコメント:
ラベル:

2021年8月24日火曜日

AtCoder Regular Contest 125

　Cまで三完でした。レートはやや下がったけど、ABで詰まって動揺してしまってもCを通せた、というのは良かった。


D - Unique Subsequence

　解説AC。
　制約からDPを使いそうなこと、一意な部分列を得たいので、部分列DPみたいな考え方をしそうなことも分かる。
　だがそこから考察を進められなかった。

　そこから、公式解説に書いてある必要十分条件に至る部分は、どうにかして考察してたどりつかねばいけないように思う。難しいけれど、時間かければ思いつけた気もするし、どうだろう……。

　その後の実装はDPなのだけど、各数字について「その数字がでてきたindexたち」をメモしながら進めていくことがポイントか。
　そうやって実装したものを、Binary Indexed Tree で高速化すれば良い。
時刻: 0 件のコメント:
ラベル:

2021年8月22日日曜日

TopCoder Single Round Match 811

　Easy, Medの二問解けて黄色に復帰。
　Easyはあまりにも簡単で驚いたが、他の人がすぐ提出しているのを確認して、提出。


Div1 Med SmoothDivisors 

　ちょっと実験したら、各素数について、その素数を因数に持つ約数が最低三つあればOKそう、と分かった。ので、p, qを素数としてp*q, p*p*qのときのみダメだろう、と。ちゃんとした証明はできてないけど、まあそうだろう、という気持ちで実装へ。

　ただ、Pythonでは間に合いそうにないので、C++を書くのに戸惑ってしまった。
　でもまあ、遅かったとはいえ、C++でちゃんとACできたこと自体が少ないので、ACできたことを喜ぼう。


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

2021年8月21日土曜日

yukicoder contest 310

 　A一完で終了。Aの後Dを考えていたけど、思いつかず、途中で考える気力が……。


No.1653 Squarefree

　解説ACしました。

　エラトステネスの篩の応用のようことしか使っていないので、解説を理解するのは難しくない。けど、こういう力任せ（？）のような方法はコンテスト中は考えられなかった。
　シンプルな問題だけに、もっと綺麗な（数学的な）方法がある気がしてしまった。

　強引にでも解いてやろう！　という気持ちになればこの方法を思い付くのはそこまで難しくない気もする（どこまで素数を列挙するべきか？　とか計算量まで分かるのは難しいかもしれないけど、できる限り列挙しておこう、みたいな気持ちでやるなら）。根性が足りなかった。
時刻: 0 件のコメント:
ラベル:

2021年8月20日金曜日

AtCoder Beginner Contest 213

 　Eまで五完。


FはSA-ISを書かないとACできない。SA-ISを理解していないため後回し……。

G - Connectivity 2

　解説放送を聞いてAC。
　$3^N$のDPなのだけど、そこがポイントではなく、

・DP[S]=S内の辺についてみたとき、Sが連結になる場合の数

　とおいて上手くいくと気付くのが重要。

　こうおいてDPが回るというのも意外だし、これを使って答えが求められるというのもなかなか思いつかないし理解し辛い。

　なお、解説放送ではこれを使って答えをどう表すか、ということは前半の解説部分で話しておらずコードを書くところでそれに触れている。
　私は前半を見て理解したつもりになってコードを書きだしたもののそこで詰まり、結局解説放送後半部分も見ることになってしまった。DPの遷移と大体同じ考え方なのに、ピンと来なかったんだよねぇ……。

　ただ、こんな風に重複なく数える、というのは、部分文字列を走査するDPと考え方としては似ているか。
　重複なく数えるために「1と連結なもっとも小さい集合を見る」というのは、部分文字列を走査するDPで「次に現れる文字のうち一番近い文字を見る」というのと対応しているのだと思う。

H - Stroll

　解説放送を聞いてAC。
　分割統治FFTというのはこういう処理なのですね。

　解説放送では自己ループのみがある場合で説明しているため、道がたくさんある場合でどうすれば良いかちょっと戸惑ったが、各道ごとに同じ処理を行えば良いということで納得した。

　なお、再帰で通常通り書いたらTLEしたため、他の人のコードのFFTの実装を見たら、配列の長さが小さい場合は直接計算しているようだったので、（FFTのライブラリ自体は書き換えずにDPの遷移の処理を）配列の長さで場合分けしたらACできた。

　FFTライブラリ自体を書き換えた方が後々のためには良いのだろうけど、どれくらいで分けるのが良いのだろう。AtCoderのライブラリでは、「畳み込む配列のうち小さい方が60以下かどうか」で場合分けしてそうだけど、自分の実装でもこれが良いのだろうか。
時刻: 0 件のコメント:
ラベル: , ,

2021年8月19日木曜日

Codeforces Round #739 (Div. 3)

 　Eが解けずに終了。


E. Polycarp and String Transformation

　正しい解法は、

・後ろから見ると消した順番が分かる
・消した順番を利用すると、最初にあった各文字の個数が分かる。それを使うと、最初の文字が復元できる
・あとは十分性のチェック

　第一ステップの「後ろから見る」を思い付けなかった。

　前からでもできそうな気がしてしまうと、なかなか後ろから見よう、と思えなくなってしまう。ただ、前からやると普通は二乗かかりそう、というところで、考え直さなくてはいけなかった。
時刻: 0 件のコメント:
ラベル: ,

2021年8月18日水曜日

AtCoder Beginner Contest 212

　Eまで五完。


F - Greedy Takahashi

　解説動画を見てAC。
　コンテスト中はGの方が解かれていたため飛ばしてしまったが、発想が難しい問題ではなかった。

　ただ、実装は結構しんどいね。
　あまり綺麗な実装を思い付けず、添え字でもミスってしまった。他の方のコードを見てこういう実装も勉強すべきかなぁ。

　→　ダブリング解法だと実装がある程度大変になるのは仕方なさそう。
　

G - Power Pair

　解説AC。
　解説の論理は理解でき、ACはした。が、しっくりきてないので解説動画を見たい。

　→　結構すっきりしました。

H - Nim Counting

　すぬけさんの解説動画を見てAC。
　ただ、アダマール変換については理解できていない……。

　とりあえず、

・愚直なDPによる解法
・xor畳み込みにより高速化できる
・アダマール変換の線形性を利用すると、等比数列の積の公式などを利用して計算できる。（線形性の証明は分かってないけど、定義から成り立ちそうな気はした）

　というあたりは分かった。

　分かっていないのはアダマール変換の部分。
　一桁の場合は解説動画通りなので分かるけれど、二桁・三桁に拡張していくというところがよく分からない。拡張するとどうしてこういう式になるんだろう……。

　いまだにFFTもピンと来てないし、畳み込みを理解するためにどうにかしないといけないんだよね。私でも理解できるような資料はないものか。
時刻: 0 件のコメント:
ラベル: , ,

2021年8月6日金曜日

yukicoder contest 308

　全完でした。 yukicoderは（難しい問題が出るとそこで寝てしまったりするため）最近ひどい成績ばかりだったのでできて嬉しい。


　ちょっと感想を。

　EもFもそんなに簡単とは思わないのに、こんなに解かれるんだなぁ、と驚きました。
　私には、Eは類題を知らなければ厳しかった気がしますし、FはHL分解のライブラリを持っていなければ厳しかった気がします。

　ただ、Fはオイラーツアーでもいけるらしいですね。それはちょっと考えたのですが、上手くいかない気がしてやめてしまった。オイラーツアーにはやや苦手意識があり、今回も気付けなかった（まだよく分かっていない）のは反省です。
時刻: 0 件のコメント:
ラベル:

2021年8月5日木曜日

2021 TCO Algo Regional Qualification 1

 　Easyで誤読＆実装方針をミス、解けたと思ったMedはシステムテストで落ちて0完。青に落ちてしまった。


OlympicShooting

　これは読解＆実装問題。
・スコアの合計が高い方が勝ち
・同じなら、後ろから順に、25回ずつのスコアが高い方が勝ち。
・それも同じなら、より後でスコア獲得した方が勝ち。

　というのを実装する。

　最初、「25回ずつ」というのを読み飛ばして戸惑った。
　その後、上手い実装がないかと考えていたのが失敗（とはいえ、短くコードをまとめている人もいた）。多少時間がかかっても愚直に書けば良かった。

TreeTokens

　解法はすぐに分かり、それであっていたが実装でミスしてしまった。

　ROOTに駒がこないためには、ROOTの隣は1個しかあってはダメ。じゃあ、その隣は、というと、3個までしかあってはダメ。その隣は7個まで。さらにその隣は15個まで。

　つまり、ある頂点の駒が高々i個になるためには、その隣の頂点での駒は高々2*i+1個であれば良い。問題が直線状で、ROOTが端にあれば、N＝（頂点数-1）として、2^N-1個が答えになる。

　では分岐があったときは？　というと、葉が深い方の枝に駒を増やしていく（2*i+1倍していく）のが最善。もう一つの分岐は、駒1個からまた増やしていく。

　そういう感じで、各頂点について「葉までの距離のmax」を前計算した後、ROOTの方がから木DPをしていく感じに解いた。

　……のだが、「葉までの距離のmax」の前計算する箇所で間違えた。
　これはよくある木DPなので、トポロジカルソートの逆順に見ていけば良いのだが、なぜかDFSみたいにしてしまっていた。

　焦っていたとはいえ良くない間違いでした。

　システムテストを通ったコードです。
  
mod=1000000007

class TreeTokens ():
    def placeMax(self, N, G, L, seed):
        state = seed
        E=[[] for i in range(N)]
        for i in range(1,N):
            state = (state * 1103515245 + 12345) % (1<<31)
            tmp = (state // 1000) % L
            p = max(0, i-1-tmp)

            E[i].append(p)
            E[p].append(i)

        #print(E)

        ROOT=G

        QUE=[ROOT] 
        Parent=[-1]*(N+1)
        Parent[ROOT]=N # ROOTの親を定めておく.
        TOP_SORT=[] # トポロジカルソート

        while QUE: # トポロジカルソートと同時に親を見つける
            x=QUE.pop()
            TOP_SORT.append(x)
            for to in E[x]:
                if Parent[to]==-1:
                    Parent[to]=x
                    QUE.append(to)


        CC=[-1]*N

        for x in TOP_SORT[::-1][:-1]:
            if CC[x]==-1:
                CC[x]=1
            if Parent[x]==ROOT:
                continue
            CC[Parent[x]]=max(CC[Parent[x]],CC[x]+1)



        AC=[0]*N
        AC[ROOT]=0
        
        ANS=0

        QUE=[ROOT]
        while QUE:
            x=QUE.pop()

            MAX=-1
            if len(E[x])==1 and x!=ROOT:
                ANS+=AC[x]
                ANS%=mod
                
            for to in E[x]:
                if to==Parent[x]:
                    continue
                MAX=max(CC[to],MAX)

            USE=0
            for to in E[x]:
                if to==Parent[x]:
                    continue
                
                if CC[to]==MAX and USE==0:
                    USE=1
                    AC[to]=(AC[x]*2+1)%mod
                else:
                    AC[to]=1

                QUE.append(to)
                
        return ANS%mod
時刻: 0 件のコメント:
ラベル:

2021年7月31日土曜日

Educational Codeforces Round 112 (Rated for Div. 2)

 　pretestはDまで四完でした。


E. Boring Segments

　解法ツイートを見てAC。

・コストの絶対値を小さくしたい→コストでソートして最小コストを決め打ったときに最大コストがいくらあれば良いかを調べたい→尺取り
・その際、どこからどこまで行けるか？　を遅延セグメント木を用いて管理すれば、ゴールまでたどりつけるかを判定できる。

　解法を見ればシンプルなのだけど、コストでソートする発想が浮かばなかった。
　最初、道の左端でソートして上手くいく気がしてしまい、それでダメだと分かった後も発想を転換できなかった。
　コストの最小値を決めて最大値を二分探索して判定問題、とは考えたのだから、尺取りも思い浮かんで良かったはずなのに……。（今回は尺取りだとできるけど、二分探索では上手くできなそうですね）

　ただ、コストのMAX-MINを最小化したいのだから、コストでソートして尺取り、というのは結構自然。それさえ思いつけば、遅延セグ木を使うやり方にたどりつくのは困難ではなさそう。
時刻: 0 件のコメント:
ラベル:

2021年7月30日金曜日

Codeforces Round #735 (Div. 2)

　Cが分からなかった。


C. Mikasa

　koboshiさんの解説が分かりやすかった。

・とりあえず立式をすると、x xor n >m　を満たす最小のxを求めれば良いと分かる。
・上の桁から確定させていく。

　の２ステップ。
　コンテスト中、どちらも考えたはずなのに、解法にたどりつけなかった。

　多分、立式した式を明示的に書かなかったのが良くなかった。
　ちゃんと紙に書き、どういう風に求めれば良いか、具体例（たとえばサンプルの最後のもの）を桁ごとに書けば分かったんじゃないだろうか。
　手間を惜しんではダメ。
時刻: 0 件のコメント:
ラベル:

2021年7月29日木曜日

AtCoder Beginner Contest 210

 　ABCEの四完。Dは結構思いつきにくい気がする。Fは難し過ぎませんか？


D - National Railway

　解説AC。
　難しい！　DPは全く思い浮かばなかった。マンハッタン距離だから、45度回転ばかり考えてたのが敗因か。

F - Coprime Solitaire

　色々解説を読んだけど、主にkyopro_friendsさんの公式解説でAC。

　2-SATに帰着する問題。
　2-SATに帰着できるということは、コンテスト中は思いつかなかったけれど、言われれば確かに、という感じ。少し慣れている人なら思いつけそう。

　だけど、その後の処理は難しすぎませんか？
　累積和を使えば二乗から線形に計算量を落とせる、と。これは思いつける気がしない。
　結構すんなり解けている人もいるようなのだけど、典型テクニックなのだろうか……。

　さらに、データの持ち方が悪いとTLEしたり、再帰を使ったSCCだとTLE+MLEしたりと大変でした。（ので、SCCは借りてACしました）
　非再帰のSCCは実装しないとまずいですね。

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

2021年7月27日火曜日

AtCoder Regular Contest 124

　Cまで三完。


D - Yet Another Sorting Problem

　解説は見たものの、さっとは理解できなかったため、参考にして実験してAC。

　グラフの問題だと思ったし、連結成分に注目するのかな？　とは疑ったものの、確信が持てず捨ててしまった。
　連結成分ごとにサイクルになる、ということに気付いてなかったのは問題。気付けば当たり前だけど、ここが考察の第一歩だったと思う。

　その後の考察はどうすれば良かったか難しい……。

　確かに、「左側/右側だけのサイクル」は「左右両方の側に要素があるサイクル」よりコストがかかるのは分かる。
　具体的には、後者は、連結成分のノード数-1回操作すれば良いが、前者はノード数+1回操作しなくてはいけない。

　ただ、サイクルごとに完結するのではないのが難しい。
　「左側だけのサイクル」と「右側だけのサイクル」が両方あった場合、前者の操作途中で後者の処理をすることにより、後者をノード数-1で済ませられる……というのが本質だった。
　逆に、「左側だけのサイクル」が複数あっても、それぞれの操作が干渉しないため、操作回数を減らすことはできない。
　なので、max(「左側だけのサイクル」の個数, 「右側だけのサイクル」の個数)だけ、操作回数が増えるものがある、ということになる。

　コンテスト中は、「左側だけの連結成分」と「右側だけの連結成分」（コンテスト中は連結成分がサイクルになると気付いてなかったのでこう書いています）が干渉することがある、ということは、連結成分ごとに見る方針は間違っているのでは？　と思ってしまい、考察を進めることができなかった。

　解法を見ても、試行錯誤するしかないかなぁ、という気もするので何を反省すべきか難しい。
　思いつけてない何かがあったというわけではなく、どれが正しい方針か分からなかったという感じだし。

　愚直solverを書いていたら多少違ったかもしれないけれど、決定打にはならなそうだし、どう実装すれば良いかもちょっと迷ってしまう。さっと書けるなら書いていたと思うので。

　うーん。
　書くなら、順列同士で、一回の操作で行けるもの同士にedgeをつけて、ソートされたものからBFSする感じか。これでN+Mが9あたりまでは判定できるなら、実装する価値はあったかも。

（EやFはACしたら追記）

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

2021年7月26日月曜日

AtCoder Beginner Contest 211

　Eまで五完でした。


E - Red Polyomino

　この問題を思い出したので、この解法で解いた。
　ただ、DPしているけど、別に計算量は良くないね。
　解いているとき、Kの制約をあまり見ていなかったのだけど、たとえばN=8, K=32ならTLEするので、この解法で解く意味はあまりなかったよう。
　ただ、コンテスト中、全探索もちょっと考えたものの実装がよく分からず避けた、という面もあるので、うーん。

F - Rectilinear Polygons

　コンテスト中に考えていた方法で自力でACできました。

　つい二次元累積和（imos法）を考えたくなるけれど、この問題では座標圧縮もきかないため間に合わない。　
　そこで、平面走査を思い付くのが重要。
　x座標が小さい順に見よう、と思えば後はポリゴンの処理が悩むところ。

　そこは、縦の線分を順番に見て行ったとき、前の線分と重なる方向か、同じ方向か、で場合分けすると上手くいきます。

　Eまでに時間がかかったのと、平面走査を思い付くまで時間がかかったため解き終わらなかったけど、これは解けなくてはいけない問題でした。


　今度からABC八問体制になるそうで、そうすると全完はかなり厳しくなりそう。今回はチャンスだったと思うので、もったいなかった。
時刻: 0 件のコメント:
ラベル:

2021年7月25日日曜日

TopCoder Single Round Match 810

 　EasyはHackされたけどMedが通って助かった。


Div1 Easy WatchedSnail


　二人ずつペアにして考えることが重要だった。
　三人以上重なってもワープできると思い込んでいたのでHackされたのも当然。図を描いたとき、一瞬、二人までしかダメじゃない？　とは思ったんだけど、なぜか大丈夫な気がしてしまった。

Div1 Med IcelandRingRoad


　AtCoderのこの問題の部分問題になっている。

　この問題はACしたことなかったけど、問題を読んだことあったため、この公式解説を読む、というムーブが取れ、救われた。

　ハッシュを使った乱択解なのでやや怪しく見えるのか、tourist氏にチャレンジされたり、neal_wu氏に褒められたりした。SRMでチャットしたの多分初めて！　ちょっと興奮した。

　これを機に、AtCoderの方の問題もACしました。

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

2021年7月24日土曜日

yukicoder contest 304

　Bが分からなかった。


No.1623 三角形の制作

　解説AC。

　まず、$n \le 2 \times 10^5$なのに、$r_i, g_i, b_i \le 3 \times 10^3$というのがどういう意味なのか気付く必要がある。
　言ってしまえば、実質$n \le 3 \times 10^3$なんですよね。そこに気付くのが重要。コンテスト中この制約は見ていたはずなのだけど、頭が回っていなかったのか理解できていなかった。

　（緑色、青色）のペアを全列挙できるということに気付いたら、累積和を使うという発想はまあ自然ですね。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 304

　Bまで二完。Cの考察が全然間違っていた……。


No.1605 Matrix Shape

　解説AC。

　自分の考察はおかしかったけど、「有向グラフが与えられる。このグラフのオイラー路(全ての辺をちょうど  回ずつ通るパス)の始点と終点の組み合わせとして考えられるものは何通りあるか？」（公式解説より）という問題になるところは良いと思う。
　（なお、私は「終点と終点の前の頂点」の組を考えていた。行列の積をちゃんと考えましょう）

　その後の処理も勉強になった。

　オイラー路が存在するグラフは、連結で、かつ、次のいずれかの条件を満たす
・全ての頂点の相対入次数が 0
・相対入次数が -1, 1である頂点が1つずつ存在し、他の頂点の相対入次数が全て0
（解説より）

　無向グラフのオイラー路判定が、全ての頂点の次数が偶数か、または奇数の頂点が二個、となることは知っていたけど、有向グラフでは相対入次数を考えれば良いことには気付けなかった。
　そして、後者の場合、始点・終点は一意に定まる。まあ、次数を見ればそれはそうですね。

　しかし、なぜか私は、始点が一意に決まっても、終点が一通りにならないグラフがあると勘違いしていた。

　こう書いて見ると、普段はしないような勘違いをしていた気がする。頭が働いてなかったか。

No.1606 Stuffed Animals Keeper

　部分和問題と似た問題になることは分かったが、その後のDPでやや苦戦。
　二乗が通る制約なのでそういうDPをすれば良い、と気付けば解けた。

No.1607 Kth Maximum Card

　これは自力で解けた。
　ただ、01BFSと思って書いたものがそうなっていなかったためWAを出してしまった。
　01BFSの復習になりました。
時刻: 0 件のコメント:
ラベル: , ,

Codeforces Round #734 (Div. 3)

　Fが通せず終了。惜しいところまでいっていた気がしたけど、実際は全く惜しくなかった。


F. Equidistant Vertices

　木のいくつかの頂点が同じ距離にある、ということは、別のある頂点（今回は中心と呼ぶ）があって、そこから等距離にあるとき、ということはコンテスト中に気付いていた。
　なので、中心を全探索すれば良いのだが、それだと重複するものや、特定の頂点たちがもっと短い距離で結ばれている場合も数えてしまう。
　それらをどのように除くか、というのが問題。

　結論からいうと、「最初の1歩が全部違う場所に行く」（LayCurseさんのツイートより）場合を数えれば良い。これは全く思いつけていなかった。
　確かに、これで、上に書いたようなダメな場合は除けている。

　あとは、x歩進むとき、最初の1歩の候補がk個以上ある場合について、DPで数え上げれば良い。
　（このDPの処理も、DP使う、と分かっていたから簡単に書けたけど、自力で思いつくのは楽じゃなかったかも）
時刻: 0 件のコメント:
ラベル:

2021年7月21日水曜日

エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）

 　Dまで四完でした。


E - Count Descendants

　深さごとにnodeを管理して二分探索、ということは思いつけていた。
　ただ、オイラーツアーを利用する発想がなかったため、LCAを用いて祖先がどこに当たるかを調べよう、という煩雑な方法を取ってしまった。
　一応、この方法でコンテスト後にACはできたので、ひどい方針だったという程ではないが、オイラーツアー（DFS順）の利用は見逃していることが多い気がする。

F - Integer Convex Hull

　公式から飛べる公式解説、ユーザ解説、解説動画を見てなんとかAC。

　典型090でAndrew's monotone chainを実装したことがあったため、公式解説の方法で実装した。（内部の点の個数の求め方はユーザ解説を読んで理解）

　ただ、確かにmonotone chainの方法を元にDPしているのだけど、ただ凸包を作るのではなく、前の点を全て試して凸になるか調べている、というのを理解するのに手間取った。

・start地点を全探索
・i→jと進む辺が凸包に使えるか全探索
・iの直前の点kを全探索（k→i→jと進んだとき、凸包になっているものを選択）

　するので四乗なのですね。

　そして、DPテーブルには、i→jが上側/下側凸包になる場合の、「総数」を入れる。つまり、全てのk（iの直前の点）に対して、k→i→jが凸包になりうるときの個数の総和を求める。ここで累積和的な考え方を使っていることも理解に手間取った。

　一応理解しACには辿り着けたけど、いや難しい……。
時刻: 0 件のコメント:
ラベル: , ,

2021年7月16日金曜日

AtCoder Beginner Contest 209

 　Dまで四完で、時間もかかってしまった。


C - Not Equal

　包除原理とかDPを疑ったため時間がかかった。
　$C_i$が小さい順番に考えると分かりやすい、と気付けば難しくないが、他の解法も考えてしまいやすいのが難しい気がした。

D - Collision

　LCAを使って解いてしまったが、使わなくても解けるというのは目から鱗。

E - Shiritori

　グラフを作って後退解析ということは、（典型90問をやっていたこともあり）すぐ思いついた。
　だが、その後の実装が難しい。
　まず、開始位置が辺なのが問題を分かりにくくしている。勝ち負けの条件を逆にしてしまいやすい。
　そして、メモ化再帰で実装しようとすると上手くいかず、後ろ向きにトポロジカルソートかSCCをしてその順番に見れば上手くのでは？　と考えたが、それでも上手くいかない。

　すぬけさんの解説動画を見たが、各頂点について出次数を持っておいて、一つずつ減らしていく……というのは思いつきにくい。
　さらに、一度見た頂点をもう一度見ないようにしないといけない、という辺りでも苦労した。多重辺が存在しうるため、二回見た方がいい気がしてしまうが、冷静に考えると見てはダメ。

　最初に方針を立てるだけなら簡単だが、その方針を詰めるのも実装するのもかなり厳しい問題だった。

F - Deforestation

　すぬけさんの解説動画を見てAC。

　各木のコストの使用回数が1～3回になるため、コストが大きいやつを一回にして、その分をコストが小さいやつに回す（三回にする）……というようなことを考えて詰まった。

　その方向性に見えてしまうと、隣同士に着目すれば良い、というのにはなかなか気付きにくい気がする。

　その後の挿入DPも、解説を聞けばすんなり理解できるけど、自力で思いつけたかどうか。ただ、これは典型処理なので、前半の考察ができたなら解けなきゃまずい。
時刻: 0 件のコメント:
ラベル: ,

2021年7月5日月曜日

AtCoder Beginner Contest 208

　Dまで四完。Eが面倒くさそうだったのでFを考えていた。惜しいところまでいった気がしたけど、全くできていなかった。


E - Digit Products

　桁DPっぽいのは分かるし、各桁の数字の積が取りうる値が少なそうなので、計算量が間に合いそうなことも分かる。
　だが、そこからの実装はなかなか難しい。

　自分の実装だと、

・i桁目までNと一致しているか？　というflag（これは、桁DPでよく使うやつ）

　に加えて、

・実際に数字が始まっているか？　というflag（たとえば、"00015"だったら、1が出たときこのflagをTrueにする）

　が必要になった。

　桁DPは、慣れればもうちょっと機械的にできるようになりそうなんだけど、そこまで解く頻度が多くないので、なかなか習熟していかない。


F - Cumulative Sum

　解説AC。

　ラグランジュ補間に関する問題だった。
　ラグランジュ補間はこのあたりで勉強したのに全く思いつかなかったのは良くない。でも、解説放送を見て、以前より大分理解が進んだと思うので、そこは良かった。
時刻: 0 件のコメント:
ラベル: , ,

2021年7月4日日曜日

Codeforces Round #729 (Div. 2)

　Cまで三完。薄橙に戻れず悲しい。


D. Priority Queue

　一応、自力AC。
　各数字に関して寄与を求める、というところまでは良くて、その後の立式で詰まった。

　ただ、各「+ x」というクエリについて、一遍に（累積和的な何かで）上手くするという方向で考えていたのはまずかった。
　各「+ x」というクエリについて、二乗の計算時間をかけて良いのだからDPすれば良いのか、と思えたのは終了10分前くらいだった気がする。

　そこまで分かってからも実装には苦労した。が、おおまかにはコンテスト中にやろうとしていた実装で合っていた気がする。
　「+ x」というクエリのxに関する和を求めたいとき、DP[i]でxがi番目に小さいようなものの場合の数として、「+ x」の後に、

・「-」というクエリが来たときは、半分の確率で一つ減らす。（つまり、DP[i-1], DP[i]にDP[i]を加算）
・「+ y」（x<y）というクエリが来たときは、半分の確率で一つ足す。
・それ以外の場合、全ての要素を二倍にする。

　という感じで。
　なお、「+ x」の前のクエリについては、似ているけどちょっと違う処理をしなければいけなかった。上手く書けばまとめられるのかな……。

　さらに、同じ数字のときの処理も難しい。コンテスト後の提出ではそこでWAを出して苦労したので、コンテスト中に通すのは厳しかったかもしれない。

　こういう、ちゃんと詰めるのって苦手なんだけど、どうすれば向上するのかな。
時刻: 0 件のコメント:
ラベル:

2021年7月2日金曜日

yukicoder contest 302

　Eまで五完。

　最近のyukicoderは、途中で寝ちゃったりして、二時間フルに考えていないことばかりだったけど、今回はまあまあちゃんとやった。


No.1583 Building Blocks

　Eとほぼ同じ人数に解かれているのを見て自力でやろうとした。が、「ソートしてDP」だろう、と実装したらWAで解説を見てしまった。
　ソートの仕方が悪いかも、ちゃんと立式したら分かるのでは？　とは思ったのだけど、実際その通りでした。これは、解説を見ずに解けなきゃいけなかった。実装も軽いしね。
時刻: 0 件のコメント:
ラベル:

東京海上日動 プログラミングコンテスト2021（AtCoder Regular Contest 122)

　ABCEの四完で約半年ぶりにHighestを更新したものの、後でEが嘘だったことが発覚。まぁ、そんなものか。


D - XOR Game

　ちょっと考えて、トライ木を使うのでは？　と思ったところで手が止まってしまったのは良くない。トライ木の理解が不足していたのが敗因だと思うので、ちゃんと復習しておかないと。

　……と思ったが、トライ木を使わなくても再帰を使えばACできると目にし、そちらの方法でAC。（トライ木の復習はしていません）

　Aの全ての要素を二つずつペアにし、それらのxorの最大値を取る……という問題を考えたとき、それができるだけ小さくなるようなペアの取り方を考える問題だ、ということはすぐに気付けた。

　問題は、どう実装するか。
　上位bitから見て行って、立っているbitが偶数個なら、立っているもの同士、立っていないもの同士をペアにすれば良い。それは再帰で書ける。

　立っているbitが奇数個だったときは、bitが立っているもの（それらの集合をBとする）と立っていないもの（Cとする）とのxorを取らなければならない（ので、答えのそのbitは必ず立つことになる）。そのようなペアのうち、最小のものを探せば良い。
　……ということは分かるが、この実装が悩ましい。これをTrie木を使って処理するというのが公式解説の方法だった。

　だがこれも上位bitから見ていく方法でできる。

　奇数個立っていたbitの次のbitを考える。

　BとCの両方でそのbitが立っているものがある、もしくは、両方でそのbitが立っていないものがある、のなら、立っているもの同士、もしくは立っていないもの同士のペアを取った方が良い。そのいずれかの最小値が答えになる（ので、再帰が回る）。
　そういうものがなければ、答えにおいて今考えたbitも立っていることが分かる。そして、その次のbitを見ることになる。

E - Increasing LCMs

　前から素因数の要素数が少ない順に追加していけば良いと思いACしたけれど、嘘でした。

　本当の解法である「後ろから決定していく」というのも一応考えていたので、WAが出ていたら方針転換できた可能性はある。

　けれど、提出したときは結構自信を持っていた（証明できた気がしていた）ので、動揺したと思う。残り二十分ほど、そんな状態で方針転換してACまでいけたか、というと……。実際のところは分かりませんね。


（Fもいずれ解きたい）
時刻: 0 件のコメント:
ラベル: ,

2021年6月30日水曜日

Kotlin Heroes: Episode 7

　Fまで六完で、T-シャツには一問足りず。もっと早く解けないと厳しい。
　とはいえ、残り30分でGかHのどちらか解ければOK、という状況はそれほど悪くなかったともいえる。いかしたかった。


G. Biome Map

　文章が分かりにくいけど、行列Aで(temperature, humidity)に対応するBiomeの番号が与えられている。「その差の絶対値の和が1になるBiome」のみが隣り合うことができるということなので、つまり、Aで隣りあっているものだけが出力すべき行列でも隣りあえるということ。ただし、出力すべき行列の行や列の長さは、Biomeの個数以下でなくてはならない。

　Aの中で上下左右に移動していって、全てのBiomeを尽くせば良い、ということなので、オイラーツアーをすれば良いと分かる。

　ただ、単純にオイラーツアーを一列に並べたのでは、行や列の長さの条件に反する。
　二行にして折り返して並べるのもダメ。縦に隣りあう部分が条件に違反してしまう。（コンテスト中は、これで良い気がしていました）

　なので、斜めに並べると良い。オイラーツアーの長さはBiomeの個数*2-1個なので、この構築でちょうどBiomeの個数*Biomeの個数の正方形ができあがる。

　実装で詰まったのは、

・Kotlinで再帰を書き慣れていなかった
・木でない一般グラフでも再帰一回でオイラーツアーが取れると気付かなかった（一回全域木を取らないといけない気がした）

　の二点。

　「斜めに並べる」という本質が見えてなかったのでコンテスト中にACするのは難しかっただろうけど、実装で詰まったりせず、オイラーツアーまですんなり書けていたら、思いつけたかもしれない。　
時刻: 0 件のコメント:
ラベル:

2021年6月29日火曜日

AtCoder Beginner Contest 207

　ABCEの四完でした。D難しい。


D - Congruence Points

　すぬけさんの解説動画を見てAC。Pythonで$O(N^3)$でも65msでした。

　いやでも確かに難しいのだけど、Sの一点目から二点目へのベクトルが、Tのどの二点のなすベクトルと対応しているか？　で二乗をかけるという方針は思いつかないといけないですね。
　そこまでできていれば、回転を複素数で計算という部分はできたかもしれない。本番中にも複素数を使うことは頭をよぎったはずなので。

　コンテスト中は、（他の人も結構ハマってましたが）角度を決め打って云々、という嘘解法にハマってました。

F - Tree Patrolling

　すぬけさんの解説動画を見てAC。
　二乗の木DPの問題は最近も解いていたのだから、自力でできなくちゃいけなかった。

　が、解説を聞いた後なのに、遷移を書くのに苦労したり、modを取り忘れたり、コーナーケースに引っ掛かったりとWAを量産してしまった。

　二乗の木DPで、子同士をマージするときの遷移は大体いつも似た感じいなるのね。FFTを使える形になるらしい。以前の二乗の木DPの問題でも、「遷移を書くのが面倒だったからFFTを使った」とか書いているツイートを見かけたけど、なぜそういうことができるか理解できた。

　それに気付けたのは収穫。
時刻: 0 件のコメント:
ラベル: , ,

2021年6月28日月曜日

AtCoder Grand Contest 054

 　Cまでの三完で101位でした。Highest更新できて嬉しい！

　ただ、難問が解けたわけではないんですよね。早解き回では時々良い成績が取れるんですが、早解きが得意というわけでもないので、なんというか、運任せのようになってしまう。今回は、BもCも結構最初から正しい解法を考えていたけれど、偶然に近いものね……。
　もっと難しい問題を解く力を付けないと。


B - Greedy Division

　初手で実験を書いたのが結果的には正解だったと思う。
　実験というのは、Wの配列に対して、どんな順列がありうるか……というのを順列全探索で求めるコードです。

　それを眺めていたら、「あれ、和がSUM/2に一致していれば、高橋君や青木君の取り方をどんな順番にしても、正しい順列が一つ求まるのでは？」と気付き（気付けば証明もしやすかった）、後はナップザック問題みたいな感じでした。

　計算量が四乗になるのがちょっと不安だったけれど、定数倍が小さそうなので大丈夫だろう、と提出したら無事AC。

C - Roughly Sorted

　これは、「2 1 4 3 6 5」でK=1の場合などを考えました。この例で、1や3はいくらでも後ろに動かせるけど、2が4の後ろにいくと途端にダメになるんですね。
　それを見て、「自分より前に登場している自分より大きい数の個数」がKに一致しているものしか動かせないんだな、と気付けました。



（DかEはできれば解説ACしたい）
時刻: 0 件のコメント:
ラベル:

2021年6月26日土曜日

Codeforces Round #728 (Div. 1)

　A一完のひどい出来。


B. Tree Array

　制約から、三乗の解法を考える。
　全てのi, j (i < j)について、j が iより先に使われる確率を考えれば良い。（主客転倒って言うのかな？）
　そうすると、iとjを結ぶpathにいくつか余計なものがくっついているような図を考えることになる。（木の直径を図示するときのやり方と同じ）
　なので、iとj上のpath上の点から始まったとき、jの方に先にたどりつく確率を調べればOK。

　……と、ここまではできたが、この確率が2ベキの和になると早合点してしまった。それでサンプルが合ったこともあり、修正できず終了。

　実際は、iから距離p、jから距離qの点からスタートしたなら、p回iの方へ進む前に、q回jの方へ進む確率を計算すれば良いので、p*qのマスで端から端への最短で向かう経路数を考えるのと似たようになる。これはDPで求めることができる。
　これを前計算すればOK。


　多分、もう少し時間が残っていて、落ち着いて考えていたらちゃんとACできたと思う。先にCを考えたりしたせいもあり、Bの正しい方針に至ったときに時間が残っていなかったのが敗因か。
　
時刻: 0 件のコメント:
ラベル:

2021年6月20日日曜日

AtCoder Beginner Contest 206（Sponsored by Panasonic）

 　Eまで五完でした。


F - Interval Game 2

　すぬけさんの解説を聞いてAC。
　NIMみたいなことをするのでは？　Grundy数を使うのでは？　とは多少は考えたものの生かすことができなかった。

　ある一つを選択したら、左右に残った二つの区間のGrundy数のxorがそのGrundy数になる、というのはちょっと思ったのだけど……。

　それに加えて、どういう遷移があるかを考えなくてはいけなかった。
　Grundy数を考えたいのだからどのような遷移があるかを考えるのは当たり前で、「いくつかの区間が選択可能」なときのGrundy数は、それぞれを選択したときのGrundy数のmexとなる。

　Grundy数の定義通りなのだけど、遷移を意識していないと書きにくい気がする。Grundy数と区間DPって相性が良いんだね。
時刻: 0 件のコメント:
ラベル: , ,

2021年6月19日土曜日

Codeforces Round #726 (Div. 2)

 　Cの誤読でハマったものの、なんとか全完。Div. 2のCくらいだと、この後に解ける問題があるはず！　と、ちょっとハマったら飛ばす決断ができるんだよね。これが、ARCとかこどふぉDiv. 1だとなかなかそういう決断はできない。


　ツイートに付け加えることは特になさそう。
　Dの正当性は、Kiriさんのツイートで理解しました。なるほどー。
時刻: 0 件のコメント:
ラベル:

2021年6月15日火曜日

AtCoder Beginner Contest 205

　Eが解けずに終了。ただ、Eは知識問題に近かったので、まあ仕方ないか。次に類題を見たときは解けるようにしたい。


E - White and Black Balls

　解説AC。
　経路数の問題なのは分かるが、それをどうやって求めればいいか、というところで詰まった。解説の図を見てなるほど、となった。

　この求め方は見たことがあったと思うが、身に着けておかなくてはいかない知識とは思っていなかった気がする。
　次出題されたときは解きたい。

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

2021年6月14日月曜日

Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)

　Cまで三完。D、Eを考えていたが解けずに終了。ここまではっきり失敗したのは久しぶりな気がする。


D. Lost Tree

　「木は二部グラフ」というキーワードすらほとんど浮かんでいない。
　クエリの回数がn/2というところから、二部グラフは考えるべきなんですよね……。

　そのキーワードを思い付くことが重要で、その後は、一回目のクエリで二部グラフのどちらに属しているか判断できる、と気付くところがポイントですね。
　二部グラフを使おうと思いついていたとして、そこで詰まっていた可能性はありそう。

E. Lost Array

　全ての要素についてクエリで聞いた回数が奇数回になれば良い、というのは分かった。では、それが実現できる最小の回数は？　というところで詰まった。
　なんか条件（1の個数や3の個数を調べて……みたいな）がないかと考えていたけど、上手くいかず終了。

　実際は、もっと愚直に構成できるか試してみるべきだった。
　ただ、毎回それをやっていると、$k=n-1$のときにTLEしてしまう。このときは、n回聞けば良いと分かるので、場合分けしてやればACできた。

　公式解説は（理解できていないが）もっと賢い方法でやっているようだけど、上記の方法はコンテスト中に考えたことをまとめただけなので、コンテスト中に通すことは可能だったはず。
　計算量を気にする前に、愚直なやり方で間に合わないかを試してみるべきだった。
時刻: 0 件のコメント:
ラベル: ,

2021年6月12日土曜日

第二回日本最強プログラマー学生選手権

　ABCDFで終了。Eはコンテスト後、自力で解けたもののかなり苦戦した。


G - Spanning Tree

　行列木定理を知らないとどうしようもない。
　これを知れたのは良かった。（証明は理解できてないけど）

　行列式の計算もはじめて書いたと思う。なるほど、掃き出し法を使うことで三乗に収めるんですね。

　ケイリーの公式といい、この行列木定理といい、知らないと思いつくのが難しい（が、競技プログラミングに出題される）定理が木の分野にはありますね。

H - Shipping

　最近、SRMで類題を見たので、解説ACしました。

　公式解説の「ハッシュを使った解法」は凄いですね。サイクルの部分はSRMのものと同じですが、木の部分もこうやって処理できるとは。
　SRMのときはサイクルのところしか読まなかったので、木の部分はどうするんだろう、と考えていたのですが、LCAを使うしかないのかな……と思っていたところでした。しかしこれもLCAを使わずにハッシュで解けるんですね。

　とはいえ、このハッシュの使い方はこのFと同じか。
　いくつかの状態があって、そのうちの一つでも存在するかどうか調べたい……というときはこのハッシュ（Zobrist Hash）を検討しても良いのかもしれない。
時刻: 0 件のコメント:
ラベル: , , ,

2021年6月11日金曜日

Codeforces Round #725 (Div. 3)

　Eが解き終わらず終了したが、コンテスト後提出したらWA。その後、約一時間かかってようやくpretest全完。


　ツイートに加えて書くことはなさそう。
　Gは最初、フローに見えて悩んでいたのは良くなかったね……。正当性がやや不安だったけど、どうやら正しそうで良かった。
時刻: 0 件のコメント:
ラベル:

2021年6月8日火曜日

AtCoder Beginner Contest 204

 　Eまで五完。Fはキーワード的には分かっていたのだが……。


E - Rush Hour 2

　ダイクストラ法。
　$\sqrt{D}$よりtimeが小さいときは、$\sqrt{D}$を調査、そうでなければ普通にtimeのときにかかる時間を計算。

　$\sqrt{D}$あたりが極値になりそうなことは、最初は微分しようとしたが面倒くさくなって、
　$x+\frac{d}{x+1}=x+1+\frac{d}{x+2}$
　を計算した。

　これは、$x$が1ずれても同じ値になるところを調べているということ。こういう$x$で極値になるはずなので。

F - Hanjo 2

　解説AC。
　うーん、行に関する部分集合たちについてDPをして、行列累乗だろうとは思ったし、横2マス見れば現在の状況が扱えることもコンテスト中に考えたはずなのだけど。

　しかし、解説をみても、「列iまでみて全ての行ではみだしている場合」と「列i+1までみてはみだしが一つもない場合」は同一のものなのに、DPするとき両方を状態として持たなくてはいけないことにピンと来なかったし、自分にはちょっと分かりにくいDPだったのかもしれない。

　遷移の行列を作るところは再帰で書いたけど、これもどう書けば良いか結構迷ってしまった。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)