2022年8月8日月曜日

Codeforces Round #812 (Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Cross Swapping

　解説AC。面白い問題だったが、最初の一手にさえ気付いてなかったので、何も言えない。

　まず、

・A[i][j]はA[j][i]としか入れ替わらない

　と気付くのが重要。（コンテスト中散々実験したのに気付かなかったのはひどかった。何故……）

　だが、A[i][j]とA[j][i]を入れ替えたいとき、iとjのどちらを用いてswapすれば良いか分からない。また、入れ替えたくない時、iとj両方使わないのか、もしくは使うのかが分からない。

　これは、グラフの問題になる。

　左上から貪欲に、A[i][j]とA[j][i]の大小に従って、iとjでswapする/しないが一致する場合は0の、一致しない場合は1が書かれた辺を張っていく。そして、iとjがループしてしまいそうなときは、辺を張らないようにする。なぜなら、ループができたら結果が決まらなくなるため。左上から貪欲に決めているので、前に決めたことを優先した方が良い。

　こうして決めた後、木それぞれについてswapする、しないを割り振っていけばOK。
時刻: 0 件のコメント:
ラベル:

LINE Verda プログラミングコンテスト（AtCoder Beginner Contest 263）

　Eまで五完。Gを考えていたが、Gは惜しくなかった。

コンテスト後のツイート

F - Tournament

　解説AC。

　DPだとは思ったが、どういうDPにすれば良いか組み立てられなかった。完全二分木なので、各段ごとにDPしていくというのは自然なのだけど、その後どう立式するかが難しい。
　勝者以外のもらえるお金を持つというのは、言われてみれば分かるけど思いつきにくい。

G - Erasing Prime Pairs

　解説AC。

　問題を見たとき、まずフローを疑ったのに、グラフの作り方を思いつかずその方針を追わなかったのはひどい。1がなければ、偶数と奇数で二部グラフになるのね、なるほど。

　実際にACしたのは、頂点を倍加し、i→j+Nに、A_i+B_iが素数のときに無限の流量を流す、という方法でACした。この解法の正当性が話題になっていたが、noshiさんのツイートに証明が書いてあった。

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

2022年8月7日日曜日

yukicoder contest 355

 　睡魔に襲われてしまいA一完でした。横になっているときにBは思いついたんだけど、起きてから解き終わりませんでした。


No.2028 Even Choice

　偶数番目の$A_i$を使うとすると、それ以降のものは全て使える、ということには結構すぐ気付いたが、実装で困った。
　後ろのindexから見て、heapqを使って、上位K-1個の値と総和を管理していけば解ける。

No.2029 Swap Min Max Min

　（寝ていたため）最初、想定解法が間違っていたという話を知らなかったが、その間違った解法で解いてしまった。

　Nが奇数の場合、奇数番目を小さい数字で埋めれば良い。
　そのあため、Nが偶数の場合、奇数番目全て、もしくは偶数番目全てを小さい数字で埋めれば良い、というのは嘘。
　ちゃんと考えると、途中まで偶数番目で、途中から奇数番目でもOK。

　解法ツイートを見てしまったけど、sampleが合わないのでそれを元に考えれば、時間あったら気付けたはず。
　ただ、sampleになかったらWAを出していただろうし、テスターだったら気付けてなかった可能性が高いよね……。

No.2030 Googol Strings

　これは自力AC。
　max(len(x)*2,len(y)*2)まで調べて、そこまで一致していたらどちらかがどちらかのprefixになっているので、長さを比較。

　で、合っている気がするけど証明できていない。

No.2031 Colored Brackets

　自力AC。DPですね。
　
　
時刻: 0 件のコメント:
ラベル:

2022年8月4日木曜日

yukicoder contest 277

　Cまでの三完でした。


No.1332 Range Nearest Query

　解説をちらっと見たらセグ木二分探索と書いてあって、確かにそれでいけるか、と思っていたけど、実際に実装するとWA。
　ちゃんと解説を読むと全然違っていて、クエリ先読みが本質の問題でした。


　……と、当時書いたままACしていなかったけど、今更、解説AC。

　絶対値を考えるときは、正と負に分けて考えるのが定石の一つ。
　正だけを考えると、平面走査＋セグ木でできる。


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

2022年8月2日火曜日

Codeforces Round #811 (Div. 3)

　全完を逃した。
　システムテストは全部通っていました。

コンテスト後のツイート


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

2022年8月1日月曜日

CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)

　AB小森健。Eの四完。紫に落ちました。辛い。

コンテスト後のツイート

D. Magical Array

　解法ツイートを見てAC。

　不変量を探す問題なのだろう、とは思ったが、それを探すことができなかった。
　正しい不変量は、

・i*A[i]の総和
・累積和の総和

　（どちらでも良い。どちらも不変量）だった。

　なぜ思いつかなかったかというと、A[i]とA[0]の差に着目してしまったというのが大きい。ある配列からの差分を考えているのだから、差分が重要なのだろう、と考えていた。

　どう思いつけば良かったんだろうか。

　累積和くらいとってみても良かったのでは、というのは一つある。

　他には、Operation 1とOperation 2の違いは、足すindexが一つ違っているというだけなのだから、index*（何か）みたいに、indexを使った不変量があるはず、という風にして思いつく方向性もあったかもしれない。

　解法ツイートで見たのだけど、配列を頻度分布とみなせば、操作1では総和が1増え、操作2では総和が2増える、ということから考えることもできた。
　これは凄く自然で納得できる。が、頻度分布とみなすところが難しいなぁ。
時刻: 0 件のコメント:
ラベル:

第三回日本最強プログラマー学生選手権-予選-（AtCoder Beginner Contest 262）

　Eまで五完。

コンテスト後のツイート

F - Erase and Rotate

　解説AC。

　ある数字を先頭に持ってくるためには、

・それより前を全て消す
・それより後の数字を全て消すもしくは先頭へ移動させた後、その数字も先頭へ持っていく

　のいずれかの方法がとれる。
　コンテスト中は二番目の方法しか考えていなかったためダメでした。

　一旦先頭へ持っていった後は、範囲最小値が分かるセグ木を使って、あるindex iからi+Kの間にP[i]より小さい数字があればindex iを消去、というのを繰り返せば良い。（先頭への移動がない場合も、この方法で作ればOK）
　ただし、Kが余っていたら、最後にPの後ろを消すのを忘れずに。

G - LIS with Stack

　解説放送を見てAC。

　解法を理解するのも実装するのも難しい。
　indexがどこに移るか考えて、「区間で何かする」という発想に思い至れば思いつけるのかなぁ。

Ex - Max Limited Sequence

　解説放送を見てAC。

　解法（の高速化以外の部分）を理解するのはそれほど難しくないけど、普通にやろうとするとDPが二乗になってしまう。確かに高速化できそうではあるのだが、実装方針が難しいし、方針を理解しても実際の実装には非常に苦労した。

　解説の方法で実装したけど、遅延セグ木を使った方が実装しやすいのかなぁ。どっちみち大変そう。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)