utsubo’s blog

競技プログラミングとか．

ACするとLEDがピカピカ

作ったもの

AtCoderのコンテストでACするとLEDが点滅する奴を作ってみました．こんなの↓

構成

Pythonで提出状況を取ってきてパース，正誤をシリアル通信でArduinoに送っています．
ArduinoではACであれば点滅，それ以外であったら点灯するようにしました．（他の色があれば，色を状態によって変えたかったのですが，手持ちになかったので...）
f:id:utsubo_21:20151225223411p:plain

pythonはシリアル通信にpyserialとhtmlパーサーにbeautifulsoupを使用．
beautifulsoupがよく分かってないので適当．
procon_led.py · GitHub

Arduinoは基本的なコマンドのみ．
serial_test · GitHub

まとめ

PythonとArduino便利！

CODE RUNNER 予選B

予選B問題

問題はこんな感じでした．

魔法の力を、ためて戦え！「Charge And Hit」
「Charge And Hit」は3人1部屋でゲームを行います。ユーザーは入室/攻撃APIをリクエストするとシステムにより各部屋に割り振られます。部屋には10匹の敵が並んでいて、ユーザーは任意のタイミングで一番前の敵を魔法で攻撃します。攻撃によって敵に与えるダメージは「魔法をためた時間」に応じて高くなります。ただし敵の体力を超えるダメージは切り捨てられて体力と等しい値になります。部屋内で与えたダメージの合計値が大きい順に室内順位がつけられ、その室内順位に応じてスコアを得ます。ユーザーは他のユーザーより多くのダメージを与えて、スコアを多く得ることを目指します。

序盤

最初はとりあえず，3秒に1回殴るプログラムを書いて動かしながら方針を考えてました．これだけでも，最序盤は2位ぐらいまでいっててビビる．

メンテナンス前(開始1時間ぐらいでメンテナンスがあった)

Info APIからjsonを貰ってくるのに悪戦苦闘してたら時間が結構経ってしまった．
敵を倒せるなら殴るに変えてたら，一気に50位ぐらいまで落ちた．HPが高い敵を狙う人のカモになっていると気づく．

メンテナンス後

以下が最終的な方針．

1. 残りの敵の中でHPが上位30%の敵をリストに入れる
2. リスト内の敵が全て倒されていたら，上と同様にリストを更新

リスト内の敵が目の前に来た時
3.1. パワーがHPの7割を超えていたら殴る．
3.2. friendsの最大パワーが敵のHPの7割を超えていて，自分のパワーが3e7より大きければ殴る．
1~3をInfoを0.2秒ごとに貰ってきて繰返していた．

書いたコード: qb2015.py · GitHub

結果

10位 (∩´∀｀)∩ﾜｰｲ
Ranking: http://graph.coderunner.jp/max.html

初めて良い感じの順位を取れてめっちゃ嬉しい．
本戦もこの調子でいけると良いんだけどなぁ...

反省

1位の方が言っていた「必ずルーム1位なら倒す」を思い付いていれば，もう少し伸びそうだった．
「後ろに並んでるHPが高い敵を狙って目の前の敵を誰も殴らない現象」が頻発する前に上位に抜け出せたのが大きかった．

IntelliJ IDEAからSceneBuilderが開かない(Mac)

少し困ったので調べると
java - How to use the SceneBuilder with IntelliJ on Mac - Stack Overflow

IntelliJ IDEAでパスを設定
Preference -> Language & Frameworks -> JavaFX -> /Application/SceneBuilder.app

Finderから
Applications -> SceneBuilderを右クリック -> パッケージの内容を表示 --> Contents -> MacOS -> ファイル名を "SceneBuilder" から "scenebuilder-launcher.sh" に変更．

とりあえず起動した．

100問マラソン 5問目 SRM 667 Div2 Med: OrderOfOperationsDiv2

問題

http://community.topcoder.com/stat?c=problem_statement&pm=13988&rd=16547

解法

dpらしい．div2Medだし貪欲だろうと高をくくっていたら駄目でした．

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int dp[1<<21];
class OrderOfOperationsDiv2{
public:
	int minTime(vector<string> s){
		for(int i=0;i<(1<<20);i++)dp[i] = 1e9;
		vector<int> bit(s.size());
		int ok=0;
		for(int i=0;i<s.size();i++){
			int tmp = 0;
			for(int j=0;j<s[i].size();j++){
				tmp <<= 1;
				if(s[i][j] == '1')tmp += 1;
			}
			bit[i] = tmp;
			ok |= tmp;
		}
		
		dp[0] = 0;
		int n = s[0].size();
		for(int i=0;i<s.size();i++){
			for(int k=0;k<(1<<n);k++){
				if(dp[k] == 1e9)continue;
				for(int j=0;j<s.size();j++){
					int l = __builtin_popcount(~k & bit[j]);
					dp[( k | bit[j] )] = min( dp[(k | bit[j])], dp[k] + l*l );
				}
			}
		}
		
		int ret = 1e9;
		for(int i=0;i<(1<<n);i++){
			if( (i&ok) == ok){ 
				ret = min(ret,dp[i]);
			}
		}
			
		return ret;
	}
};

100問マラソン 4問目 SRM 663 Div2 Hard: CheeseRolling

100問マラソン topcoder
問題

http://community.topcoder.com/stat?c=problem_statement&pm=13919
優勝するトーナメントのパターン云々

解法

kmjpさんのを見させて頂きました．
TopCoder SRM 663 Div2 Hard CheeseRolling - kmjp's blog

