戯言

つらつらと気づいたことを書いていきます。人狼とか。

炎上プロジェクトを鎮圧してきた POH Lite


プロジェクトを炎上させまくってる火村の野郎がやってるプロジェクトの火消をしたった。
工数20万人月という壮大なプロジェクト。大変だったぜ。

というわけで、Javaで現時点でCase7の最短時間出せました。Sランク、0.10秒。
https://paiza.jp/poh/kirishima/result/c5ce9b427b11c6b2c30ed48a0b12d1a3

すぐ抜かれるのだろうが・・・。


京子ちゃんも大喜び。



今までみたいにSSSランクとかあるのかな。

最初は再帰でやってみたんだけど、Case6でタイムオーバー。オーダーはO(2^n)かな。
話にならなかったので、再帰を使わずにできるアルゴリズムを考えて試してみたら、最短とれました。
オーダーは、O(maxq * n)

今回の問題は入力も出力も多くないので、今までみたいに入出力ゲームにはならず、
純粋にアルゴリズムでの勝負になりやすそうです。
この点では、今回の問題はとてもいいですね。

ただ、入出力を少なくしなければならない縛りで、作成する問題が制約されることは本末転倒なので、
入出力数を気にしないで問題を作ってほしい。

入出力用の専用メソッドを運営側が与えて、必ず使うようにすれば、入出力での勝負では無くなると思うんだけど、難しいのかな。
でも、入出力も最適化の要素の一部になのだから、初めから一切入出力をチューニングできないのも、なんか違う気がするな…。






jQueryとServletでのクッキーの扱いの違い


一部の利用者からあるメンテナンス後に、ハンドルネーム欄に入力した内容が、次に表示したときには途中で切れて表示されてしまうとの連絡をいただきました。ABCDEFと入力しても、次に表示したときはABCDなどと切れてしまう事象のようです。

トラブル箇所は、初期表示時にクッキーに保存している値をそのまま表示しているんですが、確かにメンテナンスでこの部分を変更していたので、クッキー関連で何か誤りがあるのだろうと想定して調査を開始しました。

原因は、使用するライブラリによってクッキーの取り扱いが違うことでした。





るる鯖では、クッキーの取り扱いに、ServletAPI と jQuery を利用しています。

・Servlet3.0API(tomcat)
  取得 Cookie[] cookies = request.getCookies()
  格納 response.addCookie(new Cookie(name, value))
・jQuery.cookie.js
  取得 value = $.cookie(name)
  格納 $.cookie(name, value)


この2つにはクッキーの扱いに大きな違いがあり、Servletでは値をそのまま格納しますが、jQueryではURLエンコーディングして格納します。この違いのため、Servletで格納する際にはURLエンコーディングしてから格納するように手を加えており、これで大丈夫だろうと思っていました。

しかし、jQueryでは、一部の文字においてURLエンコーディングされていませんでした。
具体的には「)」などがエンコーディングしない文字に該当します。jQueryで「)」を含む値をクッキーにセットしても「)」のまま格納します。

このjQueryで格納された「)」入りのクッキーをServletで取り出そうとすると、「)」以降の値が削除されて取得されます。(おそらくクッキーの仕様(RFC 2109)で定めた文字以外の文字が入っているので、切り捨てたのだと思われます)

つまり、こんな動作になります。
「ああ#あ)あ」をjQueryで格納すると「%82%a0 %82%a0 %23 %82%a0 ) %82%a0」として格納。(わかりやすいようにスペースを入れていますが、実際にはスペースは入りません)
これをServletで取り出そうとすると、「%82%a0 %82%a0 %23 %82%a0」部分のみを取出し、URLデコーディングして「ああ#あ」となります。これが、文字切れの原因でした。





そもそも、クッキーの仕様(RFC 2109)では2バイト文字や記号を入れてはいけません。ですがそれでは日本語などを扱う際に困るので、jQueryでは親切に、自動でURLエンコーディングしてから格納するようになっています。一方、Servletでは自動でエンコーディングしないので、URLエンコーディングするように手を加えましたが、これはいわばこのサーバの独自仕様(といっても日本語などをクッキーで扱えるようにURLエンコーディングすることが一般的に行われています)です。この全く違う2つの仕様を、合致させようとすること自体が問題だったのでしょう。

jQuery.cookie.jsのソースを眺めてみると、内部では変換に encodeURIComponent() を使っていました。この関数は、URLエンコーディングの仕様(RFC 3986)と異なり、「)」などの一部の文字は変換しない仕様になっていました。これがRFCとおりの仕様であれば今回の問題は起きなかったのですが、ずいぶん前からJavaScriptに存在しているビルトイン関数であり、RFCと異なる理由が何かあるのかもしれません。もしかしてRFC3986制定の前から存在するのかも。





よく調査しないまま2つのライブラリを使ったのが問題なので、エンコーディングとでコーディングのライブラリはそろえるべきだと痛感した事象でした。

事実、コーディングの際には、どのライブラリをどのような場面で使うかを明確に決めておらず、POSTパラメータなどで送付する値をクッキーに格納する場合は、ServletAPIを使い、サーバ通信せずにjavascript内で処理した方が簡単な場合は、jQueryを使うというように、楽な方を使っていました。反省。




女子大生との楽しいペアプログラミング paiza POH2


paizaのオンラインハッカソン vol.2。POH! Vol.2。

JavaでSSランク、0.66s。オーダーはO(H^2W^1)。

Javaで0.04s出してる人がいるから、O(H^1W^1)のアルゴリズムがあるんだと思って、
いろいろ考えたけど、これ以上は無理だった…。

O(H^2W^1)でだけど、タイム縮めるコツは、
・標準入力は一度に読み込む
・格納領域はなるべく小さく。配列は2次元までしか使わずにできる。
・格納領域は再利用し、生成を減らす。
・値が変わらないのに再設定しているなどの無駄なロジックがないかを確認。

Cだと、O(H^2W^1)でも0.05sとか出て、さらに縮めれば0.01sになるらしい。
やっぱり、O(H^1W^1)のアルゴリズムがあるのかな!?


お礼を行ってくれる木野さん
「ruru兄って実は結構出来るエンジニアだったんだね。社会人ってやっぱ凄いね。
て、手伝ってくれて、、ありがとう。」

POH! Vol.2 ruruさんの採点結果 0.66s