2022年10月27日木曜日

AtCoder Regular Contest 148

　Dまで四完。このコンテスト終了時、AtCoderのAC数がちょうど3000になった。

コンテスト後のツイート

E - ≥ K

　解説放送を見てAC。

　数列Aを小さい順、もしくは大きい順に見て、DPか何かで計算……みたいな方針を考えたが、これだと上手くいかない。

　今回は、

・大きい方か、小さい方か、どちらかなら並べ方が一通りに定まる

　というもの。

　上から見れば/下から見ればOKというものではないので気付きにくく、違う方針を検討してしたくなるけれど、こういう風に「上手い順番で見れば計算できる」こともあると押さえておこう。
　
時刻: 0 件のコメント:
ラベル:

2022年10月24日月曜日

Codeforces Round #829 (Div. 1)

　Cまで三完。Dは解法はあっていたけど制限時間が厳しく通せなかった。

コンテスト後のツイート

D. The Beach

　自力AC。
　ツイートした通りで、空きマスから適切にダイクストラをすれば良い。

　コンテスト後、Rustで通したが、書くのに30分以上かかっている。もう少し速く書けるようになりたいね。PyPyで通している人はいるけど、ちょっと技巧的な気もするし、それでもギリギリなので、他言語への書き換えが素早くできると良かった。

　このコンテストは、based on Moscow Team Olympiadということなので、PyPyじゃ制限が厳しい問題が出題される可能性は高いと思っていた。この問題は制約を見ればPyPyでは厳しそうと分かる。Rustで時間内に書き切る自信があればRustで書こうとしたはずなので、もうちょっと慣れて、速く書けるようになりたい。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 365

　調子が良くなかったとはいえ、一問も解けずに終わった。復習しましょう。


No.2103 ±1s Game

　解説AC。

　（コンテスト終了後）解説とほぼ同じことも考えたのだが、それで良いのか確信が持てずに愚直を書いたりしていた。

No.2104 Multiply-Add

　解法は自力で分かった。

　ユークリッドの互除法の要領で(a, b)→(x, 0)に、(c, d)→(y, 0)にしたとき、xとyが一致していればOK。(a, b)→(x, 0)→(c, d)のように変形すれば良い。

　ただ、最初から片方が0のときの場合を考えておらずWAを出してしまった（テストケースを見て気付いた）。気を付けねば。
時刻: 0 件のコメント:
ラベル:

キーエンスプログラミングコンテスト2022（AtCoder Beginner Contest 274）

　Eまで五完。

コンテスト後のツイート

F - Fishing

　一応、自力AC。

　イベントソートという方針は合っていたが、同時に出入りがあったり、0秒ちょうどに出ていくものを忘れていたりしていた。

　また、PyPyで通すのは結構厳しく、FractionをソートしたりしてはTLEが取れない。出入りする時間にある程度大きな整数をかけて誤差を小さくし、tupleを一次元化してからソートしたら通った。

G - Security Camera 3

　解説放送を見てAC。

　コンテスト中、フローだと思ったし、「燃やす埋める」のスライドなどを見に行ったりしたがグラフを構築できなくて、うーん。

　ただ、この問題は、二部グラフの最小点被覆と見るのが分かりやすかったか。けんちょんさんのqiitaの内容はしっかり抑えたい。

　また、グラフ構築の際、

・何を頂点にし、何を辺にするか

　を考え、

・上手くいかなかったら逆（今まで頂点にしていたものを辺に、辺にしていたものを頂点に）も試してみる

　などをすれば解けた気もする。

　類題を解いておこうと思って、これを解いたが（一応、解説は見ないで解けたが）かなり苦戦した。フローのグラフ構築は難しい。
時刻: 0 件のコメント:
ラベル: , ,

2022年10月21日金曜日

パナソニックグループプログラミングコンテスト2022（AtCoder Beginner Contest 273）

　Eまで五完。実装難の問題が多くて辛かった。

コンテスト後のツイート


F - Hammer 2

　解説AC。

　区間DPらしい……確かに！
　区間DPと言われれば解けた。DPだろうとは思ったのに、区間DPを思いつかなかったのひどい。
　実装が間に合わなかったのなら仕方ないけど、解法を思いつかなかったのはまずい。

G - Row Column Sums 2

　DPだというツイートを見て、冷静に考えたら解けた。

　上の行から見て、残りの行についての和が0の個数、1の個数、2の個数を持てば良さそうだが、ちょっと考えれば「残りの行についての和が1の個数」だけ持って、残りの和がいくつかを管理すればDPが回ることが分かる。
　これで計算量が二乗になる。

