NPCA Advent Calendar 2015 12/24


今日はクリスマス・イヴですね。
だからといって特にクリスマス関係のことはありません。
他のプロ達と違って私は
実力皆無人間なので

文が稚拙なうえに内容も薄いものとなるでしょう。

eに探す素数



問題:
r進表記のeの連続する桁で、
最初に出てくるn桁の素数

(Σ{k=0}ƒ(k)とはkの値を0より始めたƒ(k)の無限和のこととする)
私の解法の主な点としては、
・整数をm進表記の各桁の配列で表す
・eをテイラー展開した式を、下記の条件を満たすƒ(k)におけるΣƒ(k)となるように変形
kが偶数ならƒ(k) > 0, kが奇数ならƒ(k) < 0, 絶対収束する

が挙げられる

1 整数を配列で

整数を result[k]*(m^k)の総和 (0 <= result[k] < m)の形で表し、resultを求める配列とする。
但し、任意の配列とそれに0を0個以上pushして得られる配列は同値とする。
通常の記法とは逆に桁が並んでいることに注意。
例:
10進法で495 ⇔ [5, 9, 4]
[0, 0, 5] ≠ [0, 0, 0, 5] (∵ 500 ≠ 5000)
[0, 0, 5] = [0, 0, 5, 0] (∵ 500 = 0500)

1.1 大小関係

先ず、末尾に0をいくらか付け足し、2数の桁数を一致させる。
その上で、末尾から各桁の大小関係を確認する。

1.2 四則演算

筆算の方式で計算。
(2数a,bの積を求める時、bの任意の桁kにおいてdp[k] = a * kとすれば、
a * kを求める回数を各々のkにおいて1回以内に抑えられる。)

1.3 インクリメント

配列の末尾から(r-1)(rは基数)と等しくないものを探し、
そこまでの(r-1)を0に変えた上で探索結果をインクリメント。
すべて(r-1)であった場合は全て0にして末尾に1を付加。

1.4 デクリメント

1.3と同様に、配列の末尾から0と等しくないものを探し、
そこまでの0を(r-1)に変えた上で探索結果をデクリメント。
但し、全て0であった場合は即ち0なので、NaNを返す。

2 eを式に表す

e = Σ{k=0} 1 / k!
これを変形し
e = Σ{k=0}ƒ(k)
但し、非負整数xにおいて
ƒ(2x) = 1 / 2x-1
ƒ(2x+1) = 1/x! – ƒ(2x)

また この式より
e = 4 – Σ{k=0} (1 / 2k-1 – 1/k!)

3 効率化

3.1

私は1で”末尾に0を付加しても同値”といいました。
しかし仕様上、そのままでは効率が悪くなるので, 適宜短くします。

3.2

私の実装では配列によって疑似的な分数を表現しています。
そのため、適切なタイミングで約分しなければなりません。
そこで、分子と分母の最大公約数を求める必要があります。
そのアルゴリズムとして、有名なユークリッドの互換法を使っています。

(桁が求まったらその分eから減じるのも手ですが、実装していません)

実装例

