くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU

競プロ

AtCoder Regular Contest 105 参加ログ・感想

普段は、AtCoder Beginner Contestにでているが、とりあえず挑戦という事で、Bまで解ければ良いと思ってAtCoder Regular Contestに初参加してみた。 内容 結果 どう考えたか + α A - Fourtune Cookies B - おわりに 参考になる書籍 内容 Python3でやっている…

Python3で解く HHKB プログラミングコンテスト 2020 C - Neq Min

順番に与えられる、を集合で管理して、その中に前回出力した値が含まれるかどうかを判定してあげるっていうこと。 目次 目次 概要 解くときに考えた内容 出力したい値をsetとリストで管理する(TLE) 既出のpをsetか配列かで管理する コード 答えをリストで…

HHKB プログラミングコンテスト 2020 参加ログ・感想

久しぶりの企業のコンテスト。 最近諸事情により全然精進していないので結果的にはいまいちだったが、久しぶりだったので楽しかった。 内容 結果 どう考えたか + α A - Keyboard B - Futon C - Neq Min おすすめの書籍 アルゴリズムの参考書籍 最近ポチった…

ACL Beginner Contest 参加ログ・感想

本番は時間が合わず参加しなかったが、いつも通りメモを残しておく 内容 結果 どう考えたか + α A - Repeat ACL B - Integer Preference C - Connect Cities その他のおすすめの書籍 アルゴリズムの参考書籍 最近ポチった書籍 内容 Python3でやっている。 参…

Python3で解く AtCoder Beginner Contest 152 D - Handstand 2

数値そのもので考えるというより、その数値の先頭とお尻の数値の組と逆にしたお尻と先頭の数値の組みがそれぞれ幾つ存在するのかっていうことを考える問題。こういう時はdefaultdict(というか常にdefaultdictでいいと思うけど)で行う。 dictでやる場合とde…

Python3で解く AtCoder Beginner Contest 152 C - Low Elements

問題を理解するのに戸惑った。が内容的にはfor文一発でいける。 目次 目次 概要 解くときに考えた内容 コード 概要 問題 要するに数列の番目が番目から番目で一番小さい数になっているかどうかを判定する。 数列全てのindexにおいて条件が満たされているinde…

Python3で解く AtCoder Beginner Contest 151 C - Welcome to AtCoder

単純な数え上げ。問題ごとにACがでるまでWAのカウントをする。 目次 目次 概要 解くときに考えた内容 コード 概要 問題 問題は問ある。 回提出。 成功すれば失敗すればとなる。 1度でもしたらその問題のの回数は1回。 の回数は問題ごとにするまでにした回数…

Python3で解く AtCoder Beginner Contest 179 C - A x B + C

ある数の約数を数える場合は素因数分解を使えばいいが、今回は制約が大きいので、素因数分解して、全てのパターンを計算すると間に合わない。からまでの約数の個数をカウントするなら定数倍的に考える方がいい。 目次 目次 概要 解くときに考えた内容 コード…

AtCoder Beginner Contest 179 参加ログ・感想

約数の数をカウントする方法素因数分解以外思いつかずC解けずOrz 内容 結果 どう考えたか + α A - Plural Form B - Go to Jail A x B + C D - Leaping Tak おわりに 内容 Python3でやっている。 参加ログ。 所感。 コンテスト中に何を考えたか。 コンテスト…

Python3で解く AtCoder Beginner Contest 150 C - Count Order

順列の全探索をすればいい。 目次 目次 概要 解くときに考えた内容 コード 書籍 最近買って面白かった本 アルゴリズムの参考書籍 概要 問題 を与えられる。 の順列のリストを考える。(とする) ある順列とを与えるので、を辞書順に並べた時にとが何番目かを…

Python3で解く AtCoder Beginner Contest 178 C - Ubiquity

包括原理より、全パターンから条件に合わないものを引く。 計算過程では繰り返し二乗法を使う( という形は愚直に計算すると遅い) 目次 目次 概要 解くときに考えた内容 コード 書籍 アルゴリズムの参考書籍 概要 問題 長さ個の整数列が以下の条件に当ては…

AtCoder Beginner Contest 178 参加ログ・感想

初めてAしかできないっていう。本番弱いなぁ。 復習しっかりする。 内容 結果 どう考えたか + α A - Not B - Product Max C - Ubiquity D - Redistribution おわりに 内容 Python3でやっている。 参加ログ。 所感。 コンテスト中に何を考えたか。 コンテスト…

Python3で解く AtCoder Beginner Contest 149 D - Prediction and Restriction

じゃんけんにおいて、事前に相手が出す手がわかっていて、何を出して勝ったかで得点が異なる時に、何回かじゃんけんして特典の最大値を求める問題(ほぼ概要だな)。 目次 目次 概要 解くときに考えた内容 コード 書籍 アルゴリズムの参考書籍 最近ポチった…

Python3で解く AtCoder Beginner Contest 149 C - Next Prime

自分自身以上の素数を求める問題。テストサンプルに制約の中で最大の素数のヒントがあるので、そこまでのテーブルがあればいい。 あとは二分探索で探す。bisect_left, bisect_rightどちらでもできるが、たまに混乱するので、どういう風に考えて使うか軽くま…

Python3で解く AtCoder Beginner Contest 177 D - Friends

