ラベル $3^N$のDP の投稿を表示しています。 すべての投稿を表示
ラベル $3^N$のDP の投稿を表示しています。 すべての投稿を表示

2024年11月9日土曜日

yukicoder contest 452

　一問も解けなかった。ずっと参加していたわけではないけど、Aに30分以上はかけたのにひどい。


No.2953 Maximum Right Triangle

　求めたい点Bの座標は(x,y) + k(-y,x)と表せると勘違いし、WAを重ねた。
　kが実数ならこれで良いのだが、kが整数なら、これで全ての格子点は表せない。gcdを考えなくてはいけないとコンテスト終了間際に気付いたが間に合わなかった。

No.2954 Calculation of Exponentiation

　たくさんWAを出した後にAC。
　こういう問題で、たくさん提出してACするのはあまり意味ない気もする。　

No.2955 Pizza Delivery Plan

　一応自力AC。

　巡回セールスマン問題のbit DPをした後、3^Nのbit DPをすれば良いと気付いた。しかし、forループの順番を間違えてWAを出してしまった。

No.2956 Substitute with Average

　一回WAを出したが、WAが出たtestcaseを見て正しい解法に気付きAC。

　累積和みたいなことをしたい（Zero-Sum Rangesみたいなことをしたい）けど上手くいかないかなぁ、と考えていたら、A_iが30以下という制約の意味が分かった。
　そこまであっていたのだから一回でACしたかったね。（A_iが左のいくつかの要素の平均になっている、ということしか考えておらず、右のいくつかの平均になっている場合を考えていなかった）
時刻: 0 件のコメント:
ラベル: ,

2024年8月2日金曜日

日本レジストリサービス（JPRS）プログラミングコンテスト2024#2（AtCoder Beginner Contest 364）

　Fまで六完。

コンテスト後のツイート

G - Last Major City

　解説AC。（解説放送も見た）

　最小シュタイナー木を履修した。分かってしまえば難しくない。Kが高々10というところから3^NのDPと気付ければ自力で思いつくことも可能だったか？


時刻: 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 件のコメント:
ラベル: , ,

2022年1月27日木曜日

AtCoder Beginner Contest 236

　Fまで六完。

コンテスト後のツイート

G - Good Vertices

　解説放送を見てAC。

　まず「頂点の移動を隣接行列で表そう」とすら全く考えなかった。難しいのはその後なのに……。
　その後のパートが難しいのだけど、行列累乗しようという気持ちになっていないためその難しさがよく分からず。

Ex - Distinct Multiples

　解説放送を見てAC。

　辺に関して包除原理を行う→$3^N$のDPに帰着という流れ。
　難しいが、各ステップは滅茶苦茶難しいわけではないので、素早く解く人がいるのも分かる。

　$3^N$のDPの実装に戸惑ったのは反省。
　同じものをダブルカウントしないため、「ある頂点を含むものだけ考える」などしなくてはいけない。（自分は、$p<p$ xor $i$と、「一方がそれを除いたものより小さい」と書いた）
　書いたことがあったのにここで戸惑ったのは反省。
時刻: 0 件のコメント:
ラベル: , , ,

2021年8月20日金曜日

AtCoder Beginner Contest 213

 　Eまで五完。


FはSA-ISを書かないとACできない。SA-ISを理解していないため後回し……。

G - Connectivity 2

　解説放送を聞いてAC。
　$3^N$のDPなのだけど、そこがポイントではなく、

・DP[S]=S内の辺についてみたとき、Sが連結になる場合の数

　とおいて上手くいくと気付くのが重要。

　こうおいてDPが回るというのも意外だし、これを使って答えが求められるというのもなかなか思いつかないし理解し辛い。

　なお、解説放送ではこれを使って答えをどう表すか、ということは前半の解説部分で話しておらずコードを書くところでそれに触れている。
　私は前半を見て理解したつもりになってコードを書きだしたもののそこで詰まり、結局解説放送後半部分も見ることになってしまった。DPの遷移と大体同じ考え方なのに、ピンと来なかったんだよねぇ……。

　ただ、こんな風に重複なく数える、というのは、部分文字列を走査するDPと考え方としては似ているか。
　重複なく数えるために「1と連結なもっとも小さい集合を見る」というのは、部分文字列を走査するDPで「次に現れる文字のうち一番近い文字を見る」というのと対応しているのだと思う。

H - Stroll

　解説放送を聞いてAC。
　分割統治FFTというのはこういう処理なのですね。

　解説放送では自己ループのみがある場合で説明しているため、道がたくさんある場合でどうすれば良いかちょっと戸惑ったが、各道ごとに同じ処理を行えば良いということで納得した。

　なお、再帰で通常通り書いたらTLEしたため、他の人のコードのFFTの実装を見たら、配列の長さが小さい場合は直接計算しているようだったので、（FFTのライブラリ自体は書き換えずにDPの遷移の処理を）配列の長さで場合分けしたらACできた。

　FFTライブラリ自体を書き換えた方が後々のためには良いのだろうけど、どれくらいで分けるのが良いのだろう。AtCoderのライブラリでは、「畳み込む配列のうち小さい方が60以下かどうか」で場合分けしてそうだけど、自分の実装でもこれが良いのだろうか。
時刻: 0 件のコメント:
ラベル: , ,

2021年1月3日日曜日

AtCoder Beginner Contest 187

 　年も変わったし、コンテストへの参加記録を書いていきます！
　……といっても、コンテスト後、既に一日経っている。いつまで続けられるんでしょうか。


D - Choose Me

　何もしないと全員が青木氏に投票する。
　高橋氏が演説を行うと票がどれだけ動くか、と考えると、2*A+Bでソートすれば良いと分かる。

E - Through Path

　最初、全方位木DPが必要だと思い一旦飛ばした。
　Fを解いた後、やりたくないし書き終える自信がないけど、全方位木DPを書くかー、と書き始めたら、通常の木DPでいけることに気付いた。

　自然に書けば全方位木DP、「全体にxを足して、逆側からxずつ引く」ことを思いつけば普通の木DPでいける。

　とはいえ、全方位木DPでも書けるべき問題ですよね。

F - Close Group

　Nが小さいのでbit系を色々考えたが、しばらく思いつかず苦労した。
　「まず、完全グラフになっているものを列挙」を思いつけば、$4^N$のDPにはたどりつける。

　それが実は$3^N$になるというのは、この問題のsnukeさんの解説動画で覚えていた。難しい問題を解説ACしておいたのが役に立った！　と嬉しかったのですが、Educational DP Contestのこの問題もそうだったのですね。解いたはずなのに全く覚えていなかった……。



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