​
function solve(digits, radix){
	radix = parseInt(radix);
	// Invalid radix
	if(!radix){
		// default radix
		radix = 10;
	}
	digits = parseInt(digits);
	// Invalid
	if(isNaN(digits)){
		return NaN;
	}
	var forceNum = function (n){
		// Force be a number.
		if(!n)
			return 0;
		else
			return Number(n);
	};
	var bigInt = {
		wash: function (n){
			while(n.length){
				var i = n.pop();
				if(i){
					n.push(i);
					return n;
				}
			}
			n.push(0);
			return n;
		},
		incf: function (result){
			var r = result.slice();
			var s = [];
			while(r.length){
				var i = r.shift();
				if(i !== radix - 1){
					return s.concat(i + 1, r);
				}else{
					s.push(0);
				}
			}
			return s.concat(1);
		},
		decf: function (result){
			var r = result.slice();
			var s = [];
			while(r.length){
				var i = r.shift();
				if(i){
					return s.concat(i - 1, r);
				}else{
					s.push(radix - 1);
				}
			}
			return NaN;
		},
		pure: function (radix, big){
			if(!big.length){
				return 0;
			}else{
				return big[0] + radix * big.slice(1);
			}
		},
		conversion: function (radix, molecule, denomi){
			var single = function (m){
				var result = [];
				while(m){
					result.push(m % radix);
					m = Math.floor(m / radix);
				}
				if(!result.length){
					result.push(0);
				}
				return result;
			};
			var result = [];
			if(denomi){
				// denomi isn't 0, undefined, etc...
				return [single(molecule), single(denomi)];
			}else{
				// denomi is 0, undefined, etc...
				return single(molecule);
			}
		},
		comparison: function (a,b){
			var A = a.slice();
			var B = b.slice();
			var result = 0;
			single = function (x,y){
				if(x>y)
					return +1;
				else if(x<y)
					return -1;
				else
					return 0;
			};
			while(A.length || B.length){
				var i = single(
					forceNum(A.shift()),
					forceNum(B.shift())
				);
				if(i)
					result = i;
			}
			return result;
		},
		add: function (a,b){
			// a + b
			var result = [];
			var A = a.slice();
			var B = b.slice();
			var increase = 0;
			while(A.length || B.length || increase){
				var tiny = forceNum(A.shift()) + forceNum(B.shift()) + increase;
				increase = 0;
				while(tiny >= radix){
					tiny -= radix;
					increase++;
				}
				result.push(tiny);
			}
			return result;
		},
		sub: function (a,b){
			// a - b (a >= b)
			// Use comparison(a,b) before use me
			var result = [];
			var A = a.slice();
			var B = b.slice();
			var decrease = 0;
			while(A.length || B.length || decrease){
				var tiny = forceNum(A.shift());
				var parameter = forceNum(B.shift()) + decrease;
				decrease = 0;
				while(tiny < parameter){
					decrease++;
					tiny += radix;
				}
				result.push(tiny - parameter);
			}
			return result;
		},
		multi: function (a,b,m){
			// a * b
			var result = [0];
			var A = a.slice();
			var B = b.slice();
			var height = [];
			var map = (m ? m.slice() : []);
			var single = function (a,b){
				var memo = map[b];
				if(memo){
					// defined
					return memo;
				}
				var result = [];
				var A = a.slice();
				var increase = 0;
				var simple = function (a,b,i){
					var r = 0;
					var s = 0;
					while(b--){
						r += a;
						if(r >= radix){
							r -= radix;
							s++;
						}
					}
					r += i;
					if(r >= radix){
						r -= radix;
						s++;
					}
					return [r,s];
				};
				while(A.length || increase){
					var i = simple(forceNum(A.shift()), b, increase);
					result.push(i[0]);
					increase = i[1];
				}
				return map[b] = result;
			};
			while(B.length){
				result = bigInt.add(
					result, height.concat(single(A, B.shift()))
				);
				height.push(0);
			}
			return [result, map];
		},
		div: function (a,b){
			// a / b, a % b
			var A = a.slice();
			var B = b.slice();
			var result = [];
			var height = [0];
			while(bigInt.comparison(A,B) >= 0){
				height.unshift(0);
				B.unshift(0);
			}
			height.shift();
			B = height.concat(b);
			while(height.length){
				var i = bigInt.conversion(radix, 0);
				var lower, gauss = bigInt.conversion(radix, 0);
				B.shift();
				for(;;){
					lower = bigInt.multi(B,i)[0];
					if(bigInt.comparison(A, lower) < 0){
						break;
					}
					gauss = lower;
					i = bigInt.incf(i);
				}
				i = bigInt.decf(i);
				A = bigInt.sub(A, gauss);
				result.unshift(i[0]);
				height.shift();
			}
			return [result,A];
		},
		gcd: function (a,b){
			if(bigInt.conversion(a,b) < 0){
				return arguments.callee(b,a);
			}else if(!b.some(function (e){return e})){
				return a;
			}else{
				return arguments.callee(b, bigInt.wash(bigInt.div(a,b)[1]));
			}
		},
		isPrime: function (n){
			// simple test
			var i = bigInt.conversion(radix, 2);
			while(bigInt.comparison(bigInt.multi(i,i)[0], n) < 0){
				var divided = bigInt.div(n,i)[1];
				if(!bigInt.comparison(divided, bigInt.conversion(radix,0))){
					return false;
				}
				i = bigInt.incf(i);
			}
			return true;
		}
	};
	var fraction = {
		floor: function (q,h){
			var molecule = q[0].slice();
			var height = h.slice();
			while(height.some(function (e){return e})){
				molecule.unshift(0);
				height = bigInt.decf(height);
			}
			return bigInt.div(molecule, q[1])[0];
		},
		add: function (p,q){
			// a/b + c/d = (ad+bc)/bd
			var i = bigInt.multi(q[1], p[0]);
			var j = bigInt.multi(p[1], q[0]);
			var m = bigInt.add(i[0], j[0]);
			var d;
			if(i[1].length > j[1].length){
				d = bigInt.multi(q[1], p[1], i[1]);
			}else{
				d = bigInt.multi(p[1], q[1] ,j[1]);
			}
			return [m,d[0]];
		},
		sub: function (p,q){
			// a - b (a >= b)
			// a/b - c/d = (ad - bc)/bd
			var i = bigInt.multi(q[1], p[0]);
			var j = bigInt.multi(p[1], q[0]);
			var m = bigInt.sub(i[0], j[0]);
			var d;
			if(i[1].length > j[1].length){
				d = bigInt.multi(q[1], p[1], i[1]);
			}else{
				d = bigInt.multi(p[1], q[1] ,j[1]);
			}
			return [m,d[0]];
		},
		wash: function (q){
			var divisor = bigInt.gcd(q[0], q[1]);
			return [
				bigInt.wash(bigInt.div(q[0], divisor)[0]),
				bigInt.wash(bigInt.div(q[1], divisor)[0])
			];
		}
	};
	var factiorial = {
		results: (function (){
			var x = {};
			x[bigInt.conversion(radix,0)] = bigInt.conversion(radix,1);
			return x;
		})(),
		solve: function (k){
			bigInt.wash(k);
			var n = factiorial.results[k];
			console.log('fact', k);
			if(n){
				// defined
				return n;
			}else{
				var lower = arguments.callee(bigInt.decf(k));
				return factiorial.results[k] = bigInt.multi(lower, k)[0];
			}
		}
	};
	var power = {
		results: (function (){
			var x = {};
			x[bigInt.conversion(radix,0)] = bigInt.conversion(radix,1);
			return x;
		})(),
		solve: function (k){
			bigInt.wash(k);
			var n = power.results[k];
			console.log('pow', k);
			if(n){
				//defined
				return n;
			}else{
				var two = bigInt.conversion(radix, 2);
				var lower = arguments.callee(bigInt.decf(k));
				return power.results[k] = bigInt.multi(lower, two)[0];
			}
		}
	};
	var terms = {
		min_sum: bigInt.conversion(radix, 0,1), // the first term = 0
		max_sum: bigInt.conversion(radix, 4,1), // the first term = 4
		min_general: function (k){
			// 1/(k!)
			return [bigInt.conversion(radix, 1), factiorial.solve(k)];
		},
		max_general: function (k){
			// 1/(2^(k-1)) - 1/(k!)
			var i = [bigInt.conversion(radix, 2), power.solve(k)];
			var j = [bigInt.conversion(radix, 1), factiorial.solve(k)];
			return fraction.sub(i,j);
		}
	};
	function main(){
		var height = bigInt.conversion(radix,0);
		var e = [];
		var i = bigInt.conversion(radix,0);
		for(;;){
			console.log('min start');
			terms.min_sum = fraction.add(terms.min_sum, terms.min_general(i));
			console.log(terms.min_sum);
			console.log('min end');
			console.log('max start');
			terms.max_sum = fraction.sub(terms.max_sum, terms.max_general(i));
			console.log('max end');
			console.log(i);
			var tiny = fraction.floor(terms.min_sum, height);
			var ceil = fraction.floor(terms.max_sum, height);
			console.log(tiny, ceil);
			console.log(height);
			if(!bigInt.comparison(tiny, ceil)){
				terms.min_sum = fraction.wash(terms.min_sum);
				terms.max_sum = fraction.wash(terms.max_sum);
				e.unshift(tiny[0]);
				height = bigInt.incf(height);
				var E = e.slice(0,digits);
				console.log(e,E);
				if(E.length >= digits && bigInt.isPrime(E)){
					return E.reverse();
				}
			}
			i = bigInt.incf(i);
		}
	}
	return main();
}
​
var begin = new Date();
console.log(solve(10,10));
var end = new Date();
​
console.log(end - begin); // ms
​

