atcoder

C - Infinite Grid

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

E - Union

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…

第3回 RCO日本橋ハーフマラソン 本戦 (オープン) A問題だけに4h注力して参加してみた

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…

C - Synthetic Kadomatsu

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

D - Lazy Faith

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

D - AtCoder社の冬

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

D - People on a Line arc090_b

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配列 距離配列 …

C - 壁抜け (abc020_c)

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

D - Candidates of No Shortest Paths (abc051_d) ワーシャルフロイドで解いた

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

intではなくlong longで書こう (arc081_a)

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した…

B - Tree Burning (agc030_b)

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

ワーシャルフロイド簡単やん!と思ったら落とし穴 (abc079_d)

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 サンプルで通ってしまうのが怖い…

D - Recording (abc080_d)

Quiz https://atcoder.jp/contests/abc080/tasks/abc080_d Submit https://atcoder.jp/contests/abc080/submissions/3888310 要素 いもす法 タイムスケールを2倍

D - Remainder Reminder (arc091_b) 丁寧に数え上げる

問題 https://atcoder.jp/contests/abc090/tasks/arc091_b 提出 https://atcoder.jp/contests/abc090/submissions/3868505 ノート N = 11 K = 3 で見てください その他 表を書くと規則性が見える 左下には塊でK以上が発生する 右上にもちらほら発生する 1行…

絶対にintを越えないという確信がない変数はlong longにしよう (arc092_b)

問題 https://atcoder.jp/contests/abc091/tasks/arc092_b 提出 https://atcoder.jp/contests/abc091/submissions/3868349 振り返り 難しい。解説を読んで理解して実装 lower_boundと仲良くなれた int count = 0; としていたため、大きいテストケースで通ら…

CADDi 2018 for Beginnersに参加。ABD完

問題 https://atcoder.jp/contests/caddi2018b Dについて ひたすら単純な例でシミュレートし、偶数の木で押しつければ必勝っぽいと分かる AC Cについて 最後までTLEで通らず 素因数分解 sqrt(N)まで調べれば十分 レート 1200届かず 1313人のビギナー(少なく…

arc097_b Union Find木で解いた

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

言い換え力 abc099_b

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

C - Minimization arc099_a

問題 atcoder.jp 提出 atcoder.jp 方針 1を左右に伸ばしていく 注意ケース 全力で左を伸ばしに行くのではなく、1発目で右側にも少し伸ばしておいたほうがいい場合がある 左から攻めると3回だけど、右から攻めると2回になる 振り返り 証明ができていない 左右…

単調増加を見抜いてしゃくとり方をするとO(N^2) -> O(N)になった

提出 atcoder.jp 最後の2つの提出を見比べてみると どちらも2重のforなのでO(N2)に見える カット位置の単調増加を利用して、forの初期位置に前回のforの結果を利用 TLEにならなくなり、通った 学び 単調増加の性質がないか考える。あったら利用する 左から右…

どの問題から解くか?

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

1つの問題に7時間+αかけて、やっとAC (agc029_c)

問題 beta.atcoder.jp 私の提出 beta.atcoder.jp 時間がかかった理由 自作したテストケースが間違っていた 提供されているテストケースは数が少ないし答えも2, 3なので、間違ったコードでも通りうる 案の定、提出後にWA 自作するが、それが間違っていて、コ…

自作のテストデータが間違っていると致命的

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

WAとTLE, どちらを優先して直すか

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>

ABC115 あと8分あればD解けてた・・・

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

agc028 ローカルではsubtask含めて通るがサーバ側で通らず・・・

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

【C++】cin高速化

たまに見かけるこのコード cin.tie(0); ios::sync_with_stdio(false); cin高速化と呼ばれている scanfの方が速いようだが、便利なのでcin使いたい人向け 使って計測してみた M行読み込む問題 https://beta.atcoder.jp/contests/abc113/tasks/abc113_c 302ms …

atcoder abc113_c

問題 beta.atcoder.jp 解答 beta.atcoder.jp 要素 class宣言 vector + 比較関数でソート 0パディング 別の0 padding (他の人を参考) coutのやり方だと覚えられないのでprintfの方がよさげ for(int m=0; m

AtCoder ABCに1年ぶりくらいに参加。C問題すら解けずに絶望

beta.atcoder.jp ナイーブに解くと109なので無理 7, 5, 3から作れる数字を全列挙してそれらをチェックしつつカウントすればいい この方針は正解 しかし列挙ができずに時間切れ 列挙方法 再帰関数 or 3進数 どちらも時間内にどう書けばいいのか分からず 時間…