#include <bits/stdc++.h>
using namespace std;

class CheeseRolling{
public:
	long long dp[16][1<<16];
	vector<long long> waysToWin(vector<string> wins){
		memset(dp,0,sizeof(dp));
		int n = wins.size();

		//一人の時に1を代入しておく
		for(int i=0;i<n;i++){
			dp[i][1<<n] = 1;
		}

		for(int mask=1;mask<1<<n;mask++){
			int bc = __builtin_popcount(mask);
			//2^i以外は必要ない
			if(bc & (bc-1) || bc == 1)continue;

			for(int mask2=mask;mask2>0;mask2=(mask2-1)&mask){
				int bc2 = __builtin_popcount(mask2);
				//部分集合を半分ずつの部分集合に分割
				if(bc*2 != bc)continue;
				int mask3 = mask ^ mask2;
				for(int x=0;x<n;x++) if(dp[x][mask2]) for(int y=0;y<n;y++) if(dp[y][mask3]){
					if(wins[y][x] == 'Y')
						dp[y][mask] += dp[x][mask2] * dp[y][mask3];
					else
						dp[x][mask] += dp[x][mask2] * dp[y][mask3];
				}
			}
			
		}

		vector<long long> ret;
		for(int i=0;i<n;i++){
			ret.push_back(dp[i][(1<<n)-1]);
		}
		return ret;
	}
};

理解は出来たが，今後活かせる程ではないのでもう少し考える．

100問マラソン 3問目 SRM 664 Div2 Hard: BearSortsDiv2

100問マラソン topcoder
問題

配列に対しマージソートを適用する．
しかし，そのマージソートは大小比較部分が間違いがあり，数字の大小関係なしに，確率で大小を判定する．
seqという配列が入力として渡されるので，先のマージソートを適用した時，その配列が1,2,...,Nとなるような確率を求め，対数を取って答えよ

制約

1 <= N <= 40

解法

大小比較するごとに50%を選ばないといけないので，大小比較関数が呼び出されるごとに0.5ずつ掛けてlogを取った．

class BearSortsDiv2 {

	public:

	vector<vector<int> > ls;
	double ret;
	bool LESS(int a,int b){
		ret *= 0.5;
		if(ls[a][b] == 1){
			return true;
		}
		else return false;
	}
	double mergeSort(int left,int right,vector<int>& T){
		if(left+1 >= right)return 0;
		int mid = (left+right) / 2;
		mergeSort(left,mid,T);
		mergeSort(mid,right,T);

		int p1 = left,p2 = mid;
		vector<int> merged;
		while(p1 < mid or p2 < right){
			if(p1 == mid){
				merged.push_back(T[p2]);
				p2 += 1;
			}else if(p2 == right){
				merged.push_back(T[p1]);
				p1 += 1;
			}else{
				if(LESS(T[p1],T[p2])){
					merged.push_back(T[p1]);
					p1 += 1;
				}else{
					merged.push_back(T[p2]);
					p2 += 1;
				}
			}
		}
		for(int i=left;i<right;i++){
			T[i] = merged[i-left];
		}
	}

	double getProbability(vector<int> seq) {
		ls.resize(seq.size()+1);
		for(int i=0;i<=seq.size();i++)ls[i].resize(seq.size()+1);

		for(int i=0;i<seq.size();i++){
			for(int j=i+1;j<seq.size();j++){
				ls[seq[i]][seq[j]] = 1;
			}
		}

		ret = 1;
		vector<int> T(seq.size());
		for(int i=0;i<seq.size();i++)
			T[i] = i + 1;

		mergeSort(0,seq.size(),T);

		return log(ret);
	}
};

system test通しておらず．

100問マラソン 2問目 SRM 665 Div2 Hard: LuckySum

100問マラソン topcoder
問題

LuckyNumberは全桁4,7で構成された数字のことを言う．LuckySumとはLuckyNumber2つの和である．
'?'または0-9で構成された文字列(note)が渡されるので，それに一致するような最小のLuckySumを求める．

制約

noteの文字数 <= 14

解法

下の桁から埋めるように全探索．写経．

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

class LuckySum {

public:
	string note;
	long long INF;
	long long solve(int n,int up,bool secondEnd) {
		if(n == -1){
			if(up == 0)return 0;
			return INF;
		}

		long long ret = INF;
		vector<int> sum;
		if(secondEnd){sum.push_back(4);sum.push_back(7);}
		else{sum.push_back(11);sum.push_back(14);sum.push_back(8);}

		for(int i=0;i<sum.size();i++){
			sum[i] += up;
			if( note[n] == '?' || (sum[i]%10+'0') == note[n]){
				ret = min(ret, solve(n-1,sum[i]/10,secondEnd) * 10 + (sum[i]-up));
				if(!secondEnd)
					ret = min(ret, solve(n-1,sum[i]/10,true) * 10 + (sum[i]-up));
			}
		}
		if(n == 0 and up > 0 and (note[0] == '1' or note[0] == '?'))
						ret = min(ret,solve(n-1,0,secondEnd) * 10 );

		return ret;
	}

	long long construct(string note) {
		this->note = note;
		INF = 1e17;
		long long res = solve(note.size()-1, 0,false);
		if(res == INF)return -1;
		return res;
	}

};

本番中は分岐を全部書こうとして無限に時間を使っていた．こういう書き方できるようになりたい．
これで間に合うのか微妙な気がしたけど間に合うらしい．