頭良くなりたい人

AGC002 A - Range Product

問題はこちら atcoder.jp 方針 で場合分け（tex機能の関係で不等号の向きが不自然になってますが合ってます）。 ちなみにVS CodeをUbuntuストアからでなくMicrosoftからダウンロードしてインストールしたら日本語が打てるようになりました。 コード #include <bits/stdc++.h> using namespace std; int main(){ long a,b; cin>>a>>b; if(a<=0 && b>=0){ cout<<"Zero"<<endl; }else if(a>0){ cout<<"Positive"<<endl; }else{ i…

2020/04/29 17:53

ABC134 C - Exception Handling

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 de nihongo ga utenaku narimasita. Code #include <bits/stdc++…

2020/04/29 17:08

ABC141 C - Attack Survival

問題はこちら atcoder.jp 方針 ナイーブに 人の点数をいちいち引くのでは間に合いません。ラウンドで出た正解数は と分かっているので，各問の正解者に 点ずつ与えて，最後で一律に 点を引いても同じことです。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,k,q; cin>>n>>k>>q; vector<int> a(q); for(int i=0; i<q; i++){ cin>>a[i]; } vector<int> correct(n); //正解数 for(int i=0; i<q; i++…

2020/04/28 18:07

ABC127 C - Prison

問題はこちら 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; int tent_l=0,tent_r=0; tent_l=l[0]; tent_r=r[0]; for(int i=0; i<m-1; i++)…

2020/04/28 18:02

ABC071 B - Not Found

