2014年06月08日

オフラインリアルタイムどう書く #22の罠とか

バーです。
オフラインリアルタイムどう書く #22 というところに顔を出してきましたよー!間違えて足を出すと赤字になります。

以下どうでもいい駄文なので、結果が知りたい人は「続きを読む」で飛ばしてください。だけど、それがいいというオブザデッドな人あるいは動物あるいはその他は前半だけ読みましょう。

バーは競技系プログラマどころか、むしろ競技プログラミングに興味がないですし、何度も何度も何度も書きますが、そもそも本来はプログラマですらなく、データベースエンジニアです。だいたい競技系でJavaは使わないでしょ…別にJavaをDISっているわけなのですけど。ところでDISが何の略なのか知っている人は右手を上げないで左手下げない。これDISRESPECTなんですよね。のまねこのまねこ。
そんなバーが、なんで勉強会に参加する気になったか、というと、実はバーにもよくわかりません。なんとなくとしか言いようがないのですけど、無理に理由をつけようとするならバーと違う世界でコード書いている人と飲みたかったからでしょう。懇親会という目的のためならコードを書くという手段だって駆使します!目的のためには手段を選ばないのです。あれ、合ってる…

まずは事前準備として過去問を解こうと思ったのですけど、参加表明直後からトラブル対応でめーめー言ってて、コード書く時間がありません!強度を欠くだと倒れます。偽装建築です。とりあえず、参考と言われた「サイコロを転がす」や「フォークじゃない」を解くことにしました。お嬢様の目は節穴なのです。
「サイコロを転がす」を13分で解いたのがこれ。ダサいころと言って差し支えないくらい酷いコードでも動けば勝ちです。活動限界超えて暴走モード突入です。

ちょっとかかりすぎかなーでも簡単だよねーと暴君ハバネロより甘く見ていたのですけど、その次の「フォークじゃない」ではまります。生まれの不幸を祝うがいいです。Xが2人来た時の処理が解決できず、コードをまるっと作り直すクリスのような羽目になり、45分かけて書いたのがこれ。フォークじゃないのでシングルスレッドです。


問題には罠があり、心してかからないとハマる!というのがわかったのは、大きな収穫でした。これで今年の収穫祭も無事に終わらせそうです。この台詞が出るとだいたい波乱万丈になりますので、トラブル発生フラグと呼んでさしあげますわほーっほっほっほっほっほ。ぽーっぽっぽっぽっぽだと鳩です。

さて、当日めーめー言いながら、愛用のクマモンパーカーで会場に入り、実際に出された問題はこれでした。明らかに難易度が違います!まさか参加することが罠だったとは!罠にはまったひつぢはどうすればいいのでしょう?答え:美味しく頂かれる。

この問題を解くために、最初に思いついたアプローチ手法は、とりあえず全てのマスを埋めて、1×1でないマスはボックスクラスを作って処理する、という方法です。もちろん、この方法は、そこから先のアプローチ手法が思いつきませんでした。アプローチ手法と言えば、金鳥のゴキブリコックローチってすごい商品名だと思います。コックローチってゴキブリって意味なので、ゴキブリゴキブリです。コックローチでゴキブリ倒せばゴキブリゴキブリでゴキブリ倒したということになります。つまり、こうやってゴキブリって書くたびにドン引きされる世の中に警鐘を鳴らしたいです。そんな手法アプローチです。などと考えているうちに時間をロスしています。漢字で書くなら羅府です。周りは既にコードに取り掛かっているのに、バーは長考モード。実際、参加者の中で最後にキーを打ったのはバーでした。打つだしのう
そもそもバーの能力は本質的には先読みです。問題が出題されたら、その出題者の意図を先読みして結果を求める能力です。FIFOです。ワールドカップです。にも関わらずアプローチがわからないというのは出題者の意図を読み違えているか、出題者の意図にはまっているかのどちらか、あるいはバーの勘違いです。ということは、この方法はunsigned shortで65555%くらい罠です。やばいやり方に違いありません。別の方法で解かなくちゃ!などとやってる間にも時間は過ぎていきます。
とはいえ、このままボーっとしていても仕方がありませんので、まずはCellクラスを記述している最中に、フラグを持たせて…あれ?フラグ持たせる必要あるの?とひらめきました。バーが飼っている「平目宇盛(たいらのめうもり)」、通称ひらめうさんが、ヒラメだと思っていたらカレイだということが発覚したときと同じくらいのひらめきです。Cellはオブジェクトです。ということは同じCellオブジェクトを複数の配列要素に入れれば、そのオブジェクトの値が書き換わったときに他の配列要素も書き換わります。量子テレポーテーションです。
Cellクラスの中に、どこからどこまでが自分で、自分の値が何なのかを知っていればきっとなんとかなるはず!これがどこまでが自分で、どこからが他人なのか分からない曖昧な世界でどこまでも自分で、どこにも自分がいなくなっている静寂な世界だと人類が補完されます。しかも、これなら全ての座標に1つずつCellが入るので、List<List<Cell>>なんて美しくないコード書かなくても、Cell[][]と二重配列定義するだけで処理できます!こっちのほうが美しくないとか言うな!

