ねむれないのでブログシステムについて考える
適当なブログシステムをでっちあげようかな。 外部システムに依存しないものをつくりたいものだ。 理想はkinabaさんのブログ ( http://kmonos.net/wlog/134 )
何が必須だろうか。
- 前,後のページ
……だけ?もしかしたらこれだけなのか。
SRM 626 練習
そろそろICPCなので競技に復帰してみたり。 AOJとかちょろっとやって、明日はTopCoderだったりするので前回のSRMのeasyを解いてみた
157.19 / 250 pts まぁまぁかな。割とさくっと解けた気分でいたけど大分かかってる気もする。 同じチームの人に勝っていたから良いとしよう。 どうやったかというと、スコア全ての確率を計算してから適当にやる。
O(aba + cdc)くらい?
// 157.19 / 250 pts. const double not_calc = -1; double prob(int k,int want,vector<vector<double>>& memo,const int n){ if(want < 0) return 0; if(k == 0){ return want == 0; } if(memo[k][want] != not_calc){ return memo[k][want]; } double ret = 0; for(int i=1;i<=n;i++){ ret += prob(k-1,want-i,memo,n); } ret /= n; return memo[k][want] = ret; } class FixedDiceGameDiv1{ public: double getExpectation(int a, int b, int c, int d){ if(a*b <= c) return -1; vector<double> alice(a*b+1); { vector<vector<double>> memo(a+1,vector<double>(a*b+1,not_calc)); for(int i=0;i<alice.size();i++){ alice[i] = prob(a,i,memo,b); } } vector<double> bob(c*d+1); { vector<vector<double>> memo(c+1,vector<double>(c*d+1,not_calc)); for(int i=0;i<bob.size();i++){ bob[i] = prob(c,i,memo,d); } } vector<double> sum_bob(bob.size()+1); for(int i=1;i<sum_bob.size();i++){ sum_bob[i] = sum_bob[i-1] + bob[i-1]; } while(sum_bob.size() <= alice.size()){ sum_bob.push_back(1); } double ret = 0; double prob_of_win = 0; for(int a=1;a<alice.size();a++){ prob_of_win += alice[a] * (sum_bob[a]); ret += a*alice[a]*sum_bob[a]; } ret /= prob_of_win; return ret; } };
ArchLinuxでAVRを開発しようとしてみるメモ
ArchLinuxでAVR(ここではATMEGA328P)で遊ぶメモ たぶんUbuntuとかも同様にいけるんじゃないかなー
ハードウェア
とりあえず書きこみに自分が使っているものは以下
- AVRISP mkII (http://akizukidenshi.com/catalog/g/gM-02582/)
- 自作の書きこみ簡単にするやつ (とりあえずは必要ない)
ソフトウェア
パッケージ
ArchLinuxでは全て公式レポジトリから手に入る
udev
もしかしたら必要ないのかもしれない。 /etc/udev/rules.d に以下のファイルを 60-avrisp.rules としてコピーする。
SUBSYSTEM!="usb_device", ACTION!="add", GOTO="avrisp_end" # Atmel Corp. JTAG ICE mkII ATTR{idVendor}=="03eb", ATTR{idProduct}=="2103", MODE="660", GROUP="dialout" # Atmel Corp. AVRISP mkII ATTR{idVendor}=="03eb", ATTR{idProduct}=="2104", MODE="660", GROUP="dialout" # Atmel Corp. Dragon ATTR{idVendor}=="03eb", ATTR{idProduct}=="2107", MODE="660", GROUP="dialout" LABEL="avrisp_end"
一応再起動する。
繋げる
以下を参考にして繋げる。
http://allaboutee.com/2011/05/11/how-to-program-an-avr-microcontroller/
はやい話がATMEGA328P側のピンとAVRISP mkIIのピンを一緒のとこにすれば良い。 あと、AVRISP mkIIは電源を供給してくれないので、外部の電源を用意する。これもVCC,GNDに(並列に)つなければ良い。 自分の場合はmini USBから取れるようにした。
AVRISP mkIIを"最後に"回路、もしくはUSBにつなげること。mini USBを後にやるとオレンジが点滅した。
書きこみ
どうやらelfを出力した後に何かをやらなきゃいけないらしい。
main.cは以下のもので試してみた
#include <avr/io.h> int main(){ while(1){ } return 0; }
$ avr-gcc -mmcu=atmega328p main.c $ avr-objcopy -O ihex a.out a.hex $ sudo avrdude -c avrispmkII -p m328p -P usb -U flash:w:a.hex:a
Permission deniedとかいわれたらsudoをつけてみる。 avr-objcopyに-R .eepromとかしたほうがちいさくなってよいのかも?
TCO 2014 R1
ほとんど時間をとってないので、適当なコードを投げていた。 ビーム幅3と書いてある時点でお察し
// compile in C++11. use -std=c++11. #include <iostream> #include <iomanip> #include <vector> #include <valarray> #include <map> #include <set> #include <list> #include <queue> #include <stack> #include <bitset> #include <utility> #include <numeric> #include <algorithm> #include <functional> #include <complex> #include <string> #include <sstream> #include <chrono> #include <cstdio> #include <cstdlib> #include <cctype> #include <cstring> // this require C++11 #include <unordered_set> #include <unordered_map> #include <random> using namespace std; #define all(c) c.begin(),c.end() #define repeat(i,n) for(int i=0;i<static_cast<int>(n);i++) #define debug(x) #x << "=" << (x) #define dump(x) cerr << debug(x) << " (L:" << __LINE__ << ")"<< endl using ll = long long; using vi = vector<int>; ostream& operator<<(ostream& os,const vector<string>& vec){ for(const auto& v : vec){ os << v << endl; } return os; } template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; } struct State{ vector<string> board; double score; vector<int> proc; int cur; int a; State(vector<string> board_,double score_,vector<int> proc_,int cur_,int a_) : board(board_),score(score_),proc(proc_),cur(cur_),a(a_) {} }; bool operator<(const State& left,const State& right){ return left.score < right.score; } bool operator>(const State& left,const State& right){ return left.score > right.score; } // color is in [4,6] // N is in [8,16] // startSeed is in [1,2147483647]. // each value is uniformly random. // 0 -- up, 1 -- right, 2 -- down, 3 -- left. const array<int,4> dy = {-1,0,1,0}; const array<int,4> dx = {0,1,0,-1}; const array<int,8> ddy = {-1, 0, 1, -1 , 1, -1, 0, 1}; const array<int,8> ddx = {-1,-1,-1, 0 , 0, 1, 1, 1}; const int TURN = 10000; struct SquareRemover{ vector<int> playIt(int colors,vector<string> board,int startSeed){ ios::sync_with_stdio(false); cin.tie(0); const int N = board.size(); vector<State> cur; cur.push_back(State(board,make_score(board,0),vector<int>(),0,startSeed)); // auto begin = std::chrono::system_clock::now(); int ran_num = 15; const int beam_width = 4; repeat(beam,TURN){ // if(beam == 1){ // begin = std::chrono::system_clock::now(); // } // dump(beam); // priority_queue<State,vector<State>,less<State>> queue; priority_queue<State,vector<State>,greater<State>> queue; for(const State& st : cur){ repeat(ran,ran_num){ // dump(ran); // int row = row_col(mt); // int col = row_col(mt); // int d = dist_d(mt); int row = xor128()%N; int col = xor128()%N; int d = xor128()%4; if(d == 0 and row == 0) continue; if(d == 2 and row == N-1) continue; if(d == 1 and col == N-1) continue; if(d == 3 and col == 0) continue; vector<string> buf = st.board; const int cr = row+dy[d]; const int cc = col+dx[d]; if(buf[row][col] == buf[cr][cc]) continue; swap(buf[row][col],buf[cr][cc]); vector<int> proc = st.proc; proc.push_back(row); proc.push_back(col); proc.push_back(d); int a = st.a; int sc = st.cur; while(true){ repeat(r,N-1){ repeat(c,N-1){ if(buf[r][c] == buf[r+1][c] and buf[r][c] == buf[r][c+1] and buf[r][c] == buf[r+1][c+1]){ buf[r][c] = '0'+(a%colors); a = nextA(a); buf[r][c+1] = '0'+(a%colors); a = nextA(a); buf[r+1][c] = '0'+(a%colors); a = nextA(a); buf[r+1][c+1] = '0'+(a%colors); a = nextA(a); sc++; goto found; } } } break; found: continue; } const double curscore = make_score(buf,sc); queue.push(State(buf,curscore,proc,sc,a)); if(queue.size() > beam_width) queue.pop(); } } vector<State> next; while(not queue.empty()){ next.push_back(queue.top()); queue.pop(); } cur = next; } // dump(cur.front().cur); return cur.front().proc; } inline int nextA(int prev){ return (prev * 48271ll) % 2147483647; } inline unsigned long xor128(){ static unsigned long x=123456789,y=362436069,z=521288629,w=88675123; unsigned long t; t=(x^(x<<11));x=y;y=z;z=w; return( w=(w^(w>>19))^(t^(t>>8)) ); } inline double make_score(const vector<string>& sc,int cur){ int N = sc.size(); double ret = 0; repeat(row,N){ repeat(col,N){ repeat(i,8){ int cr = row+ddy[i]; int cc = col+ddx[i]; if(cr < 0 or cr >= N or cc < 0 or cc >= N) continue; if(sc[row][col] == sc[cr][cc]){ ret += 1.0/10; } } } } return ret+cur; } }; int main(){ ios::sync_with_stdio(false); cin.tie(0); auto const begin = std::chrono::system_clock::now(); int colors;cin >> colors; int N;cin >> N; vector<string> board(N); repeat(i,N){ cin >> board[i]; } int startSeed;cin >> startSeed; SquareRemover sr; vector<int> ret = sr.playIt(colors,board,startSeed); auto const end = std::chrono::system_clock::now(); cerr << std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count() << endl; for(int r : ret){ cout << r << endl; } return 0; }
Mendeleyにvimperatorから追加する。
http://www.mendeley.com/import/ ← ブックマークレットがあるので、以下のようにしてみた。
nnoremap m o javascript:document.getElementsByTagName('body')[0].appendChild(document.createElement('script')).setAttribute('src','https://www.mendeley.com/minified/bookmarklet.js'); <CR>