2023年4月30日日曜日

yukicoder contest 386

 Bまで二完。


No.2284 Assembly

 サンプル2の説明を誤読した(「i 番目の学生が前から Pi​ 番目の椅子に座る」を「Pi 番目の椅子にi番目の学生が座る」と勘違いしていた)のを修正できず、コンテスト後にTwitterで教えてもらいました。感謝。

 解説AC。
 なんとなく、大体貪欲にできるのでは? というところから考察を進められず。逆から見れば良かったのですね。

 これ、この誤読自体はよくあるものだけど、誤読してるはずと思って読み返してもどこが間違っているか理解できない……というのは頭が働いていなかった一つの証拠という気もする。だから、こういうときはどうしようもない気もする。

 対策の立て方はあるだろうけど、調子がよければこういう誤読はしないはずだから、調子悪いときのために対策を立てても仕方ないかな、と思う。

No.2285 Make A Unit Square

 解説AC。

 Grundy数だと理解した後も、どんなゲームのGrundy数を調べるのか迷ったのは反省。

ユニークビジョンプログラミングコンテスト2023 春 (AtCoder Beginner Contest 300)

 Fまで六完。

コンテスト後のツイート

G - P-smooth number

 半分全列挙という情報を得てAC。

 最大でsample2の個数なら、上手く枝狩りすれば列挙できそうな気がして、どこかまとめて(メモ化再帰を使って)計算できるところがあるのでは? という方向性で考えてしまった。

 言われてみれば半分全列挙も、劇的に計算量を改善するというよりは、全探索でも通りそうなものの計算量を減らす手段でしたね。ケアしないといけない。

2023年4月29日土曜日

Codeforces Round 868 (Div. 2)

 Dまで。EもFも復習しておきたい。

コンテスト後のツイート

E. Removing Graph

 解法ツイートを見てAC。

 Grundy数を使う問題で、一見この問題に似ている。ただ、サイクルから一回切り取るとpathになることに気を付けなくてはいけない。そのときは、この問題の簡単なバージョンだった。これらによりGrundy数を計算すれば解ける。

 ただし、それらを思い出せなくても、Grundy数は実験すれば求められる。
 実際私もコンテスト中に実験していた。しかしpath graphのGryndy数のみ実験し、cycleの場合を実験しなかったため解けなかった。path graphのGryndy数を使えば元のcycleのGrundy数もすぐ分かるのだから、ちゃんと実験していれば解けていたはず。pathの場合に何か規則性があるのでは? などと考え(実際、0にならない、という規則はあったのだが気付けなかった)最後まで実験しなかったのはダメ。

F. Random Walk

 解説ACしたが今一つ納得できていない。類題が出たら解けない気もする……。

 公式解説よりもこのコメントの解説の方が分かりやすかった。s~t間のpathに含まれる頂点の期待値がdeg(v)*d(v)になるというのは納得。
 それ以外の頂点の期待値も似たように考えて求めることはできる……というのはそう。だけど、他の方のツイートとかを見ると、もっとすっきりとした理解の仕方がある気がする。

2023年4月27日木曜日

yukicoder contest 385

 睡魔に勝てずA一完。


No.2276 I Want AC

 自力AC。

 左側のいくつかを"A"に、残りを"C"にするのが最適。凸性がありそうなので三分探索(今回は中央の二点を調べれば二分探索でOK)。

 これくらいのことも思いつかない状態なら、寝て正解だったとも言える。

No.2277 Honest or Dishonest ?

 自力AC。これは手間取らずに解けた。

No.2278 Time Bomb Game 2

 解説AC。

 自分が最初にいるマスの幅以外関係ないのでは? というのが直感で、大体それは合っていたものの、幅が1のときなどコーナーが多く、解き切るのは難しい。

No.2279 OR Insertion

 解説AC。

 桁ごとに考えるのは分かる。制約を見ると、その後DPすれば良さそうなのだが、どういうDPをすれば良いか分からなかった。

 DPで分割方法を求めようと思うのが重要。
 問題文に「分割の仕方は$2^{N-1}$」とある通り、分割の仕方はDPしなくても求められるが、DPでも求められるのは頭に入れておきたい。

 そう思えば、orの桁iが立っている/立っていないで場合分けして、Sのj文字目まで見たときのそれぞれの分割の仕方をDPで求めようという方針は立ちそう。

No.2280 FizzBuzz Difference

 解説AC。

 全く中国剰余定理を思いつかなかったが、分かってしまえば中国剰余定理の良い練習問題、という感じがする。適切に式を変形すれば中国剰余定理を使える形になるのだが、慣れていないと思いつくのも容易ではなさそう。

 こういうタイプの問題で中国剰余定理を使えることがある、と頭に入れておくしかないか。

2023年4月25日火曜日

Codeforces Round 867 (Div. 3)

  G2が解けず。

コンテスト後のツイート

G2. Magic Triples (Hard Version)

 b(中央の要素)の大きさで場合分けするという解法ツイートを見てAC。a, b, cについて、b=a*x, c=b*xとなるxの大きさが10^3より大きいか小さいかで場合分けすると上手くいく。

 高速素因数分解などの方針が頭をよぎって思いつかなかったが、aが10^9以下という制約なら、三つに(10^3ずつ)区切ることは考えなくてはいけなかった。なお、PyPyじゃ通せずRUSTでAC。

2023年4月23日日曜日

東京海上日動プログラミングコンテスト2023(AtCoder Beginner Contest 299)

 Eまで。unratedになったこともあり、Gは見ずFを考えていたが分からずに終わった。unratedでやや集中力が途切れてしまったが、集中しても解けていなかっただろうと思う。


F - Square Subsequence

 解説AC。

 解説を見ると確かに典型の組み合わせなのだが、結構難しいと思う。

 制約を見ると、何らかのDPをするとは予想できる。
 また、重複して数えないため、できるだけ左にある文字で構成される「TT」を考えようとは思える。

 だが、二つ目のTの一文字目を決め、部分列DPを使って次の文字の位置を前計算しておくと、そのうちどういうものが「できるだけ左にある文字で構成される「TT」」二番目の条件を満たしているかが分かる……というのは言われてみれば分かるが思いつかなかった。

G - Minimum Permutation

 (デバッグでWAのテストケースを探すとき他の人のコードは見たけれど)解説は見ずにAC。

 一番はじめにおける候補(その後に、今まで使った以外の全ての数字が登場している)のうち最も小さいものを採用……というのを繰り返していけば良い。
 解法はそれで良いが実装がやや面倒で、BITやセグ木を使った。

 実装難ではあるけれど、解法を思い付く難易度はFより簡単ですね。

 

2023年4月22日土曜日

Educational Codeforces Round 147 (Rated for Div. 2)

 Dまで。

コンテスト後のツイート

E. Rearrange Brackets

 貪欲で良いという解法ツイートを見てAC。

 "("と")"の距離が最も離れたものから消していけばOK。あるカッコを消すときのコストは、その外側にあるカッコ達の個数により決まるので、逆にいえば、内側にたくさんカッコを含むもの(つまり、"("と")"の距離が離れたもの)から消していけば良いということになる。