2018-01-01から1年間の記事一覧
beta.atcoder.jp この問題のテスト用データを自作した かなり時間が経った後、このデータが間違っていることが判明 その間、間違ったデータでテストを通そうとしてしまう コードが間違った側に誘導されてしまう ローカルでは(間違ったデータなのに)テスト…
WAが優先 TLEの方が見当を付けやすいのでそちらを直したい(通したい)気分になる しかしWAの方が論理が間違っているので重傷 WAから優先して直すべき TLEが起こったとき データ数が少ないときはACしている場合 論理はあっていそう 計算量を減らせばTLEがAC…
提出一覧 beta.atcoder.jp 2018-12-16 06:03:41ここでunordered_mapに変更 TLEにより通っていなかった問題が、一部ACに改善された
順位表 参加者 1750人(1つでも提出した人) 300点だと最大で683位 私は時間がかかったけどBまで解けたので657位 B, Cを飛ばしてDを正答している人が結構いて、その場合376位以上にいける 私はCまでしか見ていなかった レーティング 少し上がって1120. 緑コ…
問題 beta.atcoder.jp 提出 beta.atcoder.jp 感想 最頻値、2nd最頻値を求めた countしてsortして上位2つを取得 関数化したかったが戻り値が複数あるので戻り値用のstructを書いた かっちり書きすぎて業務用かと 書く時間もかかる 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>
サイズ指定 vector<ll> x, y; x.reserve(N); y.reserve(N); これは、こう書くべき。 vector<ll> x(N); vector<ll> y(N); アクセス vectorを宣言してpush_backをしていない状態で配列演算子で値を入れるというミスをした 以下のように FOR(i, 0, N){ ll v; cin >> v; x[i]</ll></ll></ll>…
Visual Studioを使うのが楽でしょうが、今回はVisual Studio Code(以下VSC)で設定してみました 前提 cppが対象 g++が入っていて、g++ hoge.cpp && ./a.out が動くとする VSCにエクステンション”C/C++ for Visual Studio Code”が入っている C++書いてたら自…
微分したり、差を取って最小値を求めたりして確かめた log(N)の方が嬉しい(計算量が小さくなる)
ノート この変形だけで計算量が減っている 参考 keita-matsushita.hatenablog.com
再現コード #include<stdio.h> #include<iostream> #include<iomanip> #include<string> #include<vector> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include<string> #include<math.h> #include<numeric> #include<complex> #include<ctype.h> using namespace std; typedef long lon…</ctype.h></complex></numeric></math.h></string></algorithm></set></map></stack></queue></vector></string></iomanip></iostream></stdio.h>
FOR(i, 0, 10){ bitset<D_MAX> flags(i); p(flags); } bitset<D_MAX> aaa(3); p(aaa[0]); p(aaa[1]); p(aaa[2]); output: 0000000000 0000000001 0000000010 0000000011 0000000100 0000000101 0000000110 0000000111 0000001000 0000001001 1 1 0 forの内側で毎回bitsetを</d_max></d_max>…
#include <ctype.h> islower(c) isupper(c)</ctype.h>
誰かの解法 beta.atcoder.jp すごくシンプルに書けている 読むと分かったような気にもなる 実際の値も入れて流れも追った しかし「完全に理解した」とは言えない 少し時間をおいて、また挑もう
問題 beta.atcoder.jp 解答 beta.atcoder.jp 補足 ベクトル的に解きたいのでcomplexを使用 90度の回転行列でベクトルを曲げる(机上計算) 和・差・負が楽だった
参考 http://www.nct9.ne.jp/m_hiroi/linux/cpp08.html#ans06 順列で書くと桁あふれする nCr, nCr-1の関係式から再帰で求められる 追記:競プロではこれを使うことはほぼなく、逆元を使う long long combination(int n, int r) { if (n == r || r == 0) retu…
beta.atcoder.jp こういうしりとりでしか使わないかもしれないけれど。 #include<valarray> #include<iostream> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define pn(s) cout << (#s) << " " << (s) << endl int main(){ string s = "abcde"; cout << </iostream></valarray>…
paiza.hatenablog.com しゃくとり虫だ 🐛(bug emoji)
問題 beta.atcoder.jp この問題ではナイーブに解くとO(N * M) いもす法を使うとO(N + M) いもす法の覚えかた いもす法で検索して本人の解説を読む 喫茶店の例までで十分 今回の問題の解答を読む サンプル1のテストデータで図を書き、いもす法のシミュレート…
#include<valarray> #include<iostream> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define pn(s) cout << (#s) << " " << (s) << endl void printValArray(valarray<int> A){ for(int a : A){ cout << a << " "; } cout << endl; } int main(){ valarray<int> A </int></int></iostream></valarray>…
#include<stdio.h> #include<iostream> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) void printArray(int *A, int n){ FOR(i, 0, n){ cout << A[i] << " "; } cout << endl; } int main(){ int A[] = {1,2,3}; printArray(A, 3); for(int v : A){ v = 0;</iostream></stdio.h>…
for(int i = 0; i < s.length(); i++) { if(s[i] == 'c' && s[i+1] == 'h'); ... というコードを見かけた 配列でやったら範囲エラー 文字列は終端 '\0' なのでOK 読むだけならね。書き換えはダメ stackoverflow.com s[-1]も読んでいいんです! beta.atcoder.…
beta.atcoder.jp Cまでは一瞬で解ける D問題 ハンバーガーの問題 ナイーブに生成すると250層に達する long longには収まるが、再帰的に解けそう ラスト2分でサンプル3が通り「できた!」と提出 最後の4テストでWA タイムアップ後 簡単な例でテストを足してみ…
#include <numeric> #define ALL(v) (v).begin(), (v).end() ... ll childSweetSum = accumulate(ALL(a), 0LL); // long long or int childSweetSum = accumulate(ALL(a), 0); include numericが必要 begin, endは定型なのでALL long longは初期値に 0LL と入れる</numeric>
c++でArrayを引数にするPrintArray(int a[])を作り、中でマクロARRAY_LENGTH(A)を使った LENGTH分だけforする予定だったが、長さがちゃんと取れない 引数がaというポインタで、ARRAY_LENGTHではsizeof(a)しているが・・・ これは配列の大きさではなくポイン…
問題 beta.atcoder.jp 提出 beta.atcoder.jp ローカルでは全部通るがサーバ側では通らない AtCoderはテストデータをDropboxで全公開している それをローカルに落としてテストしたらAC しかしサーバ側に提出するとRuntime Errorになるものがある ロジックとし…
たまに見かけるこのコード cin.tie(0); ios::sync_with_stdio(false); cin高速化と呼ばれている scanfの方が速いようだが、便利なのでcin使いたい人向け 使って計測してみた M行読み込む問題 https://beta.atcoder.jp/contests/abc113/tasks/abc113_c 302ms …
Class外に書くより中に書いた方がいいでしょう class Data{ public: int i; int p; int y; int order; static bool cmp_by_i(const Data &a, const Data &b) { return a.i < b.i; } static bool cmp_by_y(const Data &a, const Data &b) { return a.y < b.y;…
問題 beta.atcoder.jp 解答 beta.atcoder.jp 要素 class宣言 vector + 比較関数でソート 0パディング 別の0 padding (他の人を参考) coutのやり方だと覚えられないのでprintfの方がよさげ for(int m=0; m
string s; int a; // string to int stoi(s); // int to string a.to_string(); no symmetry!