2022年4月25日月曜日

AtCoder Regular Contest 139

　A、Cの二完。

コンテスト後のツイート

B - Make N

　解説AC。

　計算量解析は難しいけれど、

・Y=min(Y, X*A), Z=min(Z, X*B)

　として、+Aや+Bをやる回数を探索するという方針は思いつけても良かった。これを10^5回程度（ちゃんと計算量解析すれば√Nで抑えられる）やればACできる。
　証明はできなくても、これくらい思いつけたんじゃないかと思う。反省。

D - Priority Queue 2

　解説放送を見てAC。

・最後にx以上の数が何個残っているか？

　を考えるのは典型処理。思いつくべきだった。

　その後の処理も典型といって良い気がする。DPの高速化と考えると多少発想が必要だけど、こういった問題では二項係数を使いそうなので、「x以上の数が何回出たか？」に着目するのは自然。

　ABCのG問題として出てもそれほど不思議はない（EXとして出たら簡単め）問題だと思う。コンテスト中解けなかったのは時間がなかったから仕方ないけれど、時間があれば解けるようにはしておきたい。
時刻: 0 件のコメント:
ラベル:

Codeforces Global Round 20

 　pretestはF1まで通ったけれどシステムテストでEが落ちた。Eが落ちた原因は二分探索の下限の設定ミスでした。nをn-1に直したら通りました。解法自体にも自信なかったから本質的なところで落ちたのかと思ったけど、くだらないミスだったのは悲しい。

コンテスト後のツイート

H. Zigu Zagu

　解説AC。"00"の個数と"11"の個数のうち大きい方らしい。

　「一回で消せるのはどこまで？」と考えると難しいけど、「一回では消せないのはどこ？」という風に考えれば思いつけない発想ではなかった。
時刻: 0 件のコメント:
ラベル:

2022年4月22日金曜日

Codeforces Round #784 (Div. 4)

　pretestは全完。

コンテスト後のツイート


　前回のDiv. 4はDiv. 3とあまり変わらない難易度に感じたけれど、今回はrated範囲に適切な難易度と感じました。
　これならまたあっても良さそう。
時刻: 0 件のコメント:
ラベル:

2022年4月19日火曜日

Codeforces Round #782 (Div. 2)

　Cまで三完。Dは難しい。


D. Reverse Sort Sum

　解説AC。

　コンテスト中は、A[i]=1となるindex iがあったとき、Cでプラスする箇所（n個）はどこか？　という方針でずっと考えていた。（この方針で解けるかは分からないが）解説の方針とは違っていた。

　解説の方針は、問題文のようにシミュレーションしたのを逆から見る、という方法。B[i]が何か（プラスになるindexはどこか？）というのを調べていく。
　ただ、この方針が取れれば簡単というわけでもなく、その後、A[i]=0ならB[i]が寄与するindexの最小値が一つ小さくなる、ということに気付かなくてはいけなかった。これも結構難しいと思う。

　考察重視の問題で、ARCとかで出てもおかしくなさそうに見えた。（Ratedなコンテストで出てたら厳しかった）
時刻: 0 件のコメント:
ラベル:

2022年4月17日日曜日

2022 TCO Algo Round 1A

　全完。

コンテスト後のツイート

　MedをMidと書き間違えたツイートを貼り付けるのはちょっと恥ずかしい。

　Medの解法が上のツイートみたいになるのは分かりにくいけど、AとBが違うので、遷移図を描けば、まあ多分そうか、と思えた。（が、改めて考えるとよく分かっていない気もしてきた……）
時刻: 0 件のコメント:
ラベル:

ユニークビジョンプログラミングコンテスト2022（AtCoder Beginner Contest 248）

　Eまで五完で終了。Fは誤読（というか、「連結」の定義を勘違い）でした。

コンテスト後のツイート

F - Keep Connect

　自力AC。
　連結というのを、残した全ての辺同士が繋がっていれば良いと勘違いしたため解けず。その勘違いのせいで、DPの遷移が大変になったため時間が残せなかったというのも大きい。

