SRM612 Div1 Easy "EmoticonsDiv1"
問題
TopCoder Statistics - Problem Statement
訳
あなたは待ちに待ったプログラミングコンテストを間近に迎えていたためとても嬉しくなっていた。親友に対しどれほど嬉しい事か伝えようと思っている。そこで、たくさんの笑顔のアイコンを彼にチャットでコメントしようと思っている。あなたはアイコンの数 smilesが与えられる。
すでに1個のアイコンはチャットでコメントしている。あなたはタイピングがとても遅い。そこで残りのアイコンはコピペで作ることにした。
下記の2つの操作が行える。
1. 既にコメントしているアイコンを全てクリップボードにコピーする。 2. クリップボードにあるアイコンをコメントにペーストする。 3. コメントのアイコンを1つ削除する
それぞれの操作は行うのに1秒かかる。コピーするとクリップボードの情報は上書きされる。ペーストはクリップボードが空の場合は行えない。コメントの一部をコピーすることはできない。クリップボードのアイコンは削除することができない。
ちょうどsmilesのアイコンをコメントするのに必要な最小の秒数を返せ。
制約
2 <= smiles <= 1000
考えたこと
コメントのアイコンの数をM, クリップボードのアイコンの数をCとした頂点で構成されるグラフに置き換えて、M=smilesへの最短経路問題を考えるとよい。
スタートの頂点はM=1, C=0
ある頂点(m, c)からは(m+c, c), (m, m), (m-1, c)の3つの頂点へ、コストが1の辺をはれる。
ベルマンフォードかダイクストラを使えばよい。
ダイクストラを使うならプライオリティキューを使うやつじゃないと計算量的に無理だが、コストが全て1なので、単なるキューでよい。(キューの先頭から末尾へはコストは単調増加になっている)
ソースコード
int d[1050][1050]; class S{ public: S(int _m, int _c, int _o) { m = _m; c = _c; o = _o; } int m; int c; int o; }; class EmoticonsDiv1 { public: int printSmiles(int smiles) { memset(d, -1, sizeof(d)); queue<S> que; que.push(S( 1, 0, 0 )); int res = 1000; // ダイクストラ法 while (!que.empty()) { S s = que.front(); que.pop(); if (d[s.m][s.c] != -1 && d[s.m][s.c] <= s.o) continue; d[s.m][s.c] = s.o; // ちょうどsmails 結果更新 if (s.m == smiles) { res = min(res, s.o); continue; } // コピー if (s.m != s.c) { que.push(S(s.m, s.m, s.o + 1)); } // ペースト if (s.c != 0 && s.m + s.c < 1050) { que.push(S(s.m + s.c, s.c, s.o + 1)); } // デリート if (s.m > 2) { que.push(S(s.m - 1, s.c, s.o + 1)); } } return res; } };