2016.12.31 Saturday
yukicoder No.110
まーだまだつづくーよー、yukicoder。
技術系サラリーマン、ジャジャガッチの駄文です。
姉妹サイト「ジャジャガッチの勉強ノート」もよろしくお願いします。
ブログ中の回路等そのまま真似して事故になっても責任は負いませんのであしからず。
2016.12.30 Friday
yukicoder始めた。
ついでにTwitterも(@jajagacchi)。
ゆるく競技プログラミングをしたい人が集うサイト。
いつかコンテストにも参加してみたい。他のコンテストよりも敷居は大分低そうなので。
とりあえず入出力テストとしてすっごい簡単な問題を解いてみた。
問題:
1歩でぴったりaセンチメートル歩ける。
bセンチメートルの区間を歩くのに何歩歩く?
なお、区間はオーバーしても良い。
簡単だけど、少しでもかっこいいコードを書こう。
コードは続きから。
2016.12.11 Sunday
久々に蟻本を読んでいる。
というわけで深さ優先探索。
アルゴリズムは単純で、
root nodeをスタックにpushする;
while(stack.size()!=0)
{
stack.pop();//これが現在node
現在nodeの全ての子nodeをpushする;
}
これだけ。root nodeが複数あるときはこれを各root nodeについて回すだけ。
んで、やっぱりちゃんと問題解かないと理解できてるのかわかんねえや、ということでAOJ0030を解いてみた。
問題は次の通り。
「0 から 9 の数字から異なる n 個の数を取り出して合計が s となる組み合わせの数を出力するプログラムを作成してください。n 個の数はおのおの 0 から 9 までとし、1つの組み合わせに同じ数字は使えません。たとえば、n が 3 で s が 6 のとき、3 個の数字の合計が 6 になる組み合わせは、
1 + 2 + 3 = 6
0 + 1 + 5 = 6
0 + 2 + 4 = 6
の 3 通りとなります。 」
#include <iostream> #include <stack> class Node { public: Node(int val , int sum , int height) { this->val = val; this->sum = sum; this->height = height; } int val,sum,height; }; int main() { while(1) { int count = 0; int n; std::cin >> n; int s; std::cin >> s; if(n==0 && s==0) break; for(int val0=0;val0<10;val0++) { std::stack<Node> st; st.push(Node(val0,val0,1));//root nodeをpushする while(st.size()!=0) { Node node = st.top(); st.pop(); if(node.height==n && node.sum==s) { count++; } if(node.height<n)//popしたnodeの子nodeを全てpushする { for(int j=node.val+1;j<10;j++) { st.push(Node(j,node.sum+j,node.height+1)); } } } } std::cout << count << std::endl; } return 0; }
st.push(Node(j,node.sum+j,node.height+1));で子nodeを生成してpushしてる。
例によってroot nodeは複数あるのでそこにも注意。
子nodeを正しくコードに落とし込めるかがポイント。
stack->queueで幅優先探索になるのは言わずもがな。
2016.12.09 Friday
昨年の「プログラミングで彼女をつくる」に続き、「こーどがーるこれくしょん」を発表したpaiza。お次は「もし次の常駐先が女子エンジニアばっかりだったら」。うん、またアニメオタク臭くて人前で出来ない感じやな!
こーどがーるこれくしょんはC++への対応もされたのだが、評判を見ると問題があまりに簡単過ぎてタイピングゲームと言われる始末で、やる気が起こらないので放置していた。
今回はどうかな、と少しやってみると、簡単過ぎることはなさそう。ただ、プログラミング以外にときめもみたいなことしないといけないのが面倒くさい。
過去に提出したコードが見れないのが痛いが、まあ少しやってみよう。
あまりに簡単でつまんない問題については特に紹介しません。
ひとつ紹介しよう。
問題:
芦屋川雛乃は簡易的な暗号のプログラムを作成で困っています。
あなたはその暗号プログラムを完成させて下さい。
通信される内容は数字列のみとします。
暗号化は、変換対応表に従い各数字を別の数字に変換することで行います。
"257" を暗号化の例を次に示しました。 2, 5, 7 がそれぞれ、4, 3, 5 に変換されるためです。
エンコードもデコードもせねばならん。
解答は続きから。