- リスト内包表記
- 逆順リスト
- key(ソート基準)を指定したソート
N = int(raw_input())
wd = [raw_input() for line in range(N)]
wd = sorted(wd, key = lambda x : x[::-1])
for w in wd:
print w
Search on the blog
2012年5月28日月曜日
AtCoder Regular Contest #003 B: さかさま辞書
調子に乗ってもう一問解きました。pythonっぽいことをいろいろやってみました。
AtCoder Regular Contest #003 A: GPA計算
AtCoderの問題を解きました。なかなかいいですね。AtCoder。日本語だし、日本人にやさしい時間に開催されるし、いろいろな言語が使えるし。
def f(x):
if x == 'F':
return 0
return 4-ord(x)+ord('A')
N = int(raw_input())
str = raw_input()
p = map(lambda x : f(x), str)
p = 1.0 * reduce(lambda a, b : a+b, p) / N
print p
2012年5月26日土曜日
Google Code Jam 2012 Round2
Round2があった。通過するのはおそらく無理かなと思ったのでTシャツ狙いだった。最近PC+OS+開発環境を変えたので、あたふたしてグダグダな感じになるかなーとか思ってたけど、意外とスムーズに新しい環境を使いこなせたのでよかった。順位はぎりぎりTシャツに届かず。残念。ほんとぎりぎり。惜しい！
A. Swinging Wild
ターザンごっこ。つたを使って向こう側にいる彼女に逢いにいく。これは、問題文が長い。意味が分かればただのDP。英語が普通に読める自分に有利な問題だったと思う。
B. Aerobics
とりあえずsmallを乱択で解いた。この時点で77位！！これはもしかしたら通過できるのでは、とか考える。C.D.考えた後戻ってきて、large用の改良バージョン乱択を書く。十分広いんだしこれでいけるだろうと思ってやってみたけどTLE。
C. Mountain View
2のべき乗を並べてすべてのpermutationを見れば、small解けるんじゃないか。と直感的に（まったく根拠なしに）考えて実装した。サンプルすら通らない。ダメだ。1,2,3,..,Nとかにして同じことをやってみたらsampleは通ったけど、WAだった。
D. Descending in the Dark
B.解いたあとDに行った。smallは点数が低かったので完全にsmall狙い。全探索で解けそうな感じもしたけど、実装がややこしそうだったのでC.に行った。
総評
自分にしては上出来だったと思う。昨年は2000位くらいで今年は1000位くらいまであがったので、一年間の練習の成果が確認できてよかった。この調子で日々コツコツと練習を続けていこうと思う。
2012年5月13日日曜日
TCO2012 Round2B 300 BlurredDartboard
問題概要
ダーツの天才がダーツをする。彼の命中率は百発百中、狙った的には必ずあてる。しかし的が汚れていて何点か分からない的がいくつかある。ダーツの的はN個の領域に分かれていてそれぞれ1,2,3, ..., N点のどれかである。最適な戦略で点数を取っていたとき必ずP点を超えるのに必要な最小の手数はいくつか？
方針
単純に考えると、以下の3通りを考えればよさそう。
- 点数が見えている的のうち一番高いところだけを射抜いていく
- 点数が見えていないところを使う
- 点数が見えている的のうち一番高いところ+見えていないところを使う
見えないところを狙う時、例えば見えていない的が10個あったとする。その中で1つの的に絞って打ちまくったとする。もし、そこが見えていない的のうち点数が最小だった場合多くの手数が必要となるので、異なる場所を狙った方がいいことになる。あくまでも最悪の場合でも確実にP点超える最小の手数を考えているので、最悪の場合どうなるかという思考でいく。
3.について考えてみる。3は、点数最高の場所を狙う的集合に加えると、見えていない場所の点数の平均値があがる場合に有効な戦略だが、そもそもそんな場合は、1.の戦略をとったほうがお得なので、3.は考える必要がないことが分かる。
3.について考えてみる。3は、点数最高の場所を狙う的集合に加えると、見えていない場所の点数の平均値があがる場合に有効な戦略だが、そもそもそんな場合は、1.の戦略をとったほうがお得なので、3.は考える必要がないことが分かる。
ソースコード
本番書いたソースは酷過ぎた。考えを整理して書き直してみた。
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
class BlurredDartboard {
public:
int minThrows(vector<int> points, int P) {
int ret = 1<<30;
int N = points.size();
// use the highest point visible
int maxv = *max_element(points.begin(), points.end());
if (maxv)
ret = (P+maxv-1)/maxv;
// use invisible points
bool visible[64] = {0};
REP(i, N)
if (points[i])
visible[points[i]] = 1;
vector<int> unvisible;
FOR (i, 1, N+1)
if (!visible[i])
unvisible.push_back(i);
int sum = accumulate(unvisible.begin(), unvisible.end(), 0);
int m = unvisible.size();
if (sum) {
int x = P/sum*m;
P %= sum;
// use the highest point for the points remained
if (maxv)
ret = min(ret, x+(P+maxv-1)/maxv);
// use invisible points for the points remained
int cnt = 0;
while (P > 0)
P -= unvisible[cnt++];
ret = min(ret, x + cnt);
}
return ret;
}
};
2012年5月11日金曜日
はじめての自己書き換えコード
アセンブリで自己書き換えコードを書いてみました。windowsのコマンドプロンプトでdebugと打つとでてくる例のあれです。A xxxでセグメントベース + xxxのアドレスに命令を書くことができます。メモリに命令を直で打ち込むのでノイマン型コンピュータの特徴を身をもって体験できます。
U xxxでオフセットアドレスに格納されている機械語を逆アセンブルすることができるので、これを利用して簡単な自己書き換えコードを書いてみました。
まず、メインの処理。
U xxxでオフセットアドレスに格納されている機械語を逆アセンブルすることができるので、これを利用して簡単な自己書き換えコードを書いてみました。
まず、メインの処理。
-A 100
1857:0100 MOV AX, 00FF
1857:0103 MOV DX, 0001
1857:0106 CALL 200
1857:0109
1857:0100 MOV AX, 00FF
1857:0103 MOV DX, 0001
1857:0106 CALL 200
1857:0109
アキュミュレータに00FF、データレジスタに0001をロードして、オフセットアドレス200に記述されたサブルーチンを呼び出します。オフセットアドレス200には加算を行う関数を記述します。
-A 200
1857:0200 ADD AX, DX
1857:0202 RET
1857:0203
足算を引算に書き換えます。203番に引算処理を書いてみて対応する機械語を調べてみます。
-A 203
1857:0203 SUB AX, DX
1857:0205
-U 203 203
1857:0203 29D0 SUB AX,DX
足算の機械語も見ます。
-U 200 200
1857:0200 01D0 ADD AX,DX
オフセットアドレス200を29に書きかえれば、ADDがSUBになるみたいです。ということで、オフセットアドレス200の処理を以下のように書きなおします。
-A 200
1857:0200 ADD AX, DX
1857:0202 MOV BYTE PTR [200], 29
1857:0207 RET
1857:0208
これで、足算をしたあと自分自身の処理が書かれた命令を書きなおし、引算をする関数へと変わるはずです。
以下実行結果。
-G = 100 109
AX=0100 BX=0000 CX=0000 DX=0001 SP=FFEE BP=0000 SI=0000 DI=0000
DS=1857 ES=1857 SS=1857 CS=1857 IP=0109 NV UP EI PL NZ AC PE NC
1857:0109 0000 ADD [BX+SI],AL DS:0000=CD
-G = 100 109
AX=00FE BX=0000 CX=0000 DX=0001 SP=FFEE BP=0000 SI=0000 DI=0000
DS=1857 ES=1857 SS=1857 CS=1857 IP=0109 NV UP EI PL NZ NA PO NC
1857:0109 0000 ADD [BX+SI],AL DS:0000=CD
一回目の呼び出しでは足算が行われています。二回目の呼び出しでは思惑どおり引算が行われます。
読書「1Q84 BOOK2,3,4」
1Q84のBOOK2,3,4を読みました。最近本を読むスピードがあがってきた気がします。BOOK1はハードボイルドな感じでしたが、BOOK3あたりからファンタジーっぽくなってきました。BOOK4で終わりかなと思いましたが、BOOK5, 6へと続くらしいです。
BOOK4の天吾が自分の人生を昏睡状態の父親に語るシーン、青豆が首都高速道路で拳銃を自分の口の中に入れ自殺しようとするシーンは強烈でした。暗くて憂鬱な世界に惹きこまれました。そして「空気さなぎ」の内容、ふかえりがコミューンで体験したこと、青豆が暗殺したさきがけのリーダー、といろいろな物事がひとつに繋がりました。BOOK4まででおなかいっぱいな感じです。あと2巻も続くなんて信じられません。
気になることと言えば、戎野先生と小松の所在。この二人は無事なのか？それと細かいところですが、天吾がふかえりに書き直した「空気さなぎ」を見せたときにふかえりが言った「まるでわたしが書いたみたい。」これは何を意味しているんだろう。何か意味深な発言だった気がする（特に意味はないかもしれませんが。）そして青豆はどうなったのか。空気さなぎの中に入っていたけど、死んでしまったのか？レシヴァとなった天吾はどうなるのか？んー、考えてみるとまだまだ新しい展開がありそうです。
BOOK4の天吾が自分の人生を昏睡状態の父親に語るシーン、青豆が首都高速道路で拳銃を自分の口の中に入れ自殺しようとするシーンは強烈でした。暗くて憂鬱な世界に惹きこまれました。そして「空気さなぎ」の内容、ふかえりがコミューンで体験したこと、青豆が暗殺したさきがけのリーダー、といろいろな物事がひとつに繋がりました。BOOK4まででおなかいっぱいな感じです。あと2巻も続くなんて信じられません。
気になることと言えば、戎野先生と小松の所在。この二人は無事なのか？それと細かいところですが、天吾がふかえりに書き直した「空気さなぎ」を見せたときにふかえりが言った「まるでわたしが書いたみたい。」これは何を意味しているんだろう。何か意味深な発言だった気がする（特に意味はないかもしれませんが。）そして青豆はどうなったのか。空気さなぎの中に入っていたけど、死んでしまったのか？レシヴァとなった天吾はどうなるのか？んー、考えてみるとまだまだ新しい展開がありそうです。
2012年5月9日水曜日
アセンブリでユークリッドの互除法
MS-DOSのアセンブリでユークリッドの互除法を書いてみました。アキュムレータとデータレジスタに正の整数（１バイトに収まる範囲）をロードして実行するとアキュムレータに最大公約数が出力されます。
-A 100
1857:0100 DIV DL
1857:0102 MOV AL, DL
1857:0104 MOV DL, AH
1857:0106 MOV AH, 0
1857:0108 CMP DL, 0
1857:010B JA 100
1857:010D
1857:0100 DIV DL
1857:0102 MOV AL, DL
1857:0104 MOV DL, AH
1857:0106 MOV AH, 0
1857:0108 CMP DL, 0
1857:010B JA 100
1857:010D
2012年5月8日火曜日
Google Code Jam 2012 1B Equal Sums
問題
N個の要素をもつ正の整数の集合S := {S1, S2, ... SN}が与えられる。Sの異なる任意の２つの部分集合TとUを考える。Tの要素の総和とUの要素の総和が同じになる場合、T、Uの要素を出力せよ。そのようなTとUが作れない場合は、"impossible"と出力せよ。
方針
smallは、N=20でSの要素が105程度だったから、DPで解いた。largeは、N=500でSの要素が最大で1012だったので、DPでは無理。乱択アルゴリズムを使ってる人が多かった。
N=500だけど、最初の50個だけ見る。このとき作れる部分集合の個数は250 > 500 * 10 12なので、鳩ノ巣原理から確実に衝突するペアが存在する。仮に106個部分集合を作ったとすると、部分集合からペア２つを選ぶ選び方は、1012/2通り、一つのペアにおいて衝突が起こる確率は低く見積もっても1/1012なので、106個の部分集合のなかで衝突するようなペアの数の期待値は、1012/2 * 1/1012でほぼ1くらいのオーダーになる。ということで適当に部分集合を生成してその和をmapで管理していれば100万個くらいループまわせばそのうち衝突するでしょう。という方針でいく。
ソースコード
setやmapは要素数が100万くらいになると急激に遅くなる場合があるので、今回のようなケースではハッシュを使ったmapを使った方がいいと思います。以下では、boostのunordered_mapを使って実装しています。
using namespace std;
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
int N;
long long x[500];
void printNums(unsigned long long use) {
bool fst = true;
REP (i, N) {
if (use & 1LL << i) {
if (fst)
fst = false;
else
cout << " ";
cout << x[i];
}
}
cout << endl;
}
void solve() {
unsigned long long use = 0;
boost::unordered_map<long long, unsigned long long> vis;
N = min(N, 50);
unsigned long long use2 = 0;
for (;;) {
use = use * 23 + 17542197;
long long sum = 0;
REP(i, N) if (use & 1LL<<i) sum += x[i];
if (sum && vis.count(sum)) {
use2 = vis[sum];
break;
}
vis[sum] = use;
}
printNums(use);
printNums(use2);
}
#define SUBMIT
int main() {
#ifdef SUBMIT
freopen("./test.in", "r", stdin);
freopen("./test.out", "w", stdout);
#endif
int T;
cin >> T;
REP(t, T) {
cout << "Case #" << t+1 << ":" << endl;
cerr << "Case #" << t+1 << ":" << endl;
cin >> N;
REP(i, N) cin >> x[i];
solve();
}
#ifdef SUBMIT
fflush(stdout);
cerr << "all done!" << endl;
#endif
return 0;
}
2012年5月6日日曜日
Google Code Jam 2012 1B Tide Goes In, Tide Goes Out
参加録
今年はCode Jam参加しない予定でした。予選のとき旅行に行っていたので。しかしホテルでネットが使えるand友人がPC持ってきていたおかげで予選に参加できました。なんとか予選を通過しRound 1です。Round 1Aは解けた問題数的にはよかったのですが、バグにはまり時間的なペナルティで通過できませんでした。Round 1Bは2small、1large解いて何とか通過できました！去年は1Cでの通過だったので、この一年間の成長が確認できました。
問題概要
で、タイトルにある問題です。地下の洞窟でカヤックをしています。潮が満ちてきて閉じ込められました。しばらくすると潮が引き始めるので、潮が引き始めてから移動した場合、最短で何秒で洞窟の外にでれるでしょうか？洞窟の状態は地図で与えられます。
方針
現地点からゴールまでの最短パスを求める。条件が少し複雑なので注意。あと小数の演算があるので丸め誤差にも注意。
反省
「ある潮の高さにおいてある地点から別の地点に移動できるかどうか」という思考パターンでいったのが、実装を困難にした原因。移動している時間の間に潮の高さ変わってしまうので、状態数が（現在の潮の高さ、現在の場所）みたいな感じになって、これTLE厳しくないかとか思って変なDP書いたりしてた。まず最初にある時刻にある地点から別の地点に移動できるかを２つの条件に分割するべきだった。
- 潮が引いてしまったときにその移動は可能か？
- 1.が可能なら潮が少なくともどこまで引けばいいのか？
1. は時間に依存しない静的な条件です。２つのセルの形状に応じて一意に決まります。そして1.が可能だったときに、2.の時間を計算します。ある時刻tにおいて(x1, y1)から(x2, y2)に移動可能なとき、時刻u >= tにおいても移動可能となるので、そもそも状態数の中に潮の高さとかいらなかった。。うーん多分問題をきちんと把握できていなかったのだろうか。Sample Caseの下にある説明をちゃんと読んで紙と鉛筆をつかってシミュレーションしてみるべきだった。時間には余裕があったのだから。
練習でACしたソースコード
#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
typedef pair<double, pair<int, int> > Pr;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const double INF = 1e100;
const double EPS = 1e-4;
int H, N, M;
int clg[128][128];
int flr[128][128];
double dist[128][128];
double enterTime(int x1, int y1, int x2, int y2) {
if (flr[x1][y1] > clg[x2][y2]-50)
return INF;
if (flr[x2][y2] > clg[x2][y2]-50)
return INF;
if (flr[x2][y2] > clg[x1][y1]-50)
return INF;
if (H <= clg[x2][y2]-50)
return 0;
return (H - (clg[x2][y2]-50)) / 10.0;
}
double solve() {
REP(i, N) REP(j, M) dist[i][j] = INF;
priority_queue<Pr, vector<Pr>, greater<Pr> > Q;
Q.push(make_pair(0, make_pair(0, 0)));
dist[0][0] = 0;
while (!Q.empty()) {
double t = Q.top().first;
int x = Q.top().second.first;
int y = Q.top().second.second;
Q.pop();
if (t > dist[x][y])
continue;
if (x == N-1 && y == M-1)
break;
REP(k, 4) {
int xx = x + dx[k];
int yy = y + dy[k];
if (xx < 0 || xx > N-1 || yy < 0 || yy > M-1)
continue;
double u = max(t, enterTime(x, y, xx, yy));
if (u == 0.0)
;
else if (H-10*u-flr[x][y] + EPS >= 20)
u += 1.0;
else
u += 10.0;
if (u < dist[xx][yy]) {
dist[xx][yy] = u;
Q.push(make_pair(u, make_pair(xx, yy)));
}
}
}
return dist[N-1][M-1];
}
#define SUBMIT
int main() {
#ifdef SUBMIT
freopen("./test.in", "r", stdin);
freopen("./test.out", "w", stdout);
#endif
int T;
cin >> T;
REP(t, T) {
cerr << "solving #" << t+1 << "..." << endl;
cin >> H >> N >> M;
REP(i, N) REP(j, M) cin >> clg[i][j];
REP(i, N) REP(j, M) cin >> flr[i][j];
double ret = solve();
printf("Case #%d: %.16lf\n", t+1,ret);
}
#ifdef SUBMIT
fflush(stdout);
cerr << "all done!" << endl;
#endif
return 0;
}
2012年5月3日木曜日
正四面体の頂点をN色で塗るパターン
問題
N色のペンを使って、正四面体の頂点を塗ろうとしています。塗り方のパターンは何通りあるでしょうか？ただし、回転して同じものは同一と考えます。
アプローチ
対称性のあるものを塗るので、ポリアの数え上げを使います。対称性には主に２つがあります。
- rotation
- reflection
正四面体に対する回転操作全体を群で表し、それぞれの要素において不変なカラーリングパターンの平均値を求めてあげれば、欲しい値がえられます。ある写像において不変なカラーリングの集合は、その写像の軌道の数に等しいです。（この辺りの証明とかより詳細な背景は組み合わせ数学の本に載ってます。）
あとは、群の要素をどうやってもってくるか。。頂点の数は4つなので、すべての対称群を列挙したとしても4!=24個でそこから回転操作になっているものだけをがんばって抽出してもいいです。しかしWikipedia情報によると、正四面体の回転操作を表す群はalternating subgroupと同一らしいので、偶順列のみをとってくればOKということになります。
ソースコード
N=1のとき1、N=2のとき5、N=3のときは15らしいです。
bool isEvenPermutation(vector<int> v) {
int exchange = 0;
for (int i = 0; i < (int)v.size(); i++) {
if (v[i] == i)
continue;
++exchange;
for (int j = i+1; j < (int)v.size(); j++) {
if (v[j] == i) {
swap(v[i], v[j]);
break;
}
}
}
return exchange % 2 == 0;
}
int orbitCount(vector<int> v) {
int cnt = 0;
for (int i = 0; i < (int)v.size(); i++) {
if (v[i] == -1)
continue;
++cnt;
int j = i;
while (v[j] != -1) {
int tmp = v[j];
v[j] = -1;
j = tmp;
}
}
return cnt;
}
long long power(long long x, long long y) {
long long ret = 1;
for (int i = 0; i < y; i++)
ret *= x;
return ret;
}
int main() {
long long color;
cin >> color;
vector<int> v;
for (int i = 0; i < 4; i++)
v.push_back(i);
int g = 0;
long long pattern = 0;
do {
if (isEvenPermutation(v)) {
++g;
pattern += power(color, orbitCount(v));
}
} while (next_permutation(v.begin(), v.end()));
assert(g > 0);
assert(pattern % g == 0);
cout << "Pattern: " << pattern/g << endl;
}
登録:
コメント (Atom)