ABC136 D Gathering Children
問題
解説
- 最終的にどのような状態になるのか
軽くシミュレートをすると、子供たちは、最終的に"RL"または"LR"であるような境界を行き来するだけになります。文字列の長さに対して回も移動するので、これは確実です。
そこで、このような境界において子供達が右側と左側のどちらに溜まるのかをうまく決定したいという気持ちになります。
- 偶奇性
"RL"という地点があり、今"R"に居る状態からこの境界を行き来することを考えます。
1回目の移動：L
2回目の移動：R
3回目の移動：L
4回目の移動：R
というように、これはもちろん交互になるため、移動回数の偶奇を見れば分かりそうです。そして、問題文にあるというのは偶数回であると気づくことも重要です。
- 遠くからやってくる子供達
"RRRRL"という文字列があるとします。
回移動するとき、それぞれの子供達はどちらに溜まるでしょうか。
あらかじめ子供達に仮の番号をつけた状態でシミュレーションすると、
[1] [2] [3] [4] [5]
1回目 [-] [1] [2] [3,5] [4]
2回目 [-] [-] [1] [2,4] [3,5]
3回目 [-] [-] [-] [1,3,5] [2,4]
4回目 [-] [-] [-] [2,4] [1,3,5]
(4(偶数)回目から回目までも偶数回の移動なので、変わらず)
回目 [-] [-] [-] [2,4] [1,3,5]
というように、偶数番目の子供達と奇数番目の子供達に分かれるということが言えそうです。
というわけで、"R"や"L"が連続して並んでいる区間に対して、これらの処理をしていけば、問題が解けそうです。
以下のコードでは、最初"R"だけについて処理をした後に、文字列を反転させて"L"だけについて処理をしています。こうすることで、常に右に進むものとして扱えるので分かりやすいです。
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++) template<typename T> void print(vector<T> v){ for(int i=0;i<v.size();i++){ if(i)cout<<" "; cout<<v[i]; } cout<<endl; } signed main (){ string s; cin>>s; vector<int> ans(s.size(),0); //最初はRだけについて処理 rep(i,0,s.size()){ if(s[i]=='R'){ int idx=1; int ct[2]={}; ct[idx%2]++; while(i+1<s.size() and s[i]==s[i+1]){ idx++; ct[idx%2]++; i++; } if(idx%2==1){ //区間の長さが奇数なら ans[i+1]+=ct[0]; //偶数番目の要素が境界の右に溜まる ans[i]+=ct[1]; //奇数番目の要素が境界の左に溜まる }else { ans[i+1]+=ct[1]; ans[i]+=ct[0]; } } } reverse(all(s)); reverse(all(ans)); //今度はLだけについて処理 rep(i,0,s.size()){ if(s[i]=='L'){ int idx=1; int ct[2]={}; ct[idx%2]++; while(i+1<s.size() and s[i]==s[i+1]){ idx++; ct[idx%2]++; i++; } if(idx%2==1){ ans[i+1]+=ct[0]; ans[i]+=ct[1]; }else { ans[i+1]+=ct[1]; ans[i]+=ct[0]; } } } reverse(all(ans)); print(ans); }
ct[2] が、連続する区間に対して偶数番目と奇数番目である要素を数えるための配列です。ct[0]、ct[1]が境界のどちらに溜まるのかは、その区間の長さによるので、そこだけ場合分けをしてあげます。
数を数えるところは関数化するのが綺麗なんでしょうが、競プロの範囲ではそこまで考えなくても良いと思っているのでそのままです。。
ABC117 D XXOR 解説
問題
数列Aの全ての要素とのxorを最大化するようなK以下の整数を求めよ。
解説
公式解説の序盤について、Xの候補となりうる整数とは
Xがなんでも良ければ難易度が下がりますが、K以下というところが難点です。 まずK以下の整数とはどのようなものかを確認します。
例えば、2進数表示で0101という整数Kがあるとします。これはつまり5なのですが、
1<2<3<4<5→001<010<011<100<101ということを思い出せば、少なくとも3bit目が0であるような数に対しては、それより下の1,2bitがどんなものであろうと、Kよりも小さい数だと分かります。
このように、整数Kのあるiビット目が1であれば、そのビットをとりあえず0にした整数Xを持ってこれば、iビット目より下のビットはどんなでも良い、というのが公式解説の序盤です。上記はi=3のときの例となります。
001,010,011 < 101
↑1,2ビットをどう変えても3ビット目に応じて大小が決まる例。
このようなことは、Kのあるビットが1であれば、それをiビット目としていつでも言うことができます。言い換えれば、「iビット目」の候補になるのは、Kにおけるiビット目が1であるようなビットのみ、となります。
ビットの決め方
- iビット目未満のビット
さて、上記の例における1,2ビットのように、どう変えても大小の結果に影響しないビットというのは、自分の都合の良いように変えることができるわけです。（もちろんXの3ビット目は0である、ということは厳守した上で。）
ここで、x(x<i)ビット目を都合の良いように変えるとは、N個の整数のxビット目の0の数と1の数を数えて、少ない方の数字を採用するいうことです。
例えば、8個の整数において、xビット目が0のものが5個、1のものが3個あれば、Xのxビット目を0にしたときは、0 xor 1 = 1より3つの整数について1が立ちます。つまり、f(X)は増えます。対して、xビット目を1にしたときは、
1 xor 0 = 1より、f(X)は増えます。ということは、より数が少ない方にXのxビット目を設定すればよいです。
さらに、実はX自体が何かを知る必要はなくて、上記のようにf(X)にどれだけ足されるかという値がわかっているので、直接f(X)を求めることができます。
よって、都合の良いように変えていいビットについては、となります。ここで、
とは、xビット目が立っている整数の数です。
- iビット目
このビットは、唯一Kのビットが1で、Xのビットが0であるようなところです。つまりXのビットは必ず0にしないといけないビットです。この問題ではxorを取ることを目的としているので、N個の整数の中でiビットが1であるようなものだけf(X)に影響します。よって、iビット目は必ず です。
- iビット目より上のビット
ここではK以下の整数という制約を守るため、Kのビットに合わせます。
Kのy(y>i)ビット目が1ならXのyビットも1です。つまり、N個の整数のうちyビット目が0のものだけf(X)に影響します。このときはだけ影響します。
Kのyビットが0ならXのyビットも0です。つまり、N個の整数のうちyビット目が1のものだけf(X)に影響します。このときはだけ影響します。
これで全てのビットについてf(X)への影響度がわかったので、f(X)を求めることができます。
ただし、これはiビット目が決まっているからこそできることなので、i の候補が40程度なことから、全探索することを考えます。全探索する中で、Kのビットが1であるようなものについて上記の計算をして、一番大きいものを取りましょう。
コードは一部省略(using namespaceとか)
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++) signed main (){ int N,K; cin>>N>>K; vector<int> A(N); rep(i,0,N)cin>>A[i]; int res=0; // X_i < K_i、つまりX_i=0で、K_i=1であるようなiを全探索 rep(i,-1,41){ if(i!=-1 && !(K&(1LL<<i)))continue; //Kのiビット目が0ならcontinue int ans=0; //a[i]に対して、jビット目が立っているものを数える = ct rep(j,0,41){ int ct=0; rep(k,0,N){ if(A[k]&(1LL<<j))ct++; } // iビット目より上のビット if(j>i){ if(K&(1LL<<j))ans+=(1LL<<j)*(N-ct); else ans+=(1LL<<j)*ct; // iビット目 }else if(i==j){ ans+=(1LL<<j)*ct; // iビット目未満のビット }else { ans+=(1LL<<j)*max(ct,N-ct); } } res=max(res,ans); } cout<<res<<endl; }
ICPC2019 国内予選参加記
開始前
リハーサルと授業がモロ被りしてたので、リハーサル残り20分地点でJ,KをAC。問題のアルファベットが本当にJ,Kだったかは忘れました。その後15分くらいで「短句」を解こうとしましたが、本当に何が間違えているのか分からず解けなくて、「まあもう時間が終わるので本気でやってないんだぜ」感を出してごまかしていました。
リハも終わり、本番は長丁場につきお菓子と水分が必要だということで、コンビニに向かいました。ディスカバリーチャンネルで一時期話題になったサバイバル番組でも、「エド」という人が言っていました。「サバイバルに必要不可欠なのは、water,fire,shelter」だと。ここにお菓子はありませんが、少なくとも水は必要なんですね。コンビニへの行きしなに僕が所属してる部活の展示をちょうどやっていて、先輩づらして様子を見に行ったらICPCを見てくれている教授のうち2人が居て結構びっくりしました。
その後、部活の書類を提出するのをすっかり忘れていたり、学生部からの問い合わせに対応していたりしてドタバタしていました。
なんか本番が始まった
同じ部屋でお菓子の取り合いをしたり、先輩が下の階にいる後輩たちのチームからお菓子を巻き上げたりしているうちに、本番が始まりました。
座った位置的に僕がAをやる流れだったので、Aを通しました。すると先輩が「Bはやるだけ」とか言うので「じゃあおなしゃす」と言っていたらBが通りました。ここまで25分。
その後2時間半椅子を温めて終了しました。（C,Dとも結構惜しいとこまではできた)
2冠160位？くらい。一応学内１位なので、実質優勝です。
終了後
同じ部屋のチームからC問題の解法を軽く聞きました。僕らのチームは下手に考えてて実装をややこしくしていました。
部屋を片付けて、残ったお菓子を適当に袋に詰め込んで撤収です。後半何も分からず暇になって、お菓子食べながら踊っているだけかと思いましたが、案外そんなことはなく、お菓子と飲み物が減りませんでした。
初参加とかの後輩チームも、2冠とかしてたので優秀だなあ、と思いました。ただ問題のレベルが去年の折り紙と比べれば格段に易化していたとは思いますが。
終わり
結果はともあれ、楽しかったのでよかったです。
【入門】processingで最小限のシューティングゲームを作る
こんにちは、ごつちやんです。
これは最小限のシューティングゲームを作るためのチュートリアル記事です。初心者でも完成までたどり着けるように、詳しく書いていきたいと思います。
出てくるプログラムの知識は int型, float型、変数、if、配列、for程度です。どれも事前知識があると嬉しいですが、全て解説は入れているので、問題ないのではないかなと思います。
ではでは。
何か不明な点があれば、twitterの@gotutiyan_kapiまでリプ・DMを飛ばしてください。
はじめに
座標系
processingを使うと、自由に図形を描くことができます。図形を描画する際に必ず指定するのが座標なのですが、processingの場合は座標系における軸の取り方がいつもとは違います。
数学における座標系は、上に行くほどy座標が増えて、右に行くほどx座標が増えます。また、原点は左下です。
対して、processingにおける座標系は、下に行くほどy座標が増えて、右に行くほどx座標が増えます。また、原点は左上です。
setup()とdraw()
ゲームを作るに欠かせないのは「パラパラ漫画」の機構です。ページを素早くめくるように、ゲームは高速に画面が更新されています。テトリスを想像してみてください。ブロックが落ちていくだけでも、ゲーム画面は非常に高速に更新されています。この更新の速さを「フレームレート」と呼んだりしますが、フレームレートが低いことは、いわゆる「カクつく」「処理が重い」と感じる原因です。パラパラ漫画をめくる速度が遅ければ、当然絵もカクつきますね。
さて、processingにはこの「高速に画面を更新する」仕組みがあります。それがsetup()とdraw()です。これらはプログラミングの中では非常に重要な「関数」というものですが、今は割愛します。
setup()は、ゲームが始まった瞬間に一度だけ処理が行われます。
draw()は、ゲームを遊んでいる間、裏で何回も何回もひたすら処理が行われます。draw()が何回も実行されて、画面がその度に更新されることによって、パラパラ漫画はめくられます．ブロックは落ちるし、キャラは動きます。
具体的には、以下のようなテンプレを元に作成することになります。
void setup(){ //1回だけ実行される処理 } void draw(){ //何回も実行される処理 }
初期設定
今回ゲームを作るにあたって、初期設定をしましょう。
まずは実行画面の大きさです。ゲームをプレイする画面を小さくしたり、大きくしたりできます。
これはsize()によって指定することができます。サイズは一度設定すればそれ以降固定されるので、setup()に書きます。
サイズは何でも良いですが、本記事では500*500にすることにします。
void setup(){ size(500,500); } void draw(){ //何回も実行される処理 }
実行ボタンを押すと、ある程度の大きさのウィンドウが表示されます。
自機を作る
自機、つまり操作する味方を作ります。自機は以下のようなものを目指してみます。
・形は円で、直径は50
・マウスの座標に追従する
・クリックしている間、画面上部に向けてビームを撃つ
順番にやって行きましょう。
マウスに追従させる
円を描くには、ellipse()を使えば描くことができます。正確には、ellipse(中心のx座標, 中心のy座標, 横の直径, 縦の直径)です。
横と縦の直径を別々で指定できるので、楕円も描くことができますが、今回は円なので同じ値にすれば良いです。
さらに、マウス座標はmouseX、mouseYで取得できます。これはそのまま、マウスのx座標とy座標を表します。
自機は動くもの、つまり高速に更新されるべきものなので、draw()に書くことにします。
void setup(){ size(500,500); } void draw(){ ellipse(mouseX,mouseY,50,50); //自機 }
ここで実行すると分かるのですが、円がたくさん描かれてしまいます。これは一度描かれた円がずっと残るからで、draw()が回るたびに全消ししていけば解決します。
「円が描かれる」→「全消し」→「また円が描かれる」→「全消し」・・これにより、プレイヤーからは常に１つの円しか見えず、かつ動いているように見えます。
これを実現するためにbackground()を利用しましょう。
processingには描画の順序があります。プログラム的により下の方に書いた図形ほど、前面に描かれます。塗りつぶす動作は一番背面で行いたいので、draw()の直下に書きます。
background(0)なら黒背景、background(255)なら白背景です。
void setup(){ size(500,500); } void draw(){ background(255); //白背景 ellipse(mouseX,mouseY,50,50); //こっちの方が下の行に書いているので前面にでる }
ビームを撃つ
次に「クリックしている間、画面上部に向けてビームを撃つ」ことですが、これは
・クリックしているかどうかを判定する
・ビームを撃つ
のように分けて考えることができます。
クリックしているかどうかを判定するためには、mousePressed、そして、if文を使います。
if文とは、単語の通り「もし〜なら」を実現する機構です。if(条件) のように条件を指定して使い、条件を満たせば「true」となり、処理が実行されます。満たさなければ、「false」となり、実行されません。
この条件の書き方には色々なものがあるので、以下で感覚を掴んでください。
if(2==6){ //2と6は等しくないのでこの処理は実行されない } if(4>1){ //4の方が1より大きく、条件を満たすのでこの処理は実行される } if(5<7 && 4==4){ //&&で繋いだ条件は両方満たさないといけません。5<7と4==4の両方を満たしているのでこの処理は実行されます } if(5<7 && 4==3){ //5<7は満たしますが4==3は満たしていません。両方ともは満たしていないのでこの処理は実行されません }
そしてmousePressedは、マウスが押されているかどうかを検知するものです。押されていればtrue、そうでなければfalseを表します。
つまり、if文の条件式にmousePressedを当てはめることによって、押されていればtrueとなり実行され、そうでなければ実行されない機構を作れます。
さらに、その機構によって実行される処理が「ビームを撃つこと」です。何となく、分かったでしょうか。
void setup(){ size(500,500); } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ //ビームを撃つ処理がここに入る } }
では、ビームを撃つにはどうすれば良いでしょうか。本記事ではあくまで「最小限」の構成で作るので、ビームと言ってもただの線にしましょう。
線はline()で描くことができます。正確には、line(x1,y1,x2,y2)と値を４つ指定し、点(x1,y1)、点(x2,y2)をつなぐ線を描けます。
今回は、自機から画面の上部に向けてビームを撃つことを考えるので、指定する２点は以下の座標になります。
・(mouseX, mouseY)
・(mouseX,0)
この２点を繋げば、自機から真上にビームを撃つことができます。X座標は常にマウス座標に合わせるイメージです。
void setup(){ size(500,500); } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } }
敵を作る
敵を作ります。敵は複数存在するべきですが、まずは１体だけ作ってみましょう。
敵は上から降ってきて、特に攻撃などはしてきません。が、常に同じ位置から降ってきてもゲームとしては面白くありません。
まずは敵の仕様です。
・形は円で、直径は50
・上から下に降ってくる
・画面下に出てしまえば、また上から降ってくる
・また上から降ってくるとき、落ちるスピード、落ちてくる位置をランダムにする
・HPが設定されており、ビームを当てるとHPが減る。
・HPが無くなった敵はその場で消滅し、また上から降ってくる
形は円なので自機と同様ellipse()を使いますが、この時の座標はどのように設定するのが良いでしょうか。
ここで、int型の変数というものを使ってx,y座標にしましょう。
例えば、
ellipse(100,100,50,50);
と書けば、中心座標は(100, 100)の点に描かれます。しかし、実行中にこの円は動かせません。もちろん、プログラムの中心座標を書き換えて、再度実行すれば円を違う位置に描くことができますが、それは「実行し直す」操作が必要で、ふさわしくありません。
こんな時、変数を使うことによってうまく処理できます。先ほどの100とか50とかの、ただの数字というのは、変数に対して定数と呼ばれたりします。
変数の型は整数値のintにし、x,y座標としてのenemy_x, enemy_y を作成します。
int enemy_x, enemy_y; //敵のx,y座標 void setup(){ size(500,500); } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } }
乱数
さて、enemy_xは敵のx座標であり、初期値をランダムにしたいです。そうでなければ、ゲーム開始時は毎回同じ位置から敵が現れるゲームになってしまい、面白くありません。
そこで登場するのが乱数を得られるrandom(最小値, 最大値)です。一応、最大値自身は得られないことに注意します。
float rand=random(5,100); //5~99.999... float rand2=random(100); //0~99.9999
値を１つしか指定しなければ、最小値には勝手に0が入ります。
random()は最小値と最大値を指定して、その間の値の乱数を得ます。しかし、これはfloat型といって小数点まで許容する型なので、今用意したint型変数enemy_xとは型が合いません。そこで型変換を使います。型変換は、「目的の型(値)」と書くことで、型をその時の一瞬だけ変更できます。
int x=random(100); //intにfloatを代入しようとしてエラー int x=int(random(100)); //これは両方intになっているので代入できる
ちなみに、float型をint型に変換した際は、小数点以下は切り捨てされます。1.9でも1.1でも変換後は1です。
というわけで乱数の準備が整ったので、使っていきます。
まずはenemy_xの初期値をランダムに、enemy_yの初期値を-50にします。-50にするのは、最初は画面に映らないようにするためです。
初期化は最初の1回だけ行えば良いので、setup()に書きます。
ついでに敵もellipse()で描画しましょう。
int enemy_x, enemy_y; //敵の座標 void setup(){ size(500,500); enemy_x=int(random(width)); enemy_y=-50; } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } ellipse(enemy_x,enemy_y,50,50); //敵 }
widthというのは画面の幅を表すものです。これはシステム変数と呼ばれるもので、最初からprocessingが用意してくれている変数です。実はmousePressedもシステム変数です。
size()で画面サイズを設定しましたが、この時に自動でwidth、heightという名前で幅と高さが代入されます。
上から落とすということ
次にこれを上から下に落とします。
この落とすスピードもランダムにしたいので、enemy_speedも変数として作成しましょう。また、setup()でランダムに初期化します。乱数の範囲は、適当に2~5あたりにすれば良いのではないでしょうか。
動かすということは、draw()が実行される度に座標になんらかの値が足されるということです。つまりenemy_yにenemy_speedを足していけば、敵は下に落ちていきます。
ついでにhpも、enemy_hpという名前で作成し、setup()で100で初期化しておきます。
int enemy_x, enemy_y; int enemy_speed; //敵のスピード int enemy_hp; //敵の体力 void setup(){ size(500,500); enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); //スピードの初期化。6は含まないので2~5になる enemy_hp=100 //体力の初期化 } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } ellipse(enemy_x,enemy_y,50,50); enemy_y+=enemy_speed; //座標を増やしていく }
下まで落ちればまた戻る
次に「下まで落ちればまた上から降ってくる」です。方針としては 下まで行った円の座標を再び上に戻す ことを考えます。
下に落ちるとはどういうことでしょうか。それは円が画面の外に出てしまうことであり、円のy座標がheightを超えてしまうことです。ここでheightは先ほど出てきたシステム変数で、実行画面の高さが自動で格納されています。
この判定はif文で書くことができ、条件式は不等号を使って書けます。
int enemy_x, enemy_y; int enemy_speed; int enemy_hp; void setup(){ size(500,500); enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } ellipse(enemy_x,enemy_y,50,50); enemy_y+=enemy_speed; if(enemy_y-25>height){ //画面の下に出たら //元に戻す } }
if(enemy_y-25>height)がそれです。-25している理由は、円の座標はあくまで円の中心なので、ここだけで判定すればまだ上半分が見えているのに上に戻ってしまい、不自然になるからです。完全に見えなくなってから上に戻すためには、円の上側、つまりenemy_y-25である点で比べる必要があります。
では、このような条件で敵の位置をまた上に戻すにはどうすれば良いでしょうか。実はこの処理は、敵を初期化することと同じになります。setup()を見てみると、ここには既にx座標をランダムにして、y座標を上に持って行って、スピードをランダムし、そしてhpを0にする4行の処理が書かれています。これをそのままもらってこれば良いです。
int enemy_x, enemy_y; int enemy_speed; int enemy_hp; void setup(){ size(500,500); enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } ellipse(enemy_x,enemy_y,50,50); enemy_y+=enemy_speed; if(enemy_y-25>height){ //画面の下に出たら //初期化、setup()の4行と同じ enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } }
ここで、「では関数に分ければ良いのでは」と思った方は素晴らしいです。でもここでは関数の概念は割愛することにしています。
敵を「倒せる」ようにする
次に敵を倒せるようにします。この周辺の処理は以下のようになるでしょう。
・ビームと敵との当たり判定を取る
・当たり判定が起これば、敵のHPを減らす
・HPが０になった敵は消滅し、また上から降ってくる
敵とビームとの当たり判定はどう書けばよいでしょうか。
この当たり判定もやはりif文で書けます。ビームが敵に当たるということは、ビームのx座標が敵のx座標と被っていることと同じです。
ビームは線なので、x座標はただ１点、mouseXです。
でも敵は円なので、x座標と言っても範囲を持っています。これはenemy_x-25~enemy_x+25で求められます。
この２つから、数学みたいに書くとenemy_x-25<=mouseX<=enemy_x+25 を満たすとき、当たっていると言えます。
int enemy_x, enemy_y; int enemy_speed; int enemy_hp; void setup(){ size(500,500); enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } ellipse(enemy_x,enemy_y,50,50); enemy_y+=enemy_speed; if(enemy_y-25>height){ //画面の下に出たら //初期化、setup()の３行と同じ enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } //当たり判定 if(enemy_x-25<mouseX && mouseX<enemy_x+25){ //hpを減らす } }
でも、これだけではうまくいかない場合があります。自機は上方向にビームを出しているので、仮に自機より下に敵がいればその敵は倒せないはずです。でもx座標だけで判定しているので、上も下も関係なく当たり判定が起こってしまいます。ということで、敵が自機より上にいる、つまりenemy_y< mouseYの条件を追加してあげます。
このような条件の時、enemy_hpを減らします。とりあえず適当に1引くようにしましょう。
int enemy_x, enemy_y; int enemy_speed; int enemy_hp; void setup(){ size(500,500); enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } ellipse(enemy_x,enemy_y,50,50); enemy_y+=enemy_speed; //画面下に出たら if(enemy_y-25>height){ enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } //当たり判定 if(enemy_x-25<mouseX && mouseX<enemy_x+25 && enemy_y<mouseY){ //条件を追加した enemy_hp--; } }
最後に、HPが無くなれば消滅するところですが、これも結局、初期化と同じ作業になります。下に落ちずとも瞬間的に画面上に戻せば、プレイヤーは消滅したかのように感じるでしょう。この時、HPを元に戻したり、x座標、スピードを再度ランダムに設定するので、やはりsetup()の４行を持ってくることにします。
HPがなくなることはenemy_hp=0になることなので、if文でenemy_hp<0で表現できます。
int enemy_x, enemy_y; int enemy_speed; int enemy_hp; void setup(){ size(500,500); enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } ellipse(enemy_x,enemy_y,50,50); enemy_y+=enemy_speed; //画面下に出たら if(enemy_y-25>height){ enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } //当たり判定 if(enemy_x-25<mouseX && mouseX<enemy_x+25 && enemy_y<mouseY){ //条件を追加した enemy_hp--; } if(enemy_hp<0){ enemy_x=int(random(width)); enemy_y=-50; enemy_speed=int(random(2,6)); enemy_hp=100; } }
１体から複数へ
ここまで、敵を１体だけ作り、その敵についての動きを定義してきました。でもシューティングゲームは1体の敵とたわむれるゲームではなく、複数の敵と戦うから楽しいのです（これは筆者の主観が入っていますが笑）。
ということで、敵を増やすことを考えます。
複製するということと、配列
先ほど、1体の敵を作るためにはx,y,座標、スピード、体力の4つの変数が必要なことは体験できたと思います。ならば、同じように変数を増やしていけば、敵を増やすことができます。試しに以下のように作成してみましょう。
int enemy_x,enemy_y,enemy_speed,enemy_hp; //1体目 int enemy2_x,enemy2_y,enemy2_speed,enemy2_hp; //2体目 int enemy3_x,enemy3_y,enemy3_speed,enemy3_hp; //3体目 /* めっちゃめんどくさそう */
これは良くない例です。確かにこの数の変数は必要になるのですが、このような作り方では日が暮れてしまいます。
ここで登場するのが「配列」です。これはいくつかの変数をまとめたようなもので、[ ]の記号を使って、どの変数のことなのかを一括管理できます。
使い方は以下の通りです。
int x[]=new int[100]; //100個の変数を作ったことと同じ int y=x[0]; //1つ目の変数をyに代入 /* x[0]で1つ目の変数 x[1]で2つ目の変数 ..... x[99]で100つ目の変数として表記できる */
変数を作るときに名前の後ろに[]をつけると、配列として定義できます。作った配列は、名前の後ろに[数字]をつけることで、何番めの変数なのかを表します。ここで、番号を指定する数字は0始まりであることに注意です。例えば、100個の変数を配列で作れば、[0]~[99]までの番号で指定できます。また、この番号のことを添字と言います。
作るときの構文は、一般化すれば
・ 型 変数名[ ]=new 型[個数]
ですね。
敵を増やすには、x,y,スピード、HPの4つの変数を全て配列にすれば良さそうです。
効率の良い配列へのアクセス
今、配列という概念を導入しました。でも、現段階では「変数の宣言」は綺麗に書くことができます。しかし、これを使うときはどうするのでしょうか。
int enemy_x[]=new int[100] void setup(){ //ほんまにこれ書くの・・？ enemy_x[0]=int(random(width)); enemy_x[1]=int(random(width)); .................. enemy_x[99]=int(random(width)); }
ということで、for文を導入します。構文はこうです。
//iは変数名なのでなんでも良いが、for文にはよくi,j,kが使われる for(int i=0 ; i<100 ; i++){ //処理 } /* 一般化すれば for(型 変数名 = 初期値; 変数名<終わりの値+1 ; 変数への加算処理){ } とかけます。 */
for文では、ある変数（上ではi）を用意して、それを好きな範囲で順番に増やすような操作になります。
上のコードであれば、iは0,1,2,3,4,5.....99まで増えます。
と、ここまできたところで、数字の範囲が共通していることに気づきます。
・100個の要素を持つ配列の添字 → 0,1,2,3,4....99
・for(int i=0;i<100;i++)と書いたときの変数iの動き → 0,1,2,3,4....99
つまり、for文と配列は非常に相性の良いことがわかります。
よって、簡単な例では以下のような処理を書くことができます。
int x[]=new int[100]; void setup(){ //一気に初期化 for(int i=0;i<100;i++){ x[i]=int(random(width)); } }
いざ、改良へ
では、いよいよ敵を複数にしていきましょう。とは言っても、変数を全て配列にして、それをfor文で回すような処理に書き換えれば良いです。
要素数は今回は10程度にしてみます。
念のため、具体例としては
int enemy_x→int enemy_x[]=new int[10];
のようにすれば良いです。
以上から、以下のようにコードが書き換えられます。少し一気に変えますよ！
int enemy_x[]=new int[10], enemy_y[]=new int[10]; int enemy_speed[]=new int[10]; int enemy_hp[]=new int[10]; void setup(){ size(500,500); for(int i=0;i<10;i++){ enemy_x[i]=int(random(width)); enemy_y[i]=-50; enemy_speed[i]=int(random(2,6)); enemy_hp[i]=100; } } void draw(){ background(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } for(int i=0;i<10;i++){ ellipse(enemy_x[i],enemy_y[i],50,50); enemy_y[i]+=enemy_speed[i]; //画面下に出たら if(enemy_y[i]-25>height){ enemy_x[i]=int(random(width)); enemy_y[i]=-50; enemy_speed[i]=int(random(2,6)); enemy_hp[i]=100; } //当たり判定 if(enemy_x[i]-25<mouseX && mouseX<enemy_x[i]+25 && enemy_y[i]<mouseY){ //条件を追加した enemy_hp[i]--; } if(enemy_hp[i]<0){ enemy_x[i]=int(random(width)); enemy_y[i]=-50; enemy_speed[i]=int(random(2,6)); enemy_hp[i]=100; } } }
enemy関係の変数を全て配列にして全体をfor文で回すようにしただけで、ほとんどコード長を変えずに敵の数を増やすことができました。
draw()の中でfor文を回す感覚がよくわからないかもしれませんが、「毎フレーム10個の敵を一度に描画する」と考えれば良いのではないでしょうか。
draw()の最初ではbackground(255)が効いているので、「10個の敵を描画、座標の更新」→「塗りつぶし」→「10個の敵を描画、座標の更新」→「塗りつぶし」・・が繰り返されることになります。
スコアづけ
これは「おまけ」みたいな要素です。
ゲーム というのは、プレイヤーからすれば何かしらの達成感が欲しいところで、それは報酬という形で与えることができます。今回はスコアという報酬をつけて、モチベーションの向上にしたいと思います。
スコアの仕様はただ一点です。
・敵を1体倒すことで1増える。
この実装は簡単で、int score;のように変数を作ったのちに、敵の体力が0になってまた上に戻るようなときにscoreを増やせば良いです。
次に、このスコアの表示はどうすれば良いでしょうか。実はtext()というものを使えば書くことができます。
text()の使い方は以下の通りです。
text("aaa",10,10); //「aaa」が点(10,10)のところに表示される。 int x=100; text(x,10,10); //「100」が点(10,10)のところに表示される。 text("aaa"+x,10,10); //「aaa100」が点(10,10)に表示される。
このように、text()で表示する内容にはプラスの記号で繋ぐことで、複数並べることができます。
今回は、"score: "+scoreのようにすれば、「score: 4」のようにスコアが表示されるはずです。ここで、ただの文字列としての"score"と、変数名としてのscoreの違いに注意します。多くのプログラミング言語では、文字列は"ダブルクオーテーション"で囲むことで表せます。processingも例外ではありません。
int enemy_x[]=new int[10], enemy_y[]=new int[10]; int enemy_speed[]=new int[10]; int enemy_hp[]=new int[10]; int score; //スコアを格納する変数 void setup(){ size(500,500); for(int i=0;i<10;i++){ enemy_x[i]=int(random(width)); enemy_y[i]=-50; enemy_speed[i]=int(random(2,6)); enemy_hp[i]=100; } score=0; //0で初期化 } void draw(){ background(255); fill(0); //文字色は黒 text("score: "+score,10,10); //scoreを表示 fill(255); //でも他は白色 ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } for(int i=0;i<10;i++){ ellipse(enemy_x[i],enemy_y[i],50,50); enemy_y[i]+=enemy_speed[i]; //画面下に出たら if(enemy_y[i]-25>height){ enemy_x[i]=int(random(width)); enemy_y[i]=-50; enemy_speed[i]=int(random(2,6)); enemy_hp[i]=100; } //当たり判定 if(enemy_x[i]-25<mouseX && mouseX<enemy_x[i]+25 && enemy_y[i]<mouseY){ //条件を追加した enemy_hp[i]--; } if(enemy_hp[i]<0){ enemy_x[i]=int(random(width)); enemy_y[i]=-50; enemy_speed[i]=int(random(2,6)); enemy_hp[i]=100; score++; } } }
textによる文字の色は、fill()を使って変えることができます。このときの色はbackground()の時と同じで、fill(0)で黒、fill(255)で白です。ただし、fill()はellipse()の塗りつぶす色も変えてしまうので、fill(0)→テキスト描画→fill(255)→図形の描画 という流れにより、テキストだけ黒にすることができます。
他にも、文字サイズを変えたいときにはtextSize(整数)で変えることもできます。
textSize(50); text("aaa",10,10); //文字サイズ50で「aaa」と表示
以上でスコアの表示できるようになりました．今回扱う内容は，これで終了です．
さらなる発展
余裕があればやりたいところです。
ゲーム性の拡張
このシューティングゲームには、この記事には書ききれない余地がまだまだあり、かなり発展させられます。
・敵も攻撃してくるようにする
・敵のHPもなんらかの形で見えるようにする
・自機の攻撃を、ただの線だけではなくて、点線のようにしてみる（より細かい弾を連射しているような描画）
・白黒だけでなく、他の色を使ってみる
・敵を倒したとき、敵が爆発するような描画、もしくは何かしらのエフェクトを追加する
・進行方向を変えることでマンネリ化を防ぐ（例えば、「自機は上方向にビームを出して敵は上から落ちてくる」を「自機は下方向にビームを出して敵は下から上がってくる」みたいに、y座標の増減を反転させたり、戻したりする）
・敵を倒すとスコアが増えるだけでなくお金がもらえて、それを使うことで自機を強化できる。
・敵を複数倒すと必殺技みたいなのが使えて、敵を一掃できる。
などなど、様々な拡張が考えられます。
今回の記事では紹介しきれませんでしたが、ぜひ、取り組んでみてください。
シーン遷移の導入
スタート画面や操作説明画面などを追加すれば，もっとゲームらしくなります．
この話題は以下の記事で扱っているので，興味がある方はご覧ください．
PVector型の利用
今回は全ての値をint型で作成しました。その中で、enemy_xとenemy_yというのが出てきましたが、これらの宣言は独立していました。
でも、xとyの組はよく現れるものであり、１つの塊として扱えれば少し楽になれます。つまり、xの変数、yの変数という作り方ではなくて、x,yの組の変数として作るのです。
これを実現するのがPVector型です。PVector型は2つの値を保持できます。具体的には以下の通りです。
PVector point; point=new PVector(1,2); //配列みたいにnewを使うことに注意 ellipse(point.x , pount.y , 100 , 100); //ellipse(1,2,100,100)と同じ
このコードでは、変数pointは点(1,2)を表します。かつ、.x , .yのようにドットを使うことでそれぞれの値を見ることもできます。
もちろん、これの配列も作ることができるので、改良の余地があります。
ぜひ使い方に慣れて、コードを書きやすくしてみてください。
関数の利用
記事でも一瞬、関数という言葉を出した時がありましたが、関数を使えばより処理が簡潔にかけます。
例えば、敵の情報を初期化するコードは、setup()、敵が下まで落ちきった時、敵を倒したときの3つの場面で実行される可能性があり、プログラム的にも全く同じ記述が３箇所に現れています。しかしこれは冗長なので、関数を使って処理をくくり出してやることで簡潔になります。
関数を利用したものがこちらです。
int enemy_x[]=new int[10], enemy_y[]=new int[10]; int enemy_speed[]=new int[10]; int enemy_hp[]=new int[10]; int score; //スコアを格納する変数 void setup(){ size(500,500); for(int i=0;i<10;i++){ enemy_init(i); //これ！ } score=0; } void draw(){ background(255); fill(0); text("score: "+score,10,10); fill(255); ellipse(mouseX,mouseY,50,50); if(mousePressed){ line(mouseX,mouseY,mouseX,0); } for(int i=0;i<10;i++){ ellipse(enemy_x[i],enemy_y[i],50,50); enemy_y[i]+=enemy_speed[i]; //画面下に出たら if(enemy_y[i]-25>height){ enemy_init(i); //これ！！ } //当たり判定 if(enemy_x[i]-25<mouseX && mouseX<enemy_x[i]+25 && enemy_y[i]<mouseY){ //条件を追加した enemy_hp[i]--; } if(enemy_hp[i]<0){ enemy_init(i); //これ！！！ score++; } } } //初期化する処理をenemy_initという名前をつけてくくり出した。 //これは整数iを与えて、i番目の敵について初期化するもの。 void enemy_init(int i){ enemy_x[i]=int(random(width)); enemy_y[i]=-50; enemy_speed[i]=int(random(2,6)); enemy_hp[i]=100; }
どうでしょう、結構見やすくなったと思いませんか？関数を使えるようになると、処理を分けて考えやすくなるし、その結果見やすく理解しやすいコードを書くことができます。
クラス
クラスというのは、もっと大きな処理をまとめて、それを複製するイメージで増やすことができます。
例えば、今回で言う敵を増やすところは、配列を何個も作ってそれを合体させることで実現していました。でもこれは、あくまで独立に宣言された配列を、「分かっている」人間がそれをひとまとまりのように扱っているにすぎません。しかしクラスというのは、先に１まとまりとしての処理（これには変数の宣言、初期化のための関数、実際に下に落とすような処理、当たり判定をする処理など）を書いた後で、その処理ごと複製するイメージです。プログラム的にも、これはひとまとまりな処理系というのが明示的に示せます。
２つ上の項目で紹介したPVectorは、まさにクラスの考えと一致しています。x,yを独立に宣言するなら、それをまとめたものを作れば全て一度に宣言できて便利、というような気持ちです。
他の最小限ゲーム制作シリーズ
本記事ではシューティングを扱いましたが，他のゲームについても，同じくらいの粒度で説明しているものがあります．合わせてご覧ください．
Processingで始める周期運動
こんにちは。KSWLのごつちやんです。
ここでは「三角関数を使って何かする」ことを「周期運動」と銘打って、processingを使ってやっていこうと思います。
processingのインストール
processingのインストールについては他にもたくさん記事があると思うので、そちらを参照してください。（以下のサイトなどが参考になるかも）
【Processing入門】インストールと使い方（Windows編） | アルゴリズム雑記
processing入門：Processing 2のダウンロードとインストール 梶山 喜一郎
processingの基本的なメソッド
以下に自分の記事があるので参考にしてください。この記事の中でも、「基本的な構造」「円と楕円」「三角関数」「ある範囲の変数を別の範囲に移す」の項を特に読んでおくと良いです。
processingとopenframeworksを比較してみる - gotutiyan’s blog
三角関数について
最初に周期運動を三角関数を使って表現するものと説明しました。一般に三角関数は以下のような形をしています。
ここで見て欲しいのは、三角関数というグラフは、xがとる値を増やすに連れてその値は大きくなる、小さくなるを繰り返して動くものだということです。
でも、プログラムの中でこのxの値をどのように変えれば良いのかという問題があります。そこで、xを時間に設定するという考えのもと実装すれば、綺麗なものになります。
また、三角関数は-1~1の範囲しか取りません。この値をプログラムで利用すれば、たった１ピクセル単位でしか振動せず、変化が分かりません。このため、これから行う実例では、三角関数の値に100などの大きな数をかけることで、-100~100まで範囲を拡張して利用することになります。この点も重要なので、覚えておきましょう。
三角関数の利用
では、いくつかの例をもとにして、実際に三角関数を利用してみます。
円の直径に利用する
三角関数の値を円の直径に利用することで、円が周期的に大きくなったり小さくなったりします。
ここでは、xに時間としてframeCountを50で割ったものを利用しています。なぜ50で割るのかといったことは、こうすれば程よい速さで周期が回るので良いから、という説明をしておきます。
また、三角関数の値を動かしたい半径に対応させるため、[-1~1]の範囲を[50~450]に移します。
void setup(){ size(500,500); } void draw(){ background(255); float radian=frameCount/50.0; float r=map(sin(radian),-1,1,50,450); ellipse(width/2,height/2,r,r); }
円の位置に利用する
円のx座標に三角関数を適用すれば、円が左右に動きます。
以下の例では、三角関数をx座標に利用し、先ほどの例と同様に[-1~1]の範囲を[50~450]に移します。
void setup(){ size(500,500); } void draw(){ background(255); float radian=frameCount/50.0; float x=map(sin(radian),-1,1,50,450); ellipse(x,height/2,50,50); }
円の色に利用する
色をHSBで使用する時、Hの濃さを三角関数で操作すれば、虹色に変化します。
色は通常0~255で指定するので、[-1~1]の範囲を[0~255]に移します。
また、frameCount/100.0とすることで、frameCount/50.0よりも少し遅い変化を実現します。
void setup(){ size(500,500); } void draw(){ background(255); colorMode(HSB); float radian=frameCount/100.0; float c=map(sin(radian),-1,1,0,255); fill(c,255,255); ellipse(width/2,height/2,450,450); }
もう少し三角関数を使う
円挙動
これまでの例では、三角関数は１つしか使われていませんでした。ここからはさらに使う量を増やして見ましょう。
x座標にcos、y座標にsinを利用してみると、円の挙動は円になります。（少し変な表現ですが笑）
今回もmap()を使っていますが、このような変換であれば200*sin(radian)と同じなので、より表記が簡単なこちらを利用することもできます。が、混乱を避けるため全てmapで行います）
void setup(){ size(500,500); } void draw(){ background(255); float radian=frameCount/50.0; float x=map(cos(radian),-1,1,-200,200); float y=map(sin(radian),-1,1,-200,200); ellipse(x+width/2,y+height/2,50,50); }
リサージュ曲線
先ほどの円運動は、x=cos(radian)、y=sin(radian)でした。実はこの表現方法は中々応用が利いて、この式を変えるだけで全く違う顔を見せます。
今回はx=sin(3*radian)、y=sin(4*radian)としてみましょう。
4文字付け加えるだけの簡単な変更ですが、全然違う動きをします。どのような軌跡を描くのかを見たければ、background()をコメントアウトします。
void setup(){
size(500,500);
}
void draw(){
background(255);
float radian=frameCount/100.0;
float x=map(sin(3*radian),-1,1,-200,200);
float y=map(sin(4*radian),-1,1,-200,200);
ellipse(x+width/2,y+height/2,50,50);
}
アステロイド曲線
x=cos(radian)*cos(radian)*cos(radian)
y=sin(radian)*sin(radian)*sin(radian)
と変更すれば、また新しい顔を見せます。
void setup(){ size(500,500); } void draw(){ background(255); float radian=frameCount/50.0; float x=map(cos(radian)*cos(radian)*cos(radian),-1,1,-200,200); float y=map(sin(radian)*sin(radian)*sin(radian),-1,1,-200,200); ellipse(x+width/2,y+height/2,50,50); }
円の数を増やす
さて、ここまで周期運動を１つの円を動かすことで見てきましたが、まだまだ本領発揮とはいきません。円の数を増やすことで、さらなる感動を得られます。
今からやることは、円をいくつも用意してその周期の速さを変える（radianの進む速さを変える）ことです。
このために、配列を1つ用意します。
radianの配列です。以下はリサージュ曲線を例に、円をたくさん描画するものです。
ずっと見ていると複数の円が重なる場面が出てくるところが最高ですね。
PI/512*(i+1)/50; という部分にはそれなりの経験からくるものがあるのですが、説明は割愛します。PIというのは円周率3.1415..ですね。
float radian[]=new float[50]; void setup(){ size(500,500); } void draw(){ background(255); for(int i=0;i<50;i++){ radian[i]+=PI/512*(i+1)/50.0; float x=map(cos(3*radian[i]),-1,1,-200,200); float y=map(sin(4*radian[i]),-1,1,-200,200); ellipse(x+width/2,y+height/2,10,10); } }
今までと同様に、ここでのx,yに代入する式を変えることで全く違う顔を見せます。
以下はアステロイド曲線です。
float radian[]=new float[50]; void setup(){ size(500,500); } void draw(){ background(255); for(int i=0;i<50;i++){ radian[i]+=PI/512*(i+1)/20.0; float x=map(cos(radian[i])*cos(radian[i])*cos(radian[i]),-1,1,-200,200); float y=map(sin(radian[i])*sin(radian[i])*sin(radian[i]),-1,1,-200,200); ellipse(x+width/2,y+height/2,10,10); } }
色をグラデーションさせる
今、円は全て白塗りになっていて、少し味気ないです。色を加えることでもう少し綺麗に見せることができます。
具体的には、今ある50個の円を全てグラデーションさせます。
float radian[]=new float[50]; void setup(){ size(500,500); colorMode(HSB); } void draw(){ background(255); for(int i=0;i<50;i++){ radian[i]+=PI/512*(i+1)/20.0; float c=map(i,0,49,0,255); float x=map(sin(3*radian[i]),-1,1,-200,200); float y=map(sin(4*radian[i]),-1,1,-200,200); fill(c,255,255); ellipse(x+width/2,y+height/2,10,10); } }
Atcoder ABC99-D GoodGrid
問題
色iを色jに塗り替える時に感じる違和感と、色が塗られたマス目の情報が与えられる。この時、(i+j)%3=(x+y)%3となるような(i,j),(x,y)のマス目は全て同じ色に塗らなければならない。感じる違和感の最小値を求める。
解説
全探索をします。
前準備として、v[0,1,2][0,1,2,,c]の配列において、「v[i][j]:=(x+y)%3==i のマス目における色j の出現回数」とすることで、(x+y)%3=0,1,2それぞれについて、最初はどの色が何個あるのかを持っておきます。
次に、i,j,kの３重ループを０〜cで回し、i≠j≠kの時、(x+y)%3=0のマス目をi, =1のマス目をj, =2のマス目をkで塗るような全探索をします。これによって最小値を調べ、出力すれば良いです。i,j,kを決めれば、あとは(x+y)%3のそれぞれについて、「今塗られている色の個数」*「その色をi,j,kに変える時の違和感」の総和をとります。
以下、コードです（#includeは省略）
int main (){ int n,c;cin>>n>>c; vector<vector<int>> v(3,vector<int>(c)),cost(c,vector<int>(c)); rep(i,0,c)rep(j,0,c)cin>>cost[i][j]; //違和感 rep(i,0,n)rep(j,0,n){ int x;cin>>x; v[((i+1)+(j+1))%3][x-1]++; } int ans=1e18; rep(i,0,c){ //%3==0をiに rep(j,0,c){ //%3==1をjに if(i==j)continue; rep(k,0,c){ //%3==2をkにするとき if(i==k || j==k)continue; int ret=0; rep(ind,0,3){ //%3の値 int x; if(ind==0)x=i; else if(ind==1)x=j; else if(ind==2)x=k; rep(val,0,c){ ret+=v[ind][val]*cost[val][x]; } } ans=min(ans,ret); } } } cout<<ans<<endl; }
yukicoder No.643 Two Operations No.2
問題
No.643 Two Operations No.2 - yukicoder
解説
この解説は多分悪い例として見ていただくのが良いと思います。
考察のできる人は、公式解説通りに考えられるのでしょう。でも僕にはそんな思いつきはありませんでした。ならマシンパワーに頼るしかない、ということで、全探索解でACしました。これも競技プログラミングです。
操作1,2を様々な順番で実行して行って、x==yとなるような最小手順を探してみます。
問題はこの手順をどれくらいの深さまで見るかですが、適当に手元で実行すると、30回では時間がかかりすぎたので、20回にしました。
ans=10000と初期化しておいて、x==yになればctとの最小値を取ります。最終的にans==10000であれば、x==yにならなかったので-1を出力です。
今回は偶然答えが3以下になるような問題だったので、全探索が通って嬉しいですね。
#include <iostream> using namespace std; int ans=100000; void dfs(int x,int y,int ct){ //cout<<x<<y<<endl; if(ct>20){ //20回操作を試して見たら終了 return; } if(x==y){ ans=min(ans,ct); return ; } dfs(y,x,ct+1); //操作１ dfs(x+y,x-y,ct+1); //操作２ return; } int main (){ int x,y; cin>>x>>y; dfs(x,y,0); if(ans!=100000)cout<<ans<<endl; else cout<<-1<<endl; return 0; }
