SRM 569 Div I - agwの日記

*1360481488* SRM 569 Div I

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15489

250に30分、500に42分。チャレンジ1回失敗。初めてDiv I Mediumを提出し、システムテストを通った。レートは1312から1474に上がったが、後の考察で明白なバグが2つもある微妙な実装であったことが分かった。<a href="http://community.topcoder.com/stat?c=coder_room_stats&cr=22827765&rd=15489&rm=315798">Room 25</a>。

- 250に30分
-- 題意が理解出来なかった。ノートでじっくり考え、まとまってから実装を行った
-- システムテストをパス。144.59点
- 500に42分
-- 容易に理解できるが解くのが難しい問題。良問であったと思う
-- 終了ギリギリのところでサンプルの出力が合った
-- システムテストをパス。235.62点
- チャレンジを<a href="http://community.topcoder.com/stat?c=problem_solution&rm=315798&rd=15489&pm=12388&cr=23043978#defenses">1回失敗</a>。-25.00点

- 「Div I Easyを奇麗な実装で提出する」という目標は達成した(と思う)
- 後の考察で、Div I Mediumの実装に大きなバグが2つあったことが分かった。今後も精進する
- 次回のSRMもしつこく、「Div I Easyを奇麗な実装で提出する」を目標とする
-- また、「Div I Easyの提出時間を短くする」ことを何となく意識し始めることにする

*1360481489* TheDevice

http://community.topcoder.com/stat?c=problem_statement&pm=12388&rd=15489&rm=315798&cr=23043978

30分。144.59点

- 題意が理解出来なかった。ノートでじっくり考え、まとまってから実装を行った

- 以下のような演算機がある。演算機は与えられた2種類の入力の各ビットごとに演算を行う

- 同じ入力が与えられたとしても演算機の中身が違うと結果も違う

- 中身がどうなっているか分からない演算機と何種類かの入力が与えられる。任意の2つの入力を組み合わせて演算を行い、演算機の中身を特定したい。だが与えられた入力では特定しきれないかもしれない。演算機の中身を確定するために後何種類の入力が必要か答える問題

- ここまで理解するのに15分ほどかかったか

- まず、AND、OR、XOR演算子の真理値表を書いた

- ANDとOR演算子を比べる。入力が(0, 1)、(1, 0)の場合、演算子がANDであるかORであるか判別できる

- 続けてORとXOR演算子を比較する。(1, 1)の演算結果が異なる。つまり、1は二つ以上なければならない

- 最後にXORとAND演算子を比較する。演算子がXORかANDであるかは(0, 1)、(1, 0)、(1, 1)の何れの組み合わせを用いても判断することができる

- つまり、そのビットが何れの演算子で処理されてるか判別するためには少なくとも1が二つ、0が一つ必要となる
- 以下のような3種類の入力が与えられたとしよう。各ビットごとに0と1の数をカウントする。下線が引いてあるビットは先ほどの条件を満たしていないため、演算機が何であるか判別できない

- 左から2番目のビットの演算子を判別するために、1がさらに2つ必要。この例の場合はこれが答えとなる

- 0の数をc0、1の数をc1とすると、後何種類の入力が必要かは以下の式で算出できる

提出した実装は以下(システムテストをパスi)。

>|cpp|
class TheDevice {
public:
int minimumAdditional(std::vector<std::string> plates) {
int cp = 0;

for (int j = 0, bits = plates[0].size(); j < bits; j ++) {
int c[2] = {0, 0};

for (int i = 0, size = plates.size(); i < size; i ++)
c[plates[i][j] - '0'] ++;

cp = std::max(std::max(1 - c[0], 0) + std::max(2 - c[1], 0), cp);
}

return cp;
};
};
||<

- 提出が遅かったが、通せてよかった

- 「Div I Easyを奇麗な実装で提出する」という目標もクリアしたと思う

*1360481490* TheJediTest

http://community.topcoder.com/stat?c=problem_statement&pm=12265&rd=15489&rm=315798&cr=22827765

- 問題を一気に読む。簡潔で題意をすぐ理解できたからか、すごく興味が湧いた

- 上下の階で生徒を移動させ、師範の数を最小化する問題
-- 師匠はK人の生徒までを監督することができる

- システムテスト#3の解説を元に図にすると以下のようになる

- 直感的に貪欲法っぽいな、と考えた
- だが貪欲法は自分には難しすぎる。まず深さ優先探索で実装してみようと思った

- 少し考えた後にノートに以下のように記載した
-- 「繰り上がらないように貰う」
-- 「繰り下がるようにあげる」
-- 「倍数だったら何もしない」
- 結果的に無駄があったものの、よい方針であったと思う
-- 条件や方針をノートにきちんと書き出すのは効果が大きい

- 階数、つまりstudentsの要素数をNとする。制約からNの取る範囲は以下となる