　Nの制約からDPを考えるのは自然だし、RやCが2以下という制約から、それぞれの個数を持ちたいと思うのも自然ですね。
時刻: 0 件のコメント:
ラベル:

2022年10月20日木曜日

AtCoder Regular Contest 151

　ABの二完で終わり、レートを大きく落とした。B・Cで答えが合わず、愚直を書くのに時間を費やしたりしているのが厳しい。

コンテスト後のツイート

C - 01 Game

　自力AC。

　実験などして、同じ数字に挟まれている部分はturnが奇数個、別の数字に挟まれている部分はturnが偶数個増えることは分かった。

　なので、あとは両端について分かれば良い。
　真似っ子戦略ができそうだが、今一つ分からず愚直コードを書いたら、

・両端以外のturnが偶数個のときは、両端の空きマスが同じ個数のときのみ後手の勝利
・両端以外のturnが偶数個のときは、両端の空きマスの個数が1個差で、大きい方が奇数個のときのみ後手勝利

　と分かった。
　前者は真似っ子戦略を考えれば当然。
　後者は両端を「二個以上減らすことはできるけど、一個減らすことはできない」ことを使う。同じ数字を隣におけないため、一個減らそうと思っても不可能なのだ。
　なので、二個減らす回数の偶奇により、勝者が変わることになる。

　本番は、後者のとき、「両端の空きマスの個数が1個差」であれば後手が勝利していると勘違い（実験コードの分析を間違った。上記の理屈にも気付かなかった）したためWAが一個出てACできず。

　これは時間がなくて焦っていたせいですね。もうちょっと余裕があればACにたどりつけてそう。

D - Binary Representations and Queries 

　解説AC。

　問題内容を把握するのに時間がかかってしまい、解説を読んでも「なんでこんなに解かれるの？」という気持ちだったが、多少整理すると「確かにそこまで難しくないか」とも思えてきた。

・Xが異なればクエリの順番を入れ替えてもOK

　と気付くのが重要。
　これは、言われれば確かにそうか、という気持ちになる。

　これさえ気付ければ、各Xのクエリは二者で足し合うだけなので、最初の数字を1としてシミュレーションすれば良い。

E - Keep Being Substring

　解説AC。

・XとYに共通部分がある→一番長い共通部分をsuffix arrayとLCP配列を使って探す
・XとYに共通部分がない→一文字にした後、Yのどれかの文字へ変形するのが最適。最短経路問題になる。

　言われてみればそう難しくない。

　ただ、一番目について、同じことを考えたのだが、最長の共通部分の求め方が分からなかったし、解説を読んでもLCP配列が何かすぐに思い出せなかった。文字列アルゴリズムは適宜使えるようにしておきたい。
時刻: 0 件のコメント:
ラベル:

2022年10月19日水曜日

Codeforces Round #826 (Div. 3)

　Eまで五完。Rustで解いていたら、Dまででかなりの時間がかかってしまい、EからPyPyに。が、Fが解けずに終了。Fは考察から間違っていた。


F. Multi-Colored Segments

　一応自力ACした。

　[l, r, c]についてlでソートしたとき、最も大きいrと、それとは色が違うものの中で最も大きいrを管理する。
　……というようなことを二回（lについて左から、rについて右から）で解けると思ったのだけど、WAが出て困った。

　結局、l, rそれぞれについて、大きい順・小さい順でソートして、計四回似たようなことをしたらACしたが、それで良いのかよく理解していない。

G. Kirill and Company

　解説ACしたが、解説を理解するのにも、実装にも苦労した。

　まず、

・ある車を持っている友人のがいる頂点を使ったとき、どんな車のない友達の集合を運べるか？　という候補を知りたい。

　これは、BFSしながらDPして調べられる。
　DP配列としてはベキ集合を持つ。つまり、問題文の図にある頂点5なら、{{0, 1}, {0, 2}}を持つようにする。（0, 1, 2は車のない人のindex。たとえば1は2に住んでいる）
　BFSして、車のない人の家を通るたび、今までのDPの各集合にその人のindexを追加していく。
　なお、実装上は、{{0, 1}, {0, 2}}でなく、{3=(1<<0)|(1<<1), 5=(1<<0)|(1<<2)}を持った方が良い。

　これをした上で、

・車を持っていく人を順に見て、どんな集合に対処できるか？

　を見ていくDPをする。
　公式解説にあるように、これはbit DPというよりはナップザックDPに近い。

　
　解説を読んだ際、前者を処理した後どんなDPをすれば良いか分からず理解に時間がかかってしまった。自然なDPなのだが、bit DPだろう、と思っていると盲点になりやすいかもしれない。


時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)