文系ギャルが0から始める競技プログラミング#30
Intro
この記事は不定期連載です。
↓最初の一本はこちら↓
文系ギャルが0から始める競技プログラミング#0
↓直前の記事はこちら↓
文系ギャルが0から始める競技プログラミング#29
あれ？？？？これは？？？
記念すべき#30〜〜〜〜〜〜〜〜〜！（ぱふぱふ）
更新頻度は落ちてますががっつり優勝していきますので引き続きよろしくお願いいたします！！！！！！！！！！！！！！
・ABC129C ― やってみようDP
まだDPがなんなのかイマイチよくわかってないですが、
典型的なDPらしいのでやってみます。
問題文
N段の階段があります。
高橋君は現在、上り口(0段目)にいます。
高橋君は一歩で1段か2段上ることができます。
ただし、a1,a2,a3,....aM段目の床は壊れており、その段に足を踏み入れることは危険です。
壊れている床を踏まないようにしながら、最上段(N段目)にたどりつくまでの移動方法は何通りあるでしょうか？
総数を1,000,000,007で割った余りを求めてください。
制約
1≦N≦10^5
0≦M≦N−1
1≦a1<a2<...<aM≦N−1
入力
入力は以下の形式で標準入力から与えられます。
N M
a1
a2
.
.
.
aM
出力
条件を満たすような移動方法の総数を、1,000,000,007で割った余りを出力してください。
C - Typical Stairs
天の声「DPってしってる？」
？？？「わかんなーーーい☆」
まず問題を整理というか、壊れてる階段がない平和なパターンを考えます。
多分こんな感じで、
普通にのぼるのと一段飛ばしするのと考えると、こんな感じにパターン数を計算できるんでしょう、多分。
そしたら次はばりーんと壊します。
壊れたところに行こうとすると高橋くんがDEAD ENDを迎えてしまうので、壊れたところへの行き方を0通りだと考えます。
そうするとぐっとパターン数が減って、多分図のような感じになるんだと思います。
ここまではいい。
どう実装すんの！？！？！？？！？！？？？？？！！！
入力からもってきて、
int N,M;
cin >> N >> M;
int a[100001] = {};
for(int i=0;i<M;i++){
cin >> a[i];
}壊れた階段a[i]をうまくつかって、全部の階段を○×で通れるか通れないかリストにすることにします。
bool broken[100001];
for(int i=0;i<M;i++){
broken[a[i]] = true;
}i段目の階段が、trueだったら壊れてるんだね。
あとはパターン数を計算しはじめることにしました。
0段目は必ず1通りだから、最初のだけ1にしておきます。
int dp[100001] = {1};そしてここが大事ポイント！！！！！！！！！！！！！！！
制約を見たら、1段目が壊れてる可能性もある！！！！！！
ので、場合分けします。
if(broken[1] == true){
dp[1] = 0;
}else{
dp[1] = 1;
}もし1段目が壊れてたら1段目への行き方は0通り（＝ない）だし、
壊れてなかったら普通にのぼる1通りしかない。
2段めからはもう壊れてたら飛ばす！壊れてたら飛ばす！って感じでOK。
for(int i=2;i<=N;i++){
if(broken[i] == true){
continue;
}
dp[i] = dp[i-1]+dp[i-2];
dp[i] %= 1000000007;
}ついでに1000000007で割っとこうね。
最後にN段目のパターンを出力して優勝です。
cout << dp[N] << endl;は！！！！！！！！！！！！い優勝！！！！！！！！！！！！！
天才ムーブまったなし！！！！！！！！！！！！！！！！！！
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <regex>
#include <map>
#include <set>
using namespace std;
int main(){
int N,M;
cin >> N >> M;
int a[100001] = {};
for(int i=0;i<M;i++){
cin >> a[i];
}
int dp[100001] = {1};
bool broken[100001];
for(int i=0;i<M;i++){
broken[a[i]] = true;
}
if(broken[1] == true){
dp[1] = 0;
}else{
dp[1] = 1;
}
for(int i=2;i<=N;i++){
if(broken[i] == true){
continue;
}
dp[i] = dp[i-1]+dp[i-2];
dp[i] %= 1000000007;
}
cout << dp[N] << endl;
return 0;
}意外とできるかも？と思っちゃったので練習しようかと思います！！！が、
もっと他に覚えるべきことありそう。
Twitterやコメントで良かったらアドバイスください。。。
（なんとなくリストも更新しています！いつもいろいろアドバイスありがとう〜〜〜！！！）
DPって結局どういうとき使うの？
— マリー (@CBOX360) June 11, 2019
Outro
#31に続く！(不定期連載です。)
これは成功と挫折を繰り返し、
タピオカ片手に難問を解く、
ギャルプログラマが生まれるまでの物語である…。