2021-05-01から1ヶ月間の記事一覧
AtCoder 競プロ典型 90問 012 Red Painting 何も分からなかった 連結判定はUnion-Find Union-Find木はリンクと連結判定を高速で行えるデータ構造 Union-Findの実装を見ただけでAC取れる実装できたのはよかった 013 Passing ダイクストラを2回やるだけ 014 We…
AtCoder 競プロ典型 90問 009 Three Point Angle なのではTLEするがなら間に合うことから、一つだけ二分探索という発想はできてもよかったはず。。。 二分探索してくれる標準ライブラリbisectの存在を知った 010 Score Sum Queries さすがに簡単 011 Gravy J…
AtCoder 競プロ典型 90問 006 Smallest Subsequence 解ける気がせん 辞書順最小は前から貪欲法、らしい 文字列→数値はord()、数値→文字列はchr() 前計算なしの解法もあるっぽい（https://github.com/ryusuke920/kyopro_educational_90_python/blob/main/solv…
AtCoder 競プロ典型 90問 005 Restricted Digits 小問題 2 昨日行列計算が遅いと書いたがそれだけじゃなかった ①累乗する行列が間違っていた 解説には「dp[i][j]] -> dp[i+1][k]の遷移が存在する場合に第行第列が1になる」とあるが、正確には「dp[i][j] -> d…
AtCoder 競プロ典型 90問 004 Cross Sum さすがに簡単 005 Restricted Digits 全然わからん 小問題 1 余りの情報を保持した桁DPをすればいいらしい（参考） 計算量は 小問題 2 数学じゃん、行列累乗というらしい 書けたは書けたが遅くてTLEした、たぶん行列…
AtCoder ABC 201 D Game in Momotetsu World こういう解法をミニマックス法というらしい（参考） 上記実装でも通らなかった REは再帰上限のせい 上限あげると今度はTLE PyPyは再帰が遅く、やめた方がいいらしい 単純にforループでDPを逆向きに進めればいい A…
AtCoder ABC 201 C Secret Number 最初、数学的に考えてしまったが、10000通り全探索でいけることに気づけた 最初からその方針で行けてれば10分くらい早かったかも 実装に多少手こずった D Game in Momotetsu World 最適化戦略も分からず、実装も分からない…
AtCoder 昨日さぼったのを一応解いておく ABC 200 C Ringo's Favorite Numbers 2 簡単 D Happy Birthday! 2 瞬殺ではなかったが、競プロっぽい問題を解けて嬉しい ARC118 初めて一問も解けなかった 両方ともコーナーケースにやられた
AtCoder 休んでる間のABCとARCの300, 400点問題埋め ABC 199 C IPFL listのset itemはなのを忘れて無理じゃね？と思ってしまった…… 反転しているかどうかの情報を保持しての時の処理を場合分けで記述する、って確かに当たり前だよなあ D RGB Coloring 2 ムズ…
AtCoder 休んでる間のABCとARCの300, 400点問題埋め 第二回日本最強プログラマー学生選手権 C Max GCD 2 簡単だった D Nowhere P 簡単だったけど計算量考慮せずに適当にやったら1回TLEしてしまった、反省 ARC 117 A God Sequence これはできなきゃいけない問…
AtCoder 休んでる間のABCとARCの300, 400点問題埋め ARC 116 A Odd vs Even ちゃんと考えれば解けた問題 計算量の制約から素因数分解するとは考えられない→もっとたくさん実験すれば法則性に気づけた 考えすぎても時間もったいないと思ってやめてしまった、…
AtCoder ZONeエナジー プログラミングコンテスト “HELLO SPACE” D 宇宙人からのメッセージ 解説によると「答えが以上になるか？」という判定問題に持ち込んでを二分探索するらしい、なるほど メンバー毎に各パラメータが以上かどうかを調べて、5つのパラメー…
AtCoder 休んでる間のABCとARCの300, 400点問題埋め ARC 115 A Two Choices さすがに簡単 B Plus Matrix さすがに簡単 ABC 197 C ORXOR bit全探索の実装に手間取った D Opposite 余弦定理使うだけ ZONeエナジー プログラミングコンテスト “HELLO SPACE” 爆死…
『テスト駆動開発』 第Ⅲ部 テスト駆動開発のパターン 流し読み