r = 10, n = 10とし、手元の環境(Chrome 47.0.2526.106)で試した所、
8188184ms(約2時間15分)かかりました。
原因は素数判定の関数が遅いからと思われます。

素数がメインだったはずだが。

さいごに

こんな駄文におつきあい頂きまして、ありがとうございました。
取り掛かるのが遅かったせいで実装が雑で文も提出前日に書き始める始末。
こんなことにならないように、何事も余裕をもって早めに始めましょう(戒め)

GitHubは挫折しました。

さて、明日は誰が何と言おうとクリスマスですが、
日付が日付なので、こんな記事よりもよほど
秀逸な記事が現れるでしょう。

明日は最終日、担当はhideo54さんです。ご期待ください。




無題


こんにちは.NPCA Advent Calenderの記事ですが,まず,NPCAの追い出し会で行われた闇LTの話題とします.
NPCAでの「闇LT」とは,他人が製作したLT=Lightning Talkのスライドを発表することです.NPCAの追い出し会で行われたことがあります.
そして,闇LTの製作方法ですが,自分も過去に使用したLTのスライドに手を加えて闇LTとしての使用が可能なものを製作したのでそれをもとにして書きます.
元ネタのLTの1枚目,2枚目は,このようにしていました.
1枚目
2015年度 灘校パソコン研究部部内LT大会
日時 2015年7月15日
場所 灘中学校・灘高等学校 パソコン研究部 部室
発表者 灘校 (発表者氏名)
2枚目
軽く自己紹介
灘中学校(発表者の回生番号)回生 (クラス) (発表者氏名)
交通信号機等が好き
(NPCAに入部した時期) パソコン研究部入部
これについて,闇LTでは,以下のようになります.
1枚目
2015年度 フリー闇LT
日時 2015年4月1日~2016年3月31日
場所 地球
発表者 灘校○○回生 ○○
2枚目
自己紹介
灘校○○回生 ○年○組 ○○○○○○
○○○○の趣味
○○年○月 パソコン研究部入部 (○○年○月 パソコン研究部引退)
まず,タイトル変更は言うまでもないことですが,日時や場所は適当にしておけばよいでしょう.発表者ですが,この場合,部内で使用することしか考慮していないため,「灘校○○回生 ○○」としたが,部外あるいは校外で使用する可能性のある場合は,「○○ ○○」とすればよいでしょう.
2枚目ですが,自己紹介を配置する場合,発表者の属性のあいまいな部分はすべて「○○」とし,NPCAで使用する場合は「○○の趣味」とでもしておくと良いでしょう.
本題の部分は,灘校で行われた選挙を題材にしましたが,闇LTでは「仮想選挙」とし,得票率を求めるプログラムを作成したというものです.
後は,どこかに発表者を驚かせるものが必要です.先に言っておくと,NPCAなどには「プロ」と言って「趣味」と返答する文化があります.
さて,その内容は,
あなたはE月F日生まれとします
{(E+F)*(E+F)+(E+F)!+2-(E+F+1)*(E+F+2)}%3
これを計算してください
結果が1あるいは2ならば…
発表者はプロ!
結果が0ならば…
お前(発表者)はクソザコ!
さらに追い出し会向けには「プロ趣味文化からもうお別れだ!」という1文を挿入してやることも発表者を驚かせます.追い出し会では,もうすぐここを離れるんだということを何かで明示することも大切です.
内容についてですが,(E+F)!は,1月1日生まれでなければ3の倍数です.E+Fが3の倍数の場合は(E+F)*(E+F)は3の倍数になり,{(E+F)*(E+F)+(E+F)!+2}を3で割ると2余ることになるが,このとき(E+F+1)*(E+F+2)は3で割ると2余るのでそれを-してやるときれいに3の倍数ができるわけです.E+Fが3の倍数でなければ(E+F)*(E+F)は3で割って1余り,2を足すと3の倍数になります.(E+F+1)と(E+F+2)のいずれかは3の倍数ですから(E+F+1)*(E+F+2)は3の倍数です.以上より.{(E+F)*(E+F)+(E+F)!+2-(E+F+1)*(E+F+2)}%3は,E=1,F=1でなければ必ず0になるのです.そしてそこで「お前(発表者)はクソザコ!」というような,冗談のような言葉を挿入すると,面白くなります.このように計算式を使用するとより面白みが増すと思います.
最後は.「©freelance,2015」という形で締めくくって自由に使えるようにします.こうして完成です.
ありがとうございました


