結構悩んで解いた問題。 解説を読んでも if(t[i] < i) flg = false; の部分がずっとハテナだったけどt[i]はデッドラインだからデッドラインが今割るべき時間iより小さかったらNG #include<bits/stdc++.h> using namespace std; int n, h[100009], s[100009]; int main(){ ci</bits/stdc++.h>…

少し紙に書いて考えたら、なるほどーって閃いた問題 中部を基準として決め打ちすると ・基準より小さいものを上部から選ぶ ・基準より大きいものを下部から選ぶ というそれぞれの二分探索を行えば作れる祭壇のパターン数が分かる あとは全中段のパターン数を…

宅配先に近い店舗を二分探索で見つける。 今回は探したいものが環状線になっているのでd-1と0をまたぐ必要がある →番兵としてdの箇所にも店舗を置いておく(本店の座標は0=d) あとはd[i] < kを満たすような最大のd[i]を見つけて、kを跨いだ隣の店舗d[i+1]との…

T[i]がSの中に含まれているかを二分探索する。 二分探索は関数化すると実装しやすい。 問題とは関係ないけど、macを購入してから初めてのAC 自分の持ってるwindows機より軽くて持ち運びやすいmacbook airで競プロできるのは勉強時間増えるのでGOOD #include<bits/stdc++.h> </bits/stdc++.h>…

有名な8クイーン問題 ・同じ行、同じ列にクイーンを置かないこと ・左斜め上、左斜め下、右斜め上、右斜め下にクイーンを置かないこと 上記2点を満たせばよい。 ・同じ行、同じ列にクイーンを置かないこと ⇒順列そのままで全列挙可能なので判定は不要 ・左斜…

問題文通り vector <int> v; for(int i=0;i<n;i++) v.push_back(i+1); do{ }while(next_mermutation(begin(v), end(v))); 上記テンプレを覚えればとりあえずOK #include<bits/stdc++.h> using namespace std; int n; int p[9], q[9]; vector < int > v; int main(){ cin >> n; for(int i=0;i<n;i++) cin >> p[i]; for(int i=0;i<n;i++) cin >> q[…</n;i++)></n;i++)></n;i++)></int>

問題文通りに実装するだけ こういう系って再帰で実装できなかったかなぁー？とこねくり回したけどうまく書けず ググったら便利な関数出てきてほぼ写経 #include<bits/stdc++.h> using namespace std; int n; int x[10], y[10]; vector < int > v; int main(){ cin >> n; for</bits/stdc++.h>…

WAの嵐 bit探索で1を対象のビルとして左から順に探索するだけ。 1のビルの時しかpre_maxを更新していなかったので N=3,K=4 a={1, 10000, 2, 3} のようなテストケースを逃していて大量WA あと最初はlong longも忘れてた #include<bits/stdc++.h> using namespace std; int n,</bits/stdc++.h>…

問題だけ読んでほったらかしてたら急に解法が降ってきた。 例のごとく000...000 ~ 111...111までのbitでR列目をひっくり返した場合にどうなるかをC行に試す全探索を行う。 C行目は独自にひっくり返せれるのでmax(1のbit数, 0のbit数)を考えればよい。 すぐに…

結構苦労した. グループとなり得るパターンはn人をそれぞれbitのi番目に存在するか否かで考えると0000....000から1111....1111の2^nで表せれる あとは適当な2人がグループのパターンに沿っている かつ 知り合いならばok 違うならngという感じで探していく 最…

