utsubo’s blog

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

2015年振り返り

こんな目標を立てていたらしい．
2015年の目標 - utsubo’s diary

競技プログラミング

レート等

  • SRM　(903 -> 1165)
  • Marathon Match　(? -> 864)
  • CodeForces　(1440 -> 1702)
  • CODE FESTIVAL　(138位 -> 91位)
  • CODE RUNNER　(65位 -> 46位)

目標

  • SRM Div1 入り　✕（まだだめそう）
  • オンサイト　◯（CodeFes出れて良かった）
  • 蟻本読了　✕（目標自体を忘れてた）
  • CF出る　△（5回しか出てない）

若干成長できたのかなぁ．正直，誤差の範囲だと思ってます．
達成率は40％ぐらい．

英語

目標

  • 洋書読む　✕（目標自体を忘れてた）
  • 洋楽聞く　△（聞き流しは多少）

洋楽は前よりかは聞いたから，達成率は20％ぐらい．

その他

目標

  • 何かしらで2つ以上作る　◯（まだまだな部分もあるけど）
  • ラブライブの声優に1人以上会う　✕（こんなのも立てていた）
  • 大学の特待生制度で15万貰う　△（だめです）

まずまず．

雑記
  • 某社ツアーが最高でした．ほんと感謝．
  • そろそろ分野絞ってやらないといけないと強く感じます．
  • 各方面に迷惑をかけまくった一年だった．

今年も大変お世話になりました．2016年目標に続きます．

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;
	}
};

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