2023年9月29日金曜日

Codeforces Round 899 (Div. 2)

　Cまで三完。

コンテスト後のツイート

D. Tree XOR

　解法ツイートを見た。コンテスト中はbitごとに全方位木DPする方法しか思いつかなかったが、bitごとにやらずにできる。

　辺ごとの寄与を考える。辺に両端の頂点のxorを書き込んでおくと、その両端の二頂点を一致させるためには、「その値*葉の方の頂点の個数」のコストがかかる。これを全方位木DPで求めればOK。（さらにいうと、全方位木DPもいらないらしい）

　bitごとにやろうとしたときの全方位木DPはなかなか書きにくかったが、こちらの全方位木DPは実装も素直でした。
時刻: 0 件のコメント:
ラベル: ,

2023年9月28日木曜日

Educational Codeforces Round 155 (Rated for Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Interactive Game with Coloring

　解法ツイートを見た。
　高々三色で良いというのは良かったが、根から出ている枝ごとに、次の辺を1にするか2にすべきか調べなくてはいけなかった。

・子供が複数出ている頂点については、子供たちへの辺を同じ色にすれば良い。
・親が一つ、子供が一つの頂点は、三色で塗るなら、1→2→3→1……と次数順に塗っていけばいい。
　二色で塗るなら、子供が一つの頂点全てについて、親への辺が1、子供への辺が2になるようにする。それが可能なのかを調べる。
時刻: 0 件のコメント:
ラベル:

2023年9月26日火曜日

サントリープログラミングコンテスト2023（AtCoder Beginner Contest 321）

　Fまで六完だが遅かったりペナが多かったりで黄色に戻れず。Fは形式的ベキ級数を考えたのは良いのだけど、「注文の多い高橋商店」と同じ問題かと思ったらもっと簡単なDP（形式的ベキ級数で言うなら、簡単な式の掛け算、割り算）だったんですよね。もっと落ち着いてDPの式を考えないと。

コンテスト後のツイート

G - Electric Circuit

　解説放送を見てAC。$3^N$のbit DPだとは思ったが、正しい解法にたどりつけなかった。

　集合iに対して、DP[i]=iが連結成分になる場合の数と定義したとき、DP[i]を求めるところで何を引けばいいか分かっていなかった。

　まず、内部でいくつかの連結成分に分かれているかどうかは考慮せずにDPの値を求めておく。そこから$3^N$のbit DPを使って値を引いていく。

　$i=j\cup k$と表せるとき、DP[j]*DP[k]（ではないが、そのようなもの）を引くわけだが、全ての部分集合に対してこれを引くと二重に引かれる部分が出てしまう。iに属するある頂点xを定め、xを含むようなjに対して、DP[j]*DP[i/j]……ではなく、DP[j]*（i/jが一つの連結成分になっていなくても良いが、その外との辺はないような場合の数）を引いていかなくてはいけない。

　（i/jが一つの連結成分になっていなくても良いが、その外との辺はないような場合の数）は、「引く前のDPの値」なので、既に求まっている。

　解法の大枠は分かっても、詰めるのは大変な問題でした。

　ただ、「同じものをダブルカウントしないため、「ある頂点を含むものだけ考える」などしなくてはいけない。」とは、この記事にも書いている。同じところで分からなくなったのは良くない。
時刻: 0 件のコメント:
ラベル: , ,

2023年9月23日土曜日

Codeforces Round 898 (Div. 4)

　全完。あまり速くはなかったけど、普通に全完できて良かった。

コンテスト後のツイート



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

yukicoder contest 405 技術室奥プログラミングコンテスト#7 Day1

　A一完。


No.2480 Sequence Sum

　解説AC。

　全く思いつかなかった。
　1と2から作れる長さはいくつだろう（これは求められる）、そこからxとx+1で作れる個数も計算できないか？　などと考えていた。

　こういう考え方ではなく、作れない長さはいくつだろう？　と考えるべきだったんですね。

No.2481 Shiritori

　一応、自力AC。

　「aで終わってaで終わる単語」の個数を考えたら、先手が勝つ場合の勝つ方法は分かった。それ以外で後手必勝ということが分からなかったけど、投げてみたらAC。
　解説を読んだら、後手が勝つ方法も簡単（先手の場合とほぼ同じ）でした。

No.2482 Sandglasses

　解説AC。

　あまり考えずに解説を見てしまったが、有名問題の解法を使ってすっきり解ける問題だった。これは自力で解きたかった。
時刻: 0 件のコメント:
ラベル:

2023年9月22日金曜日

THIRD プログラミングコンテスト 2023 アルゴ（AtCoder Beginner Contest 318）

　Fまで六完。

コンテスト後のツイート

G - Typical Path Problem

　フローだという情報を得てAC。

　フローだと言われれば、解くのは難しくない（頂点数を倍にするところで引っかかったけど）し、フローにしか見えなくなる。
　けど、こういうグラフの問題をフローで解いた経験がなかったのでちょっとびっくりでした。
時刻: 0 件のコメント:
ラベル: ,

2023年9月21日木曜日

トヨタ自動車プログラミングコンテスト2023#5(AtCoder Beginner Contest 320)

　Fまで六完。

コンテスト後のツイート

G - Slot Strategy 2 (Hard)

　解説放送を見てAC。コンテスト中フローじゃないかとは思ったけど、二部マッチングに帰着できると気付いていなかったので何も惜しくなかった。

・各数字について考え、二分探索するとフロー（二部マッチング）になる。
・時刻の個数が問題だが、各リールについて高々N個だけ考えて良い。

　一つ目は思いつくべき内容で、それを思い付いていなかったのはいけない。二つ目は難しいが、計算量を落とそうと試行錯誤していれば思いつくかもしれない。

　なお、二分探索のNGをN-1と設定してWAをくらった。0秒後から始まるので、NG=N-2と設定しなくてはいけない。機械的にNG=-1とかしていれば問題ないが、下限を見積もろうとするとやってしまいやすいミスかと思う。
時刻: 0 件のコメント:
ラベル:

2023年9月20日水曜日

AtCoder Regular Contest 165

　Cまで三完だが、解くのが遅くペナルティをたくさん出したため青に落ちる。最近ケアレスミスが多い。

コンテスト後のツイート

D - Substring Comparison

　解説放送を見てAC。

　SCCを作る方針はあっていたが、一回のSCCでやる方針を考えていた。
　最初の文字から比較していくという方針は辞書順という条件を思えばとても自然（コンテスト中もまずはそれを考えたと思う）。ただ、何度もSCC作りを行って良いというのが思いつきにくいですね。

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

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

　遅解き四完。前半で苦労したのが響きレート-115。Eを解けなかったのはまあまあ仕方ないが……。最近、序盤のミスが目立つなぁ。

コンテスト後のツイート

E. Another MEX Problem

　解法ツイートを見てAC。
　DPを考えたのだが、区間DPを考えたのが失敗。左から順に作っていけば良かった。その上で、考えるべき遷移の個数が抑えられることが難しい。

　DP。左から作っていったとき最速でその数字を作れるかを判定していけば良い。
　遷移に使う[l, r]は、[l, r]が最も短いものを選べば良い。この個数はO(n)個に抑えられる。

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

2023年9月16日土曜日

yukicoder contest 404

　ABの二完。


No.2462 七人カノン

　解説AC。全然思いつかなかった……。

・ある時刻に何人演奏しているか？　はimos法を使えば求まる。
・それ（の累積和）を使えば、各クエリについて目立ち度の増加分が求まる。

　言われてみれば簡単。

　一気に考えようとせずに、「何人演奏しているか？」と「目立ち度の計算」を別々に求めようと考えなくてはいけませんでした。

No.2463 ストレートフラッシュ

　解説AC。

　何かしらのDPだろうと考えたが違っていた。制約から考えても、ストレートフラッシュの種類を決め打つのは自然。思いつかなくてはいけないなぁ。
時刻: 0 件のコメント:
ラベル:

2023年9月15日金曜日

AtCoder Beginner Contest 319

　Eまで五完。黄色に戻れず悲しい。
　Gは大量ペナを出したが22:40ちょうどに通った。あと一秒早ければ黄色に戻れたのに……。


F - Fighter Takahashi 

　bit DPだという解法ツイートを（たまたま）見てAC。

　bit DPだと分かれば特に難しいところはない。ただ、実装は大変。

G - Counting Shortest Paths

　コンテスト中考えていた（そして、22:40ちょうどにACした）解法は嘘解法だと思ったが、改めて考えるとそうでもないのかも？

　Nが小さい場合は普通にやらうとして、Nが大きい場合。

　startとgoalからBFSしていくと、それぞれstartからi歩でいける頂点Q、goalからj歩でいける頂点Q2が得られる。len(Q)*len(Q2)がMより大きいとき、必ずそこは一歩でいけるので、len(Q)*len(Q2)から、「Q中の頂点からQ2中の頂点へ辺が引かれているもの」を引けば良い。

　これで上手くいかないのは、ちゃんとDPしなくてはいけない場合、つまり、ある頂点を通る最短経路が二つ以上存在する場合だけれど、そういうのはNが小さい場合でないと起こらないんじゃないだろうか？

　ちゃんと考えるとよく分からなくなってきた。やはり正しい解法で解きましょう。
時刻: 0 件のコメント:
ラベル:

2023年9月3日日曜日

yukicoder contest 403

　ABDの三完。


No.2452 Incline

　hiro1729さんの解説を見てAC。
　floor sumが必要になりそうなことは分かり、「A（傾き）が負だった場合の式」の導出まではできていたのだがそこからどうすれば良いか分からなかった。

　この解説を読むと、floor sumのライブラリを少しいじるだけでAが負の場合にも対応できることが分かる。実際そう直したらACできた。

　なぜそれで良いのか分からなかったが、改めてkyopro_friendsさんのfloor sumの解説を読んだらこれで良いことが理解できた。

　公式解説はfloor sumを使っていないようですが、それはそれで難しい。

No.2454 Former < Latter

　suffix arrayを使おうとしたが上手くいかず失敗。Z algorithmを使うという情報を得てAC。

　文字列アルゴリズムの内容はちゃんと把握しておかなくてはまずい。
時刻: 0 件のコメント:
ラベル: ,

2023年9月2日土曜日

Educational Codeforces Round 154 (Rated for Div. 2)

　Dまで。

コンテスト後のツイート

E. Non-Intersecting Subpermutations

　解法ツイートを見てAC。解けなくてはいけない難易度だった。

　結構シンプルなDPだった。今の文字までの連続部分列を見たとき、最大何個重複しない数字を取れるか？　を持てば良い。
　一応、累積和が必要になるけど難しくない。
時刻: 0 件のコメント:
ラベル:

2023年9月1日金曜日

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

　Eまで五完。

コンテスト後のツイート

F - Flip Machines

　解説を読み、bit DPのところが分からず解説放送を見てAC。

　X_jとY_jが異なるようなマシンを起動すると、それらのカードにおいて期待値は表裏の平均になる……というのは言われれば分かるがパッと思いつくのは難しい。

　だが、その後の方がもっと難しい。マシーン全探索で答えが求まるのは分かるが、それでは計算量が無理。
　Nが40以下というのを利用するだろうと予想できるが、「裏が表より大きいもの」と「裏が表より小さいもの」と分けて、

・「裏が表より小さいもの」につながるいくつかのマシーンを起動したとき、いくら儲かるか?　を考えると貪欲に取れる

　ということにまず気付かなくてはいけない。これで、「裏が表より小さいもの」がNの半分より少ないときは間に合う。

　あとは、「裏が表より大きいもの」が少ないときを考えれば良い。（と、二つに分けて考えるのがまず難しいのだが）

　こちらの場合は、bit DPを使う。「裏が表より大きいもの」の集合Sを考え、そのときの損の最小値はいくらか？　というのをDP[S]でもつ。そのDPテーブルを、「裏が表より小さいもの」一つずつを見て更新していけば良い。


　解説を見て理解する分には難しくないのだが、実際に解くのは大変に感じる。

G - Redistribution of Piles

　自力AC。

　できることが、何回か減らしてから増やす、しかないので、ある減らした状態から何回増やせるかを考えれば良い。
　そうするとfloor sumを使いそうな式になるので、この公式（？）が使える形に変形するとACできた。

　ただ、自力ACとは書いたけど、最近のコンテストでfloor sumを使う問題が出たという記憶に残っていたから解けただけかもしれない……。
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)