2020-01-01から1年間の記事一覧
問題はこちら atcoder.jp 方針 「 の末尾を取得し, の先頭に挿入→ の末尾以外を とする」という操作で, を「回転」させることができます。 を回転させて得られる文字列は高々 種類なので, 回の操作後までに と一致するか調べればよいです。 コード #inclu…
問題はこちら atcoder.jp 方針 を辞書順にソートし,連結すればいいのですが,C++ではsort関数でstringもソートできるので簡単です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,l; cin>>n>>l; vector<string> s(n); for(int i=0; i<n; i++){ cin>>s[i]; } sort(s.b</n;></string></bits/stdc++.h>…
問題はこちら atcoder.jp 方針 「 を辞書順にソート→ を高い順にソート」という方針で解けそうですが,市名,点数,レストランの番号の3変数をどう扱うか。 ということで,tupleを使ってみました。 解説PDF では,pairを入れ子にして3変数を扱っています。ど…
問題はこちら atcoder.jp 方針 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> t(n); for(int i=0; i<n; i++){ cin>>t[i]; } int m; cin>>m; vector<int> p(m),x(m); for(int i=0; i<m; i++){ cin>>p[i]>>x[i]; } for(int i=0; i</m;></int></n;></int></bits/stdc++.h>
問題はこちら atcoder.jp 方針 によって税抜き価格のあたりをつけるのですが,int型は小数点以下切り捨てであるという性質上,本当の税抜価格は,a_sup,b_sup以上の整数です。 a_sup,b_sup以上である周辺の整数のうち,条件を満たすものが見つかり次第それを…
問題はこちら atcoder.jp 方針 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b,k; cin>>a>>b>>k; for(int i=0; i<k; i++){ if(a+i>=((double)a+b)/2){ break; } cout<<a+i<<endl; } for(int i=k-1; i>=0; i--){ if(b-i<((double)a+b)/2){ continue; } cout<</a+i<<endl;></k;></bits/stdc++.h>
問題はこちら atcoder.jp 方針 構造的に難しい点はありませんが,2点間の距離の公式がやや複雑なのでコードもごちゃごちゃしています。 私は整数かどうかの判定は,「int型とdouble型の値が一致するか」,という発想をよく用いるのですが,他にやっている人…
問題はこちら atcoder.jp 方針 「その単語はまだ発言していない単語である」ことと「その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する」ことを確認しています。計算量が少ないので特に工夫はしていません。 コード #include <bits/stdc++.h> using namespac</bits/stdc++.h>…
問題はこちら atcoder.jp 方針 to_stringを使ってみたかったので複雑になっています。 digit_sum+=i_str[j]-'0'の-'0'については,こちらを参考にしました。ASCIIコードでは文字'0'が48に対応しているらしいです。 コード #include <bits/stdc++.h> using namespace std; in</bits/stdc++.h>…
問題はこちら atcoder.jp 方針 各都市ではなく道路に注目しています。C. Peaks(記事にする予定)と似た発想です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> a(m),b(m); for(int i=0; i<m; i++){ cin>>a[i]>>b[i]; } vector<int> count(n</int></m;></int></bits/stdc++.h>…
問題はこちら atcoder.jp 方針 ボタンの挙動は問題文の通りに作ります。 問題はボタン が点けられるかの判定ですが, 回の操作後までにボタン が光らない場合,初期のボタン も含めてこれまでに 回ボタンが光っています。ボタンの数は 個なので,少なくとも …
問題はこちら atcoder.jp 方針 あらかじめ縁のための配列を確保しておきます。 コード #include <bits/stdc++.h> using namespace std; int main(){ int h,w; cin>>h>>w; vector<vector<char>> a(h+2,vector<char>(w+2)); for(int i=1; i<h+1; i++){ for(int j=1; j<w+1; j++){ cin>>a[i][j]; } } for(int j=0; j</h+1;></char></vector<char></bits/stdc++.h>
問題はこちら atcoder.jp 方針 以上の整数 について, 未満のすべての素数で割り切れなければ, は素数である,という普通の素数判定。 コード #include <bits/stdc++.h> using namespace std; int main(){ int x; cin>>x; vector<int> p={2}; bool not_prime=false; int i=2; wh</int></bits/stdc++.h>…
問題はこちら atcoder.jp 方針 のように を小さくしながら考えます。それぞれの に対して を最大にする貪欲法を用いています。ある A_i は B_i-1, B_i にのみ制約されるので,貪欲法で最適解が求まります。 (アルゴリズムがほぼ分からないので雰囲気で言っ…
問題はこちら atcoder.jp 方針 まず の桁数を比較し,それが同じ場合には大きい位の値から比較していきます。 コード #include <bits/stdc++.h> using namespace std; int compare(string x,string y,int i); int main(){ string a,b; cin>>a>>b; int i=0; if(a.size()>b.si</bits/stdc++.h>…
問題はこちら atcoder.jp 方針 番目のマスから順に試していき,最大値が出るたびに暫定の最大値を更新しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<long> h(n); for(int i=0; i<n; i++){ cin>>h[i]; } int count=0,count_temp=0; for(</n;></long></bits/stdc++.h>…
問題はこちら atcoder.jp 方針 普通に足すだけ。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<long long> l(n+1); l[0]=2,l[1]=1; for(int i=2; i<=n; i++){ l[i]=l[i-1]+l[i-2]; } cout<</long></bits/stdc++.h>
問題はこちら atcoder.jp 方針 「どの隣り合う 枚のタイルも異なる色で塗」るということは,10101...か01010...のいずれかです。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int count_1=0,count_2=0; //10101... for(int i=0; i</bits/stdc++.h>
問題はこちら atcoder.jp 方針 回ループを回せば良いのですが, 秒( 年)かかってしまいます。 対称性があるので綺麗に消えそうだなと思いつつ,与 をそれぞれ , 回の操作後の を として式をいじっていると, ※4行目の添字K-1はK-2の間違いです。 すごいで…
問題はこちら atcoder.jp 方針 いっぱいループしました。 コード #include <bits/stdc++.h> using namespace std; int main(){ string w; cin>>w; vector<int> count(26); bool check=true; char c='a'; for(int i=0; i<26; i++){ for(int j=0; j</int></bits/stdc++.h>
問題はこちら atcoder.jp 方針 ゴリゴリ調べる。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> k(n); vector<vector<int>> a(n, vector<int>(m)); for(int i=0; i<n; i++){ cin>>k[i]; for(int j=0; j<k[i]; j++){ cin>>a[i][j]; } } bool check=false; int count=0,loved=</k[i];></n;></int></vector<int></int></bits/stdc++.h>…
5月になりました。みなさんいかがお過ごしでしょうか。 ピカピカの新大学生の私はずっと家にいて,まだ1回しか登校していません。京アニでも見た鴨川の桜がとても綺麗だったのを覚えています。 とは言えいい加減春休みも終わるので,ブログに関係する今やっ…
問題はこちら atcoder.jp 方針 「任意の整数 に対して,」「( の最小値)」です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> p(n); for(int i=0; i<n; i++){ cin>>p[i]; } int temp_min; int count=1; // i=1は常に条件を満たす temp_min</n;></int></bits/stdc++.h>…
問題はこちら atcoder.jp 方針 で場合分け(tex機能の関係で不等号の向きが不自然になってますが合ってます)。 ちなみにVS CodeをUbuntuストアからでなくMicrosoftからダウンロードしてインストールしたら日本語が打てるようになりました。 コード #include <bits/stdc++.h></bits/stdc++.h>…
Mondai wa kochira atcoder.jp Houshin ga de saidai no youso deatta baai wa, 2-banme ni ookii youso wo syuturyoku simasu. sore igai no baai wa sonomama saidai no youso wo syuturyoku sureba iidesu. Ubuntu 20.04 LTS ni upgrade shitara, VS Code…
問題はこちら atcoder.jp 方針 ナイーブに 人の点数をいちいち引くのでは間に合いません。ラウンドで出た正解数は と分かっているので,各問の正解者に 点ずつ与えて,最後で一律に 点を引いても同じことです。 コード #include <bits/stdc++.h> using namespace std; int m</bits/stdc++.h>…
問題はこちら atcoder.jp 方針 枚だけで全てのゲートを通過できるIDカードは, から まですべての共通範囲です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin>>n>>m; vector<int> l(m),r(m); for(int i=0; i<m; i++){ cin>>l[i]>>r[i]; } bool exist=true;</m;></int></bits/stdc++.h>…
問題はこちら atcoder.jp 方針 AからZまでのアルファベットが 文字で, より,全探索でも 回以下のループで済みます。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; bool judge=false; bool exist=false; char i='a'; char result;</bits/stdc++.h>…
問題はこちら atcoder.jp 独り言 この問題AtCoderでやったことある気がするけど印ついてなかった。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b,c,x; cin>>a>>b>>c>>x; int count=0; for(int i=0; i</bits/stdc++.h>
問題はこちら atcoder.jp 方針 文字目以外がちゃんと数字になっているかチェックするのが面倒かな,と思ったら, は数字またはハイフンからなるという制約がありました。優しい。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b; string s; cin</bits/stdc++.h>…