Quiz https://atcoder.jp/contests/agc033/tasks/agc033_c Submission https://atcoder.jp/contests/agc033/submissions/5293995 木の直径 上記問題で木の直径を求める必要があったのでbfsで求めた C, 直径という大局から見るのかぁ— peroon_cp (@peroon_cp)…

Quiz https://atcoder.jp/contests/cpsco2019-s1/tasks/cpsco2019_s1_c 観察 Kは最大6 32C6 = 906192 nCkのパターンを全探索すればいい フラグでnCkを全探索する方法は？ next_permutation bit (蟻本 v2 p144) 解法1 全探索 next_permutation {0, 0, 0, 1, 1…

Quiz https://atcoder.jp/contests/abc041/tasks/abc041_d Submit https://atcoder.jp/contests/abc041/submissions/5137686 解法 公式解説の通り メモ化再帰を使用 感想 この問題は昔も解説ACしたもの。解説pdfを見て「難しい、よく解けたな」と思う 「メモ…

Quiz https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_c Submit https://atcoder.jp/contests/s8pc-6/submissions/4981908 解法 editorialの通り 感想 100個くらいつなげて到達可能なら行けそう 迷路で到達可能かどうか、ということで幅優先で解いたらTLE…

Quiz https://atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_e Submit https://atcoder.jp/contests/code-thanks-festival-2018-open/submissions/4722141 解法 dp[i][j] 整数 i まで見て、iがj個余る場合の数 例 dp…

Quiz https://atcoder.jp/contests/rco-contest-2019-final-open/tasks/rco_contest_2019_final_a 結果 時間内 0点（一部WA）（2019-03-02 18:00:00) 時間が過ぎてACしたとき 587618点 (2019-03-02 18:33:24) 中央値くらい やり残しも実装 798499点 (3/3 AM4…

Quiz https://atcoder.jp/contests/abc119/tasks/abc119_c Submit https://atcoder.jp/contests/abc119/submissions/4377522 Note N=8と小さい 伸ばしてから合成と、合成してから伸ばすのは同じ 各竹をA, B, C, D(使わない)に割り当てるのを全パターン試せば…

Quiz https://atcoder.jp/contests/abc119/tasks/abc119_d Submit https://atcoder.jp/contests/abc119/submissions/4374869 Note xの位置から見て、一番近い右にある寺・神社 xの位置から見て、一番近い左にある寺・神社 をそれぞれ求める 右の神社に行って…

Quiz https://atcoder.jp/contests/abc003/tasks/abc003_4 Submit https://atcoder.jp/contests/abc003/submissions/4361326 Note editorialの通りに包除原理 サンプルが全部通ればほぼ通る 101点の条件ではもっと小さいテストケースを作るといい 包除原理 …

Quiz https://atcoder.jp/contests/abc087/tasks/arc090_b Submit https://atcoder.jp/contests/abc087/submissions/4342479 Note 解説YouTubeの通り https://youtu.be/br3ze-KC6WA?t=1852 もう少し詳しく M個のエッジ情報を登録する visited配列 距離配列 …

Quiz https://atcoder.jp/contests/abc020/tasks/abc020_c Submit https://atcoder.jp/contests/abc020/submissions/4023131 補足 xを二分探索。探索1回ごとにワーシャルフロイドで最短経路を求める 私の場合、今までワーシャルフロイドを使うときは双方向で…

Quiz https://atcoder.jp/contests/abc051/tasks/abc051_d Submit https://atcoder.jp/contests/abc051/submissions/3924971 考え方 元々の辺のコストより軽くなったら取ってよし

intが混じっていた。WA https://atcoder.jp/contests/abc071/submissions/3913240 機械的に全てlong longにした。AC https://atcoder.jp/contests/abc071/submissions/3913253 補足 typedef long long ll; 以前、機械的にlong longにしたら遅くなってTLEした…

Quiz https://atcoder.jp/contests/agc030/tasks/agc030_b 間違った解答 WA https://atcoder.jp/contests/agc030/submissions/3897783 現在地点から離れている木の方に行けばいいのでは？ 実装も複雑になってしまい、サンプルテストケース3も通らないという…

Quiz https://atcoder.jp/contests/abc079/tasks/abc079_d Submit https://atcoder.jp/contests/abc079/submissions/3888526 落とし穴 最初はforをi, j, kの順に書き、i->j->kと経由を想定して書いたら、提出後に部分的にWA サンプルで通ってしまうのが怖い…

