2017-04-25

2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) - B: Buggy Robot ★★★☆☆

評価

良問だが若干実装疲れた.
初め, dijkstraに見えなかった.
解くのにそんなに時間がかからなかったし若干実装重いB問題かーくらいの感覚だったけど, 解いてる人数少なくて驚いた.

問題

迷路と操作列が与えられる.
操作列はUDLR(上下左右)からなる文字列である.
スタート地点にいるロボットが操作列に従って移動する.
ただし画面外に移動したりゴール後に移動したりしない.
操作列のいくつかを削除(無視)したり任意の操作を加えたりできる.
ロボットがゴールにたどり着くために操作を削除・追加する回数の最小値を求めよ.

入力例

3 3
R..
.#.
..E
LRDD

出力例

考察

dp[i][y][x] := 元の操作列[0,i)に変更を加えた操作列を実行したときに地点(x,y)に居るような変更回数の最小値
とすると,

今の操作列に従う (コスト0, (i,y,x) → (i+1, y', x'))
次の操作を無視する (コスト1, (i,y,x) → (i+1,y,x))
操作を加える (コスト1, (i,y,x) → (i+1,y,x))

の遷移がある.
(i,y,x)を頂点とするとDAGとは限らず, また, 異なるコストの辺があるのでdijkstraする.

解答

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const ll linf = 1e18;

#define FOR(i,a,b) for(ll i = (a); i < (b); ++i)
#define RFOR(i,a,b) for(ll i = (b)-1; i >= (a); --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define EACH(i,v) for(auto&& i : v)
#define ALL(v) (v).begin(),(v).end()
#define push_back pb

template<class T>
istream& operator>>(istream& is, vector<T>& v) {
    EACH(i, v) is >> i;
    return is;
}

vector<vector<vector<ll>>> dp;

struct Node {
    ll pos, x, y, cost;
};
bool operator>(const Node& n1, const Node& n2) {
    return n1.cost > n2.cost;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll h, w; cin >> h >> w;
    auto inRange = [&](ll x, ll y) {
        return 0 <= x && x < w && 0 <= y && y < h;
    };
    vector<string> m(h); cin >> m;
    string s; cin >> s;
    const ll n = s.size();
    dp.assign(n+1, vector<vector<ll>>(h, vector<ll>(w, linf)));
    priority_queue<Node, vector<Node>, greater<Node>> Q;
    ll gx, gy;
    REP(y, h) REP(x, w) {
        if (m[y][x] == 'R') {
            Q.push({0, x, y, 0});
            dp[0][y][x] = 0;
        }
        if (m[y][x] == 'E') {
            gx = x, gy = y;
        }
    }
    auto move = [&](ll x, ll y, char op) {
        if (x == gx && y == gy) return P(x, y);
        ll dx, dy;
        if (op == 'U') dx = 0, dy = -1;
        if (op == 'R') dx = 1, dy = 0;
        if (op == 'D') dx = 0, dy = 1;
        if (op == 'L') dx = -1, dy = 0;
        ll nx = x + dx, ny = y + dy;
        if ( !inRange(nx, ny) || m[ny][nx] == '#' ) return P(x, y);
        return P(nx, ny);
    };
    const string ops = "URDL";
    while ( !Q.empty() ) {
        Node node = Q.top(); Q.pop();
        ll pos = node.pos, x = node.x, y = node.y;
        ll cost = node.cost;
        if (cost > dp[pos][y][x]) continue;
        // cout << pos << " " << x << " " << y << " " << cost << " " << dp[pos][y][x] << endl;
        if (pos < n) {
            // follow
            P p = move(x, y, s[pos]);
            ll nx, ny; tie(nx, ny) = p;
            if (dp[pos][y][x] < dp[pos+1][ny][nx]) {
                dp[pos+1][ny][nx] = dp[pos][y][x];
                Q.push({pos+1, nx, ny, dp[pos+1][ny][nx]});
            }
            // ignore
            if (dp[pos+1][y][x] > dp[pos][y][x]+1) {
                dp[pos+1][y][x] = dp[pos][y][x]+1;
                Q.push({pos+1, x, y, dp[pos+1][y][x]});
            }
        }
        // give op
        EACH(op, ops) {
            P p = move(x, y, op);
            ll nx, ny; tie(nx, ny) = p;
            if (dp[pos][y][x]+1 < dp[pos][ny][nx]) {
                dp[pos][ny][nx] = dp[pos][y][x]+1;
                Q.push({pos, nx, ny, dp[pos][ny][nx]});
            }
        }
    }
    cout << dp[n][gy][gx] << endl;
}

