手元にいくつかのスイッチがあり、各スイッチはいくつかのランプにつながっている。手元にあるスイッチを押して全部のランプをつけることができるか判定せよ。ついているランプは消えることが無いので、スイッチを全部押してしまいましょう。自分はboolの配列を使ってランプがついているか判定させましたが、setを使って入れていくor取り除く方法も簡潔そうです。Hedgehog問題概要ハリネズミは胴体と針で構成されていて、胴体は頭から尾までグラフ上の頂点が単調増加な路、針はハリネズミの尾から伸びる長さ1の道である。ハリネズミの美しさが(胴体に含まれる頂点数)×(針の数)の時、最も美しいハリネズミの美しさを答えよ。胴体に含まれる頂点数とその頂点に含まれる針の数を別々に考えます。]胴体は頭から尾まで単調に増加します。よって頂点1から頂点Nまでループを回し、その中でつながっている頂点の番号が今見ている番号より大きいなら繋がっている頂点を尾とした時の胴体に含まれる頂点数=max(そのまま、今見てる頂点を尾とした時の胴体+1)と更新していけばOKです。頂点iを尾とした時の針の数は頂点iに接続している頂点数に等しいです。あとはこれらの積の最大値を求めればOKです。0;}自分は頂点番号の小さい→大きいへ有向辺を張って、「その頂点への最も長い道の長さ」を求めてました。文字列s,tが与えられる。sの部分列とそれを反転したものを組み合わせてtを作りたい。最小でいくつの部分列を足せば良いか。s="abcdbcde",t="abcde"のとき、答えは2ですが、1通りではありません。"abcd"+"e","abc"+"de","ab"+"cde","a"+"bcde"のどれでも正解です。ここでは最初に貪欲に選ぶ手法を取って行きましょう。tのi文字目を見ているときに、何文字先に進めるのか、というDPをすれば通るのかなぁ...と思いやってみたらO(|S||T|min(|S|,|T|))。ローリングハッシュとかも浮かんだけど、実装したことない。そのままタイムアップでした。いうことでkmjpさんの解説を拝見。自分はDPを1次元でやりましたが、2次元で「tのi文字目、sのj文字目を先頭とする文字列が何文字一致するのか」を求めるのが正解のようです。LCSとか久しぶりに聞きました。LCAと見間違えます。その後、tを1文字目から再現していくのですが、i文字目以降が作られていない時、先ほどの配列からtがi文字目の時、ループを回してsが何文字目から始まる時最も先へ進めるのかを調べます。1文字も先へ進めない時はtを作ることは出来ません。0;}文字列操作に弱い自覚はあるけど、何とかしておきたい。巨大な数を素因数分解した後の積を数列として与えるので、元の数の約数全てをかけ合わせたものを1e9+7で割った余りを求めてください。Codeforces解説これも「各因数毎に何回かけるのか」が分かれば簡単だよな...とか思いつつやっていました。それ以降思いつきませんでした。C同様kmjpさんの解説を拝見。数列を整理し、p[i]^q[i]という表示形式にします。ここで、p[i]^1を含む(p[i]^2以降は含めない)は全体の積の中でp[i]を用いない積の総数、つまりj!=iでの(q[j]+1)の積(=Q[i]とします)になります。+1)/2回かけられています。(長いのでP[i]とします)後はp[i]^P[i]を答えにかけ合わせればいいのですが、Q[i]はそのまま計算すると最大20万20万なのでオーバーフローします。m)となるので、P[i]はm-1でのmodを取ってあげれば良さそうです。同様にQ[i]もm-1でmodを取ります。mは素数なので確実にフェルマーの小定理が成り立つのですが、m-1は偶数なのでほとんど成り立ちません。するとQ[i]を求めるときに「先に全体の積を求めておいて、そこから(q[i]+1)で割る」という方法が取れません。m)より、am-2と1/aが同じ役割を果たします)そこで、L[i]:(q[0]+1)〜(q[i-1]+1)の積、R[i]:(q[i+1]+1)〜(q[n-1]+1)の積とおいて、L[i]×R[i]=Q[i]とすればOKです。