ElectronでTerminalっぽいウィンドウを実現しよう


どうも、競プロ一切やってないのにJOI予選をギリギリで突破してしまい蟻本とAOJを始めたHinata(ふぁぼん)です。つら。
とうとうこのAdvent Calendarも5日目になりますが技術系の記事が少ないという謎の事態になってます。NPCAの誇るプログラマsがまだ記事を書いていないというだけの話ですが。
さて、Macのターミナルって素晴らしいですよね?ですよね?あの半透明なウィンドウがたまりませんよね?自分の作ったアプリにも取り入れたいですよね?
スクリーンショット 2015-12-21 21.37.29
さて、僕はWebしかいじれません。HTMLとかCSSとかJSくらいしか書けません(書けるとは言っていない)。C++なんて書けません。Swiftなんて知りません。というわけで、Electronを使います。
npm initしてnpm install electron-prebuiltしてElectronのQuick startのコードをコピペしてきてelectron .を実行すると見知ったいつもの画面が出てくるはずです。
スクリーンショット 2015-12-21 20.44.00
とりあえず、CSSをちょっと書いて背景色を透明がかったグレーにしておきます。さらにBrowserWindowを生成するときに渡すオプションでtransparentをtrue、frameをfalseに設定しておきます。
まず、Photonを使ってタイトルバーを作ります。
Photon
スクリーンショット 2015-12-21 22.45.43
その後、信号機(もといウィンドウコントロール)を作ります。
最後にボタンを押したときにウィンドウを閉じる/最小化する/フルスクリーンモードにする処理を書き足せば終了です。
さらっと書いていますが、意外と時間がかかりました。特に信号機(赤黃緑の円形のボタン)の色と位置を再現するのにかなり時間が取られました。
他にもtitleBarStyleをhidden-insetにしてPhotonのバーと信号機を重ねあわせたりしましたが、hidden-insetにすると信号機の位置が下にずれ、タイトルバーを合わせると太くなってしまいました。タイトルバーだけではなく各種ボタンなどを置くにはちょうど良さそうです。