　正しい問題なら、最初に縦の線を取り除くかどうかを決めて、その後、コの字ごとに取り除くかを決めていくDPをするとすると、状態として最後の二点が連結かそうでないか、だけを持てば良いのですね。
　それなら遷移の式も簡単でした。

G - GCD cost on the tree

　解説放送を見てAC。
　約数による（包）除原理を使うというのは典型だけれど、「xの倍数のみからなる長さの和」を木DP（DFS）でを求められるというのが気付きにくい。

　解法も難しいけれど、TLEにならないよう実装するのが難し過ぎないですか？
　解法通り実装したつもりが、よく考えると二乗になっている……みたいなことが多いし、二乗になっていなくても、dictとかを使っているとTLEになりやすい。
　かなり苦労したけれど、setやdictを使いたくなるところで、できるだけ使わないようにしたらACできました。
　
時刻: 0 件のコメント:
ラベル:

2022年4月15日金曜日

AtCoder Regular Contest 137

　Dまで四完で、目標だったレート2200（二段）を達成しました！

コンテストへのリンク
コンテスト後のツイート


 E - Bakery

　解説AC。

　コンテスト中もフローだとは思ったが、最大流か最小費用流かも分からず、グラフが構築できなかった。

　今回は最小費用流。
　日にちを0日, 1日, 2日, …と並べてから考えると良かった。そういう数直線上でグラフを構築しようと思えたなら自力でグラフ構築できたかもしれない。

　今回の解説、解説放送で、最小循環費用流から負辺のない最小費用流へ言い換える部分も（まだ完全に理解できたとは言えないが）以前より少し理解できた気がする。



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

2022年4月12日火曜日

大和証券プログラミングコンテスト2022 Spring(AtCoder Regular Contest 138)

　AとCの二問しか解けず。

コンテスト後のツイート

B - 01 Generation

　解法ツイートを見てAC。
　コンテスト中は、実験メインで考えていたものの、「後ろから見る」という方針も一応考慮したのだが……。

　後ろから見ていくと、二つ操作ある操作のうち、二つ目、「末尾の0を除く」という操作を優先して行い、その後、「先頭の0を取り除いてflip」する、という操作が最適だと分かる。

　いや、言われてすぐピンとは来なかったのだが、「先頭の0を取り除いてflip」だけを行うとすると、これはAの先頭の0, 1, 0, 1,...がどれだけ続いているかだけで決まってしまうので、この操作を行う合間に、末尾はできるだけ取り除いた方が良い、となる。

　「操作に優先順位があるのでは？」と思い至れば、そんなに難しくなかった気もするが、コンテスト中は全く考えなかった……。

　実験したら、長さNのとき作れるPの種類数がフィボナッチ数になると分かって、そこから考察しようとしてしまった。いや、多分本当は、それを手がかりに解くこともできるんだろうけど、漸化式とか導けなかったんだよね。
　いまだになぜフィボナッチ数になるのか分かっていません。

D - Differ by K bits

　「基底」というキーワードを元にAC。

　この問題の方法（もしくは、グレイコード）で、K=1のときのときは作れる。それを改造すればKが他の値のときも解けそうなのだが、xorする値を、1(K=1)→7（K=3）のように隣りのbitを立てていくように変更するのでは上手くいかない。

　時間もなかったし、そこで困ってしまったのだが、何故上手くいかないのか？　と考えるのが大切だった。

　先の問題で上手くいくのは、(1<<i)たちが基底をなすからである。先の方法では、NとKのgcdが1でないとき、基底とならない。
　では、K個bitが立っているものたちで基底を取れれば、xorを取る値をそれらに変更することで構成できる。
時刻: 0 件のコメント:
ラベル:

2022年4月10日日曜日

Educational Codeforces Round 126 (Rated for Div. 2)

　pretestはDまで四完。

コンテスト後のツイート

　E、Fは問題文も読んでいないので後回し。
時刻: 0 件のコメント:
ラベル:

