2020-08-01から1ヶ月間の記事一覧
問題リンク 解説 2色で同じ色に塗る場所と異なる色で塗る場所が指定されるので、それを満たすように塗ることができるかという問題です。 noshi91.hatenablog.com そうすると、これとほぼ同じやり方で解くことができました。 実装も楽だね 提出コード onlinej…
問題リンク 解説 半径に明らかに単調性があるので二分探索します。 以下、半径をとします。この時、円の方程式は中心をとすると、 になります。 ある点が円の内部にある条件は、 となります。 よって、全てのの区間を含むようなが存在するかを調べると二部探…
7Hackする
そういや書くの忘れてた なれたらしい 3691ACです。
問題リンク かなり典型だと思うのですが、詰まってる人が多かったので 解説 dp[i] := 番目まで見た時の最大値としましょう。 番目を取るときは、 です。取らないときは番目から個以上を消すことができるので、 です。よって番目までのdpの最大値を管理しなが…
問題リンク 解説 の組み合わせとして全て考えられるものを全探索します。 今回のグラフは出次数が全部1でかつ、全ての頂点でループを作らないといけないことから、入次数も全て1でないといけません。 もう少し突っ込むと入次数が2以上のが1つでも存在すると…
問題リンク 解説 以下の素数をエラトステネスの篩などで列挙します。 各素数ごとに、の整数が何個素因数として持つかをチェックしていきましょう。 最後に割った後にまだ1より大きな値を持っていれば、その数は素数なのでカウントするのを忘れずに 提出コード…
問題リンク 解説 文字列を削除して作っていくので、文字列長が小さいほうから見ていきましょう。 文字の文字列から文字の文字列を作る場合、 までにが登場している である であればつくれます。 あとはRolling Hashで文字列を管理すれば解けました 提出コード…
問題リンク 解説 まず、のときは-1です。理由は簡単で、 みたいな1辺が2の正方形が4つ集まると1辺が4の正方形は偶数になるからです。 以下とします。 そうすると、であるので高々状態は8個しかなく、dpをすれば求めることができました。 提出コード
問題リンク Hyado君が解いていたので 解説 重さを昇順にして、としよう。 この時、 (絶対使うものは何もない) ]を作る (は絶対使う) ]を作る (は絶対使う) ]を作る という風にしていけば、重複なく数え上げることができる。 区間の数え上げは重さを後述にみ…
問題リンク 解説 まず2が可能かどうかを確認しましょう。可能なら2です。 以下、2では間は移動できないものとします。 2より大きい素数はすべて奇数であることに注意しましょう。 ここで、間に奇数で行く経路がなければ、-1です。 そうでなければ、を奇数で…
問題リンク 人々はおすすめするような素晴らしい問題らしいが、こういうのはクエリ平方分割で常勝ｗ！ 解説 クエリ平方分割をします。 クエリがバケットサイズを超えたら、多始点BFSの要領で更新していきます(深いほうのみに潜っていくようにしましょう) 残…
問題リンク 解説 橙のところに注目して解いていきます。 以下、レベルという概念を導入します。↑の例だとレベルが2, 3, 1みたいな感じです(雰囲気伝われ) さて、こうすると、がレベルになる条件を考えると、 から右に同じ文字が個以上続く がレベル以上 がレ…
問題リンク 解説 制約が小さいのでimos法で全探索して間に合います。 こういう入力はscanfが受け取りやすくていいね 提出コード onlinejudge.u-aizu.ac.jp
問題リンク E1とさほど難易度差がないように感じたんだけど、片方のみ解けてる人が多くいてびっくり 解説 コストが同じ場合はE1で貪欲でいいことは分かってるものとします。 そうすると、コスト1のみ使う場合とコスト2のみ使う場合それぞれについては貪欲で…
問題リンク 100位切れたのはうれしいね 解説 見た目が区間dpと書いてあるので、まずは区間dpを定義します。 にあるセグメントの数の最大値 そうすると右端をソートして(右端が同じ場合左端が右にあるものから)左から見ていきます。 そうすると、セグメントが…
問題リンク なんか時間かかった。 解説 制約があほみたいに小さいので、として考えられるものを全て列挙しましょう。 その後、Qにおけるインデントを全て調べ、uniqueに決まるかを調べるだけです 提出コード onlinejudge.u-aizu.ac.jp
問題リンク どうでもいいのですが、AOJのhttpsのほうを使っていきましょう運動をしています(AOJ-ICPCのリンクがhttpのほうなので仕方ないですが) 解説 AtCoderに似たような発想の問題があった気がします。 球を移動する場合は中心を結んだ線分を通るのが最短…
