スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

課題その1 回答1

前回送信したタグとの重複分を省く方法。
ガチで通信量を減らそうとするとクライアント側でのリソースを喰わざるを得ない。既に送ったタグをインデックス化しておく、とか思い浮かんだけど、送ったかどうかの判定にCPUもメモリも食われてしまう。固定な文字列ならいいんだけどそうでないから難しい。

スポンサーサイト

課題その1

問題 次の状況でクライアントマシンとホストマシン間の通信量を最小化せよ。クライアント上での動作速度が早く、使用メモリが少なければ尚良い。

クライアントマシンでは関数 push_tag( name ) と pop_tag() と send_tags()が呼ばれる。
push_tag(name)は、文字列 name をスタックにプッシュし、pop_tagはスタックから文字列をひとつだけポップする。
関数send_tagsが呼ばれた時点で、スタックに詰まれている文字列を /(スラッシュ) により
連結した文字列をホストマシンで表示したい。

例:
クライアントマシンで
push_tag( "hoge" ); push_tag("huge"); send_tags(); pop_tag(); send_tags(); pop_tag();
と関数が呼ばれた場合ホストマシンでは
/hoge/huge
/hoge
という文字列が表示される。

条件
・ネットワークに関することは考慮する必要は無い。
・すべての関数はシングルスレッドで実行される。
・push_tag/pop_tagは必ず入れ子状に呼ばれる。
・nameに関する保障は無い。(10通りの文字列しかないかもしれない、10万通りの文字列があるかもしれない)
・nameの最大長に関する規定は無い。切り捨ててもかまわないが最低でも32文字以上でなければならない。
・push_tagを拡張するのは可(テンポラリな文字列用のpush_tagや固定文字列用のpush_tagを用意するなど)
・ただしnameと1対1対応にあるpush_tagを用意することは認められない
・文中に「スタックに~」とあるが、内部データ構造はスタックである必要はない。
・push_tag/pop_tagの入れ子が16を超える場合は超える分については切り捨てても良い。
・最終的にホスト上で表示される文字列の長さに制限を設けてもかまわない。
 ただし最低でも1024byteは表示できなければならない。
・nameはconst char*型であり、少なくとも対応するpop_tagが呼ばれるまではそのメモリ領域の生存が保障される。
・クライアント上でのメモリ資源は貴重である。少なければ少ないほど良い。
・ホストはCPU/メモリ資源共に充実している。
・通信量が多少多くともクライアント上での動作速度が速ければそちらのほうが好ましい。
・push_tagは多くの場合関数の先頭で呼ばれ、return時にpopされる。

通信料はともかく、クライアントでの実行速度もメモリも良い回答例。ホスト上ではnull文字ターミネートの文字列を受け取ればいいだけなので楽でもある。
検索フォーム
ユーザータグ

ICPC 2009 国内予選 ゲームプログラミング 

カテゴリ
最新記事
月別アーカイブ
最新コメント
最新トラックバック
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。