他人の空似

2010 年 4 月 4 日

不可能だという事は大切なこと

Filed under: 未分類 — 中の人 @ 1:40 AM

目指す地点が合って、けれどもそれは不可能で、でも限りなく近づく事は出来る。
これって実は素晴らしい、何せ完璧には永遠にたどり着けないから。
つまり、まだ先があると常に確信して進む事が出来る。

まぁ、答えが固定な問題を固定値return以外で解く事になったから思っただけなんですがね。
たぶんもっと高速化する方法はあるはずだけど、固定値returnが最速だと判っている時点で、そんなことに取り組む意欲が無くなってしまったという話。

やはり不可能であるという事は大事だ。
日本人は本質的にマゾだというのもある意味では間違ってないのかもね、本当。

学習をかねて

Filed under: 未分類 — 中の人 @ 12:10 AM

http://www.itmedia.co.jp/enterprise/articles/1004/03/news002.htmlをやってみた。

まず記事中で紹介されている、人材獲得作戦なる方の回答
ソース
所要時間一時間ちょっと、ただし開始前に食事しつつアルゴリズムを考えていたので2時間と考えた方が良いかも。

自分のアルゴリズム知識量は少ない、少なくともプログラムコンテストで成績を残せる人たちに比べれば天地、そして最短経路問題はうろ覚えのダイクストラしか知らない。
しかもダイクストラなんぞ滅多に使わないため、この問題にダイクストラは向かないと決め付けてしまい、アルゴリズムを自作する羽目になった馬鹿な自分。(使っても対して変わらなかったとは思うけど)
幅優先探索をスタートとゴールの両方からはじめ、最初に範囲が被ったところを最短ルートとする方法で実装。
探索方法は探索先リストをもち、そのリストの場所と隣接しており未探索の部分を次探索リストに追加をスタート側とゴール側で交互に繰り返すだけ。
どこかで見たことあるアルゴリズムだけれど、名前知らないしどこかで習ったアルゴリズムでもない気がするので気にしない。
反省点はstd::vectorを使ったこと。
場所によってイテレーター使ったり添え字アクセスだったり、上下左右のポインターを持たなきゃアクセスできない事を実装始めた後まで気づかなかったり。
まだまだ自分はC++に馴染めていないんだなぁと痛感。
あと、出題にちょっとだけ不満がある。
縦横のサイズはどうやって取得するのかの情報が一切無く、入力終端の判別方法すら指定されていない。
たぶん、そこは問題の本質ではないからどういう形でも好きに実装しろという話なんだろうけど、つい完璧主義に走って無駄な時間を使ってしまった。
でも楽しかったからよし。
そういえば、この回答はきちんとLv4扱いになるのかしら?
書き上げた時のままなのでチューン不足だから、それなりにサイズでかくされちゃうとタイムオーバーしそうな内容なんだけど、
これじゃまだLv3扱いかなーどうかなー

次に、記事中で実際に課された問題。
ソース
所要時間2時間ちょっと。

アルゴリズムは書きながら考えたので粗だらけ、最初にアルゴリズム考える時間30分ぐらい取ってたらコーディング事態は1時間で終わったかも。
1~9のみなので、待ちは順子の隣り合わせ8種/順子の中抜け7種/刻子9種/アタマ9種の計33種。
この中でアタマ9種を除く24種では更にアタマ9種に振り分けて、計225種。
この225種を手牌から成立しうるものに絞込み、その上で残りの手牌から作れる限りの順子と刻子を全探索(実際には重複が出ないようちょっとだけ枝狩りしてる)
そして手牌が0になるパターンに遭遇したら、それを答え配列に追加、これだけ。
最後の全探索が微妙ですが、最大でも手牌12で4つしか作れないからね、たいした計算量にはなら無いだろうという甘い読み。
反省点はまたしてもstd::vectorを使ったこと。
中間表現に散々悩んだ挙句、既に書いたコードを捨て切れなくて「データ変更->探索->データ復元」の流れで配列の中身を追加削除しまくり。
最大でも配列長は13だから、という事で何とかなってますが、読み辛いしコスト高いしで微妙すぎた。
しかも、差し替えたいという気持ちを引きずりすぎたせいで変更復元の流れを作りこむ気になれず、結果としてほぼ同じコードが大量に……
問題への不満点は、擬似麻雀でありながらルールの説明を省きすぎなところ。
具体的には、同じ数字は4つ以上出現するのかどうか(出現するものとして書いた)
(111)(333)(555)(666)[1]なんて回答を許すのかどうかっていうのは結構大きな問題になる。
結構悩んで、問題文を読み返しても特に言及がなく、サンプルでも現出しないパターンだったから投げた、これで違う言われたら泣くね。

これで半日ぐらい潰したが、まぁ楽しかったから良いや

Powered by WordPress