2017-04-10

iTerm2でタブの複製をしたい

iTerm2 Mac

コマンドや移動の履歴まで複製できれば最高だが, ここではカレントディレクトリだけの複製をした. 応用すれば "新しいタブでコマンド実行" などが容易にできる.

it2_newtab.applescript

#!/usr/bin/osascript
-- Usage: oscript it2_newtab.applescript profile command
on run argv
    if length of argv < 1
        log "Usage: it2_newtab.applescript profile [command]"
        return
    end if
    tell application "iTerm2"
        tell current window
            create tab with profile (item 1 of argv)
            if length of argv >= 2 -- with command
                tell current session
                    write text (item 2 of argv)
                end tell
            end if
        end tell
    end tell
end run

$ it2_newtab.applescript "Profile Name" "Command"のように使い,

第一引数: 新しいタブで開くiTerm2のプロフィール名
第二引数(optional): 起動時に実行されるコマンド

を指定する

パスを通したりエイリアスしたりしておくと便利

~/.zshrc

alias clone='it2_newtab.applescript "In visor" "cd \"`pwd`\"; clear"'

iTerm2のショートカットキーに設定しても便利
無理矢理だが, ^C, clone[Enter] と強制的に入力させるようにした
キーコードは[Key Codes.app](https://itunes.apple.com/jp/app/key-codes/id414568915?mt=12)で調べると良い
f:id:drafear:20170410180529p:plain

AppleScriptで標準エラー出力にいい感じに表示する方法が分からなかったので, よかったら教えてくださいmm

参考にしたサイト

www.iterm2.com
developer.apple.com

2017-04-05

ラピゲ勉強会した

日常

京大マイコンクラブ (KMC)で毎年新入生向けに開催されているイベント「ラピッドコーディグ祭り」に向けてゲームを作ってみた。

ラピッドコーディグ祭りはゲームを作ったことない新入生でも上回生の手厚いサポートの下で1日で1からゲームを作ることを体験していただくイベントで、略すと「ラピゲ」になるそう。

「ゲ」ってなんだよ、って思ったら、昔は「ラピッドゲームコーディング祭り」って呼ばれていてその名残みたい。

ラピゲではrubyでSDL2のラッパであるsdl2quickを使ってゲームを作るんだけど、そこで新入生に教えるために2時間くらいかけて軽くゲームを作ってみた。

ゲーム内容はシンプルで、上から降ってくる玉が下に落ちるまでにクリックで消していくエイムゲー。

色々あって配布はできないんだけど、興味があったらKMCの新歓に来てくだされ。

f:id:drafear:20170405134357p:plain

2017-03-31

はてなブログのアイコンの画質悪くね？

自分の記事上だけでいいから、とりあえずアイコンの画質を上げたいと思って、外部のアイコンを読み込むよう、アイコンのURLを置換する処理をヘッダに加えた

Before

f:id:drafear:20170331203852p:plain:w400

After

f:id:drafear:20170331203851p:plain:w400

設定 -> [ブログタイトル] -> 設定 -> 検索エンジン最適化 -> headに要素を追加
に以下を設定(srcには画像URLを設定)

<script type="text/javascript">
window.addEventListener("DOMContentLoaded", function() {
    var icons = document.querySelectorAll(".profile-icon");
    for (var i = 0; i < icons.length; ++i) {
        if (icons[i].alt === "id:drafear") {
            icons[i].src = "http://www.paper-glasses.com/api/twipi/drafear/original";
            icons[i].style.borderRadius = "32px";
            icons[i].style.width = "64px";
            icons[i].style.height = "64px";
        }
    }
});
</script>