問題リンク こんなド典型がDiv. 2 - Eで出るんですね 解説 交点が1つあるたびに長方形が1つできます。 ということで、これは明らかに平面操作をすればいいのでBITなどを利用して、などを管理して、程度で解けました 縦と横をぶった切ってるケースに注意 提出…

問題リンク 解説 複素平面上で考えると分かりやすいです。 複素平面上では距離の変更も回転も積であらわせます。 本質的にクエリ0とクエリ1は同じです。 クエリ2は各ベクトルの和であるので、言い換えると複素数の和です。 よって、クエリ0とクエリ1は区間積…

問題リンク 解説 クエリ問題であるので、クエリ無しで解くことを考えましょう。 ある値が達成できるかどうかを考えます。 この時,、 としていいです。 そうすると、 のとき のとき とすればいいことに気づきます。 よって、最大値のみ注目すればいいので、が…

問題リンク 解説 まず、移動パターンは4通りしかありません。 かつ < →番目から一番近い以上のところに行く かつ < →番目に一番近い以上のところからくる かつ < →番目から一番近い以下のところに行く かつ < →番目に一番近い以下のところからくる なので、…

解法 問題文を言い換えると、 かつのようなペアが何個あるか数え上げる問題になる。 桁数が同じ数字を考えると、であるので、桁数が異なる場合だけ考えればいい とすると、桁数がと ()のような上記の条件を満たす整数の組み合わせは簡単な算数で求められる。…

問題リンク 解説 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に似たような発想の問題があった気がします。 球を移動する場合は中心を結んだ線分を通るのが最短…

問題リンク 解説 prefixのxorの累積は制約からせいぜい1024通りしかありません。 よってA - Zero-Sum Rangesと同様の方法で、各値について何通りあるかを求めることができます。 計算量はです(定数？に1024がつきます) C++なら余裕を持って間に合います 提出…

問題リンク 解説 0が1つもない場合は逆元が存在するのでやるだけです。 0がある場合はもし塗りつぶしたので0が全て消えたのなら、0以外の全ての積から0以外の塗りつぶしたのを割りましょう。 全部きえてなければ0です。 以上で求めることができました。 提出…

問題リンク 解説 制約に森と書いています。ということでトポロジカル順にみていきましょう。 現在持っている値が正なら後に足していった方が得なのでつなげます。 負ならこれを足すと損なので、後回しにします。 復元はこの順番の管理をみればいいのでトポロ…

問題リンク 解説 葉から見ていきましょう。そうするとgood moodの人とbad moodの人の人数がそれぞれ一意に定まります。 上に登っていってる間はbad→goodにすることのみができ、このときgood - badは2増加します。 それをgood mood の人とbad moodの人が0以上…

問題リンク 落ちたので参考にしないでください(落としていただいた方ありがとうございます) 解説 明らかに線形計画法です。 Pythonのscipyにはシンプレックス法があるのでそれを貼ります。 これだけです。 落とすの頑張る人是非頑張ってみてください 提出コ…

問題リンク ごめんなさい！！のところ全く読んでなかったです。修正しました。 解説 DPで解きます。dpの定義を dp[i][j] := i番目まで見た時、j個分けている としましょう。こうしたとき、愚直にDPを遷移させると以下のようなコードになると思います。 もち…

問題リンク 解説 現状Fastestですのでその解説。 実はでこの問題を解くことができます。 詳しくはこの記事で jupiro.hatenablog.com 提出コード yukicoder.me