AOJ 2698 Wall Making Game
問題文
H * W のマス目を持つ盤面が与えられる. 盤面の各マスは初期状態で empty か marked である.
この盤面を使って以下のような2人ゲームを行う. (原文中の挿絵が分かりやすいので参照してください)
1. プレイヤーは empty であるマスを選択し, そのマスを wall にする. この時, 選択できるようマスが無い場合, そのプレイヤーの負けである.
2. wall にしたマスから四方向に wall を延伸する. この操作は wall か盤外に到達するまで行う.
2人が最適に行動したとき, どちらが勝者になるか. 1 <= H, W <= 20
解法
Grundy 数を使って解く. 同様の分裂するタイプの Grundy 数を使った問題は蟻本にも載っている(第2版 P.283).
dp[sx][sy][gx][gy] := 左上頂点座標が (sx, sy), 右下頂点座標が (gx, gy) である長方形に対する Grundy 数. としてメモ化再帰する.
O((HW)^2).
ソースコード
int H, W; vector<string> s(20); int dp[20][20][20][20]; int grundy(int sx, int sy, int gx, int gy) { if (gx < sx || gy < sy) return 0; if (dp[sx][sy][gx][gy] >= 0) return dp[sx][sy][gx][gy]; set<int> st; for (int i = sx; i <= gx; i++) { for (int j = sy; j <= gy; j++) { if (s[i][j] == '.') { st.insert(grundy(sx, sy, i - 1, j - 1) ^ grundy(i + 1, sy, gx, j - 1) ^ grundy(sx, j + 1, i - 1, gy) ^ grundy(i + 1, j + 1, gx, gy)); } } } int res = 0; while (st.find(res) != st.end()) res++; return dp[sx][sy][gx][gy] = res; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> H >> W; memset(dp, -1, sizeof(dp)); for (int i = 0; i < H; i++) cin >> s[i]; cout << (grundy(0, 0, H - 1, W - 1) ? "First" : "Second") << endl; }
AOJ 1373 Placing Medals on a Binary Tree
問題文
深さ 1e9 の完全二分木と N 枚 (N <= 5 * 1e5) のメダルが与えられ, メダルを順番に二分木のノード上に置いていく.
各メダルには正整数 x が書かれており, 深さ x を持つノードの上にしか置くことができない.
また, そのノードを根とする部分木に既にメダルが置かれているようなノードにも置いてはいけない. (すなわち, 根から各メダルへのパス上に他のメダルが存在してはいけない)
メダルを順番に置けるなら置いていく. この時, 各メダルが置けるなら YES, そうでないなら NO を出力せよ.
解法
x が書かれたメダルを2つ置く場合, (x-1) の書かれたメダルを1つ置くものと見做してもよい.
よって, 各深さ k (0<=k<=N) に対してメダルが置かれているかどうかだけを覚えておき, 新しくメダルを置く際にこれを更新していく.
既に 0 が埋まっているか, 新しいメダルを置いた時に 0 のメダルができ, かつ他のメダルが残る場合に NO を出力する.
この判定を O(1) or O(logN) で行うのがこの問題の要所. 自分は Fenwick Tree を使って sum[1, x[i]] ?= x[i] で判定した.
YES の場合は愚直に (x-1) のメダルに置き換えていけばよい. この置き換えは高々 O(N) 回しか行われないので間に合う.
N < x[i] となるような x[i] は 0 のメダル生成に関与しないので, 存在するかどうかだけ覚えておけば良い.
ソースコード
template <typename T> class FenwickTree { const int n; vector<T> data; public: FenwickTree(int _n) : n(_n), data(_n, 0) {} void add(int pos, const T &value) { for (int i = pos; i < n; i |= i + 1) data[i] += value; } T sum(int pos) const { T res = 0; for (int i = pos - 1; i >= 0; i = (i & (i + 1)) - 1) res += data[i]; return res; } T sum(int l, int r) const { return sum(r) + (-sum(l)); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; FenwickTree<int> ft(N + 1); int cnt = 0; bool zero = false; vector<int> x(N); for (int i = 0; i < N; i++) { cin >> x[i]; bool f; if (zero) { f = false; } else if (N < x[i]) { cnt++; f = true; } else if (!ft.sum(x[i], x[i] + 1)) { f = true; ft.add(x[i], 1); } else { if (ft.sum(1, x[i] + 1) == x[i] && (cnt || ft.sum(x[i] + 1, N + 1))) { f = false; } else { f = true; while (ft.sum(x[i], x[i] + 1)) { ft.add(x[i], -1); x[i]--; } ft.add(x[i], 1); if (x[i] == 0) zero = true; } } cout << (f ? "Yes" : "No") << endl; } return 0; }
感想
値を set で管理したら余裕で TLE したので Fenwick Tree に書き換えたら通って虚無.
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3329722
ICPC審判団講評では多倍長2進小数に変換する解法が示されていた.
http://icpc.iisf.or.jp/past-icpc/comments/2016.pdf
AOJ 2678 Cube Coloring
日本語記事が見つからなかったので
問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2678
Cube Coloring | Aizu Online Judge
1 × 1 × 1 の小立方体で構成される X × Y × Z の直方体と座標P (A, B, C) が与えられる.
各小立方体の座標を (0, 0, 0) から (X-1, Y-1, Z-1) までの座標で表し, 小立方体 (x1, y1, z1) と (x2, y2, z2) の距離を |x1 - x2| + |y1 - y2| + |z1 - z2| で定義する.
正整数 N が与えられるので 各 i+1 (1 <= i + 1 <= N) に対し, P との距離d % N が i となるような小立方体の個数を出力せよ. (2 <= N <= 1000, 1 <= X, Y, Z <= 1e6)
解法
O( X * Y * Z ) で全ての小立方体を数えていては TLE する.
各座標軸で mod を取り複数の小立方体をまとめた後, 定義に従って数え上げればよい.
計算量は O(N3).
ソースコード
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
ll X, Y, Z, A, B, C, N;
ll cnt_x[1000], cnt_y[1000], cnt_z[1000], res[1000];
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin >> X >> Y >> Z >> A >> B >> C >> N;
for (int i = 0; i < X; i++)
{
int diff = abs(i - A) % N;
cnt_x[diff]++;
}
for (int i = 0; i < Y; i++)
{
int diff = abs(i - B) % N;
cnt_y[diff]++;
}
for (int i = 0; i < Z; i++)
{
int diff = abs(i - C) % N;
cnt_z[diff]++;
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
for (int k = 0; k < N; k++)
{
int idx = i + j + k;
if (idx >= 2 * N)
idx -= 2 * N;
else if (idx >= N)
idx -= N;
res[idx] += cnt_x[i] * cnt_y[j] * cnt_z[k];
}
}
}
for (int i = 0; i < N; i++)
{
cout << res[i] << " \n"[i == N - 1];
}
}
感想
3重ループ内で % 演算子を使ったら TLE したので if 文で処理したら4倍弱速くなって(3.9s -> 1.1s) AC. うーん.
HACK TO THE FUTURE 2019予選 ばらばらロボット
概要
73位/519 でしたが、20卒枠で予選通過しました。
コンテストに参加するにあたって以前のコンテストの参加記に助けられたので自分も記録を残します。
コンテスト参加までにやったこと
この予選がマラソンコンテスト初参加でした。
ビームサーチや焼きなましなどの単語は知っているけれど何をしているのかは分からないぐらいの地点からスタートです。
とりあえずいくつかの解説記事を読みながら HTTF2018 予選 山型足し算*1 を解きました。主に以下の解説記事を参考にさせていただきました。
乱択・山登り・焼きなまし辺りを書いて予選4位ぐらいの得点が取れるようにしました。ついでに XorShift をライブラリ化しておくと便利です。
コンテストでやったこと
高得点を取る方法については他の方の解説記事にお任せします。
問題概要
- 'S', 'L', 'R' からなる命令列が複数与えられる
- '.', '#', 'D', 'T', 'L', 'R' からなる盤面を構築する
- 盤面上で命令列を実行し、全ての命令が実行された後の状態に応じ得点が得られる
- 30ケースに対する得点の和を最大化したい
(各命令の意味及び得点計算式は問題文参照)
解法
やったこと
- 適当な盤面から山登り・焼きなまし
- 初期盤面は '.' で埋めておく(最終的に 'L' を適度に撒いておくようにした)
- 評価関数は与えられた得点計算式をそのまま使う
- 盤面構築には '.', 'L', 'R' 以外は使わない。この3種類の配置・撤去で遷移を行う
'T', 'D', '#' を使わなかった理由は 'L', 'R' だけで十分な解空間が確保できると考えたためです。シミュレータをバグらせたくないという理由もあります。
最終的に山登り回数は 4000回程度になりました。
やらなかったこと
- 変更したマスを通るロボットのみを対象に得点を再計算する
- 変更したマスで回転するロボットのみを対象に得点を再計算
このどちらかを実行していれば山登り回数を増やせることは分かっていましたが、実装しきれるか自信が無かったので諦めました。
結局最後の3時間は暇していたのでやるべきだった。
気づかなかったこと
- 初期盤面を 'L' で埋めておく
- 命令列の圧縮
何を食べたら 'L' 埋めに気付けるんでしょうか・・・
感想
- 基本的な山登りができれば(20卒枠通過には)十分な点数が取れる問題だった
- さらに上位を目指すには考察・実装が重そう
- 夕飯*2を食べた後力尽きたのは反省
- 最後の方は焼きなまししていたが、山登り高速化の方が優先度高かった(焼きなましで一応点数は上がった)
HACK TO THE FUTURE 2019 本選参加記
概要
20卒枠で予選通過(73 位)したので参加してきました。
slack, git, (twitter) にコンテスト中のログを残していたので時系列で参加記を書きます。
質問などあればコメントか twitter にお願いします。
前日
交通費・前後泊宿泊費が出るので前日入り。
金曜日は4限まで計算機科学実験及演習4*1 があるので 19時頃の新幹線で東京に向かいます。
夜飯は北品川周辺で Md*2 と餃子定食を食べました。
RELEASE THE SPYCE 8 話を見て就寝。
コンテスト当日
目黒川に沿って歩き、大崎駅 ThinkPark Tower を目指します。
topcoder の衣類を着ている人を見てビビるなどする。
受付でTシャツでない衣類(HTTFパーカー)を受け取り、適当な場所に座ります。
コンテスト開始(10:30)
問題概要
- 1000ターンでモンスター「高橋君」を育成し、最終的な所持金を最大化する
- 実行できる行動はアルバイト、「高橋君」のスキルトレーニング、討伐の3種類
- 討伐には基本報酬額、要求スキル、受注可能期間が定められている
- 「高橋君」のスキルレベル、受注ターンにより実報酬額は(指数的に)変化する
とりあえずビジュアライザで遊びたいので毎ターンアルバイトをする自明解を提出(11:00)
最初に考えたこと
- あるスキルのレベルが1上がるだけで実報酬額は倍になるので、レベルを0から1にするだけでもかなり報酬が増えるはず
- 基本的にアルバイトするよりは各ターンで報酬額が最大の討伐を受注する方がお得
- 重実装も無さそうなのでとりあえずシミュレータを書きたい
最初の 200ターンでアルバイト、次の10ターンで各スキルレベルを0から1にする、以後はその時点で報酬額が最大の討伐を実行するコードを提出(11:20)
この時点でシミュレータは完成していた。
スキルレベル強化が偉いと分かったので、ランダムにスキルを選びトレーニングが可能なら実行、そうでなければ討伐を実行するように変更し提出。得点が100倍になる。完全に調子に乗る(11:30)
完全に理解したので1位です #HTTF
— ざき🍆 (@zaki_joho) December 1, 2018
考えたこと2
- そもそも序盤からアルバイトせずに討伐を受注すればいいのでは？
- トレーニングはスキルレベルが上がると指数的に費用が増加するが、スキルレベル上昇による報酬額の増加はそれを上回るっぽい
ここらで人々の得点が爆発し、順位表が壊れる。表示得点のデノミが行われた。
【お知らせ】ドラゴンボール感を出し過ぎたので点数を1/10000にしました。 #httf
— chokudai(高橋 直大) (@chokudai) December 1, 2018
アルバイトをやめ、最初からトレーニングor討伐受注を行うように変更し提出。また得点が100倍になる。(12:20, 101631938.31 points)
この時点では余裕の一位だったので調子に乗ったまま昼食へ。エビチリ弁当を選択。
カフェスペースには PC 持ち込み禁止だったので解法を考えながら完食。
実行結果をビジュアライザに投げると意図していない行動を取っていた(無効な行動をしていた)。討伐が受注可能か確認する部分がバグっていたので修正し提出。(12:40, 133646794.66 points)
考えたこと3
- 現状では各ターンで報酬額が最大の討伐を選択しているが、これは締切ギリギリに受注した方が報酬が増えることを考慮していない
- 討伐が「短期間」「中期間」「長期間」に分かれていることを考慮していない
- 締切ちょうどに討伐を受注すると報酬が10倍になることを使いたい
- 全スキルレベルがMAXになる前後で行動決定ルーチンを変えるべきでは？
以上の考察から
- スキルレベルがMAXになるまでは可能な限りトレーニングを行い、所持金が足りなくなった場合は締切が比較的近い討伐の内で報酬額が最大のものを選択。
- MAXになった後はそのターンで締切を迎える討伐を選択。
に行動決定方法を修正。kurenai3110 さんを抜いて1位になる。(14:00, 316193686.45 points)
トレーニングの際、どのスキルレベルを上げるかは毎回ランダムに決定していた。
乱数の引きによって1割ぐらい得点が上下することが分かっていたので試行回数を稼いで最終所持金が最大となるものを出力する方針に変更。この時点では1試行あたり150ms 程度かかっていた。
高速化のためにやったこと
- vector を可能な限り生配列に変更
- 討伐を B[i] ごとに分類・基本報酬額でソートして保持
- 最良の行動を string で持っていたのを pair<int,int> で持つように変更
- 報酬額を前計算
150倍速くなって1000回程試行回数が稼げるようになった。
スコアも上がって3.4 億点(16:00)
しかしこの時点で4位ぐらいになっていた。上位陣とは1割近く差をつけられているので割と焦る。残り2時間半で何ができるだろう…
最後に考えたこと
- スキルレベルがMAXになるまではその時点で報酬額が最大の討伐を選択しているが、これは最善ではないはず
- どのスキルレベルを上げるかはランダムに選択しているが、これも最善ではなさそう
- (サンプルケース埋め込み………)
ここで体力が尽きて地蔵になり、ビジュアライザで遊ぶ人になる。
たまに小さな修正をして乱数に祈るなどしていた気がする。
上振れを引いて最高得点を更新。これが最終得点になります.。（は？）(16:30)
standings 凍結(17:30)
この時点で5位だった気がする。
既に完全に頭が寝ていたので乱数に祈ったりカフェスペースでコーヒーを飲んだりして時間を潰す。ICE COFFEE ボタンを押したらホットコーヒーが出てきた。
コンテスト終了(18:30)
近くの赤い人達が bitDP とか最小費用流をしたみたいな会話が聞こえてくる。本当に同じ問題を見ていたのだろうか・・・
会社紹介(18:45)
- ツカモさんとナカモさんが出てきて Loppi の話をしていた気がする
- ほとんど寝てました・・・ごめんなさい・・・
- 競プロer 激推ししてるらしいです
懇親会(19:00)
酒と肉とピザが出た。ビール一杯で終了。合鴨のロースが美味しかった。正直眠すぎて懇親どころではなかった。
結果発表(20:00)
ここで凍結されていた順位表の最終結果発表。
5位から1位、その後6～10位の受賞者が発表される形式。
9位まで名前が呼ばれず、それはそう。(ラスト2時間寝ていたため)
しかし、10位で名前が呼ばれました。マジか。賞金 ￥10,000 を頂きました。
賞金貰いました！！フューチャーアーキテクト株式会社さんありがとうございます！！！#HTTF pic.twitter.com/m3QeukBY4F
— ざき🍆 (@zaki_joho) December 1, 2018
表彰後は初めてお会いした同大学のてんぷらさんやツカモさんに声を掛けていただきました、ありがとうございました。
最後に記念撮影をして参加賞を受け取って解散。エントランスは既に閉まっているので裏口を通って帰ります。
感想
初めて参加したマラソンコンテストで賞金を貰えるとは思っていなかったので本当に嬉しいです。*3
大半の人がコンテスト終了直前に得点更新していたことに驚きました。人々勝負強いですね・・・
会社サイド全面バックアップといった印象で、F社の好感度が上がった。イベントを開催していただきありがとうございました。
2年後も新卒枠になっているはずなので(コンテストがあれば)是非参加したいです。(ツカモさんお願いします！！)
反省
- 予選も最後3時間地蔵だったし、本選も最後2時間地蔵だったし*4、マラソンのために体力が欲しい
- トレーニングを行うスキルをランダムに選んでいたが、ここで焼きなましをすると良かったらしい(焼きなましするには試行回数が足りないと思っていた)
- 中盤にある特定の討伐を目指してスキルに指向性を持たせると良かったらしい
- 上記の2点と重複することだが、数ターン先読みして行動決定するべきだった
- 序盤でバグらず1位をキープできていたのはえらかった
コンテスト翌日
完全に寝過ごしてフロントからの電話で起きるなどした
スヤスヤしてたらフロントから電話かかってきて追い出された
— ざき🍆 (@zaki_joho) December 2, 2018
Md と再合流し、春日亭で油そばを食べる
帰宅(19:00)
順位ボードを持って帰ってきてしまった
