ラベル 積の和典型 の投稿を表示しています。 すべての投稿を表示
ラベル 積の和典型 の投稿を表示しています。 すべての投稿を表示

2026年1月18日日曜日

AtCoder Regular Contest 182

　ABの二完だが、レートは上がった。

コンテスト後のツイート


C - Sum of Number of Divisors of Product

　解説AC。
　積の和典型の練習をしようと思って解こうとしたが難しく、解説を読んでもしばらく理解できず非常に苦労した。

　公式解説のように積の和典型を適用すると、タワーと積み木の問題と同等になることは分かる。しかし、それがbit DPで表せることが分からなかった。（ChatGPTに聞いたりしつつ悩んだ）

・どこかで積み木を選ぶのだから、積み木を置いたそのときに選べば良い

　と考えると理解できた。
　たとえば、「6」の積み木を置くとき、それは、2と3の位置に積み木を一個ずつ選ぶことを意味する。
　そして、それまでに2の位置や3の位置の積み木を選んでなかったとしたら、このときに選べば良い。
　その、既に選んだかどうかでbit DPをしている。

　また、最初に積み木が一個ずつ置いてあり、それを選んでも良いので、bit DPの初期値は全て1になる。

　こういう考え方でDPを書いたものが、この提出。これを行列累乗で高速化するとACできる。



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

2026年1月14日水曜日

AtCoder Regular Contest 212 (Div. 2)

　ABDの三完。

コンテスト後のツイート

C - ABS Ball 

　解説放送を見てAC。

　積の和典型と言われても全然ピンと来ないし、積の和典型の解法自体も忘れているしで全然ダメでした。

　というか、最初この問題を見たとき、積の和典型を使うのでは？　と思ったはずなのに、苦手意識があるせいか、そう思ったことを忘れてDPを考えていたのもダメ。もっと練習した方が良さそう。







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

2025年3月30日日曜日

AtCoder Beginner Contest 399

 　Eまで。

コンテスト後のツイート

F - Range Power Sum

　解説AC。

　「積の和典型」とも呼ばれる、組み合わせに帰着して解く問題。この解法、何度見ても解けるようにならないのだが……。
　コンテスト中に「積の和典型」で検索したのに解けておらず、辛い。





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

2023年2月11日土曜日

yukicoder contest 376

 　Dまで四完。


No.2212 One XOR Matrix

　解説ツイートを見てAC。

　sampleから再帰的に構成しようとは思ったのだが、構成方法が思いつかなかった。

・縦横のxorが0になる4*4行列はすぐに見つかる

　ことを利用して、sampleのものと二つで構成しようと考えると良かった。
　sampleのようなxorが1になるようなものを左上、右下に。0になるものをそれ以外におき、上の桁は適当に作れば条件を満たす。

No.2213 Neq Move

　一応自力AC。

　適切にDFSしたら通ったが、実装に時間がかかったし、一回WAも出してしまった。

No.2214 Products on Tree

　解説AC。

・積の和は計算しにくいので、組み合わせの問題に味方を変える

　は典型だが、どう読み替えればいいのか、なかなかコツが掴めない。
　その後の木DPの遷移は自力で考えたが、遷移を導くまで苦労してしまったのは反省。
時刻: 0 件のコメント:
ラベル: ,

2022年11月12日土曜日

大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)

　Eまで五完。

コンテスト後のツイート

F - Sorting a Matrix

　解説AC。

　行については、最小値・最大値を見てソートするのはOK。
　その後、列について考えるとき、ある行の二つの列で大小関係があるときに辺を張り、ループしたらダメ、としたい。が、辺の本数が多くなりそうで困っていた。

　こういうとき使うのが、超頂点を加える手法ですね。
　ただ、最近、この問題で使った方法とは超頂点の使い方が違うのが難しい。「同じ数字たちをまとめるために超頂点を使う」という手法はなじみがなかった。
　（とはいえ、超頂点を使うこと自体を考えなかったのはダメ）

　なお、答が一致した後もTLEを取るために苦戦した。

G - Random Walk to Millionaire

　解説放送を見てAC。

　Xの二乗とは何か？　と考えたとき、「どこでレベルアップしたか？」の組み合わせと考えてDPへ持ち込む。
　考え方は分かるのだけど、この問題でこの手法を使うとは。

　ただ、この問題ではDPくらいしかやりようがないし、DPを高速化しようと思ったらXの二乗というところを上手く使うしかない。そう思えば、この変形をするしかない、と考えるのは自然だとは思う。

　しかし、元々積で与えられているものを分けて考えるというのはピンと来なくて。難しい。
時刻: 0 件のコメント:
ラベル: , ,

2021年7月27日火曜日

AtCoder Regular Contest 124

　Cまで三完。


D - Yet Another Sorting Problem

　解説は見たものの、さっとは理解できなかったため、参考にして実験してAC。

　グラフの問題だと思ったし、連結成分に注目するのかな？　とは疑ったものの、確信が持てず捨ててしまった。
　連結成分ごとにサイクルになる、ということに気付いてなかったのは問題。気付けば当たり前だけど、ここが考察の第一歩だったと思う。

　その後の考察はどうすれば良かったか難しい……。

　確かに、「左側/右側だけのサイクル」は「左右両方の側に要素があるサイクル」よりコストがかかるのは分かる。
　具体的には、後者は、連結成分のノード数-1回操作すれば良いが、前者はノード数+1回操作しなくてはいけない。

　ただ、サイクルごとに完結するのではないのが難しい。
　「左側だけのサイクル」と「右側だけのサイクル」が両方あった場合、前者の操作途中で後者の処理をすることにより、後者をノード数-1で済ませられる……というのが本質だった。
　逆に、「左側だけのサイクル」が複数あっても、それぞれの操作が干渉しないため、操作回数を減らすことはできない。
　なので、max(「左側だけのサイクル」の個数, 「右側だけのサイクル」の個数)だけ、操作回数が増えるものがある、ということになる。

　コンテスト中は、「左側だけの連結成分」と「右側だけの連結成分」（コンテスト中は連結成分がサイクルになると気付いてなかったのでこう書いています）が干渉することがある、ということは、連結成分ごとに見る方針は間違っているのでは？　と思ってしまい、考察を進めることができなかった。

　解法を見ても、試行錯誤するしかないかなぁ、という気もするので何を反省すべきか難しい。
　思いつけてない何かがあったというわけではなく、どれが正しい方針か分からなかったという感じだし。

　愚直solverを書いていたら多少違ったかもしれないけれど、決定打にはならなそうだし、どう実装すれば良いかもちょっと迷ってしまう。さっと書けるなら書いていたと思うので。

　うーん。
　書くなら、順列同士で、一回の操作で行けるもの同士にedgeをつけて、ソートされたものからBFSする感じか。これでN+Mが9あたりまでは判定できるなら、実装する価値はあったかも。

E - Pass to Next

　解説AC。
　積の和典型の練習ということで解いたが、積の和典型を使うと分かっても自力で解けず、解説を見ても理解するのに苦労した。積の和典型を使う問題って難し過ぎないか？


・隣の人に渡すボールの数をCとしたとき、min(C)=0の場合を考えると重複を省ける
・積の和典型を使いたい
・A[i]の玉を自分と隣に分けるとき、そのうち自分の玉を選ぶか？　隣の人の玉を選ぶか？　を考えるとDPにできる

　というあたりを考えると解ける。

　積の和典型を応用する問題で重要なのは、いつ玉を選ぶか？　ということのようだ。そこは押さえておこう。

　

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