グラフの連結 目次 目次 概要 解くときに考えた内容 BFS Union-Find コード BFS Union-Find 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人いる。 1. 個の友人関係情報が与えられる。 1. 直接友人でなくても、友人の友人は友人であるとする…

Python3で解く AtCoder Beginner Contest 177 C - Sum of product of pairs

要求されている掛け算の和を累積和を使ってシンプルにする事ができるかどうかを試されている。 目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 個の整数が与えられる。 1. をで割った余りは?…

AtCoder Beginner Contest 177 参加ログ・感想

ABまでできた。Bが案外難しかった。Cは勘違いしてた。Cは単純に累積和を別リストにもって頭から順番に足していけばいいだけだったのに過去問にひきづられて困惑。DはUnion-Find(実装したことなく、無理だった)。本番弱いなぁ。 内容 結果 どう考えたか + α…

Python3で解く AtCoder Beginner Contest 148 D - Brick Break

かなりシンプルな問題。砕いて残ったものが1, 2, 3...という風に並んでる状態を目指す。左から順番に砕くか判定していく。 目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 個のレンガが並んで…

Python3で解く AtCoder Beginner Contest 148 C - Snack

目次 目次 概要 制約 解くときに考えた内容 コード 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人人でも均等にお菓子を分けられるような最小のお菓子の数は? 制約 は整数 解くときに考えた内容 単純にの最小公倍数を求める。 最小公倍数を…

Python3で解く AtCoder Beginner Contest 151 D - Maze Master

startとgoalを自分で決める迷路で最長の手数のstartとgoalはなにかっていう問題。久しぶりに迷路問題解いた。普通はスタートとゴールを設定するんだけど、ゴールまで設定するとTLEになるので、スタートだけ設定して、BFSでやって最大手数の場所を結果的にゴ…

Python3で解く AtCoder Beginner Contest 176 D - Wizard in Maze

上下左右の移動だけでなく、制限があるワープができる条件で、最低限のワープ数で迷路にゴールできるかを問う問題。結論から言うと、計算量的にきつかった。自分にはこれ以上は思いつかなかったが、ともかく、普通の移動→そこをスタート地点してワープ→そこ…

Python3で解く AtCoder Beginner Contest 176 C - Step

その時点でのmax値を保持してその値より、小さかったら、差分を足すということを続けるだけ。 概要 解くときに考えた内容 TLE AC コード TLE AC 書籍 最近ポチった書籍 アルゴリズムの参考書籍 概要 問題 1. 人が並んでいる。 1. 順番に身長がである。 1. 左…

AtCoder Beginner Contest 176 参加ログ・感想

ABCまで、Dももうちょっとだった。Cで線形探索すればいいだけだったのに無駄なことで時間を使いすぎた。Dは久しぶりの迷路実装で忘れてた。今日ので復習が大事であることを再確認した。 内容 結果 どう考えたか + α A - Takoyaki B - Multiple of 9 C - Step…

Python3で解く AtCoder Beginner Contest 175 D - Moving Piece

当たり前だが、制約が大きいので、一つ一つ移動させてスコアの和の最大値を求めようとするとTLEになる。そこを工夫する必要があり、の和で考えて対応した。最初に選んだマスがある意味運命を左右することになるので(止まるという選択肢はあるものの)そこを…

Python3で解く AtCoder Beginner Contest 175 C - Walking Takahashi

移動している様子を書きながら、考えればできそう。 は正として考えればいいし、が小さめな時は0へどんどん向かっていけばいいし、動ける回数が余ったら、余った回数の偶奇で場合分けする。 概要 解くときに考えた内容 コード 概要 問題 1. 座標上のにいる。…

AtCoder Beginner Contest 175 参加ログ・感想

また、ABまで。しかもBで相当時間かけてしまってCの時間が足りなかった。まだまだ問題をこなす量が足りないのを実感。まぁでもCはちょっとだった。Dはとりあえず通る実装かけたけどこれをコンテスト中に書くのは辛い印象。 内容 結果 どう考えたか + α A - R…

Python3で解く AtCoder Beginner Contest 147 D - Xor Sum 4

問題を把握するには、連続したシグマが何を意味しているのか、XORの特性を理解することがポイント。それさえできれば結構単純。自分は桁ごとに考えた。制約としてギリなのでローカル化しないとTLE。もっと工夫できるのかもしれないけど。 目次 目次 概要 制…

Python3で解く AtCoder Beginner Contest 147 C - HonestOrUnkind2

問題文をみて瞬間に、ムムッとなる。データの読み込みに慣れていればさほどでもないが、いきなり嫌な感じがした。 結局、全探索っていう感じだが結構その探索も結構面倒。なるだけ詳細を書きながらまとめる。 目次 目次 概要 解くときに考えた内容 コード 書…

Python3で解く AtCoder Beginner Contest 174 D - Alter Altar

個存在する状態をを目指すようにして、それぞれの状態における最小の手数を数えて、全状態の中で最小値をみつければいい。状態をどう考えるか、その時の最小の手数はどう考えればいいかというのがポイント。 概要 解くときに考えた内容 反省点 コード 概要 …

Python3で解く AtCoder Beginner Contest 174 C - Repsept

問題は7, 77, 777 ... を純粋に並べようとするとTLEになってしまう。累乗の計算量というのはかなり大きいので、制約が大きい時はつかえないというのがポイント(知らなかったOrz)。あとは、あまりの話なので大きい数の余りを計算するのではなく余りを定数倍…