問題はこちら 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; while(judge==false && i<='z'){ for(int j=0; j<s.size(); j++){ if(s.at(j)==i){ exist=true; brea…

2020/04/27 20:47

ABC087 B - Coins

問題はこちら 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<a+1; i++){ for(int j=0; j<b+1; j++){ for(int k=0; k<c+1; k++){ if(500*i+100*j+50*k==x){ count++; } } } } cout<<count<<endl; …

2020/04/27 19:56

ABC084 B - Postal Code

問題はこちら atcoder.jp 方針 文字目以外がちゃんと数字になっているかチェックするのが面倒かな，と思ったら， は数字またはハイフンからなるという制約がありました。優しい。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b; string s; cin>>a>>b>>s; bool judge=true; if(s.size()!=a+b+1){ judge=false; }else if(s.at(a)!='-'){ judge=false; } for(int i=0; i<a+b+1; i+…

2020/04/27 16:45

ABC052 B - Increment Decrement

問題はこちら atcoder.jp 方針 特になし。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; string s; cin>>n>>s; int x=0; int x_max=0; for(int i=0; i<n; i++){ if(s.at(i)=='I'){ x++; }else{ x--; } if(x>x_max){ x_max=x; } } cout<<x_max<<endl; }

2020/04/27 16:39

はてなブログのTex機能についての愚痴（と対処法）

私はブログ記事内で数式を書きたいとき，はてなブログのTex機能を利用しています。 使い方は簡単で，Texのコマンドを[tex:]タグの中に書くだけです。 例えば，[tex:e^{i \theta} = \cos \theta + i \sin \theta]のように書くと， オイラーの公式が表示されます。 非常に便利なこの機能なのですが，機能自体の不完全さや，TexコマンドとMarkdown記法の衝突によって，うまく表示されないことがよくあります。 例えば， [tex: A = \left( \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 …

2020/04/24 03:28

Educational DP Contest を解く

どうも，『アルゴリズム理論の基礎』でアルゴリズムを初めて勉強しているshadeです。 まだ読了できていませんが，競技プログラミングでは頻出（多分）の動的計画法（DP）について一通り勉強したので，アウトプットも兼ねてAtCoderの「Educational DP Contest / DP まとめコンテスト」の問題を解いていきたいと思います。 順次解いた問題は追加されます。 コンテストページはこちら atcoder.jp A - Frog1 方針 足場 から足場 に辿り着くまでのコストの総和の最小値を ，足場 から足場 に行くためのコストを ，足場 から足場 に行くためのコストを と表すと， であ…

2020/04/21 03:35

超数弱が京大文系数学にどう立ち向かうか

私は一浪して予備校に通い，京都大学（文系）に合格しましたが，現役時は独学をしていました。教科書の内容すら全範囲は扱われないような高校だったので，基礎から自力で勉強する必要がありましたが，良い勉強方法がわからず，現役時は数学「だけ」のせいで落ちたと言っても過言ではありません（得点率およそ1割）。 そんな私でも，予備校生活の一年間で数学力は格段に伸びました（と言ってもせいぜい合格者平均くらいですが）。 現役の頃と浪人生活の一年では何が違ったのか考えました。もちろん予備校に通える方は通えば良いのかもしれませんが，数学がとても苦手だけど京大を目指したいという方に向けて，自分が使った参考書なども思い出し…

2020/04/19 20:39

AtCoder Problems の Boot camp for Beginners を埋めていく

AtCoder ProblemsのBoot camp for Beginnersに掲載されている問題を埋めていきたいと思います。言語は基本的にC++(g++)です。自分の復習用に記録していきますが，公開しておけば詳しい方からアドバイスがもらえたりするかもしれないと思って。AtCoder Problemsのdifficulty基準で，下に行くほど難易度が上がる（傾向がある）ようです。 Easy 100 #1 B. Power Socket #2 C. Rally #3 B. Qualification simulator #4 B. Tax Rate #5 B. Can you solve th…

2020/04/19 15:10

ABC063 B - Varied

問題はこちら atcoder.jp 方針 の各文字について， 内にそれが何個存在するかを数えています。 個以上あればアウト。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; bool check=false; for(int i=0; i<s.size(); i++){ int counter=count(s.begin(),s.end(),s[i]); if(counter>=2){ check=true; break; } } if(check==false){ cout<<"y…

2020/04/18 17:59

ABC108 B - Ruined Square

問題はこちら atcoder.jp 方針 正方形に外接する，各辺が 軸， 軸に平行であるような正方形を描いて考えました。 コード #include <bits/stdc++.h> using namespace std; int main(){ int x_1,y_1,x_2,y_2; cin>>x_1>>y_1>>x_2>>y_2; int a=y_1-y_2; int b=x_2-x_1; int x_3,y_3,x_4,y_4; x_3=x_2+a; y_3=y_2+b; x_4=x_3-b; y_4=y_3+a; cout<<x_3<<" "<<y_3<<" "<<x_4<<" "<<…

2020/04/18 17:56

ABC114 B - 754

問題はこちら atcoder.jp 方針 の 桁である部分文字列を一つずつ調べています。 ご主人様が大好きな数は なのに，問題名は で変だなと思ったら，ABC114は シリーズなんですね。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int number=0,min=0; for(int i=0; i<s.size()-2; i++){ number=stoi(s.substr(i,3)); if(abs(number-753)<min min==0){ min=abs(nu…

2020/04/17 15:00

ABC158 B - Shift Only

問題はこちら atcoder.jp 方針 工夫点は入力段階で一度偶奇判定をしていることくらいです。簡単。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; bool even=true; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; if(a[i]%2!=0){ even=false; } } int count=0; while(even==true){ for(int i=0; i<n; i++){ a[i]/=2; if(a[…

2020/04/17 14:44

ABC158 B - Count Balls

問題はこちら atcoder.jp 方針 を 個で割って，余った分を場合分け。 コード #include <bits/stdc++.h> using namespace std; int main(){ long n,a,b; cin>>n>>a>>b; long q=n/(a+b); long r=n%(a+b); if(r<=a){ cout<<q*a+r<<endl; }else{ cout<<(q+1)*a<<endl; } }

2020/04/17 14:40

ABC153 D - Caracal vs Monster

問題はこちら atcoder.jp 方針 体力 のモンスターを倒すのに必要な攻撃回数を求めるアルゴリズムを とすると， times(H){ if H=1 1 を出力 else if H>=2 2*times([H/2])+1 を出力 } と再帰的に表せます（ は最初の攻撃）。] （ガウス記号，床関数）の処理がありますが，整数型は小数点以下切り捨てなので実際には何もする必要がありません。 かなり易しい部類のD問題ですね。 コード #include <bits/stdc++.h> using namespace std; long times(long h){ if(h==1){ return 1…

2020/04/17 01:23

ABC092 B - Chocolate

問題はこちら atcoder.jp 方針 人目の参加者が期間中に食べるチョコレートの数は， を満たす （ は非負整数）の個数です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,d,x; cin>>n>>d>>x; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; } int eat=0; for(int i=0; i<n; i++){ for(int j=0; j<d; j++){ if(a[i]*j+1>d){ break; } eat++; }…

2020/04/16 17:56

AGC027 A - Candy Distribution Again

問題はこちら atcoder.jp 方針 要求するお菓子が少ない子どもから順番に配っていけばいいですが， 番目まで配って 番目の子どもに配る際は注意が必要。要求するぴったりの数でないと喜んでくれないので，別で（残っているお菓子の数）（ 番目の子どもが要求するお菓子の数）であるかを確認しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,x; cin>>n>>x; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a[i]; } sort(a.begin()…

2020/04/16 17:49

ABC116 B - Collatz Problem

問題はこちら atcoder.jp 方針 「コラッツの問題」を題材にした問題です。私は数学には詳しくないので名前は知りませんでしたが，これを題材にした入試問題を見たことがあります。 例を見れば分かりますが， になった後は の繰り返しになっています。どのような に対してもこうなるというのが「コラッツの問題（予想）」の主張で，これを証明なしに用いてコードを書いてしまいました。 AtCoderの解説PDFでは， を順番に求めていく方法が本解となっています（そりゃそうだ）。ちょうどコード例は掲載されていなかったので，近いうちにこちらの方法でのコードを追記しておきます。 コード #include <bi…

2020/04/16 02:14

ABC094 B - Toll Gates

問題はこちら atcoder.jp 方針 ごちゃごちゃした問題文ですが，求めるコストは から までにある料金所の数と， から までにある料金所の数のうち小さい方です。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m,x; cin>>n>>m>>x; vector<int> a(m); for(int i=0; i<m; i++){ cin>>a[i]; } int cost_0=0,cost_n=0; for(int i=0; i<m; i++){ if(a[i]<x){ cost_0++; }else…

2020/04/16 01:57

ABC122 B - ATCoder

問題はこちら atcoder.jp 方針 は高々10文字なので，考えられる の部分文字列をすべてチェックしています。 コード #include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; string subs; int length=0; for(int i=0; i<s.size()+1; i++){ for(int j=0; j<s.size()-i+1; j++){ bool judge=true; subs=s.substr(j,i); for(int k=0; k<i; k++){ if(su…

2020/04/16 01:45

ABC142 C - Go to School

問題はこちら atcoder.jp 方針 問題文を読むと，出席番号 番の生徒は 番目に登校したことが分かります。つまりこれを変換して， 番目に登校した生徒の出席番号 を出力する配列を作れば終わりなのですが，ここで頭が混乱してしまいました。ということでC++のレファレンスを調べていると，vector<pair>で2要素をペアにして扱えるらしいことが分かったので，そちらを使って実装しています。firstに ，secondに の情報が入っています。この状態でsortすると，firstが小さい順 secondが小さい順でソートされます。なお，AtCoderの解説PDFでは，最初に示した方法が華麗に実装…

2020/04/16 01:06

ABC138 C - Alchemist

問題はこちら atcoder.jp 方針 「最後に残る具材の価値を最大にしたい」ということは，「 回目の操作で最も価値の大きい2つを鍋に投入したい」ということです。 鍋に入れられた具材の影響力は回数を経るごとに で割られて小さくなっていくので，価値の小さい具材から鍋に入れていけばいいです。コード中では， 回目の操作のみint型同士の計算になるので，double型に変換して小数点以下が出るようにしています（もともと をdouble型で宣言すれば済む話ですが，どっちの方が綺麗なコードなんでしょうか）。 コード #include <bits/stdc++.h> using namespace std…

2020/04/15 16:06

ABC132 C - Divide the Problems

問題はこちら atcoder.jp 方針 題意の を値の小さい順に並べ替えると，求める の個数は， より大きく， 以下である整数の個数に等しい。簡単な問題なんですが，僕は最初 for(int i=d[n]; i<d[n-1]+1; i++){ int arc=0,abc=0; for(int j=0; j<n; j++){ if(d[j]>=i){ arc++; }else{ abc++; } } if(arc==abc){ count++; } } こんな大層なループを作ってTLEになりました。脳死はいけません。 コード #include <bits/stdc++.h> using name…

2020/04/15 00:10

ABC161 C - Replacing Integer

問題はこちら atcoder.jp 方針 例3が見るからにTLEを誘っているので，馬鹿正直に題意の操作をするのは断念。 のとき，題意の操作により は となっていきます。 となるまでこの操作を続ける（ を で割り切れなくなるまで割る）と，（ : を で割った余り）となり，以後 のときに合流します。問題は のときですが，これは操作を続けても か にしかならないので，このうち小さい方を出力すればいいですね。 コード #include <bits/stdc++.h> using namespace std; int main(){ long n,k; cin>>n>>k; long surplus=n…

2020/04/15 00:00

AGC014 A - Cookie Exchanges

問題はこちら atcoder.jp 方針 言われた操作を記述するだけですが，while内を単に … a=b/2+c/2; b=c/2+a/2; c=a/2+b/2; … などとしてしまわないように注意。きれいな漸化式なのでやりたくなります。 「無限回操作が行える 有限回の操作後，初期状態に戻る」と解釈しています（証明はしていません）。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a_ini,b_ini,c_ini; //A,B,Cの初期値 cin>>a_ini>>b_ini>>c_ini; int a=a_…

2020/04/14 17:42

ABC160 C - Traveling Salesman around Lake

問題はこちら atcoder.jp 方針 一番距離の遠い家と家の間を避けて湖を一周すればいいです。 と の間は原点を通るので別で計算しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int k,n; cin>>k>>n; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a.at(i); } int d_max=0; for(int i=0; i<n-1; i++){ if(d_max<a.at(i+1)-a.at(i)){ d_max=a.at(i+1)-a.a…

2020/04/14 17:34

ABC068 B - Break Number

問題はこちら atcoder.jp 方針 特に難しい点はありませんが， のとき が出力されないよう変数maxを で初期化しています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int count_max=0; int max=1; // 求める整数 for(int i=1; i<n+1; i++){ int count=0; int j=i; while(j%2==0){ j/=2; count++; } if(count>count_max){ count_max=count; m…

2020/04/14 17:31

ABC088 B - Card Game for Two

問題はこちら atcoder.jp 方針 与えられた を大きい順にソートして，交互に取ってもらっています。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> a(n); for(int i=0; i<n; i++){ cin>>a.at(i); } int alice=0,bob=0; // aの要素を大きい順にソート sort(a.begin(),a.end()); reverse(a.begin(),a.end()); if(n%2==0){ for(int i=…

2020/04/14 01:58

ABC074 B - Collecting Balls (Easy Version)

問題はこちら atcoder.jp 方針 「これら 台のロボットのうちいくつかを起動して」なんて言われると身構えてしまいますが，各 に対して，ボールと近い方のロボットを起動するだけですね。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,k; cin>>n>>k; vector<int> x(n); for(int i=0; i<n; i++){ cin>>x.at(i); } int d_sum=0; for(int i=0; i<n; i++){ if(x.at(i)<k-x.at(i)){ d_sum…

2020/04/14 01:55

ABC086 B - 1 21

問題はこちら atcoder.jp 方針 と を数値として受け取るか文字列として受け取るか迷いましたが，数値だと桁数による場合分けが必要な解法しか思いつかなかったので文字列扱いにしています。 string型で受け取ってもstoi関数でint型に変換できるので便利ですね。平方数かどうかの判定は， が整数になるかどうかで行っています。これが本解かと思いましたが，AtCoderの解説PDFでは を総当たりで調べています。 コード #include <bits/stdc++.h> using namespace std; int main(){ string a,b; cin>>a>>b; int a…

2020/04/13 20:07

ABC157 B - Bingo

問題はこちら atcoder.jp 指針 例によってスマートな解き方が分かりません。数字表と判定表の2つのビンゴシートを作って穴が開く場所を先に調べ，後からビンゴの成立を調べています。本問は のビンゴなので何でもないですが， だったりした場合にはビンゴの成立判定を工夫する必要がありそうですね。 コード #include <bits/stdc++.h> using namespace std; int main(){ vector<vector<int>> a(3,vector<int>(3)); vector<vector<bool>> a_m(3,vector<bool>(3)); for(…

2020/04/13 17:45

パナソニックプログラミングコンテスト2020 B - Bishop

問題はこちら atcoder.jp 指針 問題を読んでもあまり意味が分かりませんが，よくよく例を見てみれば，左上端（初期位置）を としたとき， の と の偶奇が一致するマス目に印がつくことになりそうです。文中の条件式からも と の偶奇が一致しないマス目には行けないことが分かります。 と をint型で宣言すると例3でオーバーフローしてしまったので，long型にしています。 コード #include <bits/stdc++.h> using namespace std; int main(){ long h,w; cin>>h>>w; if(h==1 w==1){ cout<<1<<end…

2020/04/13 17:43

三井住友信託銀行プログラミングコンテスト2019 B - Tax Rate

問題はこちら atcoder.jp 指針 こういう小数の処理にはかなり苦手意識があります。 とりあえず で仮の を出しておいて，その で逆算してうまく行かなければ と を試してます。 センスがないコードでごめんなさい。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; int x; x = n / 1.08; int n_p1=x*1.08; int n_p2=(x+1)*1.08; int n_p3=(x+1)*1.08; if(n_p1==n){ cout<<x<<endl; }else…

2020/04/13 15:20

ABC139 B - Power Socket

問題はこちら atcoder.jp 指針 特に言うことはないです。指示通り。 コード #include <bits/stdc++.h> using namespace std; int main(){ int a,b; cin>>a>>b; int socket=1; int i=0; while(socket<b){ socket+=a-1; i++; } cout<<i<<endl; }

2020/04/13 15:16

CODE FESTIVAL 2016 qual B B - Qualification simulator

問題はこちら atcoder.jp 指針 問題文中の 国内の学生は、現在予選の通過が確定した参加者がA+B人に満たなければ、予選を通過する 海外の学生は、現在予選の通過が確定した参加者がA+B人に満たず、さらに海外の学生の中での順位がB位以内なら、予選を通過する を忠実に実装していきます。 「現在予選の通過が確定した海外の学生がB人に満たない」と言えばいいところを，「海外の学生の中での順位がB位以内」という表現を使っているのはなぜだろうかとちょっと考えましたが，同義と捉えて問題ないです（ですよね？）。 コード #include <bits/stdc++.h> using namespace s…

2020/04/13 14:57

ABC121 B - Can you solve this?

問題はこちら atcoder.jp 指針 問題文の通り。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n,m,c; cin>>n>>m>>c; vector<int> b(m); for(int i=0; i<m; i++){ cin>>b.at(i); } vector<vector<int>> a(n,vector<int> (m)); for(int i=0; i<n; i++){ for(int j=0; j<m; j++){ cin>>a.at(i).at(j); } } int count=0;…

2020/04/13 14:42

ABC156 C - Rally

問題はこちら atcoder.jp 指針 スマートな方法が思いつかなかったのでローラー作戦。 なのでそれでも問題なさそう。問題文通りに整数 と一次元ベクタ を宣言して， の最小の要素から最大の要素までの範囲で を動かし，求める最小値を出しました。 コード #include <bits/stdc++.h> using namespace std; int main(){ int n; cin>>n; vector<int> x(n); for(int i=0; i<n; i++){ cin>>x.at(i); } int sum=0,sum_min=0; sort(x.begin(),x.end…

2020/04/13 13:12