Cを飛ばしてFまで。Gは5秒後にAC。
コンテスト後のツイート
F 二乗の木DP。遷移を書くのが大変。
— titia (@titia_til) January 28, 2023
G クエリ先読みしてスコアを座標圧縮。セグ木で個数を、BITでスコアの総和を管理。二分探索でどこまで使うかを求める。どちらかというと実装問題。
C - Path Graph?
解法ツイートを見た。
次数と辺の数だけ見ていけると思ったけど、連結性も判定しなくてはいけなかったのね。確かに。
2023年1月30日月曜日
ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)
2023年1月24日火曜日
ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286)
Fまで六完でした。
コンテスト後のツイート
ウルシステムズプログラミングコンテスト2023(AtCoder Beginner Contest 286) Fまで六完。
— titia (@titia_til) January 21, 2023
C x回rotateしたときの最小値をそれぞれ調べる
D DP
E N回BFS
F 拡張ユークリッドの互除法で復元。素数だけだとダメで、4や9を使う。
G 一筆書き問題に帰着させたいが、帰着させるのを失敗。
G - Unique Walk
解説AC。
一筆書き問題へ帰着する方針はあっていたが、帰着させ方が分からなかった。
Sに含まれない辺でつながった頂点をUnion-findでくっつけて良い、というのは解法としては分かりやすいが、直感的に明らかという気もしない。ので、思いついていたらすぐ実装しようと思えたかも分からない。
ただ、Sに含まれる辺については一筆書きの考え方を使えそうなのだから、Sに含まれない辺で何かをしよう、と考えるべきだった。
2023年1月23日月曜日
AtCoder Regular Contest 154
Cまで三完。Dは惜しかったような惜しくないような。
コンテスト後のツイート
C B[i]!=B[i-1]なるiたちについて、対応するAの文字を探して全部あればOK。ただし、A=BでないのにBがAのrotateしたものだとダメ。
— titia (@titia_til) January 22, 2023
D "? x x y"を使って1を探す。あとは"? x ONE y"でxとyの大小関係が分かるので二分探索していく……という方針だと5ケースWA。これだとクエリ数超過する？
D - A + B > C ?
1を探すまでのクエリ数がN回でいけるというヒントを見てAC。
"? x x y"でNoがきたらxはyより小さい、ということを利用して、順に見ていけば分かりますね。言われてみれば簡単だけど、コンテスト中は思いついていなかった。
後半は、"? 1 x y"（1は1と判明しているindex）を用いて、挿入ソート＋二分探索（二分挿入ソート）でやりました。
2023年1月21日土曜日
yukicoder contest 374
Bで睡魔に襲われA一完。
No.2195 AND Set
コンテスト中、クエリ3で出力するものがSのandではなくorであるようなコードを書き（各bitに何個数字が入っているか管理し、それが0より大きいもののorを出力）、修正方法が分からなくなり寝てしまった。
結構簡単に修正でき、現在何個Sに入っているかを持つようにするとandでも求められた。
No.2196 Pair Bonus
自力AC。
DPが必要に見えて、実は必要ないのは面白い。
No.2197 Same Dish
自力AC。
余事象を考えれば良いと気付いたら、後はわりとすんなり解けた。
No.2198 Concon Substrings (COuNt-CONstruct Version)
自力AC。
onononononon……と並べておいて、間にcを挿入する方針で解いた。
解説とは違ったけれど、writerさんのブログによると、この方針で解いた人が多かったらしい。
No.2199 lower_bound and upper_bound
解説AC。
経路数の数え上げに帰着するのが難しい。とはいえ、総和を固定すれば経路数になるというのは言われれば納得できるもの。制約からいって、何かを固定して考えるのは自然だから、思いつきたいものではある。
その後の計算は、二項係数の差で求められるのはこの問題で覚えていたが、引く値（というか、反転の軸となる直線の式）を間違えて苦労してしまった。
2023年1月16日月曜日
Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round)
Dまで四完だが、Dがシステムテストで落ちて悲惨。
コンテスト後のツイート
Codeforces Round #844 Dまで。
— titia (@titia_til) January 15, 2023
B ソートして、A[i]<=iかつA[i+1]>i+1ならOK
C 含む文字はnの約数個なので、頑張って調べる。
D A[j]-A[i]の差が連続奇数の和になるという条件から絞った。
F 累積和の頻度数を持ってDPだと思ったが答えが合わない。解法も違うっぽいね。
D. Many Perfect Squares
やり方はツイートの通り。
初期値を0にしたのが落ちた原因で、そこを1に変えたら通った。
最初に「n=1のとき答え1」と例外処理を書いたのがミスの一因。ただ、これが悪かったとは言えない。
とはいえ、こういう「とりあえず分かった部分を書く」のにも功罪あるなぁ。
E. Rectangle Shrinking
解説は見なかったが、デバッグの際にtestcaseを見てAC。
解法自体は分かったけど、実質実装問題なので、WAを出してデバッグに苦労しているのはまずい。
2023年1月15日日曜日
AtCoder Regular Contest 153
ABの二完。
コンテスト後のツイート
AtCoder Regular Contest 153 二完で終了。
— titia (@titia_til) January 14, 2023
A 全列挙
B 二回操作すると元のグリッドの平行移動になる
C Noになりうるのは+1と-1の数が同じときだけ、とは気付いたがそれ以外の実装ができず終了。
C - ± Increasing Sequence
解説AC。
まず、もっと早く「"No"」とだけ投げるべきだったかも。
Noになる数が多いと分かれば、YesかNoかを判定しようという気持ちになり考察が進んだ。
Dを並行して考えていたせいで送れた、というのもあるが、分からないときはペナ覚悟でこういうのを投げた方が良いかもしれない。
さてコンテスト終盤、1と-1が同数で、それがカッコ列に近い、というのが分かり、どこで調整すればいいか分からなくなったのだが、((()))の最後の")"で調整しようというのは思いつきたかった。
もうちょっと具体例など書いて考えれば分かったはずなのだが……。（ただ、コンテスト後に考えて分からず、結局解説を見たので、時間をかけても分からなかった可能性はある）
カッコ列に近いとは思ったのに、累積和を取ってみようと思わなかったのもまずい。そちらを経由して思いついた可能性もある（が、残りの時間が少なかったのでやや厳しい）。
なお、1と-1が同数のときは乱択で通した（最後の一項以外はx, x+1, ... で並べ最後の項で調整。xをランダム）。コンテスト中に提出したものがTLEになったのがなぜか、というのもちゃんと分かるべきだった。xの範囲がどのあたりなら良いかもちゃんと考えねば。
2023年1月14日土曜日
yukicoder contest 373
無理矢理通したものが目立つ。
コンテスト後のツイート
yukicoder contest 373 ABC通した後FGを非想定で通した。
— titia (@titia_til) January 13, 2023
F sqrt(残り)の切り下げを答えに加えていくと大体通ったので、一項目を乱択したら通った（Hackできなそう？）
G 適当に下六桁を絞った後、時間ギリギリまで上六桁を調べて見つからなければNOを出力するやつを投げたら通った。（Hackできそう）
No.2187 三立法和 mod 333
埋め込みで自力AC。
想定解法も埋め込みなので、これは無理矢理通して良い問題だった。コンテスト中も埋め込みをしようと考えたが、Pythonで特に高速化もせず書いたためコンテスト中に終わらなかった……。並列処理の書き方とか学ばなきゃね。
Rustでも結構時間がかかったが、無事実行が終わりAC。
2023年1月13日金曜日
AtCoder Grand Contest 060
AB二完でした。
コンテスト後のツイート
AtCoder Grand Contest 060 ABの二完でした。
— titia (@titia_til) December 25, 2022
A DP。三文字見る。
B 曲がり角だけ見ればOK。自分の初提出（22:33）はこれに条件を加えたものでした。N=5,M=2,RDDDDでK=1のときはNOだと思っていたため、他に条件が必要だと思って迷走。WA覚悟ダメ元で条件を抜いて提出したらACしてびっくりしました。
C - Large Heap
解説放送を見てAC。
分かってしまえば自然な解法なのだが、実際に解くのは難しい。とりあえず、
・順列がヒープ的になる確率を求めるなら、1/(部分木)を掛け合わせる
ということは知識として知っておいた方が良い。思いつけて良い内容だけど、本番中はこれに気付かなかった。そして、これに気付けなければ解けようがなかった。
あとは、上手く二乗DPにしようと頑張るしかないかな……。
ただ、Pythonのpow(a, b, mod)が遅いのは知らなかった。TLEをなくすためにはこれを自分で書き直さないといけない。さらに、modでの逆数を求める関数も別に作ると高速化できる。このことは頭に入れておこう。
Codeforces Round #843 (Div. 2)
遅刻参加してDまで四完。
E. The Human Equation
解法ツイートを見てAC。
累積和の最大値 - 最小値が答え。
確かに、この操作では累積和の最大値を一つだけずらすことができるが……。気付くのは結構難しい気が。
2023年1月12日木曜日
AtCoder Beginner Contest 284
Fまで六完。
コンテスト後のツイート
AtCoder Beginner Contest 284 Fまで六完
— titia (@titia_til) January 7, 2023
D 10^7あたりまででNを割り切る数があったら、それがpかq
E 悩んだけどDFSするだけだった。
F 左右からRolling hash
G - Only Once
解説AC。
期待値を考える気持ちはあったのだが、漸化式を考えて迷走してしまった。漸化式も必要なく、（グラフの問題として捉えた後は）かなり素直な見方で解ける問題だった。
問題の見た目が大仰なのにびびってしまったところもあるかもしれない。解けなくてはいけない問題だった。
Educational Codeforces Round 141 (Rated for Div. 2)
Dまで四完だが、Dは（予想通り）Hackされた。
コンテスト後のツイート
D 次に使う要素を持ってDP。雑にCounterを使って書いたら、PyPy3-64だとTLEしたが、PyPy3だと通った。
— titia (@titia_til) January 8, 2023
E A[i]>B[i]のとき、A[x]/xとB[i]/(x-1)を比較するなどしてダメな場所を更新。xの値は平方分割して、上からと下からの二通りやる。セグ木でやったらTLEした。もっと高速な方法がありそう。
D. Different Arrays
Counter（dict）のDPはやはり遅い。
ちゃんと配列を使いましょう。（ratedだったらそう書き直したと思うが、unratedなので……）
E. Game of the Year
解説ツイートを見てAC。
平方分割しか思いつかなかったが、もっと良い方法があった。
・xでダメならxの約数でもダメ
ということを利用する。これだとPyPyでもTLEにならず、ACできる。
2023年1月11日水曜日
Codeforces Round #842 (Div. 2)
Cまで三完。早めにD捨てていればEをACできたと思うけど、D解けなかったのもまずい。
コンテスト後のツイート
Codeforces Round #842 (Div. 2) Dが分からなくて、Eやっと答えがあった。
— titia (@titia_til) January 5, 2023
E 二項係数と包除。一回以下でソートできるときは、左側/右側1/3がソート済みのときから、両側1/3がソート済みのときを除く
二回以下でソートできるときは、中央1/3に1～2*nが何個入るかで場合分けすると二項係数でかける。
D. Lucky Permutation
解法ツイートを見てAC。グラフの問題だろうと思ったのに、どういうグラフを考えれば良いか分からなくなった。
頂点を1～n、iからP[i]へ辺が出ているグラフを考えると、いくつかのサイクルで表されたグラフとなる。そして、ソートされたものに戻すためには、それぞれの連結成分について、連結成分数-1回だけかかるので、それらを足し合わせれば良い。
この問題では、1, 2, 3, 5, 4, 6, 7 のように一ヶ所逆転した部分があるものにしたい。ソートされた状態にした後、もう一回操作すれば作れるのは明らか。
もっと少ない回数でできるか、というと、「iとi+1が同じ連結成分に含まれる」という箇所があれば一回省略することができる。これは、さっき作ったグラフのiとi+1が繋がっているものを互い違いに付け替えることになり、サイクルが二つに分かれるので操作回数が一回減る。
2023年1月10日火曜日
yukicoder contest 372
ABの二完でした。Cはしばらく考えたものの問題内容を理解できず、Dは分からなかった……。
コンテストへのリンク
No.2177 Recurring ab
自力AC。
冷静に問題文を理解したら解けた。
・$0.ababab=a*(p^{-1}+p^{-3}+\dots)+b*(p^{-2}+p^{-4}+\dots)$
となるので、それを式変形する。
ただ、その後も二分探索が必要だったりするので、決して簡単な問題ではないと思う。
No.2178 Payable Magic Items
解説AC。
グラフを考えればBFSの問題になる。言われてみれば確かに。
コンテスト中、$5^8$がたいして大きくならないことは調べたのだが、それを生かせなかったのは反省。
No.2179 Planet Traveler
自力AC。
tの値が同じが異なるか、それぞれで二点間の距離を計算する。
立式すると、不等式が出てきて同値変形に戸惑った。誤差を適当に処理しようとするとWA。
・不等式を二乗するときは、両辺の正負を確認してから
という、大学受験でしばしば見られる処理をきちんと行うのが大事。私はかなり手間取ってしまった。
2023年1月7日土曜日
Hello 2023
Dまで四完。
コンテスト後のツイート
E 全勝や全敗を削っていく方針でやっていたけど、[1,2,3]が[4,5,6]に全部勝っているけど、[1,2,3]内や[4,5,6]内では勝者なし、というときの処理ができず終了。
— titia (@titia_til) January 3, 2023
E. Anya's Simultaneous Exhibition
解法ツイートを見た。
強連結成分分解で最強成分が分かれば良い。
このためには、勝利数が多い方から順番に見ていく。自分より勝利数が多いどれかに勝っていればOK、とする。
そして、
・勝利数が大きい順に見れば、その接頭辞が強連結成分になっている
・接頭辞の負けの数＝そこまでの人数での試合数 となっている部分を調べればクエリn回で求まる
となる。
トーナメントグラフにおいては、次数をソートして考えるのは典型らしいので押さえておきたい。
2023年1月2日月曜日
Good Bye 2022: 2023 is NEAR
Dまで四完。Eは大まかな解法は合っていたようなのだけど……。
コンテスト後のツイート
Good Bye 2022: 2023 is NEAR pretestはDまで
— titia (@titia_til) December 30, 2022
A 最小のものを更新
B N,1,N-1,2,...
C 差と小さい方を全列挙。差がx(<=N)で割り切れるものの小さい方の集合がx個あるとダメ
D 個数の少ない数字から決める。残り1個ならそれを採用。残り二個なら片方採用して答え二倍。A[i]=B[i]で残り一個なら答えn倍。
E. Koxia and Tree
解説・解法ツイートなどを見て苦労してAC。特に、このツイートのおかげで理解できました。とりゐさんに感謝。
蝶というより質点として考えていた。xの質点とyの質点が辺の両端にあるとき、辺に方向をつけると、(x+y)/2の質点二つに変化する。
そうやって移動しても、質点が質点をおいこすことがないため、移動した辺以外の辺については、x側の質点の個数やy側の質点の個数は変わっていない。それを利用して答えを計算できそう。
……と、ここまで（Editorialに書いてある内容）はコンテスト中に分かっていた。
問題は、答えにどう反映させるか。
質点がxからx+kに増えるのだから、その差分kと反対側にある個数を掛けたものだけ増える……とか考えて混乱していた。
今回、初期状態での答えが分かるため、差分計算で考えたくなるが、今回はそうしない方が良い。各辺を有向にしたごとに、その辺の寄与を考えていく。
その際、
・x側に質点があり、y側にはなくて、x→yに移動するとき
・x側に質点があり、y側にはなくて、移動しないとき
……
と、一つ一つ場合分けして考えるのが重要。
質点の重さみたいに考えてしまったが、それらはあくまで確率。片側にあるか/ないかの確率が分かっている。なら、あるかないか全て場合分けして考えれば良い。
なんとなくのイメージで考えてしまったのが失敗の原因だった。あるかないかの確率が分かっているのだから、あるときとないときで場合分けして考える、というのは何が既知かを理解していれば自然だった。
登録:
投稿 (Atom)