…ちょっと前段で遊びすぎたので、ここからは真面目ひつぢモードで書きます。





解いたコードはこちらです。

業務でこんなコード書いたらぶっとばされますね!競技専用は、とにかくアイデアをコードに起こすことを重視して速度追及するため、エラー処理とか気にしないし、メソッド分けや変数のスコープとかも気にしない!

実際のメインロジックはtestメソッドです。
まず、配列の大きさを引っ張って、それで二重配列cellListを作り、大きなCell、たとえばleft1,top4,width3,height2というcellの場合、(1,4)(1,5)(2,4)(2,5)(3,4)(3,5)に同じCellオブジェクトをぶち込みます。このときの内部の値はxが1〜3、yが4〜5なので、xmin=1,xmax=3,ymin=4,ymax=5となります。(23〜36行目)
次に、空(null)の配列要素には1マスのCellオブジェクトで埋めます。(38〜50行目)
初期値として、(0.0)マスには値1が入るのでnumに1を入れておきます。(52行目)このCellが2×2のセルなら、(0,0)(1,0)(0,1)(1,1)のすべてのnumが同時に1になります。
後は探索です。初めは再帰探索して、無限ループとスタックオーバーの罠に陥りましたので、while(!mugenSerach())というひどいコードで切り抜けました。(53行目)
さて、探索ロジックmugenSearchですが、単純に、Cellの左側と上側の合計を計算して、計算できた場合は値を埋めるという処理を行っています。ここで「計算できる」というのは、「左側と上側の全てのCellの値が0でない」ときで、そうでない場合は計算せずに後回しです。x→y探索(78〜86行目)とy→x探索(88〜96行目)を両方行っているのは、こう書かないと嫌らしい配列の切り方で時間かかりすぎ!となるだろうという予測からで、別に1つのループでもたぶん解けます。
実際のCellの値計算はcalcCellで行っています。(100〜119行目)皆様、セルの二重計上の処理で苦しんだみたいですけど、バーのCellオブジェクトは自分のセルの幅を保持していますので、特に難しいことはありません。単にforループの加算演算子に足し算対象となったセルの幅なり高さなりを足しこんであげるだけです。(107行目、115行目)

これで完成。およそ1時間で、ほぼ全てのテストケースで正解が得られ解け、1時間若干オーバーくらいで全てのテストケースをクリアしました。

ちなみに、ハマったポイントは
1.26行目でArray out of index。
→大きなセルがない場合に発生。24行目の追加で回避。
2.無限ループ。
→原因はセルの中の値をnum%100で持ったため。ちょうど100のときに永遠に0以外にならず、無限ループに入ります。%100をやめました。
3.ずれたCellから値を取るとおかしくなる。
→はじめ、たとえば107行目の計算をtgt.ymax-tgt.yminにしていたので、左のセルと計算したいセルの高さにずれがあると、飛びすぎで値が少なくなります。言ってることがわからない場合は、コードを書き換えて実行してみれば、なんなのかわかります。

そんなわけで無事に勝利したのですけど、人数が増えたらペアプロとか言われて、Javaで参加しているのはバー以外にもう1人しかいなくて、えーと。

ひつぢのペアがって、なんて捕食フラグですか!><
posted by バー at 13:27| Comment(0) | TrackBack(0) | リアル | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。
この記事へのトラックバックURL
http://blog.seesaa.jp/tb/398989092
※ブログオーナーが承認したトラックバックのみ表示されます。
※言及リンクのないトラックバックは受信されません。

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。