ICPC2012 新入生教育編1 ループと配列と
本日は新入生に向けて配列・ループのテクニックを伝授した。以下は、その練習問題と解説を記す。
(ここ教えたほうがいいとかフィードバックあったらお願いします)
和の合計問題
n個のボールが与えられ、i番目のボールには数字a[i]が記されています。 ボールを3つ取り出した時に和がmとなる組み合わせが存在するか。存在する場合はYES、存在しない場合はNOを出力せよ。 なお、同じボールを複数回取り出せるものとする。 ただし値の範囲は以下のものとする。なお、n=0,m=0のとき終了とする。 0 <= n <= 100 0 <= m <= 3000 0 <= a[i] <= 1000 input n m a[0] a[1] ... sample input 4 5 1 2 3 4 4 128 1 2 3 4 0 0 sample output YES NO
解説編1 新入生に望む解法
nより大きい配列a[MAXN]をあらかじめ確保しておき、a[i]にボールの数字を入れていく
3重ループでa[i]+a[j]+a[k]==mとなれば存在する。
#include <iostream> using namespace std; const int MAXN=100; int a[MAXN]; int main() { int n,m; while(cin>>n>>m&&(n||m)) { for(int i=0;i<n;i++) cin>>a[i]; bool ans = false; for(int i=0;i<n;i++) for(int j=0;j<n;j++) for(int k=0;k<n;k++) { ans |= (a[i]+a[j]+a[k]==m); } cout<<(ans?"YES":"NO")<<endl; } return 0; }
また、下記の点について補足して教えておいた。
cinの使い方(値の取得からEOFの認識など)
const intや#defineで定数化しておくこと
ひと通り全員出来たところで、O(オーダー)の概念についても説明した。
今回の問題はforが1重と3重の部分がある。一番時間かかっている部分は3重の部分であるので、O(n^3)とする。
また、競技プログラミングにおける時間計算量の概算方法についても補足した。
O(n^3)でn<=100なので、100^3 => 10^6 => 1M(メガ)
プロセッサが1GHzとすると、10^6/10^9 => 0.001秒くらいである。
競技プログラミングでは2秒以内に終わるように求められることが多いので注意が必要である。
n<10000となった場合について考えてもらい
10000^3 => 10^12 => 1000秒くらいなので、もう少し早いアルゴリズムを考えてもらう。
解説編2 2年目以降の人に望む解答
O(n^2)で解くと、10000^2 => 10^8 => 0.1秒くらい
配列をうまく使う、類題が蟻本に載っているのでそちらを参考にしてもらった。
a[i]+a[j]==m-a[k]なので2重ループと2重ループなのでO(n^2)となる
#include <iostream> // cin cout #include <cstring> // memset using namespace std; const int MAXN=10000; const int MAXM=3001; int a[MAXN]; char b[MAXM]; int main() { int n,m; while(cin>>n>>m&&(n||m)) { for(int i=0;i<n;i++) cin>>a[i]; memset(b,0,sizeof(b)); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { b[a[i]+a[j]]=1; } bool ans = false; for(int i=0;i<n;i++) { ans |= (m>=a[i]) && (b[m-a[i]]); } cout<<(ans?"YES":"NO")<<endl; } return 0; }
配列bの添字とa[i]+a[j]を対応させて記録しておくことが大事である。
素数の問題
素数とは、1と自分自身以外には割り切れない数のことをいう。 問題1 0 <= n <= 100 までの数が与えられる、素数の場合はYES 素数以外の場合はNOと出力せよ、なお0は終了を意味する。 問題2 6桁の素数を大きい順番に100個表示させなさい 問題3 6桁の素数の平均を整数で表示しなさい 問題4 6桁の素数のうち、3のつく素数の個数を表示しなさい (XXX3XXや3XXXXXなど) 入力例 問題1 1 2 3 4 5 6 7 出力例 問題1 NO YES YES NO YES NO YES 問題2 999983 ... 998539 問題3 550964 問題4 388800
問1,問2は問題文の素数の定義通りに考えれば良い。
問3は愚直にやると実行時間がかかるし、intの上限についても考慮すべきという落とし穴も用意した。
問4は各自工夫すべし。
新入生に望む解法1
#include <iostream> using namespace std; bool isPrime(int n) { if(n<=1) return false; for(int i=2;i<n;i++) if(!(n%i)) return false; return true; } int main() { int n; while(cin>>n&&n) { cout<<(isPrime(n)?"YES":"NO")<<endl; } return 0; }
新入生に望む解法2
ここでふるいさせても良かったけどさせなくてもいいことにした。
#include <iostream> using namespace std; const int MAXN=1000000; // 7桁の最小値 const int MINN=100000; // 6桁の最小値 bool isPrime(int n) { if(n<=1) return false; for(int i=2;i<n;i++) if(!(n%i)) return false; return true; } int main() { int num = 0; for(int i=MAXN-1;i>=MINN;i--) if(isPrime(i)) { cout<<i<<endl; if(num<100) num++; else break; // 中で比較した方が回数が減るけどあんま気にしない } return 0; }
2年目以降に望む解法3
#include <iostream> using namespace std; const int MAXN=1000000; const int MINN=100000; typedef long long int ll; // intよりでかい char prime[MAXN]; // グローバル変数は0で初期化される int main() { // エラトステネスのふるい for(int i=2;i*i<MAXN;i++) if(!prime[i]) for(int t=i*2;t<MAXN;t+=i) prime[t]=1; ll ans = 0; ll num = 0; for(int i=MAXN-1;i>=MINN;i--) if(prime[i]) { ans += i; num += 1; } cout<<(ans/num)<<endl; return 0; }
ansやnumをintにすると-1994になっちゃうよ。
エラトステネスのふるいのアルゴリズムは以下のとおり
とりあえず全部素数としておく (prime[x]==0)
2は素数 => 2の倍数は素数でない prime[4]=1; prime[6]=1; ...
3は素数 => 3の倍数は素数でない prime[6]=1; prime[9]=1; ...
4は素数でない (4の倍数は2の倍数の時に消したから気にしない)
5は素数 => ...
2年目以降に望む解法4
オーダー的に死ぬかと思ったけどそうでもなかった。
#include <iostream> using namespace std; const int MAXN=1000000; const int MINN=100000; char prime[MAXN]; // グローバル変数は0で初期化される int main() { // エラトステネスのふるい for(int i=2;i*i<MAXN;i++) if(!prime[i]) for(int t=i*2;t<MAXN;t+=i) prime[t]=1; int ans = 0; for(int i=MAXN-1;i>=MINN;i--) if(prime[i]) { int da = 0; for(int n=i;n;n/=10) da |= ((n%10)==3)?1:0; ans += da; } cout<<ans<<endl; return 0; }
その他、細いテクニックは他人のソースコードを見て勉強すべし。
これからプログラミングの基礎力を付けたい方へ
プログラミングを始めて力を付けたいって方、しかし、どんなことができるか分からない、どんなことをしたいか分からない方
情報工学の基礎を楽しく学ぶ方法を伝授します。
この文章は、情報系新入生やパソコンギークになりたい方にお勧めです。(特に競技プログラミングを始めたい方にお勧めかも)
内容自体は、競技プログラミングやるといいよって話です。はい。
競技プログラミングとは
世の中には競技プログラミングと呼ばれるものがあります。数多くの問題が存在し、情報系の基礎力となるプログラミングやアルゴリズムのスキルが身につきます。
ソフトウェアのプログラミングの競技大会のこと。
主に、コンピュータ アルゴリズムに関する問題が数問出題されて、それを数時間以内の制限時間で解く。正しく解けたかどうかは、出題者側が用意したテストデータに対して、正しい答えを返すかどうかで判定されることが多い。
はてなキーワード
最大値はいくつ？とか 最短距離はいくつ？とか
そんな感じの問題ですねー。
オンラインジャッジ
さて、そんな競技プログラマの一般的な練習の場としてオンランジャッジと呼ばれるサービスがいくつかあります。
私の周りではAOJを使って練習している方が多いですね。とりあえずアカウント登録してVolume100をいくつかやってみるといいですよ。
おすすめ書籍(入門編)
プログラミングの宝箱 アルゴリズムとデータ構造
基本文法が終わったら、データ構造とアルゴリズム！下記は分かりやすくて、面白い題材のある本です。
プログラミングの宝箱 アルゴリズムとデータ構造 第2版
posted with amazlet at 12.04.08
プログラミングコンテストチャレンジブック
基礎力が整ったら実践を交えて勉強しましょう。競技プログラマ必携です！
![プログラミングコンテストチャレンジブック [第2版] 〜問題解決のアルゴリズム活用力とコーディングテクニックを鍛える〜](http://ecx.images-amazon.com/images/I/41bHxtpurqL._SL160_.jpg)
プログラミングコンテストチャレンジブック [第2版] 〜問題解決のアルゴリズム活用力とコーディングテクニックを鍛える〜
posted with amazlet at 12.04.08
おすすめ書籍(ステップアップ編)
Effective C++
中規模以上のソフトウェアを開発するために。C++のルールとマナーについて。
Effective C++ 原著第3版 (ADDISON-WESLEY PROFESSIONAL COMPUTING SERIES)
posted with amazlet at 12.04.08
アルゴリズムクイックリファレンス
ただのリファレンスではなく詳しい解説もあり、どのような時にどのアルゴリズムを使うべきか参考になります。
アルゴリズムクイックリファレンス
posted with amazlet at 12.04.08
おすすめ書籍(闇の軍団編)
Modern C++ Design
闇のC++er軍団への入門書。実に技工に富んだ面白い本だと思います。学部1年の時は読みふけりました。
Modern C++ Design―ジェネリック・プログラミングおよびデザイン・パターンを利用するための究極のテンプレート活用術 (C++ In‐Depth Series)
posted with amazlet at 12.04.08
おすすめ書籍(その他)
vimテクニックバイブル
宗教戦争が起こりそうなのでその他に。Linuxやエディタについての知識を深めると効率上がりますよ。
Vimテクニックバイブル 〜作業効率をカイゼンする150の技
posted with amazlet at 12.04.08
このように基礎力をしっかり身に付けたあとに、ウェブ系だとかゲーム系だとかやるといいんじゃないですかね。
HTML5/Javascriptでマルチプラットフォームのゲームを作るときの小ネタ
iPhoneやAndroidといったスマートフォンや、iPadなどのタブレット端末を意識したゲーム作りの小ネタです。
イベントの伝播を防ぐ
スマートフォンやタブレット端末ではタッチイベントが多用されます。
ブラウザで実行する際に、タッチすると拡大縮小やフォーカスやスクロールといった現象が発生します。
これを防ぐために下記のようなコードを仕込みます。
function on_touch(e) { // hogehoge e.preventDefault(); }
拡大縮小を制御する
スマートフォンやタブレット端末ではウィンドウを扱わないので仮想ウィンドウサイズを決めることができます。
metaタグで指定することで開いた時の拡大縮小の率を設定することができます。
なお、設定次第で実行速度が向上する場合があります。
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
htmlのヘッダに上記のように設定することができます。
initial-scaleはデフォルトの拡大率です。
user-scalableはユーザーに拡縮を許可するかです。
参考：http://www.minimo.jp/?p=308
リサイズ
スマートフォンでは、デフォルトで設定した解像度を下回る場合があります。
また、タブレット端末では全面に拡大して用いたい場合があります。
下記のように、canvasの大きさを100%に設定することで実現できます。
<head> <style type="text/css"> #imgCanvas { width:100%; height:100% } </script> </head> // hoge hoge <canvas id="imgCanvas" width="640" height="480" style="border:1px black solid;" />
また、ブラウザ情報やスクリーンサイズから判断して拡大縮小を行うのもよいでしょう。
if( document.body.clientWidth < 640 || document.body.clientHeight < 480 ) { var target = document.getElementById('imgCanvas'); target.style.width="100%"; target.style.height="100%"; }
タッチ座標とゲーム内座標
上記の項目のようにスクリーンの拡大縮小を行なっている場合があります。
そのような場合にタッチ座標とゲーム内の座標にズレが生じてしまいます。
例えば、全画面に拡大した場合は比率を補正する必要があります。
var x = e.touches[0].screenX; var y = e.touches[0].screenY; if( resize_flag ) { var w = document.body.clientWidth; var h = document.body.clientHeight; x = parseInt( 640 * (x/w) + 0.5 ); y = parseInt( 480 * (y/h) + 0.5 ); }
参考までに
以前、HTML5/Javascriptで弾幕STGを作りました。
右クリックからソースを開けば全部見られます。(jsやりたてなので結構ヒドイですが)
雲色の風
ヒューマンインタフェースとゲーム制作6 ユーザビィティテスト
開発者は自分でプレイすることは多いと思います。要するにデバッグ地獄（ｒｙ
けれども、他の人や特定のパターンのユーザにしか分からない、「つまらない部分」があるはず。
ユーザ(プレイヤー)にシステム(ゲーム)を実際にプレイしてもらい
様子を観察することで、制作物の品質の向上を図ります。
想定目的
ゲームをクリアする
ユーザが楽しむ
ステップアップする
想定ユーザ
一般的なユーザ
ターゲットユーザ
特殊なユーザ(子供など)
ユーザビリティテスト
実験者が進行を行う
観察者が記録を行う
テストの内容は以下の要因を考えておくと決めやすい
- 目的(問題発見・問題原因・比較)
- 手順(自己紹介・礼・趣旨説明・テスト) *緊張をほぐす
- データ収集方法(発話内容・操作ログ・ヒアリング・アンケート)
あるシーンについて
どんなことを考えていたとか
なぜそのような行動を取ったのか
楽しそうな顔・雰囲気がしていたか
今後に役立てる情報はいくらでも採取できるはずです。
テストの評価
- 作業負荷(疲れる)
- 覚醒度(あくびなど)
- 注意(集中力がいる)
- 疲労ストレス(めんどくさい)
- 心電図・血圧・呼吸・脳波・フリッカ
ヒューマンインタフェースとゲーム制作5 ユーザ・タスク分析
ゲームを制作する上でユーザーのことを考えるという行為は重要です。
また、ゲームにおけるタスクは適切か検証することも必要でしょう。
例えば、あのステージをこんなふうに攻略するユーザーはそんな反応を期待していて
後にこんな遊び方を提示したら喜ぶんじゃないかな。って感じで分析すると面白いかも。
ユーザの分析
ゲームを利用するユーザの特性を把握することが大切
・動機、目的、能力、経験、性格、年齢、性別、文化
・ユーザ層
・ユーザの変化
例えばこんなテーブルを作ってみると。
| 動機 | 窮屈な日常からの開放 | 非日常、強めの刺激 |
| 目的 | ストレス発散 | もっとスピード感を押し出してみる |
| 能力 | ゲーマー | ちょっぴり高めの難易度 |
| 経験 | よくゲームやる | 異色な感じを出さないと埋もれるが、質によっては王道もあり |
| 年齢 | 10代 | 難しい表現には注意が必要 |
| 性別 | 男 | 中二病 |
| 文化 | ネット | 攻略情報にあふれかえっている |
人物像をイメージするだけで色んなアイディアや対策が思い浮かんできますね。
これを複数、より多いパターンを想像することで、万人受けするヒントが得られるかもしれません。
情報が多くなってくると、今度は情報を搾り取る技術が重要になってきますね。
ユーザ層というのは、管理者/顧客/大人/子供など様々です。
ユーザの変化というのは、学習効果です。
タスクの分析
ゲームの内容にも深く直結する。
要求される機能・作業の重要度・問題点の明確化を行う。
- このステージから次のステージの難易度は妥当か。
- ゲームの流れが単調になってないか。
- ユーザに余裕がなくなってないか。
などなど
具体的には以下の点を書きだす。
- タスクの目標
- 作業内容
- 作業手順
また、書き出したら以下のように分析することができます。
| 帰納的分析 | ユーザにタスクを課して、問題点を観察。実際にやるパターン。 |
| 演繹的分析 | 構造的に解析。数式や他のパターンから追求。 |
既に存在するゲームについて分析を行ってみると面白いかもしれませんね。
特にメジャーなタイトルは洗礼されています。
ジャンプを覚えさせる
攻撃を覚えさせる
防御を覚えさせる
特に最初の段階では、注意して対策を立てなくてはいけません。
ヒューマンインタフェースとゲーム制作4 アイコンの設計
プレイヤーアイコン・武器アイコン・メニューアイコン・敵アイコンなどなど
アイコンってやつはいろんな所で使われているんです。
ただカッコイイだけではなくて適切な設計を行えるようにしたいものです。
アイコン(イメージ)の性質
- 言語より学習・記憶が容易
- 国際性がある(万人に伝わりやすい)
- 機能や状態を表現できる
- 情報が多くて多義的になりやすい(不要な意味まで持ってしまう)
辞書アイコンがあったとして、読むことができるのか、武器として装備することが（ｒｙ
xは閉じるなのか、掛け算なのか、禁止なのか（ｒｙ
アイコンの種類
- 対象アイコン：作業の対象を表す。♂♀、eはIE起動のアイコン
- 操作アイコン：操作を表す。マウスポインタ
- 状態アイコン：状態の"変化"を示す。ゴミ箱、クエストの進捗で色が変わるアイコン
- 例示アイコン：意味のある関連のある図
- 約束アイコン：意味的根拠がない図。PSPの○×△□
状態アイコンで時間とか進捗とかを、なんとなくとか雰囲気でとか伝えるのに便利。
約束アイコンは意味ないものだけど、xで閉じるとか、+で加算とか使い古されたものは、むしろ分かりやすい。
アイコンの認知
- デスクトップメタファ
PCの操作をデスクの操作に見立てた。
メモ帳・フォルダなどなど
