おはやし日記

テーマ……バイク←プログラミング←旅

C++

座標圧縮備忘録

座標圧縮、なるアルゴリズムに出会いました。どうにかわかったつもりになったので記録しておきます。自分用メモ的な精度。 座標圧縮とは 詳しくは参考のサイトを見てください。 簡単に言うと、「座標の広い範囲に散らばっている点について、その相対的な位置…

AtCoder M-SOLUTIONS プロコンオープン 2020 反省会 [A,B,C,D完][C++]

久しぶりの参戦。 A #include <bits/stdc++.h> using namespace std; int main(){ int x;cin>>x; if(x<600)cout<<8<</bits/stdc++.h>

AtCoder ABC173 反省会 [A,B,C,D完][C++]

こんにちは。ABC173でした。 ギリチョンDまで解けました。 A A - Payment int main(){ int n;cin>>n; for(int i=0; i<20; i++){ if(n<=i*1000){ cout<<(i*1000)-n<<endl; return 0; } } } なんかまどろっこしいけど通るから………… B B - Judge Status Summary int main(){ int N;cin>>N; int ac=0, wa=0, tle=0, re=0; rep(n,N){ string s;cin>>s; if(s=="AC")ac++; i…</endl;>

Codeforces 1373 D. Maximum Sum on Even Positions

こんにちは。こどふぉでした。 C、bit全探索でそれなりの数sを生成してもpseudocodeと自分のコードに差が出ないので原因不明だ— おはやし (@hys2490_tw) June 25, 2020 はい、もしやと思ってintを全部long longにしたら通りました気づくのが遅すぎる— おはや…

Codeforces 1370 D. Odd-Even Subsequence

こどふぉでした。 3完でした。 (二分探索といえばlower_boundや!って思ってたので)↓ 二分探索とは なるほど〜〜〜 探索条件について ok な範囲と ng の範囲を左右から伸ばしていくという感じですね AtCoder灰・茶・緑色の方必見!二分探索を絶対にバグら…

AtCoder ABC171 反省会 [A,B,C,D,E完]

こんにちは。ABC171でした。 5完でした!!! 即席解説記事行きます A 愚直な実装。 #include <bits/stdc++.h> using namespace std; int main(){ char x;cin>>x; if('A'<=x && x<='Z')cout<<"A\n"; else cout<<"a\n"; } B ソートして小さい方から $K$ 個取る。 #include <bits/stdc++.h> u</bits/stdc++.h></bits/stdc++.h>…

Codeforces #650 D. Task On The Board を解く(こどふぉ 問題文和訳あり)[C++]

こんにちは。まさかのこどふぉへ進出。 Cまで解きました。 で、Dの解説とサンプルコード(Codeforces Round #650 (Div. 3) Editorial - Codeforces)を読んだらなるほどぉ〜〜〜ってなったので自分で書いてみます。 問題 https://codeforces.com/contest/136…

AtCoder ABC170 E - Smart Infants を解く [C++]

こんにちは。昨日はABC170でした。 o-treetree.hatenablog.com Eが、multisetとかいうのを使って実装すれば解けるよって解説に書いてあったのでやってみたところ、1つだけWAが出てわけわからんになったので(https://atcoder.jp/contests/abc170/submissions…

AtCoder ABC170 反省会 [A,B,C,D完, E追記]

こんにちは。ABC170でした。 ↑意気込み ↑謎の予言 (追記:Eも解けたので良ければ見ていってください o-treetree.hatenablog.com ) A 1:37で提出 #include <bits/stdc++.h> using namespace std; int main(){ vector<int> x(5); for(int i=0; i<5;i++)cin>>x[i]; for(int i=0; i</int></bits/stdc++.h>…

自作デバッグ関数の覚書き

プログラム書いていて、途中結果を出力したいときってありますよね。うんうん。 今まで こんな感じでやってました #include <bits/stdc++.h> using namespace std; #define debug(x) cout<<#x<<" = "<<(x)<</bits/stdc++.h>

グラフの関節点と橋を求めて再帰DFSを知る

こんにちは。再帰のDFS(深さ優先探索)っていままでよくわからなくて、スタックを使えばBFS(幅優先探索)の書き換えで済むじゃんと思っていました。過去記事でもスタックDFSを使っています。 o-treetree.hatenablog.com ただ、スタックDFSは「順番がDFSで…

AIZU ONLINE JUDGE GRL_1_A 単一始点最短経路 を解くダイクストラ法の実装

こんにちは。 o-treetree.hatenablog.com ちょっと前にAOJの問題を解いて動的計画法を学びましたが↑、グラフも勉強しようかなって思ってグラフのページを開きました。1番最初にあったのが 単一始点最短経路 です。何も知らない僕は最初幅優先探索でやりまし…

AtCoder ABC169 反省会 [A,B,D,E完]

こんにちは。ABC169でした。 atcoder.jp 感想 なんでぇ? それでは、振り返っていきましょう。スピード重視の雑解説(?)です。 A やるだけ。33秒で提出できました。 #include <bits/stdc++.h> using namespace std; int main(){ int A,B;cin>>A>>B; cout<</bits/stdc++.h>

AtCoder ABC134 E - Sequence Decomposing を解く [C++]

こんにちは。今夜はABC169です。ここ数日競プロに触ってなかったので、やっとくか!ということで未解答だったABC134に挑戦しました。そしたらE問題が、先日勉強したDPの応用ですらっと解けて嬉しかったので書いています。 o-treetree.hatenablog.com こちら…

DP(動的計画法)でレーベンシュタイン距離(編集距離)問題を解くまでの過程メモ

昨日は最長増加部分列の問題を解きました https://o-treetree.hatenablog.com/entry/DPL1D 今日は、AOJの編集距離の問題を解きます。 といっても、相変わらずDPテーブルは思いつかなかったので検索してわかりやすかった解説を紹介する感じです。 参考にする…

DP(動的計画法)で最長増加部分列(LIS)問題を解くまでの過程メモ

なんか連載みたいになってんな 前回はDPでナップザック問題を解きました。 AOJでその次にあった最長増加部分列を解きました。 というか、解けなかったので検索して最長増加部分列(LIS)の長さを求める - Qiitaを見てなるほど〜ってなったのを自分なりにまとめ…

DP(動的計画法)でナップザック問題を解くまでの過程メモ

0-1 ナップザック問題 この0-1ナップザック問題が解けたので動的計画法初心者がその思考過程を記録しておく。 その後、簡単な書き換えによって一般ナップザック問題(命名: おはやし)が解けたので追記している。 先にコイン問題 前段階としてコイン問題(何…

DP(動的計画法)でコイン問題を解くまでの過程メモ

これは、https://o-treetree.hatenablog.com/entry/DPL1B(明日投稿)の前段階の記事です。動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)で「コイン問題」を解いていますが、DPとはなんぞや、みたいなところには触れておらず、解説を見…

vector<pair>のソートの覚書き [C++]

なんとなくpairをソートしてみたら面白かったのでメモする。 pairにも大小関係があるのでソートできる マクロばっかで申し訳ないがとりあえず昇順ソート #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; #define mp make_pair #define ff first #define s</int,></bits/stdc++.h>…

AtCoder ABC138 C - Alchemist のわかりやすい解説

atcoder.jp 解説PDFわかりにくすぎてタイトルに「わかりやすい解説」って書いちゃった 問題概要 $N$ 項の数列 $ \{ v_1, v_2, v_3, \cdots , v_N \} $ がある。ここから2つの数字 $v_a, v_b$ を取り出して、その平均 $ \frac{v_a+v_b}{2} $ を戻す。 この操…

AtCoder ABC139-E を有向グラフ初心者がC++で解く

ABC139 - E に挑戦します。 最初は、n日目に出場する選手のリストを作って探索しようと思いましたがうまくいかず、解説を読む。 https://img.atcoder.jp/abc139/editorial.pdf 「$N(N-1)/2$試合のそれぞれを頂点に見立て、(略)有向グラフを考えます。」「…

AtCoder ABC168【ABCD=AC】

こんにちは。ABC168でした。 今回は48分でDまで解けました!しかもWA無し! Eはまだ無理ですね、見当もつかない。 A 提出 AC #include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ int N; cin>>N; N %= 10; switch(N){ case 2: case 4: case 5</bits/stdc++.h>…

AtCoder ABC165-Cをスタック利用DFSで解く

概要 atcoder.jp これをc++で解く。 概要 解答 コード 詳細 初期状態 スタックについて ABC165-Cの条件に合わせる 得点計算 提出コード 一応おしまい 失敗 参考 この問題を解くには、生成しうる数列を全て作って各々数列の得点を求め、最大値を見つける。(…

cとc++で最大公約数、最小公倍数を求める

gcdとlcmの実装 最大公約数(GCD : Greatest Common Divisor)と最小公倍数(LCM : Least Common Multiple)を求めるプログラムをc言語で書いてました。競プロ(AtCoder)で使うためです。最近使用言語をc++に乗り換えたのでcからc++に書き換えていたら色々…

競プロABC問題風記事の解説

これの解説記事です。先に↑を見てください。ちなみに「ABC問題」は数学の難問「ABC予想」のことではありません。競技プログラミングの「AtCoder Beginner Contest」の略称です。 なお、この解説が正しいかどうかは(全文に渡って)保証しかねます。多分あっ…

AtCoder ABC167【3完】

こんにちは。 ↑これは昨日の僕。今日が当日です。 今回はAからCまで、1発ACでした。Dは時間的に無理だったし細かい実装もわからんので諦めた A atcoder.jp 提出 AC #include <bits/stdc++.h> using namespace std; int main(){ string s, t; cin>>s>>t; int l = s.size(); f</bits/stdc++.h>…

ABC165, 166反省会

ABC165 A 提出 B 提出 C ABC166 A 提出 B 提出 C 提出 D ABC165 ダメでした A A - We Love Golf 提出 AC #include <stdio.h> int main(){ int K, A, B; scanf("%d%d%d",&K,&A,&B); int bl = 0; for(int i=A; i<=B; i++){ if((i%K)==0)bl++; } if(bl){ printf("OK\n");</stdio.h>…

makefileを利用して簡単にmac,VSCodeでbits/stdc++.hを使う

こんにちは。 競プロではC++が強いそうですね。 C++ではインクルードファイルとして #include <iostream> //入出力 #include <string> //文字列 #include <vector> //配列 ... 等々書くそうですが、面倒なのでAtCoderでは<bits/stdc++.h>を使うと良い、という話になっています。 これは、gccに付属する</bits/stdc++.h></vector></string></iostream>…

プライバシーポリシー ・お問い合わせはこちら