いろいろがんばりたいブログ

情報科学科の人がいろいろ書きます。

引越し

自前のブログシステムを構築した(してる)ので引越し

まだRSSがないので不便かもしれないけど、そのうち。

http://pushl.net/blog/

ねむれないのでブログシステムについて考える

適当なブログシステムをでっちあげようかな。 外部システムに依存しないものをつくりたいものだ。 理想は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とかも同様にいけるんじゃないかなー

ハードウェア

とりあえず書きこみに自分が使っているものは以下

f:id:tomoki_imai:20140616133034j:plain

f:id:tomoki_imai:20140615232937j:plain

ソフトウェア

パッケージ

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>