問題 atcoder.jp 解法 問題を読んだ段階で、ソートを行うクエリをどう扱うか（普通にソートすると計算量くってTLEっぽい）がポイントと思われる。 そこで、次のように処理する。 キュー Q1と最小値を優先的に取り出す優先度付きキューQ2を用意して、クエリを…

問題 atcoder.jp 問題概要 長さLの木材がある．以下のQ個のクエリを処理せよ． i番目のクエリは(ci,xi)で与えられる． ci=1のとき：木材の左端からxiの地点で木材を切る． ci=2のとき：木材の左端からxiの地点を含む木材の長さを出力する． 1≤L≤109 1≤Q≤2×10…

問題 atcoder.jp 解法 問題を一見すると 「どの商品に何枚半額割引券を使えばよいか？」 という問題に見える。 だが半額割引券を1枚ずつ使っても結果は変わらない。 なので、 「一番値段が高い商品に1枚ずつ割引券を使う」 という貪欲法で解ける。 あとは、…

問題 atcoder.jp 解答 BFS(幅優先探索)で、あっさり解ける。 BFSの探索をかけて、ans[i]に部屋iの一個前の部屋番号を記録。 ansが一通り揃っているなら、"Yes"の後にまとめて表示。 感想 問題読んで、dfsかbfsだろうな？とは思うが、どっちだろう感ある。 は…

問題 atcoder.jp 解法 数列A, Bを、それぞれ先頭から何個目まで使用することができるか？という問題。 数列A, Bを、しゃくとり法で走査する。 数列Aはゼロから。 数列Bは最後尾から条件を満たす位置を走査して、最大値を調べる。 実装

問題 atcoder.jp 解法 数列 7, 77, 777, 7777, ....は 漸化式 10+7 で表現できる。 これはmod（余り）をとった値でも同様。 7%K の次の77%K も 10+7の関係にある。 それを利用して、K回この処理を繰り返せば、とりうる余りは１ループする。 この余りのループ…

問題 atcoder.jp 解法 数列Aの中のAiの倍数を配列fをつくって、あらかじめカウントしておく。 f[i]はIの約数の数が入る。 これができてしまえば、Aiの数値の約数はf[Ai]を参照すればわかる。 f[Ai]が1ならば、Aiの約数は自分自身しかないので、数列Aの中にAi…

問題 atcoder.jp 解法 1 〜 Nまでの約数を配列に保存する方針。 1の倍数、2の倍数、3の倍数……と各配列に1づつ足していく。 この約数を求める計算量は Nを外にだして Σ部分は調和級数になるので、だいたいlogNになる。 ゆえに計算量はO(NlogN)とのこと。 約数…

問題 atcoder.jp 解法 フロイドワーシャルとかライブラリ叩けば良いんじゃね？と思ってたんだが、この問題で求められてる処理自体がフロイドワーシャルのアルゴリズムそのものですよ。 というアルゴリズム教養問題だった。 なるほど、こういう処理なのね。 …

ABC206でできなかった問題をやってみる。 atcoder.jp 解説 はまやんさん解説、snukeさん放送を参考に、Union Findで解くパターンでやってみる。 入力例１の数列にUnion Findをかけて木構造を作ると次のような木構造ができる。 ABC206D 入力例1 要素は2, 3, 5…