Quiz https://atcoder.jp/contests/abc077/tasks/arc084_b Submit https://atcoder.jp/contests/abc077/submissions/3902787 その他 他の人の解答を見ていたら、ダイクストラをライブラリで持っていて適用して解いている人が多かった 発想 「桁の和」は、数…

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秒のコストがかかる（チャンネル変更しないならかからない）」と言って…

#include<bitset> // char to int int ctoi(char c) { if (c >= '0' && c <= '9') { return c - '0'; } return 0; } const int FLAG_NUM = 10; // 1023 => 00111 11111 vector<int> num_to_flags(int x){ stringstream ss; ss << static_cast<std::bitset<FLAG_NUM> >(x); string s = ss.str(); </std::bitset<flag_num></int></bitset>…

問題 https://asprocon2.contest.atcoder.jp/ 10日くらい開催されるマラソンマッチ スケジューリング問題 ゲーム：Factorioみたいだと思って興味を持った ちゃんと提出している人は50人くらい 5位以内で賞金 順位表を見ると1位は4497,7310,2339点など 満点は…

Quiz https://atcoder.jp/contests/abc082/tasks/arc087_b Submit https://atcoder.jp/contests/abc082/submissions/3883793 要素 DP boost split ちなみにboostはbrew install boostで入った(Mac) 縦移動・横移動の分離（別々に考えて良い） Segmentation F…

Quiz https://atcoder.jp/contests/abc084/tasks/abc084_d Submit https://atcoder.jp/contests/abc084/submissions/3879182 要素 エラトステネスのふるい（今回はなくてもよい） 累積和 left～rightでの個数＝＞f(v) : 0～vまでの個数を求めておき、f(right…

Quiz https://atcoder.jp/contests/abc085/tasks/abc085_d Submit https://atcoder.jp/contests/abc085/submissions/3878954 解き方 最後の一発は投げるでも切るでもいい。1番ダメージの大きいものでとどめを刺す 以下同様に、最後に投げた刀以外で最大ダメ…

Quiz https://atcoder.jp/contests/abc085/tasks/abc085_b Submit https://atcoder.jp/contests/abc085/submissions/3878831 解法 sortしてuniqueしてsize取ればOK、と思いきや ゴミがvectorの後端に残るのでeraseが必要 uniqueがゴミの先端を返してくれるの…

問題 https://atcoder.jp/contests/abc086/tasks/arc089_b 提出 https://atcoder.jp/contests/abc086/submissions/3878597 周期性 周期性から[0,2K), [0, 2K)の領域にW, Bが収まる WはBに変換できる 点の数を数える問題 グリッドの塗り方は左下の点を[0,2K),…

Quiz https://atcoder.jp/contests/abc089/tasks/abc089_d Submit https://atcoder.jp/contests/abc089/submissions/3872597 Else 「累積和をいくつか持つ必要がある・・・」と思ったが ステップ間隔が一定なので、1つの配列に収まる たとえばD=3なら、3本の…

問題 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/abc091/tasks/arc092_a 提出 https://atcoder.jp/contests/abc091/submissions/3859736 要素 Pointクラス定義 他を見ると、pairでx, yを扱っている人が多かった Pointクラスの比較演算子定義（ソートができるようになる） …

問題 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時)、自分の親を書き換えるの…

s = "abcde"; string t = s.substr(2, 10); p(t); p(t.length()); cde 3 気が利いています

answer_arc098_b.cpp:30:16: warning: ^ has lower precedence than ==; == will be evaluated first [-Wparentheses] if(a+b == a^b){ コンパイラ賢い

100円均一でA4 30枚ノートを複数買っておいている 競プロ専用としてガリガリ書いていく まとめ用ではなく、例を書いたり、思ったことを書いたりして解くときに使う 1冊目は10日で使い切った 湯水のように使ってきたつもりだったが、10日もかかっている 1日辺…

C++ In my case, I use % on double // error ll num = floor(value / pow(unit, i)) % unit; // fixed ll num = (int)floor(value / pow(unit, i)) % unit;

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

問題 https://atcoder.jp/contests/arc033/tasks/arc033_3 提出 https://atcoder.jp/contests/arc033/submissions/3828872 Segment Treeについて参考にしたサイト http://www.creativ.xyz/arc033c-406 Segment Treeを使おうと思ったきっかけ https://www.sli…

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

問題 atcoder.jp 平方分割を使っても解ける問題 平方分割とは 長さLのリストを sqrt(L) で分割する 参考 プログラミングコンテストでのデータ構造 from Takuya Akiba www.slideshare.net 提出 atcoder.jp vectorにpush_backする度にsort 遅そうだが、リスト…

それは何 グループをまとめる「Union」 同じグループか判定する「Find」 これらをO(logN)で実現するデータ構造 実装の参考 プログラミングコンテストでのデータ構造 from Takuya Akiba www.slideshare.net 提出 atc001.contest.atcoder.jp 多くのテストデー…

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

提出 beta.atcoder.jp 抜粋 pairの比較関数を定義すればいい bool compare_by_b(pair<int, int> a, pair<int, int> b) { if(a.second != b.second){ return a.second < b.second; }else{ return a.first < b.first; } } int main(){ ... vector<pair<int, int> > pairs(M); // 入力 FOR(i, 0, M)</pair<int,></int,></int,>…

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…