Quiz https://atcoder.jp/contests/abc080/tasks/abc080_d Submit https://atcoder.jp/contests/abc080/submissions/3888310 問題文 「-0.5秒～」の箇所、ここで「チャンネル変更には0.5秒のコストがかかる（チャンネル変更しないならかからない）」と言って…

問題 https://atcoder.jp/contests/abc090/tasks/arc091_b AC code https://atcoder.jp/contests/arc091/submissions/11678651 解説 N=20, K=5で具体的に描いてみましょう (Google spreadsheetの関数 ARRAYFORMULAというのを使ってみた) 右上の黄色い領域は…

問題 https://atcoder.jp/contests/abc091/tasks/arc092_b 提出 https://atcoder.jp/contests/abc091/submissions/3868349 公式解説放送を見て bitごとに求めて間に合う（30bitとしてもNlogN x 30はTLEしない） 周期が見える modをとってよい sortしておいて…

問題 https://atcoder.jp/contests/caddi2018b Dについて ひたすら単純な例でシミュレートし、偶数の木で押しつければ必勝っぽいと分かる AC 解説放送を見て思うこと 実験する（N=2） L, Wを押し付ける 遷移 表 Cについて 最後までTLEで通らず 素因数分解 sq…

問題 https://atcoder.jp/contests/abc097/tasks/arc097_b 考察 交換可能なら同じグループとする 同じグループというのを木で表す（値が同じなら同じグループ） Union Find木 ミスしたところ (UF) グループをまとめるとき(Union時)、自分の親を書き換えるの…

問題 https://atcoder.jp/contests/abc099/tasks/abc099_b 提出 https://atcoder.jp/contests/abc099/submissions/3829667 振り返り 問題をちゃんと読むこと 総当たりの前に、設定を言い換えることができないか考える 雪が積もっても2本の差は変わらないこと…

問題 https://atcoder.jp/contests/abc101/tasks/arc099_a 提出 https://atcoder.jp/contests/abc101/submissions/3823261 方針 1を左右に伸ばしていく 注意ケース 全力で左を伸ばしに行くのではなく、1発目で右側にも少し伸ばしておいたほうがいい場合があ…

All提出 https://atcoder.jp/contests/abc102/submissions?f.User=peroon 最後の2つの提出を見比べてみると どちらも2重のforなのでO(N2)に見える カット位置の単調増加を利用して、forの初期位置に前回のforの結果を利用 TLEにならなくなり、通った 学び 単…

beta.atcoder.jp 例えばこの大会 Aは簡単なのでまず解く B, C, Dは得点が近い Bのテストケースは2種 Cのテストケースは2種 Dのテストケースは3種 追加でテストケースを自作する時、作り間違えるリスクがある サンプルテストケースが多い方が状況を理解しやす…

問題 https://beta.atcoder.jp/contests/agc029/tasks/agc029_c 私の提出 https://beta.atcoder.jp/contests/agc029/submissions?f.User=peroon 時間がかかった理由 自作したテストケースが間違っていた 提供されているテストケースは数が少ないし答えも2, 3…

beta.atcoder.jp この問題のテスト用データを自作した かなり時間が経った後、このデータが間違っていることが判明 その間、間違ったデータでテストを通そうとしてしまう コードが間違った側に誘導されてしまう ローカルでは（間違ったデータなのに）テスト…

WAが優先 TLEの方が見当を付けやすいのでそちらを直したい（通したい）気分になる しかしWAの方が論理が間違っているので重傷 WAから優先して直すべき TLEが起こったとき データ数が少ないときはACしている場合 論理はあっていそう 計算量を減らせばTLEがAC…

問題 beta.atcoder.jp 私の解答 beta.atcoder.jp 文字列を使わずに数字だけで解いてみた 賢い解答 beta.atcoder.jp #include <iostream> using namespace std; int main() { int n; cin >> n; cout << 1110 - n << endl; }</iostream>

beta.atcoder.jp Cまでは一瞬で解ける D問題 ハンバーガーの問題 ナイーブに生成すると250層に達する long longには収まるが、再帰的に解けそう ラスト2分でサンプル3が通り「できた！」と提出 最後の4テストでWA タイムアップ後 簡単な例でテストを足してみ…

問題 beta.atcoder.jp 提出 beta.atcoder.jp ローカルでは全部通るがサーバ側では通らない AtCoderはテストデータをDropboxで全公開している それをローカルに落としてテストしたらAC しかしサーバ側に提出するとRuntime Errorになるものがある ロジックとし…