実装例: electron-translucent-window

結論: Photon強い
追記: 乱文失礼しました。


AdventCalendar遅延証明書


駄菓子カップラーメンを食べながら執筆しているしゅがぽよであります。

この AdventCalendar のサイト、実は12/16 23:59 (JST)迄に構築しなければならなかったはずだったのですが手こずって12/17の4時頃になってしまいました。ごめんなさい。

設定ファイル書き換え後再起動せず、NPCAの他のサイトを落としてしまいそちらの原因を総当たりしなかったせいでした。

困ったら なんでもかんでも 再起動


やめて!一撃必殺やめて!


やめて!一撃必殺やめて! – NPCA Advent Calendar 3日目

どもです。お前が担当になるんだよ^^された\のなです/
タイトルに特に意味は無いです
さて、今日で三日目になるAdventCalendarですが、後になるほど真面目な話になるわけでもなく
また@hPaProjectさんのように素晴らしい話が出来るわけでもないのでご容赦ください・・・

まぁ嘆き苦しむ事ばかり書いても仕方ないので自分が辛うじて出来そうなお話をしまっせ。

皆さんはゲームを作ろうと思った事はありますか?
ちょっとはありますよね。え?あるよね?あるって言ってよ!
しかし、そうせっかく考えたゲームがクソゲーとなってしまっては悲しい事この上ないですね。
なのでここではゲームがクソゲー化するポイントをピックアップして書いていこうと思います。

まずその①:過度な運ゲを作らない
これはほぼどのジャンルにも言えることですね。
ちなみに、攻略方法の内1つに運任せがある、ということは私はあまり悪いだとは思いません。
しかし、まともな突破方法が運ゲしかないというステージを作ってしまうことはいけないと思います(小並感)

次にその②:序盤から高難易度のものを作らない
最初から「高難易度である」と公言しているゲームの場合ではそのようなゲームが好きな人に需要があるでしょうが、
公言せず高難易度をぶっ込んでしまうとすぐ飽きられてしまうので注意しましょう。
高難易度を作りたい人はeasy/normal/hardの様に難易度を分けるのも一つの手かもしれません。
もちろんですが自分でクリアできることを確認しましょうね。

そしてその③:極端に強いキャラを出さない
RPGや格ゲーなどですね。
沢山キャラを作るほどある程度の強弱や有利不利が出るのは必然ではありますが、
ほとんどが「○○でよくね?」のようないわゆるゲームバランスの崩壊が起こらないことに注意しましょう。
正直結構難しい事だと思いますが、キャラはゲームの肝となる存在ですから頑張って調整しましょう。

とりあえず3つほど挙げてみました。(考える気が無くなってきた)
割りと基本的なことですが、いざ自分が作るとなるとなかなか気づけないことが多いと思います。
とくに製作段階で「うっはwwwこれおもしれぇwww」とか思って半分冗談で追加したものが
クソゲー化する原因となってしまうというのがよくあるので作品を冷静に見つめ直すことを忘れないようにしましょう。
それではみなさん、クソゲーにならないよう注意して良いゲーム、いっぱい作ってくださいね! (の_な)ノシ