2022年4月9日土曜日

Codeforces Round #781 (Div. 2)

　Dまで四完。

コンテスト後のツイート

今のところEは解かなそう。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 338

　Dまで四完。Eが間に合わず終了。


No.1897 Sum of 2nd Max

　自力AC。コンテスト中も正しい方針を考えていたのだけど、詰め切れなかった。

　NとKの制約が両方$2*10^5$以下なので、どちらかしか全探索できないが、要素の総和を求める、ということなので、「あるxが大きい方から2番目になるような数列の個数」を考えた方が良さそう。
　その際、

・xより大きいものが一個、それ以外はx以下
・全てx以下

　の二通りに分け、前者からは「xが含まれない場合」を除く。後者からは「xが一個も含まれない場合」および「xが一個だけ含まれる場合」を除くと考えると計算できる。

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

2022年4月8日金曜日

AtCoder Beginner Contest 246

　Fまで六完。

コンテスト後のツイート

G - Game on Tree 3

　自力でAC。

　答で二分探索して判定問題にするのはこういう問題の定石。その後、どうやら葉から木DPしていけば良いと分かる。
　……が、その後を詰められなかった。

　「答えがx以上になるか？」という判定問題を考えるとき、例えば、根から整数x以上が書かれたノード2つと繋がっていればOK（答えはx以上）となる。
　根から1つだけ辺が出て、その頂点から整数x以上が書かれたノード3つと繋がっていればOK。

　そういう感じで考えると、頂点pに対して、

・DP[p]=1 if 頂点pに書かれた整数がx以上

　としておき、さらに、

・DP[p]+=DP[pの子達]の和 - 1

　とした感じになる。
　が、それだけではダメ（ここまではコンテスト中に考えられていた）で、

・「頂点pに書かれた整数がx以上」のとき、「DP[p]は少なくとも1になる」

　と気付くことが重要。

　式の説明・証明をしようと思えばできるんだけど、その説明を得るためにも実験しなくちゃいけなさそうなので、ギリギリの場合などを色々試して調べるしかなさそう。
時刻: 0 件のコメント:
ラベル:

2022年4月7日木曜日

yukicoder contest 281

　AB二完と冴えない結果。


No.1374 Absolute Game

　解説AC。
　解説を見ればその戦略が最適なことは理解できる。……が、直感的には今一つピンと来ていない。

　それぞれが取れる戦略は限られている（大きい方か小さい方か、どちらかから貪欲が最適であろうと予想できる）ので、そのいくつかを適当に書いてみれば無理矢理ACすることはできた気がするが、ちゃんとやるにはどうすれば良いんだろう。

　立式しようと思えば、解説のように立式するのはそう難しくないので、「とりあえず立式」案件かなぁ。
　こういうゲーム系の問題だと、今一つ立式しようという気になれないけど、立式した方が分かりやすいことが多いのかも。

No.1375 Divide and Update

　（今更だが）自力AC。

・配列Aに対して、l, rを選んで区間[l, r]をXに変更するという操作を行う。sum(A)を合計を最大にするのは？

　という問題を考えると、Aの各要素からXを引いて、累積和を使えば解ける。

　Aの要素を増やしながらこれができれば、さらに逆からYについて同様のことを行うことにより元の問題が解ける。
　これは、累積和の最大値を管理・更新してしながらAの要素を追加していけば良い。

　最初考えたときは、BITかセグ木かが必要な気がしたけど、そういったデータ構造を使わず累積和だけでACできたのはちょっと意外でした。

No.1378 Flattening

　AGCでほぼ同じ問題が出題された。AGCでは自力ACできて良かった。
時刻: 0 件のコメント:
ラベル:

2022年4月1日金曜日

Codeforces Round #780 (Div. 3)

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

コンテスト後のツイート


　F、セグ木を三本立ててやったけど、BITで良かったです。
　最初BITで書こうと思ったのに、ダメな気がしてセグ木にしたのはなぜだったんだろう。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)