2019-01-01から1ヶ月間の記事一覧
追記:2021/09/29 今見ると拙いな^^; Quiz https://atcoder.jp/contests/abc031/tasks/abc031_d 文字列と数字の対応関係(語呂合わせ)を求めよ AC https://atcoder.jp/contests/abc031/submissions/3993696 解法 1の長さは2 2の長さは3 3の長さは1 のように…
Quiz https://atcoder.jp/contests/abc032/tasks/abc032_b Submit https://atcoder.jp/contests/abc032/submissions/3980763 int a = s.size() - k; if(a<0){ p(0); return 0; } ここでaをかませる必要があった s.size() - k < 0 で判定してしまうと、size()…
int main() { // atan(y, x) p(atan2(0, 1)); // 0度 p(atan2(1, 1)); // 右上 45 degree = PI/4 p(atan2(1, -1)); // 左上 p(atan2(-1, -1)); // 左下 p(atan2(-1, 1)); // 右下 } 0 0.785398 2.35619 -2.35619 -0.785398 注意点 atan2はy, xの順に入れる!…
Quiz https://atcoder.jp/contests/abc034/tasks/abc034_d Submit https://atcoder.jp/contests/abc034/submissions/3977225 補足 テストケースのラスト1つが通らず試行錯誤 下記のようにすると通った。表示精度の問題か・・・ double OK; ... // WA #define…
Quiz https://atcoder.jp/contests/abc035/tasks/abc035_d Submit https://atcoder.jp/contests/abc035/submissions/3976518 一般的補足 priority_queueはデフォルトでは値の大きい順に取り出す なのでgreater指定をする そのためには比較演算子 > の定義が…
Quiz https://atcoder.jp/contests/abc035/tasks/abc035_c 補足 見た瞬間「いもす法やな」と分かった 競プロを続けていくと、このように「あれとあれを組み合わせそう」と分かるのだろう その候補を増やせるように精進していく
Quiz https://atcoder.jp/contests/abc040/tasks/abc040_d Submit https://atcoder.jp/contests/abc040/submissions/3969509 補足 Union Find木を作りながらクエリに答えていく必要がある 何順にソートするか 橋作りとクエリ解答、同じ年数においてどちらを…
Quiz https://atcoder.jp/contests/abc040/tasks/abc040_c Submit https://atcoder.jp/contests/abc040/submissions/3965786 補足 1次元のDP ここから始めれば「DP怖くない」と思えるかもしれない 貪欲法でダメだというテストケース in 22 0 100 10 100 20 1…
Quiz https://atcoder.jp/contests/abc041/tasks/abc041_d Submit https://atcoder.jp/contests/abc041/submissions/3965624 解き方 editorial参照 要素 トポロジカルソート ビット演算 DP (bit DP) 感想 必要な要素が多くて大変だった
Quiz https://abc014.contest.atcoder.jp/tasks/abc014_2 Submit https://atcoder.jp/contests/abc014/submissions/3958647 // i番目のビットは立っているか X >> i & 1 補足 簡潔で使いやすい 0番目の商品から選ぶことに注意 2N通りの総当たりを試すならビ…
Quiz https://atcoder.jp/contests/abc045/tasks/arc061_b Submit https://atcoder.jp/contests/abc045/submissions/3956962 解法 O(N)で回せば間に合う 点の位置と周辺8点をカウントアップ 注意点 入力a, bがy, xの順である
私自身、editorialで分からなかったときに問題のタイトルなどで検索して他の人のブログをみて救われている そのようなヒントになれればいい ログとして、成長記録として書いている このままいい成長ができたとして、あの時点ではあの程度だったというのも情…
Quiz https://atcoder.jp/contests/abc045/tasks/arc061_a Submit https://atcoder.jp/contests/abc045/submissions/3953258 補足 差し込むかフラグの生成やevalもどきの作成など、大がかりにしてしまった Pythonならsplit, evalを使っただろう 最強最速アル…
Quiz https://atcoder.jp/contests/abc046/tasks/arc062_a Submit https://atcoder.jp/contests/abc046/submissions/3952655 学び ceilするので入力をdoubleで受け取っていたら大きい値を受けきれずにWA ll用のceilを定義し、入力もllで受けるように変更した…
Quiz https://atcoder.jp/contests/abc049/tasks/arc065_b Submit https://atcoder.jp/contests/abc049/submissions/3933727 補足 2つだし、私は find2, union2などで済ませた 他の人の解答を見ると、UnionFindクラスを作ってインスタンスを2つ作っていた な…
Quiz https://atcoder.jp/contests/agc021/tasks/agc021_b Submit https://atcoder.jp/contests/agc021/submissions/3933490 Step 1 Rを無限大に持っていくと凸包内の点などの確率が0になる 凸包を求めて垂直二等分線の角度が2πのうちのどれだけを占めるかが…
内積を求めたかったんだけど、かけ算の演算子では求まらないようだ 他の人は内積用の関数を定義している( float dot( ... ) ではかけ算は何をするのか、実際にやってみた int main() { auto c0 = complex<double>(1, 1); auto c1 = complex<double>(0, 1); auto c2 = c0 * c1</double></double>…
Submit https://atcoder.jp/contests/agc021/submissions/3928741 9.999999999999999 = 10? 上記提出コードでWAになった状態を見てみると、 9999,9999,9999,9999 を 1000,0000,0000,0000 で割った値を整数で受け取った結果 9を意図していたのに10が入ってい…
現在地 現状、緑コーダー 蟻本は簡単なところまでしか読めていない 他にも数冊持っているが中途半端 実践だ!ということでAtCoderのABCを解いていく これは有効 最初はCまで解ければいいとしていた 最近はDも理解できる(ものもある) 課題 DP ビット テスト…
Quiz https://atcoder.jp/contests/abc051/tasks/abc051_d Submit https://atcoder.jp/contests/abc051/submissions/3924971 考え方 元々の辺のコストより軽くなったら取ってよし
Quiz https://atcoder.jp/contests/abc060/tasks/arc073_b Submit https://atcoder.jp/contests/abc060/submissions/3924457 今回の盲点 wの範囲が異常に狭いので戦略が変わる 累積和の元の配列の長さが0だとエラーになる(下記コードの場合) Ac0[0] = V0[0…
Quiz https://atcoder.jp/contests/abc065/tasks/arc076_b Submit https://atcoder.jp/contests/abc065/submissions/3924290 Step1 解説pdfの通り、X, Yでそれぞれソートしてエッジを貼ればエッジ数O(N)になることに気づく Step2 最小全域木の構築 クラスカ…
Quiz https://atcoder.jp/contests/abc066/tasks/arc077_b Submit https://atcoder.jp/contests/abc066/submissions/3919723 要素 問題を上手く捉え、重複した値で挟まれていない箇所の組み合わせで求める 解説pdf参照 nCrなる組み合わせを求めるが、n=10000…
想定 7つお菓子がある 3つ買っていいよと言われた場合 どんな買い方と合計金額になるかを列挙 コード #include<algorithm> #include<complex> #include<ctype.h> #include<iomanip> #include<iostream> #include<map> #include<math.h> #include<numeric> #include<queue> #include<set> #include<stack> #include<stdio.h> #include<string> #include<string> #include<…</string></string></stdio.h></stack></set></queue></numeric></math.h></map></iostream></iomanip></ctype.h></complex></algorithm>
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/abc075/tasks/abc075_c グラフから辺を取り除いたとき、 グラフ全体が非連結になるような辺のことを橋と呼びます。 与えられたM本のうち橋である辺の本数を求めてください。 Submit https://atcoder.jp/contests/abc075/su…
Quiz https://atcoder.jp/contests/agc024/tasks/agc024_b Submit https://atcoder.jp/contests/agc024/submissions/3908452 解答を見てから通した Pからiを求める逆変換の配列Q Qで2, 6, 8とインクリメンタルになっている その時、対応するxは3, 4, 5 これ…