↓どうでも良い話↓
皆さんはクリスマス、何しますか?私はポケモンでニックネーム「リアじゅう」の
大爆発しか覚えてないメレシーを大量に流す予定です。
そこそこ良い個体だと思うのでかわいがってあげてください()


JOIとは何だったのだろうか


おはようございます(書いてるの午後四時くらい)JOIで1番の問題文読み間違えて60点落として240点(B)になった宗安です。地学とか絶対社会科やろ(錯乱)

advent calendar の存在を忘れていて遅れましたごめんなさい
今日は僕が現状解ける今年のJOIの4番までの解説まがいのものを即興でしたいなーと思います。言語は一応C++です。
5番以降はやらなくても通るらしいのと僕にはできないのと尺の都合でやりません。

問題1 科目選択 (Selecting Subjects)

JOI 君は物理,化学,生物,地学,歴史,地理の 6 科目のテストを受けた. それぞれのテストは 100 点満点で採点された.
JOI 君は物理,化学,生物,地学の 4 科目から 3 科目を選択し,歴史,地理の 2 科目から 1 科目を選択する.
テストの合計点が最も高くなるように科目を選ぶとき, JOI 君の選んだ科目のテストの合計点を求めよ.

日本語が読めればできる問題ですが、僕は日本語が読めなかったのでできませんでした。

地学を社会に含めるとこうなりました。

#include<stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
int main (){
	int a[6];
	for(int i=0;i<6;i++){
		scanf("%d",&a[i]);
	}
	sort(a,a+3, greater<int>());
	sort(a+3,a+6, greater<int>());
	printf("%d\n",a[0]+a[1]+a[3]+a[4]);
	
	return 0;
}

実際には地学は理科に含まれるらしいのでこんな感じになります。

#include<stdio.h>
#include <algorithm>
#include <functional>
using namespace std;
int main (){
	int a[6];
	for(int i=0;i<6;i++){
		scanf("%d",&a[i]);
	}
	sort(a,a+2, greater<int>());
	sort(a+2,a+6, greater<int>());
	printf("%d\n",a[0]+a[2]+a[3]+a[4]);
	
	return 0;
}

それぞれの理科と社会をそれぞれソートして上位を足せば終わりです。

問題2 ゼッケンの交換 (Swapping Bibs)

JOI 高校の N 人の生徒が東西に一列に並んでいる.列の西の端から i 番目の生徒が生徒 i である.それぞれの生徒は整数が 1 つ書かれたゼッケンを付けている.
最初,生徒 i のゼッケンには整数 Ai が書かれている.
バトンが M 個あり,バトンには 1 から M までの番号が付けられている.
k = 1, 2, …, M に対し,以下の操作を行う.バトン k (2 ≦ k ≦ M) に関する操作は,バトン k – 1 に関する操作が終わってから行う.
先生がバトン k を生徒 1 に渡す.
バトンを受け取った生徒は,以下のルールに従ってバトンを渡す.
ルール:生徒 i がバトン k を受け取ったとする.
1 ≦ i ≦ N – 1 のとき: 生徒 i のゼッケンの整数を k で割った余りが,生徒 i + 1 のゼッケンの整数を k で割った余りよりも大きいとき,
生徒 i と生徒 i + 1 がゼッケンを交換し,生徒 i は生徒 i + 1 にバトンを渡す.そうでないときは,ゼッケンを交換せずに,生徒 i は生徒 i + 1 にバトンを渡す.
i = N のとき: 生徒 N はバトンを先生に渡す.
先生が生徒 N からバトン k を受け取ったら,バトン k に関する操作は終わりである.
生徒のゼッケンに最初に書かれていた整数とバトンの個数 M が与えられたとき,先生が生徒 N からバトン M を受け取った後の,それぞれの生徒のゼッケンの整数を求めるプログラムを作成せよ.

#include<stdio.h>
int main (){
	int a[100],n,m;
	scanf("%d%d\n",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		for(int j=0;j<n-1;j++){
			if(a[j]%i>a[j+1]%i){
				int c=a[j];
				a[j]=a[j+1];
				a[j+1]=c;
			}
		}
	}
	for(int i=0;i<n;i++){
		printf("%d\n",a[i]);
	}
	return 0;
}

