CodeIQ/スペーストーキー問題
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
*スペーストーキー問題 [#xc93af4b]
-CodeIQで結城浩先生が出題されていた、スペーストーキー問題...
-解説を書く予定ですが、問題提出の締め切りが終わったあとに...
-なお、問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hi...
-結城先生の[[CodeIQのページはこちら>http://www.hyuki.com/...
*突然ひらめきが [#s5d19a64]
-ずーっと画面とにらめっこしていて、
--aが大量に挿入される
--たまにbが追加され、その時は文字の並びが乱れる(?)
-ぐらいしか気づいていませんでした。
-しかし、ふと唐揚げを食べながら閃きました。「Run Length E...
*Run Length Encodingについて [#dec36ea9]
-Run Length Encodingとは、可逆圧縮方式の一種です。
-同じ符号が連続で現れるときに特に効果を発揮する符号化の方...
-例えば、「''1000000円''」という文字を読むときに
--「いち、ぜろ、ぜろ、ぜろ、ぜろ、ぜろ、ぜろ、えん」と読...
--「ひゃくまんえん」と読んだ方が、圧倒的に速い(=圧縮さ...
-これがRun Length Encoding です
*今回も問題のポイント [#j4d6b2c8]
-試しに、WebAPIを使って幾つかエコーバックを見てみましょう。
|foo|faob|
|hello|haealboa|
|run|rauana|
-こんな具合に、aがそこかしこに挿入されますが、たまにbが追...
-よく見れば、対応する入力する場所では同じアルファベットが...
--f''oo'' -> fao''b''
--he''ll''o -> haeal''b''oa
-んで、何故bなのか?実は同じ文字が「2回」連続してることを...
-じゃあ、同じアルファベットが3回連続してる部分は無いのか...
-しかしそこはWebAPIの出番!実際に入力してみれば良いわけで...
-例えば aaa は ac に変換されます。
-どうやら、本当に文字を繰り返せば繰り返しただけ、次のアル...
*符号化できる/できない [#b6b75717]
-Run Length Encoding は、シンボルの桁数が偶数でなければな...
-デコードする際に、なんという符号を、何回繰り返すか、とい...
-先ほどの「1000000円」の例で言えば、
--「ひゃくまん」で、
--1が1回、
--0が6回、
--それぞれ繰り返す事を表しています。
-しかし、今回は繰り返される符号も、繰り返す回数も、どちら...
+2文字ずつ取得し、
+1文字目を
+2文字目に該当する回数だけ繰り返す
-事を繰り返します。
-自然と、''奇数長の符号''は復号化できないことになります。
-これが今回の「対応する入力がない場合」に相当します。
*エンコードでなく、デコード [#x02f8efa]
-今回の問題のポイントは
--復号化することで期待のコマンドになるような入力を考える
-という点です
-なので、コマンドが既に符号化された記号と見立てて、それら...
-先ほどの符号化の手順をもとに、復号化の手続きを考えると
+先頭から2文字ずつ切り出してくる
+2文字目を数字Xに置き換える
+1文字目をX回繰り返す
+次の2文字をまた取ってくる
-の繰り返しで表現できます。
*ソースコード [#lcf36c68]
-私が書いたコードは以下の通りです。
-C++で書きました
#geshi(c++,number){{
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
std::string decode(const std::string& rawString)
{
std::string result;
for(int i = 0;i < rawString.length()-1;i+=2)
{
char a, b;
a = rawString[i ];
b = rawString[i+1];
for(int j = 0;j <= b - 'a';j++)
{
result.push_back(a);
}
}
return result;
}
bool isFormatAcceptable(const std::string& rawString)
{
if((rawString.length() & 1) == 1){
return false;
}else{
if(rawString.length() == 0){
return false;
}else{
return true;
}
}
}
int main(int argc, char** argv)
{
using namespace std;
string inputFilename;
if(argc <= 1)
{
inputFilename = "./words.txt";
}else{
inputFilename = string(argv[1]);
}
ifstream inputFile(inputFilename.c_str());
if(inputFile.is_open() == false)
{
cerr << "Failed to open " << inputFilenam...
return -1;
}
cout << "Succeeded to open " << inputFilename << ...
do{
string temp;
inputFile >> temp;
if(isFormatAcceptable(temp) == false){
cout << "X:" << temp << endl;
}else{
cout << decode(temp) << ':' << te...
}
}
while(inputFile.eof() == false);
return 0;
}
}}
*入力のあるなし/複数 [#f8f177ba]
**対応する複数の入力 [#k1082769]
-今回、Run Length Encodingは可逆圧縮です。
-可逆圧縮ですので、ある記号Xが符号化でYという記号になった...
#ref(SpaceTalkyEncodeDecode.png)
-図で表したのは、符号化された記号Yと、そのれを復号化した...
-「可逆圧縮」という意味は、「''Yに対応するXが必ず1つだけ...
-今回の問題は、符号化することで特定のコマンドXになるよう...
--ここで、仮に、特定のコマンドになるなる入力AとBが存在し...
--このAとBは両方コマンドXと等価な符号に「符号化」されます。
--先ほどの、「可逆圧縮」という特性から、この符号Xは必ず複...
--ですので、そんな符号AとBは存在しない訳です。
-問題文中に「''入力が複数ある場合はひとつだけ答えてくださ...
**対応する入力なし [#j7bfb04f]
-一方で、入力が存在しない記号もあります。
-サクッと書きましたが、その点についてもう少し考察します
-元符号の集合をX、符号化された集合をYとおくと前述の図のよ...
-ここで、全集合の数を考えてみます。
--今、encoderに入力できる文字列は
--アルファベット小文字のみ
--最長1024文字
--と定義されています
-しかし、encoderの出力はどうでしょうか。
--試してみると分かりますが、符号Yの長さは[[最長2048文字>h...
#ref(SpaceTalkyEncodeDecodeSet.png)
-図で示したように、元符号Xと、符号化された符号Yでは、集合...
--可逆圧縮なので、Y→Xとなる対応関係は保証されています。
--しかし、集合の大きさで言えば符号Yの集合の方が大きいので...
--今回の例で言えば、符号長が奇数文字のコマンドがそれに当...
-なので、「対応する入力が存在しない」ことに疑心暗鬼になっ...
-前述の図の通り「対応する入力が存在しない」ことは十分あり...
--当然、私の解答が正解であるかどうか、まだ決まってない訳...
*追記 [#j1a96c80]
-18:00追記
-採点結果が届いて、残念ながら評価3だった。悔しい!
終了行:
*スペーストーキー問題 [#xc93af4b]
-CodeIQで結城浩先生が出題されていた、スペーストーキー問題...
-解説を書く予定ですが、問題提出の締め切りが終わったあとに...
-なお、問題の詳細は[[こちら>https://codeiq.jp/ace/yuki_hi...
-結城先生の[[CodeIQのページはこちら>http://www.hyuki.com/...
*突然ひらめきが [#s5d19a64]
-ずーっと画面とにらめっこしていて、
--aが大量に挿入される
--たまにbが追加され、その時は文字の並びが乱れる(?)
-ぐらいしか気づいていませんでした。
-しかし、ふと唐揚げを食べながら閃きました。「Run Length E...
*Run Length Encodingについて [#dec36ea9]
-Run Length Encodingとは、可逆圧縮方式の一種です。
-同じ符号が連続で現れるときに特に効果を発揮する符号化の方...
-例えば、「''1000000円''」という文字を読むときに
--「いち、ぜろ、ぜろ、ぜろ、ぜろ、ぜろ、ぜろ、えん」と読...
--「ひゃくまんえん」と読んだ方が、圧倒的に速い(=圧縮さ...
-これがRun Length Encoding です
*今回も問題のポイント [#j4d6b2c8]
-試しに、WebAPIを使って幾つかエコーバックを見てみましょう。
|foo|faob|
|hello|haealboa|
|run|rauana|
-こんな具合に、aがそこかしこに挿入されますが、たまにbが追...
-よく見れば、対応する入力する場所では同じアルファベットが...
--f''oo'' -> fao''b''
--he''ll''o -> haeal''b''oa
-んで、何故bなのか?実は同じ文字が「2回」連続してることを...
-じゃあ、同じアルファベットが3回連続してる部分は無いのか...
-しかしそこはWebAPIの出番!実際に入力してみれば良いわけで...
-例えば aaa は ac に変換されます。
-どうやら、本当に文字を繰り返せば繰り返しただけ、次のアル...
*符号化できる/できない [#b6b75717]
-Run Length Encoding は、シンボルの桁数が偶数でなければな...
-デコードする際に、なんという符号を、何回繰り返すか、とい...
-先ほどの「1000000円」の例で言えば、
--「ひゃくまん」で、
--1が1回、
--0が6回、
--それぞれ繰り返す事を表しています。
-しかし、今回は繰り返される符号も、繰り返す回数も、どちら...
+2文字ずつ取得し、
+1文字目を
+2文字目に該当する回数だけ繰り返す
-事を繰り返します。
-自然と、''奇数長の符号''は復号化できないことになります。
-これが今回の「対応する入力がない場合」に相当します。
*エンコードでなく、デコード [#x02f8efa]
-今回の問題のポイントは
--復号化することで期待のコマンドになるような入力を考える
-という点です
-なので、コマンドが既に符号化された記号と見立てて、それら...
-先ほどの符号化の手順をもとに、復号化の手続きを考えると
+先頭から2文字ずつ切り出してくる
+2文字目を数字Xに置き換える
+1文字目をX回繰り返す
+次の2文字をまた取ってくる
-の繰り返しで表現できます。
*ソースコード [#lcf36c68]
-私が書いたコードは以下の通りです。
-C++で書きました
#geshi(c++,number){{
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
std::string decode(const std::string& rawString)
{
std::string result;
for(int i = 0;i < rawString.length()-1;i+=2)
{
char a, b;
a = rawString[i ];
b = rawString[i+1];
for(int j = 0;j <= b - 'a';j++)
{
result.push_back(a);
}
}
return result;
}
bool isFormatAcceptable(const std::string& rawString)
{
if((rawString.length() & 1) == 1){
return false;
}else{
if(rawString.length() == 0){
return false;
}else{
return true;
}
}
}
int main(int argc, char** argv)
{
using namespace std;
string inputFilename;
if(argc <= 1)
{
inputFilename = "./words.txt";
}else{
inputFilename = string(argv[1]);
}
ifstream inputFile(inputFilename.c_str());
if(inputFile.is_open() == false)
{
cerr << "Failed to open " << inputFilenam...
return -1;
}
cout << "Succeeded to open " << inputFilename << ...
do{
string temp;
inputFile >> temp;
if(isFormatAcceptable(temp) == false){
cout << "X:" << temp << endl;
}else{
cout << decode(temp) << ':' << te...
}
}
while(inputFile.eof() == false);
return 0;
}
}}
*入力のあるなし/複数 [#f8f177ba]
**対応する複数の入力 [#k1082769]
-今回、Run Length Encodingは可逆圧縮です。
-可逆圧縮ですので、ある記号Xが符号化でYという記号になった...
#ref(SpaceTalkyEncodeDecode.png)
-図で表したのは、符号化された記号Yと、そのれを復号化した...
-「可逆圧縮」という意味は、「''Yに対応するXが必ず1つだけ...
-今回の問題は、符号化することで特定のコマンドXになるよう...
--ここで、仮に、特定のコマンドになるなる入力AとBが存在し...
--このAとBは両方コマンドXと等価な符号に「符号化」されます。
--先ほどの、「可逆圧縮」という特性から、この符号Xは必ず複...
--ですので、そんな符号AとBは存在しない訳です。
-問題文中に「''入力が複数ある場合はひとつだけ答えてくださ...
**対応する入力なし [#j7bfb04f]
-一方で、入力が存在しない記号もあります。
-サクッと書きましたが、その点についてもう少し考察します
-元符号の集合をX、符号化された集合をYとおくと前述の図のよ...
-ここで、全集合の数を考えてみます。
--今、encoderに入力できる文字列は
--アルファベット小文字のみ
--最長1024文字
--と定義されています
-しかし、encoderの出力はどうでしょうか。
--試してみると分かりますが、符号Yの長さは[[最長2048文字>h...
#ref(SpaceTalkyEncodeDecodeSet.png)
-図で示したように、元符号Xと、符号化された符号Yでは、集合...
--可逆圧縮なので、Y→Xとなる対応関係は保証されています。
--しかし、集合の大きさで言えば符号Yの集合の方が大きいので...
--今回の例で言えば、符号長が奇数文字のコマンドがそれに当...
-なので、「対応する入力が存在しない」ことに疑心暗鬼になっ...
-前述の図の通り「対応する入力が存在しない」ことは十分あり...
--当然、私の解答が正解であるかどうか、まだ決まってない訳...
*追記 [#j1a96c80]
-18:00追記
-採点結果が届いて、残念ながら評価3だった。悔しい!
ページ名: