ABC-C
結構単純。必殺技は大きいものから使っていけばいい。 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問題 体モンスターがいる。 回必殺技が使え、必殺技は一発でモンスター倒せる。 必殺技以外だとモンスターの体力を一回の攻撃でだけ減…
3の倍数になるかどうかなので、mod3で場合分け、そしてさらにその結果で場合分けっていうふうに愚直にやる。 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問題 各桁にを含まない正の整数が与えられる。 の桁数をとして未満個ある桁を消…
まず、 すべてのパターンを一気に考えようとせず、かつを満たすの組み合わせ数を出せるようにする。その後条件を詰めていく。 結果的に、問題はなので、かつとして考えることができる。 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問…
問題の意図的に約数を列挙すればいい。 目次 目次 概要 解くときに考えた内容 コード 参考になる書籍 概要 問題 が与えられる。 とした時に割り切れる を全て列挙できる? 解くときに考えた内容 文意から、約数列挙するだけ。 約数列挙は手元に関数があるの…
問題を理解するのに戸惑った。が内容的にはfor文一発でいける。 目次 目次 概要 解くときに考えた内容 コード 概要 問題 要するに数列の番目が番目から番目で一番小さい数になっているかどうかを判定する。 数列全てのindexにおいて条件が満たされているinde…
単純な数え上げ。問題ごとにACがでるまでWAのカウントをする。 目次 目次 概要 解くときに考えた内容 コード 概要 問題 問題は問ある。 回提出。 成功すれば失敗すればとなる。 1度でもしたらその問題のの回数は1回。 の回数は問題ごとにするまでにした回数…
ある数の約数を数える場合は素因数分解を使えばいいが、今回は制約が大きいので、素因数分解して、全てのパターンを計算すると間に合わない。からまでの約数の個数をカウントするなら定数倍的に考える方がいい。 目次 目次 概要 解くときに考えた内容 コード…
順列の全探索をすればいい。 目次 目次 概要 解くときに考えた内容 コード 書籍 最近買って面白かった本 アルゴリズムの参考書籍 概要 問題 を与えられる。 の順列のリストを考える。(とする) ある順列とを与えるので、を辞書順に並べた時にとが何番目かを…
包括原理より、全パターンから条件に合わないものを引く。 計算過程では繰り返し二乗法を使う( という形は愚直に計算すると遅い) 目次 目次 概要 解くときに考えた内容 コード 書籍 アルゴリズムの参考書籍 概要 問題 長さ個の整数列が以下の条件に当ては…
自分自身以上の素数を求める問題。テストサンプルに制約の中で最大の素数のヒントがあるので、そこまでのテーブルがあればいい。 あとは二分探索で探す。bisect_left, bisect_rightどちらでもできるが、たまに混乱するので、どういう風に考えて使うか軽くま…
要求されている掛け算の和を累積和を使ってシンプルにする事ができるかどうかを試されている。 目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 個の整数が与えられる。 1. をで割った余りは?…
目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人人でも均等にお菓子を分けられるような最小のお菓子の数は? 制約 は整数 解くときに考えた内容 単純にの最小公倍数を求める。 最小公倍数を…
その時点でのmax値を保持してその値より、小さかったら、差分を足すということを続けるだけ。 概要 解くときに考えた内容 TLE AC コード TLE AC 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人が並んでいる。 1. 順番に身長がである。 1. 左…
移動している様子を書きながら、考えればできそう。 は正として考えればいいし、が小さめな時は0へどんどん向かっていけばいいし、動ける回数が余ったら、余った回数の偶奇で場合分けする。 概要 解くときに考えた内容 コード 概要 問題 1. 座標上のにいる。…
問題文をみて瞬間に、ムムッとなる。データの読み込みに慣れていればさほどでもないが、いきなり嫌な感じがした。 結局、全探索っていう感じだが結構その探索も結構面倒。なるだけ詳細を書きながらまとめる。 目次 目次 概要 解くときに考えた内容 コード 書…
問題は7, 77, 777 ... を純粋に並べようとするとTLEになってしまう。累乗の計算量というのはかなり大きいので、制約が大きい時はつかえないというのがポイント(知らなかったOrz)。あとは、あまりの話なので大きい数の余りを計算するのではなく余りを定数倍…
単純に計算すると計算量多すぎるので、桁の条件を詰めつつ最大値を求める方法と二分探索がある。 目次 目次 概要 解くときに考えた内容 コード 条件を満たす最大の桁におけるを計算 二分探索 概要 問題 の整数を買いたい。 買うには、円必要。(はの桁数) …
街が個あるので全部パターン数えていると計算量が大きくなってしまう。最終的に平均の距離を出すのでそこも合わせて工夫する 概要 解くときに考えた内容 コード 愚直に、全経路パターンの和を出す方法 各街同士の距離の和を出して、重複回数をかける方法 概…
このコンテストのA, Bは九九の問題であった。この問題はそれを制約の範囲でかなり大きい表をイメージする。 がと大きいので工夫して探索 概要 解くときに考えた内容 コード 概要 問題 九九のようにのマスがある。 そのマスの値はである。 2以上の1つ整数を与…
同じ文字をグループとして捉えてその切れ目を数える 概要 解くときに考えた内容 コード 概要 問題 文字列が与えられる。 例えばaabbbbaacaであれば、[aa][bbb][aa][c][a]のように隣接する文字が同じ場合は一つのグループとする。(問題的にはスライム) 最終…
インデックスをいい感じにずらして考えられるかの問題 こういう問題を逆順列を求める問題というらしい 概要 解くときに考えた内容 コード 概要 問題 出席番号の人が来たときの自分を含めている人数を与えられる。 どういう順番で来たのかを出席番号で答えら…
bit全探索をマス目に対して行う。行と列に対してbit全探索をするのでネストが深くなる。bit演算子に慣れていないとコード自体がよくわからんので、そこらへんもまとめる。さらに、itertoolsでbitの列挙はできるのでそれもやる。 概要 解くときに考えた内容 b…
カウントした値を持ってからクエリを処理する系っていうパターン。 別の方法もある。先に持ち点から全クエリ分引き算しておいて正解したら足す。 概要 解くときに考えた内容 コード 概要 問題 ・最初の時点で全員ポイントもっている。 ・回クイズを行って、…
コンテストの最中は、探索するというか貪欲的に求めると勘違いしてしまった。heapqとdequeを駆使してごちゃごちゃやったが条件を詰められず。 けんちょんさんがこの問題は、しゃくとり法や累積和 +二分探索で考えたということをTweetされていたので、2つと…