- 生徒の数が倍数であることはあまりないであろうから、大体2Nの探索を行う問題であると考え、深さ優先探索を設計。引数のiとjは階と一つ前の階からの生徒の情報であるとした

- また、jは正負双方の値を取る値と定義した

- jが正のときは一つ前の階に割り当てることができなかった生徒の数を表している
- jが負のときは一つ前の階にまだ余裕があることを表している

- さて、一つ前の階での師範の数は決定済であることを意識しつつ考えよう
- jが正である場合は、一つ前の階では監督しきれなかった生徒が押し寄せてきているということであるため、元々この階にいた生徒との和を取ってやる
- またjが負である場合、一つ前の階の師範にはまだ余力があることになる。一つ前の階に生徒を出来る限り回してしまえばこの階の負担は軽くなる。この場合も和を取ってしまえばよい。ただし、一つ前の階の師範にこの階の生徒数以上の余力があると合計が負の値となってしまうため、注意が必要だ。負の値である場合もこの階で監督すべき生徒はいないため、0にしてしまおう

- niを各階の生徒の数であるとすると、ここまでを以下の式で実装できる

- 一つ前の階からの差分を加味した生徒の数が師範一人が監督することができる人数Kの倍数であった場合、あまり考えることはない

- そうではない場合を考えよう。以下のような場合だ

- 丁度ではないけれども、必要な師範の数mを大体算出することはできる。前提条件より、mは整数ではない

- 師範の数は整数であることに対し、このmは実数だ。そのため、mの床関数を取ったものか、それより一つ大きい数(floor(m) + 1)を考慮することにしよう

- mの床関数を取ったものを採用した場合、師範が監督し切れない生徒が出てくる
-- mが整数ではないからだ

- その場合は次の階に生徒を送ってしまえばよい
-- ただし、次の階に送れる生徒の数の上限は、元々その階にいた生徒の数だ

- この数は以下のように算出できる

- もう一つの場合を考えてみよう。その階でfloor(m) + 1人の師範を割り当てる場合だ

- mが整数でないことを思い出すと、floor(m) + 1人の師範が教えられる生徒の数には余裕があることが分かる

- 余裕がある場合は深さ優先探索の引数として、負の値として渡すことにした。そのため、実際の計算式は以下となる

- 後はメモ化を考慮しながら実装を行うだけだ
- 訪れる状態の数は最大で220だろうか
-- niが[1, 100000]まで取るので、あまりメモにヒットしないことも予想できる。深さ優先探索でこの規模のグラフをトラバースできるのかどうか確信はなかったが、当たって砕けてみることにした

提出した実装は以下(システムテストをパス)。

>|cpp|
#define INF 2000000000

class TheJediTest {
public:
int minimumSupervisors(std::vector<int> students, int K) {
students_ = students;
K_ = K;

memo_.clear();

return dfs(0, 0);
};

private:
// MEMOIZE!
int dfs(int i, int j) {
int key = i * 100000000 + j;

if (memo_.count(key))
return memo_[key];

int& r = memo_[key];

if (i == students_.size())
if (j <= 0) {
return r = 0;
}
else {
return r = INF;
}

int n = std::max(students_[i] + j, 0);

if (n % K_ == 0) {
return r = dfs(i + 1, 0) + n / K_;
}
else {
int m = n / K_;

if (n - m * K_ <= students_[i]) {
r = dfs(i + 1, n - m * K_) + m;
}
else {
r = dfs(i + 1, students_[i]) + m + 1;
}

return r = std::min(dfs(i + 1, n - (m + 1) * K_) + (m + 1), r);
}
};

private:
std::vector<int> students_;
int K_;

std::map<int, int> memo_;
};
||<

- SRMの最中は実装しながら考えていたため、この実装は今回行っている考察の内容に比べるとかなり劣る。その上、この実装には明らかなバグが2つと無駄がある
- 一つ目のバグはメモ化だ。jは負の値を取り得るので、このキーは衝突する可能性がある
- 二つ目のバグはその階にいた生徒全員を次の階に送ってしまっていることだ

- これらのバグを察知してか、2回チャレンジをされたが、運良く生き残った
- それどころか、システムテストもパスしてしまった
- SRM終了直後はDiv I Mediumの初提出とシステムテストの通過に大喜びしていたのだが、内容が全く共合わない実装であった

- さて、SRM後に行った上述の考察を元に実装をやり直してみた

やり直した実装は以下(システムテストをパス)。

>|cpp|
#define INF 2000000000

class TheJediTest {
public:
int minimumSupervisors(std::vector<int> students, int K) {
students_ = students;
K_ = K;

memo_.clear();

return dfs(0, 0);
};

private:
int dfs(int i, int j) {
std::pair<int, int> key(i, j);

if (memo_.count(key))
return memo_[key];

int& r = memo_[key] = INF;

if (i == students_.size())
return r = (j <= 0) ? 0 : INF;

int n = std::max(students_[i] + j, 0);