Ｎ個からＫ個取り出す組み合わせの列挙
簡単のため、まずＮ（＞３）個の整数｛１，２，３，，，Ｎ－１，Ｎ｝のうちから３個取り出す組み合わせの列挙を考えます。
#include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define FOR(i,a,b) for(int i=a;i<b;i++) #define each(it,v) for(auto &it : v) #define mod 1000000007 #define all(v) (v).begin(),(v).end() #define vi vector<int> #define vl vector<long> #define P pair<int,int> using namespace std; main() { int n; cin>>n; vector<vi> u; for(int i=0;i<n-2;i++) { for(int j=i+1;j<n-1;j++) { for(int k=j+1;k<n;k++) { vi v={i+1,j+1,k+1}; u.push_back(v); } } } each(v,u) { each(it,v)cout<<it<<" "; cout<<endl; } } //マクロをふんだんに使っており読みづらいかと思います。ごめんなさい。
これによりｎ＝５を入力としたときは、
5 1 2 3 1 2 4 1 2 5 1 3 4 1 3 5 1 4 5 2 3 4 2 3 5 2 4 5 3 4 5
が出力できます。
取り出す個数が固定されており、かつ、３個のみと少ない個数であるためfor文を回すだけで実現しました。
lucky pin問題でこんなようなコードを書いた記憶があります。
これが３個ではなくＫ個となってくるとfor文では太刀打ちできませんので工夫します。
そこで
ループ回数も動的に対応できるよう再帰関数にしました。
int n; void f(int k,vi v) { if(k==0) { each(it,v)cout<<it<<" "; cout<<endl; }else { rep(i,n) { vi u=v; u.push_back(i+1); f(k-1,u); } } } main() { int k; cin>>n>>k; vi v; f(k,v); }
参考コード：こちらの１６ページ
たとえばｎ＝７，ｋ＝３と入力させた場合、
7 3 1 1 1 1 1 2 1 1 3 1 1 4 1 1 5 1 1 6 1 1 7 1 2 1 1 2 2 1 2 3 1 2 4 1 2 5 1 2 6 1 2 7 1 3 1 1 3 2 1 3 3 1 3 4 1 3 5 1 3 6 1 3 7 1 4 1 1 4 2 1 4 3 1 4 4 1 4 5 1 4 6 1 4 7 1 5 1 1 5 2 1 5 3 1 5 4 1 5 5 1 5 6 1 5 7 1 6 1 1 6 2 1 6 3 1 6 4 1 6 5 1 6 6 1 6 7 1 7 1 1 7 2 1 7 3 1 7 4 1 7 5 1 7 6 1 7 7 2 1 1 2 1 2 2 1 3 ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ 7 3 6 7 3 7 7 4 1 7 4 2 7 4 3 7 4 4 7 4 5 7 4 6 7 4 7 7 5 1 7 5 2 7 5 3 7 5 4 7 5 5 7 5 6 7 5 7 7 6 1 7 6 2 7 6 3 7 6 4 7 6 5 7 6 6 7 6 7 7 7 1 7 7 2 7 7 3 7 7 4 7 7 5 7 7 6 7 7 7
となります。
これは組み合わせの列挙ではないですね。
しかも計算量がＯ（nk）と非現実的すぎます。
setを使おう
int n; void f(int k,set<int> s) { if(k==0) { each(it,s)cout<<it<<" "; cout<<endl; }else { rep(i,n) { set<int> t=s; if(!t.count(i+1)) { t.insert(i+1); f(k-1,t); } } } } main() { int k; cin>>n>>k; set<int> s; f(k,s); }
setの中身を１度確認してから要素を入れるか入れないかを判断させています。
中にすでに同じものがあるかどうかの判断にs.count(x)が使えそうだなと思ったので使ってみています。
ｎ＝４，ｋ＝３と入力させた場合、
4 3 1 2 3 1 2 4 1 2 3 1 3 4 1 2 4 1 3 4 1 2 3 1 2 4 1 2 3 2 3 4 1 2 4 2 3 4 1 2 3 1 3 4 1 2 3 2 3 4 1 3 4 2 3 4 1 2 4 1 3 4 1 2 4 2 3 4 1 3 4 2 3 4
同じものが重複して出力されています。
まとめて１つのset<set
int n; set<set<int>> comb; void f(int k,set<int> s) { if(k==0) { comb.insert(s); }else { rep(i,n) { set<int> t=s; if(!t.count(i+1)) { t.insert(i+1); f(k-1,t); } } } } main() { int k; cin>>n>>k; set<int> s; f(k,s); each(s,comb) { each(it,s)cout<<it<<" "; cout<<endl; } }
１つの大きなsetにまとめました。
ｎ＝４，ｋ＝３の出力は以下のようになります。
4 3 1 2 3 1 2 4 1 3 4 2 3 4
１つの大きなsetにまとめるのは少し面倒なので
int n; void f(int k,set<int> s) { if(k==0) { each(it,s)cout<<it<<" "; cout<<endl; }else { rep(i,n) { set<int> t=s; if(t.empty()) { t.insert(i+1); f(k-1,t); }else if(*rbegin(t)<i+1) { t.insert(i+1); f(k-1,t); } } } } main() { int k; cin>>n>>k; set<int> s; f(k,s); }
setの中の最大値*rbegin(t)を使う事によって大きなsetの中にまとめる作業を省くことに成功しました。
具体的には「setの中にある要素たちより大きい数字しか入れない」をしています。
これによって、例えば
1 2 3 4 5 6 7 8
と並んでいるうち、1と4を既に要素として持っている場合、
「最大値より大きい数字しか見ない」とは「4より右側のみを見る」ことになります。
探索の方向が右方向に固定できるので「あっちから数字持ってきたりこっちから持ってきたり最終的に同じ組み合わせが出来ちゃった（重複）」が発生しません。
このようにif文をもってして重複パターンを回避できているので、このコードに関してはsetではなくvectorのほうが（計算量的に）よいかもしれません。（中身は必ずsortされているので）（setのinsertは対数時間かかる）
結論
#include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define FOR(i,a,b) for(int i=a;i<b;i++) #define each(it,v) for(auto &it : v) #define mod 1000000007 #define all(v) (v).begin(),(v).end() #define vi vector<int> #define vl vector<long> #define P pair<int,int> using namespace std; int n; void f(int k,vi v) { if(k==0) { each(it,v)cout<<it<<" "; cout<<endl; }else { rep(i,n) { vi u=v; if(u.size()==0) { u.push_back(i+1); f(k-1,u); }else if(u.back()<i+1) { u.push_back(i+1); f(k-1,u); } } } } main() { int k; cin>>n>>k; vi v; f(k,v); }
とりあえず現状はこんなようなものかなと思います。
ここまでお読み頂きありがとうございました！
深さ優先探索入門
今回の参考資料です。
実践・最強最速のアルゴリズム勉強会 第二回講義資料(ワークスアプリケーションズ & AtCoder)
例題
まずN人にM個のリンゴを配る組み合わせの数を出力するプログラムを考えます。
main()
{
//入力を受け取ります
int n,m; cin>>n>>m;
int ans=0;
cout<<ans<<endl;
}
「N人にM個配る組み合わせ数」は、
「１人目に０個配り、N－１人にM個配る組み合わせ数」と、
「１人目に１個配り、Nー１人にMー１個配る組み合わせ数」と、
・
・
・
「１人目にM個配り、Nー１人に０個配る組み合わせ数」の合計で求められます。
再帰的に書けそうです。
dfs(n,m)=dfs(n-1,m)+dfs(n-1,m-1)+...+dfs(n-1,0)
実装してみます。
int dfs(int n,int m) { int res=0; for(int i=0;i<=m;i++) { res+=dfs(n-1,i); } return res; }
また、ｎ＝１の場合これは「１人にM個配る組み合わせ数」を表します。
１人でリンゴを総取りする以外ないのでこれは１をreturnさせてよいです。
int dfs(int n,int m) { if(n==1)return 1; int res=0; for(int i=0;i<=m;i++) { res+=dfs(n-1,i); } return res; } main() { int n,m; cin>>n>>m; int ans=dfs(n,m); cout<<ans<<endl; }
大きい問題（ｎ人）を小さい問題（１人とそれ以外）に分けて考えています。
この「それ以外」の人数が１人になる深さまで探索して最後にそれらの合計をreturnさせるアルゴリズムなんだなあと解釈しました。
例題その２
深さ優先探索というとやはりマス目の中を探索していくイメージがあります。
第１回ARCのC問題を考えます。
８クイーン問題です。レイトン教授に似た問題がありました。
高々６４マスなので、本番でこの問題に出遭った場合には全探索するかもしれません。
char board[8][8],ans[8][8]; bool flag; main() { //入力受け取り for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cin>>board[i][j]; } } //出力 if(flag) { for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cout<<ans[i][j]; } cout<<endl; } }else { cout<<"No Answer"<<endl; } }
とりあえず入出力だけを書きました。
方針が立たないので、まず「ある空きマス（ｘ、ｙ）に１つのクイーンを置いてもよいか」を調べる関数を作ることにします。
※次の中タイトルまでしばらくDFSの準備のための実装が続きます。
８方向を考える前に、
まず「現在の位置から左上方向にクイーンがないか」だけを調べて、判定を返すコードを書いてみましょう。
bool isOK(int y,int x) //OKるかOKないか（置けるか置けないか） { //左上 int ty=y,tx=x; int dy=-1,dx=-1; while(true) { ty+=dy; tx+=dx; if(board[ty][tx]=='Q')return false; } return true; }
これでは無限ループとなってしまいます。
盤面の外に出た場合には調べる前にbreakさせましょう。
bool inBoard(int ty,int tx) { if( 0<=ty&&ty<=7 && 0<=tx&&tx<=7 )return true; return false; } bool isOK(int y,int x) { //左上 int ty=y,tx=x; int dy=-1,dx=-1; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } }
左上方向に移っていくのでｘとｙを１ずつ小さくしていけばよいです。
この調子で左上だけではなく、真上方向と右上方向も実装してみます。
bool isOK(int y,int x) { //左上 int ty=y,tx=x; int dy=-1,dx=-1; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } //真上 ty=y;tx=x; dy=-1;dx=0; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } //右上 ty=y;tx=x; dy=-1;dx=1; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } return true; }
ここで、「左上」「真上」「右上」は、dx の値を変えただけでやっていることは同じ操作であることが分かるかと思います。
これはその他の方向についても同様で、ｄｘとｄｙのパターンは-1 0 1の３通りずつしかありません。この組み合わせによってどの方向へ移っていくのかが決定されます。
これはfor文を使って以下のようにまとめられます。
bool isOK(int y,int x) { int ty,tx; for(int dy=-1;dy<=1;dy++) { for(int dx=-1;dx<=1;dx++) { if(dy==0&&dx==0)continue; ty=y; tx=x; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } } } return true; }
ｄｙ＝０かつｄｘ＝０の時には、移動がありませんので、continueさせておく必要があります。
ここまでのコードを利用すると、
「整数ｘ、ｙと８×８のマス目を入力とした時に、空きマス（ｘ、ｙ）にクイーンを置けるか」を判定するプログラムが作れます。
using namespace std; char board[8][8]; bool inBoard(int ty,int tx) { if( 0<=ty&&ty<=7 && 0<=tx&&tx<=7 )return true; return false; } bool isOK(int y,int x) { int ty,tx; for(int dy=-1;dy<=1;dy++) { for(int dx=-1;dx<=1;dx++) { if(dy==0&&dx==0)continue; ty=y; tx=x; while(true) { ty+=dy; tx+=dx; if(inBoard(ty,tx)==false)break; if(board[ty][tx]=='Q')return false; } } } return true; } main() { int x,y; cin>>x>>y; for(int i=0;i<8;i++) { for(int j=0;j<8;j++) { cin>>board[i][j]; } } if(isOK(y-1,x-1))cout<<"OKru"<<endl; else cout<<"OKnai"<<endl; }
これで準備ができました。
次にどうやって深さ優先探索していくかについて考えます。
どうやる
方針としては、
「とりあえず目の前のマスAにクイーンを置けるのなら、置く。次の空きマスを見ていって、8個全て置けるかを試す。最後まで置けなかったのならば、マスAは置いてはいけなかった場所ということになるので置かないことにする。次のマスを見る。（以下繰り返し）」
ということになるかと思います。
2次元盤面ですが、方針より、1次元的に走査していきますので各64マスに番号を振ります。*1
「０番から６３番まで探索したときにクイーンを８個置けるかどうか」を、dfs(0,8)と表します。
- ０番にクイーンを置くとした場合、残りのマスに７個のクイーンを置けるか知りたいため、
dfs(0,8)→dfs(1,7)と遷移させます。
dfs(1,7)は「１番から６３番までで７個クイーンを置けるか」を表します。 - ０番にクイーンを置かないとした場合、残りのマスに８個のクイーンを置けるか知りたいので、
dfs(1,8)を調べます。
このように考えると第２引数は「残りクイーンの数」と捉えられます。
「残りクイーンの数」が０となれば全て置けたということなので true を返せます。
最後のマスを調べても「残りクイーンの数」が０となっていない場合には、false を返します。
bool dfs(int pos,int nokori) { if(nokori==0)return true; if(pos==64)return false; }
探索していきましょう。
まず入力から、現在のpositionにすでにクイーンが置かれている場合、「置かない」という選択肢は取れないので「置けるかどうか」のみを調べます。
//必ず置かないといけない if(board[y][x]=='Q') { //置けるのか if(isOK(y,x)) { //置けるのならば遷移させてみる。遷移先がtrueならtrueを返せる。 if(dfs(pos+1,nokori-1))return true; }else { //そもそもここに置けないのならゲームオーバーなのでfalseを返す return false; } }
つぎに空きマスについて調べる場合を考えます。
クイーンは置いてもいいし置かなくてもいいです。
ので、遷移先は２つあります。
そのどちらもがfalseである場合には、置いても置かなくても最後までたどり着けないルートということが分かります。falseを返します。
//置けるのか if(isOK(y,x)) { //置けるのならば遷移させてみる。遷移先がtrueならtrueを返せる if(dfs(pos+1,nokori-1))return true; } //置くルートがダメだった場合（なのでelseにしない） if(dfs(pos+1,nokori))return true; //置かないので残りのクイーンの数nokoriはそのまま
ところでこの問題の出力形式はクイーンを８個置いた完成図を出力しないといけないので、探索しながらその図も作らないといけません。
なので、それを考慮しつつbool dfs(int pos,int nokori)を完成させます。
bool dfs(int pos,int nokori) { if(nokori==0)return true; if(pos==64)return false; int y=pos/8; int x=pos%8; if(board[y][x]=='Q') { if(isOK(y,x)) { if(dfs(pos+1,nokori-1))return true; }else { return false; } }else { if(isOK(y,x)) { board[y][x]='Q'; //置いた if(dfs(pos+1,nokori-1))return true; else board[y][x]='.'; //置いてダメだったようなので取った } if(dfs(pos+1,nokori))return true; } return false; }
これにて完成です。（提出コード）
ここまでお読みいただきありがとうございました。
E - 通勤経路
古い問題ということもあり、解説記事が少なかったので、
記事にします。
問題雑概要
(1,1)から(w,h)までの経路を数えます。w,hはそれぞれ100以下です。
今回の問題では、交差点で「曲がる」という選択が2連続で出来ません。
「曲がった」場合には、次の交差点では一度「直進」する必要があります。
進行方向は常に上か右かの2択です。
方針
DPをします。
遷移を考えます。
通常であれば、以下のようなコードで済みます。
dp[i+1][j]+=dp[i][j]; dp[i][j+1]+=dp[i][j];
しかし今回の場合、進み方に制限がかかっているため無闇に上や右に進めません。
状態を持たせる
過去２回分の進行方向を状態として持たせます。
連続で「直進」している場合には、「直進」「曲がる」の両方を選べますし、
過去２回の進行方向が異なる場合には「曲がった」ということになるので、「直進」にのみ遷移できます。
//2回前の進行方向をlast_last_direction、１回前の進行方向をlast_directionとする //縦方向の移動→０、横方向の移動→１とする //配列のサイズは多めに宣言しておく int w_max=110, h_max=110, last_last_direction=3, last_direction=3; int dp[w_max][h_max][last_last_direction][last_direction];
（これは後で気づきましたが、状態はわざわざ２次元用意する必要はなく、
０：横横
１：横縦
２：縦横
３：縦縦
とかにすれば１次元でも十分機能するはずです。bit探索的な考え方ですね。）
なお、問題文上では、
JOIさんは，通勤時間を短くするため，東または北にのみ向かって移動して通勤している．
というように進行方向を示していますが、この記事では便宜上、東向きを「横方向」、北向きを「縦方向」と呼びます。上下も左右も区別しません。
遷移
現在の位置（ｉ、ｊ）は４つの状態を持ちます。
そのそれぞれの状態について、どこから遷移されてくるかをそれぞれ考えます。
状態は以下のように表せました。
dp[i][j][0][0] dp[i][j][1][0] dp[i][j][0][1] dp[i][j][1][1]
まず縦方向の移動から考えます。
縦は０を表すので、dp[ i ][ j ][ k ][ 0 ]が遷移先となります。（last_directionが縦を表している）
dp[i][j][0][0]+=dp[i-1][j][0][0]+dp[i-1][j][1][0]; dp[i][j][1][0]+=dp[i-1][j][1][1];
- dp[ i ][ j ][ 0 ][ 0 ]は縦縦となるため、遷移元が１つ前の交差点で曲がった場合でも受け入れられます。
しかし、２回前の操作も縦方向の移動である必要があるため、例えばdp[ i-1 ][ j ][ 0 ][ 1 ]は受け入れられません。 - dp[ i ][ j ][ 1 ][ 0 ]は横縦です。つまり「曲がる」を選択したので、その前の操作としては「直進」を連続で選んでいる場合のみ認められます。この時の直進は横移動です。
横方向へ移動する遷移も同様に書けます。
dp[i][j][1][1]+=dp[i][j-1][1][1]+dp[i][j-1][0][1]; dp[i][j][0][1]+=dp[i][j-1][0][0];
初期化を考える
考えます。
初期位置は通常１を置きます。（初期位置への経路は１通りなので）
ですが今回の場合は、１つの位置が４つの状態を持っています。
ややこいので初期位置dp[ 0 ][ 0 ][ last_last_direction ][ last_direction ]は飛ばします。
| h\w | 0 | 1 | 2 |
|---|---|---|---|
| 0 | ? | ? | |
| 1 | ? | ||
| 2 | ? | ||
| 3 | ? |
？の部分について考えます。
結論から言うと、？＝１です。直進するしかないからです。
問題はこの１をどの状態に置くべきかということです。
端を進むだけなので進行方向は常に同じです。
[ 0 ][ 0 ] あるいは[ 1 ][ 1 ]に入れるのがよいでしょう。（ここらへんでｗを高さ、ｈを横幅としてコーディングしていることに気づく）
for(int i=1;i<w;i++) dp[i][0][0][0]=1; for(int i=1;i<h;i++) dp[0][i][1][1]=1;
横横、縦縦の状態に入れておくことで「直進」「曲がる」どちらでも選べるようになります。
その他の状態は０でよいです。
ここまでを一旦実装します。
#include<bits/stdc++.h> using namespace std; int dp[110][110][3][3]; int ans[110][110]; main() { int w,h; cin>>w>>h; for(int i=1;i<w;i++)dp[i][0][0][0]=1; for(int i=1;i<h;i++)dp[0][i][1][1]=1; for(int i=0;i<w;i++) { for(int j=0;j<h;j++) { if(i==0||j==0)continue; //初期化ずみ if(i>0) { dp[i][j][0][0]+=dp[i-1][j][0][0]+dp[i-1][j][1][0]; dp[i][j][1][0]+=dp[i-1][j][1][1]; } if(j>0) { dp[i][j][0][1]+=dp[i][j-1][0][0]; dp[i][j][1][1]+=dp[i][j-1][1][1]+dp[i][j-1][0][1]; } } } //4つの状態を1つにまとめる for(int a=0;a<2;a++)for(int b=0;b<2;b++)for(int i=0;i<w;i++)for(int j=0;j<h;j++) { ans[i][j]+=dp[i][j][a][b]; } //debug for(int a=0;a<2;a++)for(int b=0;b<2;b++) { printf("[%d][%d]\n",a,b); for(int i=0;i<w;i++) { for(int j=0;j<h;j++) { cout<<dp[i][j][a][b]<<" "; } cout<<endl; } cout<<endl; } for(int i=0;i<w;i++) { for(int j=0;j<h;j++)cout<<ans[i][j]<<" "; cout<<endl; } }
入力例１の3 4を投げてみます。
3 4 [0][0] 0 0 0 0 1 0 0 0 1 1 1 1 [0][1] 0 0 0 0 0 1 0 0 0 1 1 1 [1][0] 0 0 0 0 0 1 1 1 0 0 1 1 [1][1] 0 1 1 1 0 0 1 1 0 0 1 2 0 1 1 1 1 2 2 2 1 2 4 5
このようになります。5つ目のテーブルの右下が答えです。
なお、今回の問題では、100,000で割った余りを出力するよう求められます。
w=49, h=49くらいでlong longを超えるからです。
const int mod=1e5; dp[i][j][0][0]+=(dp[i-1][j][0][0]+dp[i-1][j][1][0])%mod;
cout<<ans[w-1][h-1]%mod<<endl;
というようにこまめにmodを取ってあげるとよいでしょう。int型で十分動くようになります。
提出コードはこちらです。
解説はここまでで以上になります。
ここまでお読みいただいた方、ありがとうございました。
【2020/02/21更新】みんなよう見とる【Vtuber】
個人的に追っている人の一覧です。
一部Vでない方もいます。
-------------------------------------------------------
にじさんじ
《にじさんじ所属の女神》モイラ
鈴谷アキの陽だまりの庭
アキくんちゃんネル
渋谷ハジメのはじめ支部
樋口楓【にじさんじ所属】
月ノ美兎
勇気ちひろ
Shizuka Rin Official
エルフのえる / にじさんじ所属
家長むぎ【にじさんじ所属】
Yuhi Riri Official
伏見ガク【にじさんじ所属】
剣持刀也
♥️♠️物述有栖♦️♣️
宇志海いちご
鈴鹿詩子 Utako Suzuka
Gilzaren III Season 2
文野環【にじさんじの野良猫】ふみのたまき
森中花咲
Kanae Channel
Akabane Channel
安土桃
卯月コウ
Re‡D.E.放送局【鈴木勝/にじさんじ】
D.E.放送局【鈴木勝/にじさんじ】
緑仙channel
みどりのさぶちゃんねる
ドーラ
《IzumoKasumi》Project channel【にじさんじ】
轟京子/kyoko todoroki【にじさんじ】
シスター・クレア -SisterClaire-
花畑チャイカ
社築
春崎エアル
成瀬 鳴
笹木咲 / Sasaki Saku
本間ひまわり - Himawari Honma -
魔界ノりりむ
Kuzuha Channel
雪汝*setsuna channel
椎名唯華
闇夜乃モルル / Moruru Yamiyono
鷹宮リオン
【にじさんじ】神田笑一.
雨森小夜
飛鳥ひな【にじさんじ所属】
舞元啓介
竜胆 尊 / Rindou Mikoto
でびでび・でびる
でびちゃんねる
桜凛月
町田ちま【にじさんじ】
月見しずく
ジョー・力一 Joe Rikiichi
遠北千南 / Achikita Chinami 【にじさんじ】
夢追翔のJUKE BOX
黒井しば【にじさんじの犬】
矢車りね - Rine Yaguruma -
ベルモンド・バンデラス
海夜叉神/黄泉波咲夜【にじさんじ】
八朔ゆず【にじさんじ】
名伽尾アズマ☀️
童田明治-わらべだめいじー-
Kudou_chitose / 久遠千歳
【3年0組】郡道美玲の教室
夢月ロア🌖Yuzuki Roa
小野町春香-OnomachiHaruka-にじさんじ
語部紡
瀬戸 美夜子 - Miyako Seto
御伽原 江良 / Otogibara Era【にじさんじ】
戌亥とこ-Inui Toko-【にじさんじ】
アンジュ・カトリーナ - Ange Katrina -
リゼ・ヘルエスタ -Lize Helesta-
三枝明那 / Akina Saegusa
愛園 愛美/Aizono Manami
鈴原るる【にじさんじ所属】
雪城眞尋/Yukishiro Mahiro【にじさんじ所属】
エクス・アルビオ -Ex Albio-
レヴィ・エリファ-Levi Elipha-
葉山舞鈴 / Hayama Marin【にじさんじ所属】
ニュイ・ソシエール //[Nui Sociere]
葉加瀬 冬雪 / Hakase Fuyuki
加賀美 ハヤト/Hayato Kagami
夜見れな/yorumi rena【にじさんじ所属】
黛 灰 / Kai Mayuzumi【にじさんじ】
アルス・アルマル -ars almal- 【にじさんじ】
相羽ういは〖Aiba Uiha〗にじさんじ所属
天宮 こころ / Kokoro Amamiya 【にじさんじ所属】
エリー・コニファー / Eli Conifer【にじさんじ】
ラトナ・プティ -Ratna Petit -にじさんじ所属
早瀬 走 / Hayase Sou【にじさんじ所属】
健屋花那【にじさんじ】KanaSukoya
シェリン・バーガンディ -Shellin Burgundy- 【にじさんじ】
フミ/にじさんじ
星川サラ / Sara Hoshikawa
山神 カルタ / Karuta Yamagami
えま★おうがすと
魔使マオ -matsukai mao-
ルイス・キャミー
不破 湊 / Fuwa Minato【にじさんじ】
白雪 巴/Shirayuki Tomoe【にじさんじ】
グウェル・オス・ガール / Gwelu Os Gar 【にじさんじ】
ましろ / Mashiro
奈羅花 - Naraka -
来栖 夏芽-kurusu natsume-【にじさんじ】
フレン・E・ルスタリオ
イブラヒム【にじさんじ】
メリッサ・キンレンカ
田角 陸 - Riku Tazumi
いわながちゃん
バーチャル債務者youtuber天開司
Fairys Channel
NIJISANJI ID Official
Hana Macchia Ch.【NIJISANJI ID】
ZEA Cornelia Ch.【NIJISANJI ID】
Taka Radjiman【NIJISANJI ID】
Miyu Ottavia 【NIJISANJI ID】
Amicia Michella【NIJISANJI ID】
Riksa Dhirendra【NIJISANJI ID】
Rai Galilei【NIJISANJI ID】
hololive ホロライブ - VTuber Group
Mio Channel 大神ミオ
Aqua Ch. 湊あくあ
AZKi Channel
Choco Ch. 癒月ちょこ
Coco Ch. 桐生ココ
Rushia Ch. 潤羽るしあ
Okayu Ch. 猫又おかゆ
Watame Ch. 角巻わため
Suisei Channel
Subaru Ch. 大空スバル
Flare Ch. 不知火フレア
Towa Ch. 常闇トワ
SoraCh. ときのそらチャンネル
フブキCh。白上フブキ
Mel Channel 夜空メルチャンネル
Kanata Ch. 天音かなた
Pekora Ch. 兎田ぺこら
Haato Channel 赤井はあと
Korone Ch. 戌神ころね
Roboco Ch. - ロボ子
Shion Ch. 紫咲シオン
Matsuri Channel 夏色まつり
Luna Ch. 姫森ルーナ
アキロゼCh。Vtuber/ホロライブ所属
Miko Ch. さくらみこ
Noel Ch. 白銀ノエル
Marine Ch. 宝鐘マリン
Nakiri Ayame Ch. 百鬼あやめ
LupinusVirtual Games
すーちゃんねる
なずちゃんねる-Nazuna Channel
小雀とと
一ノ瀬うるは
しぐれうい
神楽めあ / KaguraMea
佃煮のりおちゃんねる【犬山たまき】
織田信姫
たなかのちゃんねる
はなつぐ / Hanatsugu
うさこち
幼龍埜ゆい
白雪レイドーReid Channelー
Uge Channel / 杏戸ゆげ 【ブイアパ】
しらゆりヘブンちゃんねる
すももチャンネル
あっくん大魔王
伊東ライフ
はじめての二分探索
やります。
AtCoder TagsのAtCoder_Tags_Hintという機能で二分探索のタグがついていたので、*1
ちょうどよいと思い、練習することにしました。
Tagをクリックすると、
と出ます。
ででどん
1≦X≦109から条件を満たすXを探します。
sortされた整数列から探すわけなので二分探索が出来そうです。
c++にはlower_boundやupper_boundといった便利なライブラリがありますが、
今回は初めての二分探索なのでまずは自分でいちから作ってみます。
たしか二分探索は半分の位置を見て次調べるのが前か後ろか決めるようなものだったと思うので、
int left=0,right=1e9; int mid=(left+right)/2; //500000000
とします。
今回の問題の条件を満たすか調べます。
if(a*mid+b*d(mid)<=x)right=mid; else left=mid;
条件を満たす場合には右端を縮めて、
満たさない場合には左端を縮めます。
ちなみにd(mid)は整数midの桁数を返す自作関数です。
int d(int mid){return to_string(mid).size();}
これを何回かループさせて答えを探索するはずなのですが、ループの抜け方がイマイチ分かりません。
安直に左端leftと右端rightが一致したら抜けるようにしてみましょう。
あと、デバッグ用の出力を追記したり、型をlong longで統一させたりしています。
ll left=0,right=1e9,mid; while(right!=left) { mid=(left+right)/2; printf("%lld %lld %lld\n",left,mid,right); ll t=a*mid+b*d(mid); if(t>x)right=mid; else left=mid; } cout<<mid<<endl;
これにサンプル10 7 100を入れると、
こうなります。
無限ループです。
ただ答えの9には辿り着けているので嬉しいです。
実際10分くらい9にすら辿り着けなくて悪戦苦闘していたので十分嬉しいのです。
ループ
正しいループの抜け方を考えます。
9と10が境目です。
境目の左側は条件を満たし、右側は条件を満たしませんつまり、このleftが条件を満たす最大値を示します。
whileの抜ける条件をright-left!=1として最後にleftを出力させてみます。
ll left=0,right=1e9,mid; while(right-left!=1) { mid=(left+right)/2; printf("%lld %lld %lld\n",left,mid,right); ll t=a*mid+b*d(mid); if(t>x)right=mid; else left=mid; } cout<<left<<endl;
こうなります。
きれいですね。
他のサンプルでも試しましたが、サンプル２以外は上手く機能しました。
サンプル２は2 1 100000000000です。
これはお店に売られている最大整数が買えるパターンです。
このパターンも拾えるように修正をして提出をします。
提出
using namespace std; ll d(ll mid){return to_string(mid).size();} main() { ll a,b; ll x; cin>>a>>b>>x; //まず最大整数を買えるのかどうか調べとく ll c=1e9; if(a*c+b*d(c)<=x) { cout<<c<<endl; return 0; } ll left=0,right=1e9,mid; while(right-left!=1) { mid=(left+right)/2; //printf("%lld %lld %lld\n",left,mid,right); ll t=a*mid+b*d(mid); if(t>x)right=mid; else left=mid; } cout<<left<<endl; }
無事ACしました。
とりあえず二分探は寒色系を目指すにあたっての必須科目だと思うので自分の手足のように使いこなせるようになりたいです。
対戦ありがとうございました。
ここまでお読みいただきありがとうございました。
動的計画法の練習
動的計画法はなかなか実装が慣れません。
一度時間を取ってちゃんと勉強してみます。
問題
この問題で練習します。
atcoder.jp
人は基本リンクを踏まないのでスクショを置きます。
解法その１
設定されうる暗証番号がたかだか103通りなのでそれを利用して解きます。
ラッキーナンバーSから暗証番号"ijk"が作れるかどうかのループを1000回回します。
自分もこの解法で解いたコードを提出しました。(提出コードのリンク)
解法その２
まず多次元配列を作ります。
bool dp[pos][len][current];
bool型となっています。
これはN桁のラッキーナンバーSを、
あるところまで走査した結果（ pos ）、
何文字か拾ってきて（ len ）、
ある文字列（ cuurent ）を作れるのかどうかをtrue/falseで表します。
最後にpos = Nかつlen = 3のtrueを数えます。
この個数がSを最後まで走査して3文字拾って作れる文字列の個数となります。
今回のアルゴリズムの流れとしては
ある地点（ dp[ i ][ j ][ k ] ）から次に進める道を開拓していって到達可能な目的地の数を最後に集計するという流れになります。
つまり配列を宣言した時点では配列の中身は全てfalse、未開拓状態です。
左の原点Oから出発して右下の太線のどこか1点まで行きたいです。
経路はどのようでも構いません。行けるかどうかが知りたいです。
最後に行けた数を数えます。
とりあえず
dp[0][0][0]から始めていきましょう。
始めの状態として全ての配列の中身はfalseですが、スタート地点に立てないとなると道の開拓の仕様がないので、これはtrueとします。
これが初期条件となります。
dp[0][0][0]=true;
次に、遷移を考えます。
解説にもあるように、この動的計画法の遷移は「次の文字を拾うか」「次の文字を無視するか」の2通りしかありません。
つまり、dp[ i ][ j ][ k ]において、
dp[ i+1 ][ j+1 ][ k * 10+S[ i ]-'0' ]（次の文字を拾う場合）
[ i+1 ] ← (次の文字を見てるので当然１プラスされる)
[ j+1 ] ← (次の文字を拾うというので当然 len もプラスされる)
[ k * 10+S[ i ]-'0' ] ← (「次の文字」はS[(i+1)-1])
dp[ i+1 ][ j ][ k ]（次の文字を拾わない場合）
[ i+1 ] ← (次の文字を見てるので当然１プラスされる)
[ j ] ← (次の文字を拾わないのでそのまま)
[ k ] ← (こちらもそのまま)
の2つが次に進める道となります。
ここで「次に進める」は、そこはtrueであるということを表します。
「次に進める道をtrueとする」、これがループ毎に行う動作となります。
dp[i+1][j+1][k*10+S[i]-'0']=true; dp[i+1][j][k]=true;
また「次に進める道がある」ということは「今いる場所にも来れる」ということでもあるので、ループ中に行う動作の始めに今いる場所に来れるのかどうかを調べます。
つまり、dp[i][j][k] = falseであればcontinue;させます。
if(!dp[i][j][k])continue;
実際に
コードを組みましょう。
ループの中身から取り掛かります。
{
if(!dp[i][j][k])continue;
dp[i+1][j+1][k*10+S[i]-'0']=true;
dp[i+1][j][k]=true;
}
ここでdp[i+1][j+1][k*10+S[i]-'0']=true;についてですがこの時、jが3以上であればこの操作は無用なので頭にif文をくっつけます。
{
if(!dp[i][j][k])continue; //来れない道
if(j<3)dp[i+1][j+1][k*10+S[i]-'0']=true; //文字を拾う
dp[i+1][j][k]=true; //拾わない
}
ループの外側を作ります。
rep(i,n) //for(int i=0;i<(int)(n);i++) { rep(j,4) { rep(k,1000) { if(!dp[i][j][k])continue; if(j<3)dp[i+1][j+1][k*10+S[i]-'0']=true; dp[i+1][j][k]=true; } } }
到達できた目的地の数を集計します。
for(auto it : dp[n][3])ans+=it; //範囲for文
色々必要なものを追記して繋げます。
#include<bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; int n,ans; string S; bool dp[30009][4][1009]; main() { cin>>n>>S; dp[0][0][0]=true; rep(i,n) //for(int i=0;i<(int)(n);i++) { rep(j,4) { rep(k,1000) { if(dp[i][j][k]==false)continue; if(j<3)dp[i+1][j+1][k*10+S[i]-'0']=true; dp[i+1][j][k]=true; //デバッグ用出力 //printf("%d %d %d\n",i,j,k); } } } for(auto it : dp[n][3])ans+=it; cout<<ans<<endl; }
結論
dp難しいです。
理解できてるのかどうかは、いくつかの類題を解いてみないとなんとも言えないです。*1
精進です。
ここまでお読みいただきありがとうございました。
追記（2月11日）
類題を解きました。
atcoder.jp 解法です。
int x; bool dp[110000]; main() { cin>>x; dp[100]=true; dp[101]=true; dp[102]=true; dp[103]=true; dp[104]=true; dp[105]=true; rep(i,x) { if(!dp[i])continue; rep(j,6)dp[i+100+j]=true; } cout<<dp[x]<<endl; }
先のラッキーナンバーの問題のように
まずtrueとなる初期値を設定してその後、道を開拓していく方法がスムーズに実装できました。
メモ化再帰関数を作る方法もあるかと思いますがそれよりもシンプルなコードになっているかと思います。
類題を解きました。（その２）
atcoder.jp 解法です。
int n,m,cnt; main() { cin>>n>>m; vector<pair<int,int>> p(n+10); //fisrtに「歩けるか歩けないか（0/1）」、secondに「そこに行き着くまでの経路数」を入れる。10はバッファ p[0].second=1; //0段目に行き着くまでの経路数は１ for(auto &it : p)it.first=true; //床が壊れている段をfalseにする int t; rep(i,m) { cin>>t; p[t].first=false; } rep(i,n) { if(!p[i].first)continue; p[i+1].second=(p[i+1].second+p[i].second%mod)%mod; p[i+2].second=(p[i+2].second+p[i].second%mod)%mod; } //debug //for(auto it : p)printf("%d %d %d\n",cnt++,it.first,it.second); cout<<p[n].second<<endl; }
これについても同様に
初期値を入れて、
進める道だけ開拓して
を繰り返すだけでした。
ここらへんから「dp楽しいやん？」と思えるようになってきました。
追記その２（2月11日）
こんばんは。動的計画法完全理解者の樋口です。
本日も動的計画法の練習問題を解いたのでその記録を追記させていただきたいと思います。
提出したコードは以下のようになります。
using namespace std; int h,n,a,b; main() { //入力 cin>>h>>n; vpii v; //vector<pair<int,int>> int t=0; rep(i,n) //for(int i=0;i<(int)n;i++) { cin>>a>>b; v.push_back(make_pair(a,b)); t=max(t,a); } // 配列の宣言と初期化 int dp[h+t]; each(&it,dp)it=1e9; //for(auto it : dp) dp[0]=0; // HP0を削るに必要な魔力は当然0 //値の更新 rep(i,h+t) { rep(j,n) { //配列の外にアクセスされると困るのでif文を置く if(i+v[j].first<=h+t)dp[i+v[j].first]=min(dp[i+v[j].first],dp[i]+v[j].second); } } //debug //each(it,dp)cout<<it<<endl; //出力 int ans=INT_MAX; rep2(i,h,h+t)ans=min(ans,dp[i]); cout<<ans<<endl; }
体力iを削り切るために必要な最小魔力を配列に入れていきます。
ここでのミソは与える総ダメージ量は入力Hと等しくなくともよいということです。
最後の3行がそれについてのコードとなりますが、
与えたダメージ量がH以上、H+t未満での最小値をansとしています。
ここでいうtは一度の攻撃で与えられる最大火力、つまり一番攻撃力の高い魔法のダメージ量です。
入力が
9 2
8 1
1 10
といった場合、攻撃力8消費魔力1の魔法を2回撃つのが最適解となりますが、与える総ダメージ量は16(≠9)となります。
こんな場合でも、上記の3行によって解をしっかり取ってくることができます。