そのまま再現すればおk。
最後の人の時は何もしないってところ以外は気を付けるところはないかと思います。

問題3 ロシアの旗 (Russian Flag)

K 理事長はロシアで開催される IOI 2016 に合わせて旗を作ることにした.K 理事長はまず倉庫から古い旗を取り出してきた.
この旗は N 行 M 列のマス目に分けられていて,それぞれのマスには白・青・赤のいずれかの色が塗られている.
K 理事長はこの旗のいくつかのマスを塗り替えてロシアの旗にしようとしている.ただし,この問題でいうロシアの旗とは以下のようなものである.
上から何行か (1 行以上) のマスが全て白で塗られている.
続く何行か (1 行以上) のマスが全て青で塗られている.
それ以外の行 (1 行以上) のマスが全て赤で塗られている.
K 理事長が古い旗をロシアの旗にするために塗り替える必要のあるマスの個数の最小値を求めよ.

#include<stdio.h>

int n/*縦*/,m/*横*/,fc[50][3]/*0white 1blue 2red But it's not evangelion*/;
int min;
int main (){
	scanf("%d%d\n",&n,&m);
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			char c;
			scanf("%c",&c);
			if(c=='W'){
				fc[i][0]++;
			}else if(c=='B'){
				fc[i][1]++;
			}else{
				fc[i][2]++;
			}
		}
		scanf("\n");
	}
	min=10000;
	for(int i=1;i<n-1;i++){
		for(int j=i+1;j<n;j++){
			int num=0;
			for(int k=0;k<n;k++){
				if(k<i)num=num+m-fc[k][0];
				else if(k<j)num=num+m-fc[k][1];
				else num=num+m-fc[k][2];
			}
			if(num<min)min=num;
		}
	}
	printf("%d\n",min);
	return 0;
}

毎回すべてのマスをあたったとしても計算量はO(mn^3)で、今回はn<=50なので間に合いますが、n<=100とかになってくるとつらいので、 僕は各行にどの色がどれだけあるかをあらかじめ調べてから全探索するというやり方をしました。O(mn+n^2)

問題4

JOI 国には東西に走る 1 本の十分に長い道路がある.JOI 国の王宮が道路沿いにあり,JOI 国における道路沿いの位置は整数 A で表される.A = 0 のときは王宮の位置を表す.
A > 0 のときは,王宮から東へ A メートル進んだ位置を表す.A < 0 のときは,王宮から西へ -A メートル進んだ位置を表す. JOI 国の道路沿いには N 軒の家があり,家には西から順に 1 から N までの番号が付けられている.JOI 国には N 人の国民がいて,国民には 1 から N までの番号が付けられている. 家 i には国民 i が住んでいる.家 i の位置は 0 でない偶数 Ai で表される.A1, ..., AN は全て異なる. JOI 国では,近年国民の運動不足が問題になっている.国民の健康が気になった JOI 国の王様は,国民全員に散歩をする命令を出した. 王様が命令を出すと,全ての国民は一斉に東向きまたは西向きに歩き始める.それぞれの国民がどちらの向きに歩き始めるかは,国民ごとに決まっている.全ての国民は,歩くときは 1 秒あたり 1 メートルの速度で歩く. JOI 国の国民は皆おしゃべりが大好きである.散歩の途中にほかの国民に出会うと,その場所で立ち止まって世間話を始めてしまう. すでに立ち止まっている国民に出会った場合も同様である. 一度立ち止まった国民は,再び歩き出すことはない. JOI 国には Q 人の重要人物がいる.JOI 国の王様は,命令が出されてから T 秒後の,Q 人の重要人物の位置を把握しておきたい. 命令が出されてから T 秒後の,Q 人の重要人物の位置を求めるプログラムを作成せよ. [code language="cpp"] #include<stdio.h> long long int a[100000]/*家*/,d[100000]/*向き*/,stop[100000][2]/*位置、時間*/; int ever[100000]; long long int n,t,q,x[100000]; int main (){ scanf("%lld%lld%lld",&n,&t,&q); for(int i=0;i<n;i++){ scanf("%lld%lld",&a[i],&d[i]); if(d[i]==2&&d[i-1]==1){ stop[i][0]=(a[i]+a[i-1])/2; stop[i][1]=(a[i]-a[i-1])/2; stop[i-1][0]=(a[i]+a[i-1])/2; stop[i-1][1]=(a[i]-a[i-1])/2; ever[i]=1; ever[i-1]=1; } } if(d[0]==2){ ever[0]=1; stop[0][1]=2000000000000000000; } if(d[n-1]==1){ ever[n-1]=1; stop[n-1][1]=2000000000000000000; } for(int i=0;i<n;i++){ if(ever[i]==0){ if(d[i]==2){ stop[i][0]=stop[i-1][0]; stop[i][1]=a[i]-stop[i-1][0]; } } } for(int i=n-1;i>=0;i--){ if(ever[i]==0){ if(d[i]==1){ stop[i][0]=stop[i+1][0]; stop[i][1]=stop[i+1][0]-a[i]; } } } for(int i=0;i<q;i++){ scanf("%lld\n",&x[i]); int p=x[i]-1; if(t<stop[p][1]){ if(d[p]==1){ printf("%lld\n",a[p]+t); } if(d[p]==2){ printf("%lld\n",a[p]-t); } }else{ printf("%lld\n",stop[p][0]); } } return 0; } [/code] これは今日完成させました。 一人一人の止まる場所と時間を出せばよいことがわかります。 まず向かい合ってる人々を止めます。 つぎに右端で右向いてる場合や左端で左向いてる場合は止まる時間を十分大きく設定しています。 つぎにまだ止まっていない右向きの人を右端から順に見ていってすぐ右側の人が止まっている場所で止めます。 左向きも同様に左端から見ていきます。 出力は見たい時間が止まる時間より大きいかどうかで場合分けしています。