電球M[i]に使うスイッチをビットで管理する スイッチのON/OFF全パターンとM[i]のビットのマスクを取って1の数をカウント カウントの剰余がP[i]と一致していればめでたく電球M[i]は点灯 そういえば今回は書かなかったけどビットカウントをするときは for(int …

電球M[i]に使うスイッチをビットで管理する スイッチのON/OFF全パターンとM[i]のビットのマスクを取って1の数をカウント カウントの剰余がP[i]と一致していればめでたく電球M[i]は点灯 そういえば今回は書かなかったけどビットカウントをするときは for( i=b…

bit全探索 毎クエリ計算しているとTLEになるのでクエリの外で前計算してテーブルに持たせておいて,各クエリの処理はテーブルを参照する クエリ処理は気をつけよう…(反省) #include<bits/stdc++.h> using namespace std; int n; int q; int a[29]; map < int, bool > mp; int</bits/stdc++.h>…

これと同じ感じ気が付けば過去問精選100問の工夫して通り数を減らす全列挙まで終了 tanukistune.hatenablog.com #include<bits/stdc++.h> using namespace std; int m, n; vector < pair<int, int> > vm; vector < pair<int, int> > vn; map < pair<int, int >, bool > np; int main(){ cin >> m; for(int i</int,></int,></int,></bits/stdc++.h>…

パッと見た瞬間,A[0]~A[n-1]の間のどこかに入り口があってB[0]~B[n-1]の間のどこかに出口がありそうってなる 最悪のケースで最左端から最右端の可能性もあるしなぁってなりながらもとりあえず2分探索書いてみたけどサンプル合わず サンプルよく見てみると入…

愚直にやるとO(N^4)でキツい 正方形の性質としてある1辺の長さと残りの3辺の長さが同じである つまり任意の2点の距離が分かれば残りの2点は推測できるため,2点を調べるためのO(N^2)で済む ここまでは分かってたのに 面積=a*a+b*b で済むところを sqrt(a*a+b*…

愚直にやるとO(N^3) 3桁が肝っぽいなーと思いつつも分からないので解説へ 000~999がN文字で作れるかを見るとO(10^3*N)でOK (10^3は定数だから無視…？まぁいいや) #include<bits/stdc++.h> using namespace std; int n; string s; int main(){ cin >> n; cin >> s; int cnt =</bits/stdc++.h>…

この問題…過去の社内コンテストで同じの出たぞ…！！ 一応全探索で解いた ピザCの枚数が決まればピザAとピザBの枚数も決まるからピザCの枚数をループで回しながら答えを探す #include<bits/stdc++.h> using namespace std; int a, b, c, x, y; int main(){ cin >> a >> b >> </bits/stdc++.h>…

全列挙最終問題一人が2曲歌っても点数の高い方しか加点されないことに注意 異なる2曲の選び方を0<=i<mとi+1<=j<mのiとjで表現するとi<jかつi!=jになる #include<bits/stdc++.h> using namespace std; int n, m; long long int a[109][109]; int main(){ cin >> n >> m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin >> a[i][j]; long long ans = 0; for(int i=0;i</n;i++)></mとi+1<=j<mのiとjで表現するとi<jかつi!=jになる>

全探索問題 サンプル2 HATAGAYA の出力結果が5なのに驚いた パッと見そんなにあるように思えない… #include<bits/stdc++.h> using namespace std; string s; int main(){ cin >> s; int ans = 0; for(int i=0;i</bits/stdc++.h>

全探索問題2問目 奇数って条件を忘れないように (サンプル合わなくて焦った) #include<bits/stdc++.h> using namespace std; int n; int main(){ cin >> n; int ans = 0; for(int i=1;i<=n;i+=2){ int cnt = 0; for(int j=1;j<=i;j++){ if(i%j == 0) cnt++; } if(cnt == 8) </bits/stdc++.h>…

なんか解説見てばかりだったので過去問精選 100 問でアルゴリズム力つけてから典型90問やろうかな まずは全探索から a + b + c = x を満たす a, b, c を探すのは3重ループでも良いけど x - a + b = c って式変形するとループ一つ減らせるってのは過去に何か…

6問目！！ 5問目はムズすぎて飛ばしました. 社内コンテストに向けてだから…ね 一周したらまた戻ります パッと見でDPかなーって思ったけどO(NK)とか10^10だしなぁ 辞書順だから貪欲か？でも選び方分かんねぇーって事で解説へ 後ろから精査して前から何番目に…

パッと見た瞬間に累積和 初めて解説に頼らずAC まぁ☆2だしね #include<bits/stdc++.h> using namespace std; int h, w; int a[2009][2009], b[2009][2009], c[2009][2009]; int main(){ cin >> h >> w; for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) cin >> a[i][j]; for(in</bits/stdc++.h>…

初見ダイクストラか？って思ったけどなんかグラフが簡潔過ぎやしないかと違和感 多分自分の知らないやつや！って事で早速解説へ 木の直径:ノード最短距離の最大値 単語はにわかに知っていたが意味は初知り 1.まず適当なノードを選んでそこから全ノードへの最…

典型90問のB問題 再帰使いながら()表示すればイケるやろとか思ってたらなんかうまくいかず... 解説ちらりとみてなるほどbitかーとか思いながら書いて提出したらWA なんでや！って見たらjの方向が(n-1)→0じゃないとダメだったみたい うーん…もっと精進します …

2月くらいにある社内のコードコンテストに向けて典型問題復習中 競プロとかちゃんとやってたの7年ぶり？ その頃も別に特段強くはなかったけど久しぶりにやったら絶望. 問題見た瞬間になんかLでかいけどDPとか行けんのか? って思って少し考えたけどギブ なる…

c言語を学びたい時,c言語をコンパイルしてくれるような環境が欲しくなる. Linuxなんかだとターミナルからコマンドで簡単にコンパイルしてくれるのだけど,windowsだと動作が重いvisual studio等をいちいち開かなきゃならないからなんかテンション下がる. 昔は…

僕は普段はc++を使って競技プログラミングなるものをしています. たまにPHPやjavascriptやHTML,SQL,CSS等を使ってwebで動くものも作ったりしますが,普段はあまり多くの言語を使いません. しかし,今回Excel VBAを使って1ヶ月分のチェックリストを作らなくては…

テスト