競プロ
普段は、AtCoder Beginner Contestにでているが、とりあえず挑戦という事で、Bまで解ければ良いと思ってAtCoder Regular Contestに初参加してみた。 内容 結果 どう考えたか + α A - Fourtune Cookies B - おわりに 参考になる書籍 内容 Python3でやっている…
順番に与えられる、を集合で管理して、その中に前回出力した値が含まれるかどうかを判定してあげるっていうこと。 目次 目次 概要 解くときに考えた内容 出力したい値をsetとリストで管理する（TLE） 既出のpをsetか配列かで管理する コード 答えをリストで…
久しぶりの企業のコンテスト。 最近諸事情により全然精進していないので結果的にはいまいちだったが、久しぶりだったので楽しかった。 内容 結果 どう考えたか + α A - Keyboard B - Futon C - Neq Min おすすめの書籍 アルゴリズムの参考書籍 最近ポチった…
本番は時間が合わず参加しなかったが、いつも通りメモを残しておく 内容 結果 どう考えたか + α A - Repeat ACL B - Integer Preference C - Connect Cities その他のおすすめの書籍 アルゴリズムの参考書籍 最近ポチった書籍 内容 Python3でやっている。 参…
数値そのもので考えるというより、その数値の先頭とお尻の数値の組と逆にしたお尻と先頭の数値の組みがそれぞれ幾つ存在するのかっていうことを考える問題。こういう時はdefaultdict（というか常にdefaultdictでいいと思うけど）で行う。 dictでやる場合とde…
問題を理解するのに戸惑った。が内容的にはfor文一発でいける。 目次 目次 概要 解くときに考えた内容 コード 概要 問題 要するに数列の番目が番目から番目で一番小さい数になっているかどうかを判定する。 数列全てのindexにおいて条件が満たされているinde…
単純な数え上げ。問題ごとにACがでるまでWAのカウントをする。 目次 目次 概要 解くときに考えた内容 コード 概要 問題 問題は問ある。 回提出。 成功すれば失敗すればとなる。 1度でもしたらその問題のの回数は1回。 の回数は問題ごとにするまでにした回数…
ある数の約数を数える場合は素因数分解を使えばいいが、今回は制約が大きいので、素因数分解して、全てのパターンを計算すると間に合わない。からまでの約数の個数をカウントするなら定数倍的に考える方がいい。 目次 目次 概要 解くときに考えた内容 コード…
約数の数をカウントする方法素因数分解以外思いつかずC解けずOrz 内容 結果 どう考えたか + α A - Plural Form B - Go to Jail A x B + C D - Leaping Tak おわりに 内容 Python3でやっている。 参加ログ。 所感。 コンテスト中に何を考えたか。 コンテスト…
順列の全探索をすればいい。 目次 目次 概要 解くときに考えた内容 コード 書籍 最近買って面白かった本 アルゴリズムの参考書籍 概要 問題 を与えられる。 の順列のリストを考える。（とする） ある順列とを与えるので、を辞書順に並べた時にとが何番目かを…
包括原理より、全パターンから条件に合わないものを引く。 計算過程では繰り返し二乗法を使う（ という形は愚直に計算すると遅い） 目次 目次 概要 解くときに考えた内容 コード 書籍 アルゴリズムの参考書籍 概要 問題 長さ個の整数列が以下の条件に当ては…
初めてAしかできないっていう。本番弱いなぁ。 復習しっかりする。 内容 結果 どう考えたか + α A - Not B - Product Max C - Ubiquity D - Redistribution おわりに 内容 Python3でやっている。 参加ログ。 所感。 コンテスト中に何を考えたか。 コンテスト…
じゃんけんにおいて、事前に相手が出す手がわかっていて、何を出して勝ったかで得点が異なる時に、何回かじゃんけんして特典の最大値を求める問題（ほぼ概要だな）。 目次 目次 概要 解くときに考えた内容 コード 書籍 アルゴリズムの参考書籍 最近ポチった…
自分自身以上の素数を求める問題。テストサンプルに制約の中で最大の素数のヒントがあるので、そこまでのテーブルがあればいい。 あとは二分探索で探す。bisect_left, bisect_rightどちらでもできるが、たまに混乱するので、どういう風に考えて使うか軽くま…
グラフの連結 目次 目次 概要 解くときに考えた内容 BFS Union-Find コード BFS Union-Find 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人いる。 1. 個の友人関係情報が与えられる。 1. 直接友人でなくても、友人の友人は友人であるとする…
要求されている掛け算の和を累積和を使ってシンプルにする事ができるかどうかを試されている。 目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 個の整数が与えられる。 1. をで割った余りは？…
ABまでできた。Bが案外難しかった。Cは勘違いしてた。Cは単純に累積和を別リストにもって頭から順番に足していけばいいだけだったのに過去問にひきづられて困惑。DはUnion-Find（実装したことなく、無理だった）。本番弱いなぁ。 内容 結果 どう考えたか + α…
かなりシンプルな問題。砕いて残ったものが1, 2, 3...という風に並んでる状態を目指す。左から順番に砕くか判定していく。 目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 個のレンガが並んで…
目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人人でも均等にお菓子を分けられるような最小のお菓子の数は？ 制約 は整数 解くときに考えた内容 単純にの最小公倍数を求める。 最小公倍数を…
startとgoalを自分で決める迷路で最長の手数のstartとgoalはなにかっていう問題。久しぶりに迷路問題解いた。普通はスタートとゴールを設定するんだけど、ゴールまで設定するとTLEになるので、スタートだけ設定して、BFSでやって最大手数の場所を結果的にゴ…
上下左右の移動だけでなく、制限があるワープができる条件で、最低限のワープ数で迷路にゴールできるかを問う問題。結論から言うと、計算量的にきつかった。自分にはこれ以上は思いつかなかったが、ともかく、普通の移動→そこをスタート地点してワープ→そこ…
その時点でのmax値を保持してその値より、小さかったら、差分を足すということを続けるだけ。 概要 解くときに考えた内容 TLE AC コード TLE AC 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人が並んでいる。 1. 順番に身長がである。 1. 左…
ABCまで、Dももうちょっとだった。Cで線形探索すればいいだけだったのに無駄なことで時間を使いすぎた。Dは久しぶりの迷路実装で忘れてた。今日ので復習が大事であることを再確認した。 内容 結果 どう考えたか + α A - Takoyaki B - Multiple of 9 C - Step…
当たり前だが、制約が大きいので、一つ一つ移動させてスコアの和の最大値を求めようとするとTLEになる。そこを工夫する必要があり、の和で考えて対応した。最初に選んだマスがある意味運命を左右することになるので（止まるという選択肢はあるものの）そこを…
移動している様子を書きながら、考えればできそう。 は正として考えればいいし、が小さめな時は0へどんどん向かっていけばいいし、動ける回数が余ったら、余った回数の偶奇で場合分けする。 概要 解くときに考えた内容 コード 概要 問題 1. 座標上のにいる。…
また、ABまで。しかもBで相当時間かけてしまってCの時間が足りなかった。まだまだ問題をこなす量が足りないのを実感。まぁでもCはちょっとだった。Dはとりあえず通る実装かけたけどこれをコンテスト中に書くのは辛い印象。 内容 結果 どう考えたか + α A - R…
問題を把握するには、連続したシグマが何を意味しているのか、XORの特性を理解することがポイント。それさえできれば結構単純。自分は桁ごとに考えた。制約としてギリなのでローカル化しないとTLE。もっと工夫できるのかもしれないけど。 目次 目次 概要 制…
問題文をみて瞬間に、ムムッとなる。データの読み込みに慣れていればさほどでもないが、いきなり嫌な感じがした。 結局、全探索っていう感じだが結構その探索も結構面倒。なるだけ詳細を書きながらまとめる。 目次 目次 概要 解くときに考えた内容 コード 書…
個存在する状態をを目指すようにして、それぞれの状態における最小の手数を数えて、全状態の中で最小値をみつければいい。状態をどう考えるか、その時の最小の手数はどう考えればいいかというのがポイント。 概要 解くときに考えた内容 反省点 コード 概要 …
問題は7, 77, 777 ... を純粋に並べようとするとTLEになってしまう。累乗の計算量というのはかなり大きいので、制約が大きい時はつかえないというのがポイント（知らなかったOrz）。あとは、あまりの話なので大きい数の余りを計算するのではなく余りを定数倍…