まとめ(というか感想)

今年は4番がでーぺーじゃなかったのでつらかったです。
来年は1番でミスしたりしたくないので日本語が読めるようになりたいと思います。
ところで明日から冬休みとかスキー講習が始まるので皆さん宿題とか頑張ってください(適当)
クリスマスまであと7日ですね。
尺の都合で今回はここまでです(次回はありませんが)それではみなさんさようなら。


maimai Pinkが始まった話。 – NPCA Advent Calendar 1日目


どうも。魔法少女へくとぱ( @hPaProject )です。卒業生です。
受験生なのでよく死にます。
タイトルは嘘です。後輩はもっとセンスに溢れた面白いタイトルにしてくれると思います^^

今日はNPCA Advent Calendarの1日目ということで、初日に最高学年を持ってくるということはきっと無茶ぶりをしろという後輩からの熱いメッセージですね(適当

それでは今日は1日目にふさわしく(?)ゆるーい話題をば。

さてまあ皆さんがゲームとかを作るときに何を用意する必要があるかという話なんですが、

・プログラミングスキル
残念ながら私にそのスキルがありません(白目
・開発環境
各自勝手に用意して(._.)
・画像
頑張れ(丸投げポイー
・音楽
作曲スキル、むしろ下さいって感じだ

これだけだと私が何も書けないので、

・世界観とか

これについて少し話していきましょう。(そもそも世界観を作らないなら知ったこっちゃねーです)

世界観を作るにあたって大事なことは、「魅力ある世界観か」ということでは無いと私は考えています。
なぜかって?世界観というか設定とか結局は自己満だしね!自己満の結果それに共感してくれる人で好き者コミュニティが出来るのがあるべき姿だと思ってるよ私は!
まあよって「魅力ある世界観」とか自己満に完結してしまいがちなので度外視度外視(._.)(投げやり
じゃあ何が大事と考えているかというと、「矛盾ない世界観かどうか」だと思っています(世の中には設定整合性警察いっぱいいるから(._.))。
それに矛盾があったら設定を積み重ねていった時に収拾がつかなくなりがちなので土台の設定くらいは綿密に組みましょう。
どういうことを決めればいいか?まあシナリオに至る背景設定くらいは決めましょう。シナリオ作りやすいしオヌヌメb
それ以外はまあ好みですけど、私みたいな物好きは地理条件とおおまかな歴史から決めます。物好きだからね。

え?自分は物好きじゃない?
じゃあ読むなよ!設定作らないでシンプルなゲーム作っとけばいいじゃない!(逆ギレ

……はい、取り乱しました。ここは美少女JKな魔法少女へくとぱちゃんに免じて許して?(爆

お目汚し失礼しました。この辺で筆を置かせていただきます。

†今日の締めの川柳†
世界観
しっかり研究
せないかん

明日からは後輩がもっと上手くて後世国語の教科書に絶世の名作として語り継がれるような俳句を連発してくれるのでお楽しみに!

以上、NPCA Advent Calendar 1日目担当、友利奈緒みんなのお姉ちゃん保登モカ魔法少女へくとぱでした!