日記

のみろぐ

主に競プロ日記です

LeetCode110

A問題「Reorder Log Files

問題概要

  • ログが与えられます
  • ログの形式は2つあります
  • 1つ目は「識別子より後が全部小文字」で、それをletter-logsと呼びます
  • 2つ目は「識別子より後が全部数字」で、それをdigit-logsと呼びます
  • そこで、letter-logs→digit-logになるように並べ替えて下さい。
  • letter-logsは識別子を無視して辞書順になるように並び替えて下さい
  • ditgit-logsは与えられたままの順序でOK

考察

  • ログがletter-logsかdigit-logsかは、ログの最後の文字を見て数字かどうか判定すれば良さそう。
  • letter-logsの並び替えがちょっとだるそう。連想配列でえい!!ってできそう。keyは識別子以下の文字列とする。valueはログ全体の文字列とする。
  • 最後にletter-logsの連想配列と、digit-logsの配列を繋げた配列を返せばよさげ

解法

  • 考察通りの実装する

コード

class Solution {
public:
    vector<string> reorderLogFiles(vector<string>& logs) {
        // letter-logsとdigit-logsを別々に並べ替えた配列を作る
        map<string, string> letterLogs;
        vector<string> digitLogs;
        for (string log : logs) {
            char lastChar = log.back();
            if (lastChar >= '0' && lastChar <= '9') {
                // digit-logsの処理
                digitLogs.push_back(log);
            } else {
                // letter-logsの処理
                int idx = 0; // 識別子後の空白index
                for (int i = 0; i < log.size(); i++) {
                    if (log[i] == ' ') {
                        idx = i;
                        break;
                    }
                }
                string key = log.substr(idx+1, log.size());
                letterLogs[key] = log;
            }
        }
        
        // 最後にletter-logsとdigit-logsを組み合わせた配列を作る
        vector<string> ans;
        for (auto x : letterLogs) {
            ans.push_back(x.second);
        }
        for (string s : digitLogs) {
            ans.push_back(s);
        }
        
        return ans;
    }
};

感想

  • lexicographicallyって英単語、呪文か???ってなった。レキシコグラフィカリー!!(あんまかっこよくないな)。コンテスト中は調べなかったけど辞書順って意味らしい。
  • 識別子後の空白indexを求めるやつ、breakし忘れてはまった。人の製にするのは良くないんですが、これデバッグがだるい。コードをローカルにコピペしてmain関数からクラスをインスタンス化してメソッドを呼び出してデバッグした。だるくないかこれ。もっと良い方法あるのかもだけど
  • 英語呼んで思うんだけど、一度呼んだだけじゃ何言ってるかよく分からない。3回くらいかみ砕きつつ読まないと読めない。にゃーん

B問題「Range Sum of BST

問題概要

  • 2分探索木が与えられます。
  • ノードの値の総和を求めて下さい。

考察

  • やるだけっぽいけど、ノードのたどり方覚えてねぇ...
  • ググったら->っていうアロー演算子使うっぽい。100億年振りに見た
  • ということで、再帰書いて終了。

コード

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
   int sum = 0;
   int rangeSumBST(TreeNode* root, int L, int R) {
      if (root->val >= L && root->val <= R) {
         sum += root->val;
      }

      if (root->left != NULL) {
         rangeSumBST(root->left, L, R);
      }
      if (root->right != NULL) {
         rangeSumBST(root->right, L, R);
      }

      return sum;
   }
};

改善

  • ホントは再帰関数だけで完結するコード書きたかったけど、書き方分かんなかったので外部にint sumを作った。
  • 他の人のコード見た感じ、以下の用の書けるみたい。URL
  • よくわからん。おなか空いたから後で見る
class Solution {
public:
   int rangeSumBST(TreeNode* root, int L, int R) {
      int sum = 0;

      if (root->val >= L && root->val <= R) {
         sum += root->val;
      }

      if (root->left != NULL) {
         sum += rangeSumBST(root->left, L, R);
      }
      if (root->right != NULL) {
         sum += rangeSumBST(root->right, L, R);
      }

      return sum;
   }
};

知見

  • 構造体のポインタ型の要素にアクセスするにはアロー演算子を使う。->こんなやつ。コンテスト中はドットでアクセス出来ずに詰んでた(入門書レベルだぞこの内容)

C問題「Minimum Area Rectangle

問題概要

  • 点が(x, y)座標が与えられます。
  • x, y座標と平行になるような辺で構成された最小の長方形を求めて下さい

考察

コンテスト中の考察

  • 4つの点を全探索すると$O(N4)$なので間に合わない。他の方法を考える必要がある
  • 問題を整理すると、以下のような状況になる。そして、点Pと点Oを決め打って上手いこと処理しようと考える。だが、ここでどうやっても無理だなーと思いコンテスト終了

f:id:nomikura:20181112081728p:plain

理想の考察

  • 全探索は $O(N4)$ で間に合わないので、他の方法を考える必要がある
  • 状況を整理すると以下のようになる。そこで、点を2つ決め打つ。すると、(a, b)と(d, c)が確定する。あとは、(a, c)と(d, b)が存在するかを確認すればいいだけとなる。これはsetを使うと楽に書ける
  • 計算量は $O(N^{2}log_N)$ となる

f:id:nomikura:20181112081748p:plain

コード

class Solution {
public:
   int minAreaRect(vector<vector<int>>& points) {
      // 全座標をsetに入れる
      set<pair<int, int>> pts;
      for (vector<int> p : points) {
         pts.insert({p[0], p[1]});
      }

      int ans = 1600000001;
      // 長方形の対角となる点p, qを決め打つ
      for (auto p : pts) {
         for (auto q : pts) {
            int a = p.first, b = p.second, c = q.second, d = q.first;
            // x, y座標がかぶってたら処理を飛ばす
            if (a == d || b == c) continue;
            if (pts.count({a, c}) && pts.count({d, b})) {
               ans = min(ans, abs((a - d) * (b - c)));
            }
         }
      }

      if (ans == 1600000001) return 0;
      return ans;
   }
};

要点

情報の重複を避ける

  • 画像にすると以下の通り。P, Oを決め打った場合、(a, b)と(a, c)を確定させるためdが明らかにならない。しかし、P, Qを決め打つ場合、(a, b)と(d, c)を確定させるため、全ての座標が明らかとなる。
  • 今回は、2つの要素の情報が重複したため計算が間に合わなかった。なので、確定させる要素に重複がないようにすれば良かったのかなーと思う。

f:id:nomikura:20181112081809p:plain

setの話

  • setのメソッドであるcountの計算量は$O(logN)$
  • いつもfind使ってるけどcountの方が良さげ

D問題「Distinct Subsequences II

  • わかりません
  • 典型らしいです

Future Contestを無料運用にした

まえがき

  • Future Contestとは?→これ
  • 初めてWebサイト作ってみたで作ったサイトを無料運用にしたのでログを取っておく。
  • ただのメモなので技術的なことは詳しく書いてない
  • 時系列順に書いてく
  • たぶんめっちゃアホみたいなことやってる

使ってるもの

クラウド

  • GAE

言語

  • Go

アーキテクチャ

  • 最終的には以下のようなアーキテクチャになった。
  • 5分に一度コンテストサイトのAPIを叩いてクラウドストレージに保存する。
  • クライアントからリクエストが来たら、クラウドストレージからコンテストデータを読み出して整形し、HTMLとしてクライアントに返す。
  • 正確にはAtCoderのコンテストページをスクレイピングして別にAPIサーバーを立てているが、ココにはそれは書いてない。

f:id:nomikura:20181101214919p:plain

やったことを簡潔に

  • GAEが動く環境は、スタンダード環境とフレキシブル環境の2つがある。僕はそれをしらず、ずっとフレキシブル環境で動かしていた。
  • 無料枠が使えるのはスタンダード環境だけなので、スタンダード環境に乗り換えた。
  • 変更点は大体以下の通り

  • app.yamlをスタンダード環境用に書き換えた

  • スタンダード環境で動く用のコードに書き換えた
  • cron.yamlを使った。

お金がやばくなる

f:id:nomikura:20181101214940p:plain

  • ぎゃぁぁぁぁぁぁぁぁ!!!!!!
  • 44日で15000円くらい消費されてる
  • 無料で3万使えるとは言え、こうも早く消費されるとつらい。
  • GAEはこれからも使いたいので無料で運用する方法を知っておきたい

無料運用する方法をググってみる

  • ググると、こんな感じの記事が出てくる。なんか良さげなので、とりあえずこの設定をapp.yaml(設定ファイル)に書き込んでデプロイしてみる。ちゃんとは覚えてないけど、そのときのapp.yamlは以下のような感じ(上手く動きません)
runtime: go
env: flex

threadsafe: true

automatic_scaling:
  min_idle_instances: automatic
  max_idle_instances: 1
  min_pending_latency: 3000ms
  max_pending_latency: automatic
  • でも、デプロイできない。「min_idle_instancesとかいうパラメータは存在しないよ」って怒られる。他のパラメータも怒られてしまう。

自分でapp.yamlを書いてみる

  • デプロイしようとすると、パラメータの名前自体が怒られるので、app.yamlの書き方がおかしいんだろうなーと思った。なのでapp.yamlの書き方をググった。
  • すると、app.yamlによるアプリ構成という記事が見つかった。公式の記事はすごいわかりやすかったので、これを元に設定ファイルを書くことにした。
  • Google Cloud Platformの無料枠によると、とりあえず1日28インスタンス時間を守れば無料運用できそうだなーと思った(ストレージは5GBも使わないし、メールも使わないため)。ただ、「1 日あたり 1,000 回の検索オペレーション、10 MB の検索インデックス作成」というのはよく分からなかったので無視した。
  • インスタンス時間とは、全てのインスタンスが動いている合計時間のことである。1つのインスタンスを24時間動かすと、それは24インスタンス時間になる。なので、とりあえず1つのインスタンスだけ動かせば無料枠からはみ出ることは無い(弊害はありそうだが)
  • というわけで、app.yamlを以下のように書き換えた(正確には覚えてないけど確かこんな感じ)。この設定でインスタンスが勝手に1台以上立つことはない。完璧だと思ってた。
runtime: go
env: flex

automatic_scaling:
  min_num_instances: 1
  max_num_instances: 1

お金が減り続ける

  • 残り 320 日で、¥17,017です
  • 残り 319 日で、¥16,420です
  • 残り 317 日で、¥16,214です
  • 残り 316 日で、¥16,011です

  • 残り 314 日で、¥15,393です

  • 残り 313 日で、¥15,392です
  • ...
  • うわああああああああああああああああああ!!!!!
  • なぜかお金が減り続ける。
  • インスタンスの状況を確認しても、1つしか立っていない。なので、お金が消費されるはずが無い。
  • 「1 日あたり 1,000 回の検索オペレーション、10 MB の検索インデックス作成」という謎の項目もあんまり関係なさそう
  • なので、料金履歴を見てみることにした。最初からそうしていればいいじゃんって感じだけど、料金表みても何にお金使ったかが分かりづらい。
  • とりあえず、料金表を調べてみた。料金表の内容をコピペしてググると、Stack Overflowの記事が見つかった。
  • 記事によると、「App Engineのバージョンが複数あることに原因がある」みたいなことを言ってた。以下の画像では「11件のバージョン」と表示されている。これが無駄らしい。なので、最新バージョン以外を消してみた。はい、一件落着。

f:id:nomikura:20181101214958p:plain

お金が減り続ける2

  • 状況は以前と変わらず、お金が減り続ける。うーん、つらい
  • わけ分からん部分で8000円くらい吹っ飛んでたりして、笑えてくる。
  • 次は、料金表の怪しい部分に焦点を当てて調べてみた。
  • その結果、料金は以下のように使われていることがわかった。(英語版の料金一覧ページで「Core Hours」という単語が見つかったので、この辺が怪しそう)

f:id:nomikura:20181101215018p:plain

  • そこで、日本語版の料金ページの表を参考に、料金を計算してみた。

  • すると、 以下のように対応することがわかった。計算してこの3つが対応することを確認した。

料金表の文章 リソース
App Engine Flex Instance RAM Japan メモリ
App Engine Flex Instance Core Hours Japan vCPU
Compute Engine Storage PD Capacity in Japan 永続ディスク
  • 実際に見た料金表は、以下の表である。これを見て分かるんだけど、「フレキシブル環境で動く」みたいなことが書いてある。何も知らずに今まで動かしてきたため、フレキシブル環境とは???と思った。そして、色々調べた結果、フレキシブル環境は無料枠が無いことが判明した!!!(うーん、これはひどい

f:id:nomikura:20181101215047p:plain

GAEの動作環境

  • 料金表のページに普通に書いてあったんだけど、GAEの動作環境は「スタンダード環境」と「フレキシブル環境」があるみたい。
  • スタンダード環境では無料枠が使えて、フレキシブル環境では無料枠が使えない。
  • 僕は今までそれを知らずにフレキシブル環境で動かしていた。元々クイックスタートを参考にして、これをベースに進めていた。そして、このページのタイトルに大きく書かれているがこれは「フレキシブル環境でのGoのクイックスタート」だった。うーん、このミスはひどい。
  • というわけで、今フレキシブル環境で動かしている者をスタンダート環境で動かせば良いことがわかった。

スタンダード環境を試してみる

  • スタンダード環境で動かすために必要なことを調べた結果、app.yamlをスタンダード環境用に書き換えれば良いことがわかった。なーんだ、簡単じゃん!!
  • GAEでGo言語製ウェブサーバーのためのapp.yamlの基本的な書き方というブログを参考にした。この記事を見ると、app.yamlenv: standardと書き込めばいいっぽい。けど、これを書き込んでデプロイしても怒られる。このあと色々してもよくわかんなくなった。
  • スタンダード環境のクイックスタートがあったので、それを参考にした。このページに載ってるHelloWorldのコードをコピペしてデプロイしたらちゃんと動いた。
  • コンソールからバージョンを見ると、「標準」と表示されるようになった。いままでは「フレキシブル」だった。これはスタンダード環境で動いているということだろう。

Future Contestをスタンダード環境に切り替える

  • 先ほどのHello, worldのプロジェクトで使ったapp.yamlをそのままFuture Contestで使ってデプロイしてみた。
  • デプロイには成功するが、サイトを見ても「500 (何かしらのメッセージ)」が表示される。ステータスコード500は、サーバー側にエラーが起きたことを表す(このとき知った)。なので、GAEのエラーログを見た。
  • すると、該当箇所が見つかった。GETリクエストをしている部分だった。
  • 調べたところ、Issuing HTTP(S) Requests)という公式ドキュメントが見つかった。これによると、スタンダード環境では以下のようにGETリクエストを送る必要があることがわかった。
func handler(w http.ResponseWriter, r *http.Request) {
        ctx := appengine.NewContext(r) // これを作る必要がある
        client := urlfetch.Client(ctx)
        resp, err := client.Get("https://www.google.com/")
        if err != nil {
                http.Error(w, err.Error(), http.StatusInternalServerError)
                return
        }
        fmt.Fprintf(w, "HTTP GET returned status %v", resp.Status)
}
  • 該当部分を書き換えたが、まだエラーは消えなかった。次に出たエラーは、ファイル読み書きの部分だった。どうやらスタンダート環境では通常の方法でファイル読み書きをする事はできないようだ。
  • 調べたところ、Google Cloud Storageを使うと良いことがわかった。5GBが無料で使えるので、安心して使えそうだ。
  • 大体の使い方はGitHubに載っていた。これを参考に該当箇所を変更したところ、いつも通りサイトが動いてくれた(クラウドストレージで結構手こずったけど)

定期的に更新する

  • このサイトは、各コンテストサイトから5分に一度情報を取得する。
  • 今まではこの部分をゴルーチンを利用して関数呼び出していたが、スタンダード環境だとそれができなさそう。なぜなら、スタンダート環境では以下のようにctxを作らないと外部操作ができない(たぶん)。ctxを作るには*http.Requestの情報が必要であるが、この関数はユーザがこのサイトにアクセスしたときにしか呼び出されない。
func handler(w http.ResponseWriter, r *http.Request) {
        ctx := appengine.NewContext(r) // これを作る必要がある
}
  • 解決方法としては、5分に1回このサイトにアクセスすれば良いのでは?と思う。調べてみると、cron.yamlというファイルにそういった設定を書き込めるようだ。cron.yamlリファレンスがあるので、それを参考にして書いた。
  • これで大丈夫だろうと思ってデプロイしたが、5分に1回呼び出す処理が出来ていない。これは罠なんだけど、gcloud app deployではcron.yamlはデプロイされない。gcloud app deploy cron.yamlというコマンドを打ってようやくcron.yamlがデプロイできるようだ。
  • このコマンドを打ったらちゃんと動いてくれた。

その他

AtCoderAPIサーバーを立てる

  • Future ContestはAPIを叩くだけのシンプルな機能にしたかった。AtCoderスクレイピングしていたので、AtCoderコンテストのAPIを別に用意した。
  • コンテスト用のAPIkenkooooさんが製作したものがあるが、過去のコンテストのみを扱っている。僕は開催予定のコンテストを含めた全てのコンテスト情報が欲しかったため、自前で用意した。
  • フレームワークを使った方が楽そうだったので、Ginというフレームワークを使った。これもフレキシブル環境とスタンダート環境では書き方が少し違う。
  • Ginを用いたHello world(スタンダード環境)を参考にコードを書いた。
  • 通常のnet/httpで書くハンドラとGinで書くハンドラは少し違う。違いは以下のようである。スタンダード環境では*http.Requestの情報が必要なため、それを取得するコードを書く必要がある。w, rの取得方法はIssueに載ってた(もっとわかりやすいページがあるのかも知れないけど)
// 通常のハンドラの書き方
func handler(w http.ResponseWriter, r *http.Request) {
        ctx := appengine.NewContext(r)
}

// Ginでのハンドラの書き方
func handlerGin(c *gin.Context) {
  // 以下で通常net/httpで使っていた値を取得できる
  var w http.ResponseWriter = c.Writer
  var r *http.Request = c.Request
}

ページがプレーンテキストとして表示される

  • ページがHTMLとして表示されず、プレーンテキストとして表示されたしまった。他のサイトのレスポンスを見たところ、レスポンスヘッダにcontent-type: text/htmlが付いていることがわかった。このときのFuture Contrstはcontent-type: text/planeであった。なので、content-type: text/htmlに設定したらページがHTMLとして表示された。
  • GinでHTMLテンプレートを扱えるらしいんだが、僕の場合は上手く動かなかった。なので、通常のテンプレートエンジンを用いた。

ページが更新されない

  • キャッシュが消えず、更新しても同じページが表示される現象が起きた。ブラウザのキャッシュを消すスーパーリロードを試したがダメだった。原因はGAE側のキャッシュにあった。GAE側のキャッシュを消すことでこの問題は解決した。
  • キャッシュが追加されたのは、このブログを参考にして書いたcache-control: public, max-age=3600が原因だと思う。これをレスポンスヘッダにくっつけるとキャッシュが使われるそう。これを消したらキャッシュは使われなくなった。
  • キャッシュは高速な処理を可能にする技術ではあるが、ページが更新されないのは面倒なのでキャッシュは使わないことにした。上手い使い方があるのかも知れないが,よく分からない。

結果

  • 無料運用できたー!わーい!
  • それなりに時間をかけてしまったけど、これが今の実力ということで... f:id:nomikura:20181101220419p:plain

感想

  • 個人のブログは問題解決の足がかりにはなる。しかし、初めて読むにしては内容が不十分な場合がある。なので、結局公式ドキュメントを見た方が早いことがわかった。
  • ただ、公式ドキュメントは分量が多くて全てに目を通すのは大変である。なので、ググって出てきたブログが参考にしている公式ドキュメントを見るのが最適かなぁとか思ってる。調べ方に関してはよく分からん...
  • かなり遠回りをしてしまった気がする
  • 今回はパワポアーキテクチャかいた。draw.ioをちょっと触ってみたが、すごい使いやすかった。最初からこれ使えば良かった...

これから

  • GitHubのREADMEを書き直す。ライセンス(MITみたいな)と、使用方法。みんな以外と使いたがるらしいので書くつもり。
  • CodeforcesJSONがたまに取得できない。なので、その辺をなんとかしたい
  • GAEでは無料でDBが使えない。herokuだと無料でDBが使えるみたいなので、次はherokuを使ってみたい

初めてWebサイトを作ってみた

まえがき

  • どうやって作ったっけなー...って思い出すのだるいからどうやって作ったかとかを書いとく
  • 後で読み返して「懐かしいな~」みたいなことを言いたい
  • とりあえず動くことを目標にして作ったからいろいろヤバイかもしれない
  • サーバーサイドの知識ほとんど無くて間違ってること書いてるかもしれないので、指摘してもらえるとありがたいです

成果物

Future Contest

  • 複数の競プロサイトのコンテスト情報をまとめて表示してくれるサイト

開発に至った経緯

  • Twitterで「便利サイト作ってみた!!」みたいなのがたくさん流れてきて、僕もそういったWebサイトを作ってみたいと思った
  • AtCoder, Codeforces, CSA, yukicoderなど、普段使う競プロサイトのコンテスト予定を1つのサイトで見れるサイトが欲しかったので作ってみようかなーって感じだった
  • 僕がつくろうとしているサイトの上位互換みたいなサイトも見つけたが、なんか見づらかったので自分で作ることにした。
  • あと、いい感じの競プロカレンダーもあったけどカレンダーだと月ごとにしか見ることができない。僕は予定されたコンテスト一覧を1つのページで見ることができるサイトが欲しかった。

機能とか

処理の流れ

f:id:nomikura:20180925174031j:plain

  • なんか解像度が死んでる。パワポで図を作ったんだけどなんか使いづらくね?なんか良い感じのツールあったら教えて下さい~(draw.ioっていうツールが便利っぽい?)

言語

  • Go言語
  • 選んだ理由は、高速に動くから
  • あと、他の言語が気に入らなかったので

クラウド

  • GAEを使った
  • 理由は、GAEだとすぐにサイトが作れそうだったから(公式のサポートが手厚かった)

対象サイト

コンテスト情報の収集

使ったツールまとめ

  • Advanced REST client
    • GETとかPOSTを簡単に送れる
    • ヘッダとかもつけて送れる
    • これを知る前はGoからプログラムを実行していた。こんな便利なツールがあるとは...
    • ただ、ちょっと重い気がする(もっと軽いツールあったら使いたい)
  • JSON-to-Go
    • JSONを貼り付けるだけでGoの構造体にパースしてくれる
    • 構造体が分かると、GoからJSONを読み込むのが楽になる
  • goquery

情報取得方法まとめ

サイト 方法
Codeforces API
CS Academy コンテストページにて、リクエストヘッダにx-requested-with: XMLHttpRequestを追加してGETリクエストを送るとJSONが返ってくる
AtCoder コンテストページにて、リクエストヘッダにcookie: language=jaを追加してGETリクエストを送る。返ってきHTMLをスクレイピングする。
yukicoder API

Codeforces

  • APIが公開されているのでそれを使った
  • APIの説明によると、gym=falseの時に通常のコンテストを取得してgym=trueの時に通常でないコンテストを表示するっぽいことがわかる。欲しいのは通常のコンテストサイトなのでこのURLにある情報を取得することにした

CS Academy

  • 公式がAPIを公開してなかったのでスクレイピングしようとした。ただ、スクレイピングではJS実行前の情報を取得するらしかった。なので、JSで構成されてるコンテスト情報を取得できなかったらしい。
  • 調べた感じ、phantomjsというツールを使えばJS実行後のコンテスト情報が取得できることがわかった。でも、使い方がよく分からなかった(後で分かるんだけど)
  • よくわからなくなったので、先輩に頼った。
  • すると、リクエストヘッダにx-requested-with: XMLHttpRequestを追加すれば良いことがわかった。なぜ分かったのかは以下に書きます(先輩に聞いただけですが)
  • デベロッパーツールを開いてNetworkをクリックし、ページを更新すると以下の画像のようなページになる。そこにあるcontestっていう2つのファイルが怪しい。1つはDocでもう1つはXHRだった。XHRの方のレスポンスを見ると、JSON形式で返ってきていた。XHRの方のcontestsをクリックするとリクエストヘッダとかが書かれてる。そこから、Advanced REST clientを使ってどのリクエストヘッダを送ればJSONが返ってくるかを実験する。実験の結果、x-requested-with: XMLHttpRequestをリクエストヘッダに追加すればJSONが返ってくることがわかった。

f:id:nomikura:20180925174025p:plain

AtCoder

  • 開発者ツールのNetworkで確認した感じ、APIは使われていないっぽい(あんまり詳しくないけど、ResponseでJSONを返すものが無かったからAPIは使われていないと判断した)
  • なので、スクレイピングしてコンテスト情報を取得することにした
  • でも、このサイトもCSAと同様にJS実行前のサイトがスクレイピングされたらしく、コンテスト情報が上手く表示されない。
  • なので、phantomjsを使うことにした。phantomjsのダウンロードはこのサイトがわかりやすかった。
  • pahtomjsを使ってスクレイピングすることには成功したが、GAE上にダウンロードできなかった。PaaSだからサーバー側はあまりいじれないらしい。なので、Goファイルと同じディレクトリにphantomjsの実行ファイルを置いて、Goから実行することにした。それをやってみたところ、次はpahtomjsのPATHが通ってないと怒られた。PATHを通そうとしたが、PaaSだからか知らないけどなんかうまくできなかった。なのでpahtomjsを使うことは諦めた。
  • このタイミングで先輩がどうやってCSAからJSONを返す方法が分かったのか聞いたので、その方法を試した。リクエストヘッダを全部試してみた。結局はリクエストヘッダにcookie: language=jaを追加すれば良いことがわかった。cookieの情報はかなり多く探すのが大変だった(実はこの辺の作業でやらかしたんだけど、それはまた別の話ということで)
  • リクエストヘッダにそれを追加してGETリクエストを送るとHTMLが返ってくるそれを頑張ってスクレイピングすればコンテスト情報を取得できる。スクレイピングにはgoqueryを使った。go get github.com/PuerkitoBio/goqueryをしてGoでimportすれば使えるのですごい楽だなーと思った。

yukicoder

  • このサイトを開発した当初、公式のAPIはなかった。カレンダーから情報を抜き取ることにした。しかし、GoogleカレンダーAPIを使う方法がよく分からなかった。色々調べたんだけどね。なので、デベロッパーツールから色々たどりまくってGoogleカレンダーのyukicoderのJSONが載ってるサイトまで辿り着いた。
  • だだ、今はAPIが公開されているので一瞬でコンテストデータの取得方法がわかるという...
  • いつか修正する予定

サーバー

  • サーバーって言うよりクラウドって言う方が正しいのかな?
  • 今回はGCPが提供する内のGAEを使ったと思う。というか手順通りにやってみただけなので、正直自分が何を使ってるのかとかよく分かってない。
  • このサイトに言語ごとの始め方が載ってる。手順通りにやればできるのですごいありがたい。
  • 3万円分のクレジットが1年間無料で使えるらしいので使ってみた。
  • DBとかも使ってみたいなーと思ってる。

見た目

  • HTMLとCSSをゴリゴリ書いた。
  • 開発後に知ったんだけど、Bootstrapっていう見た目を良い感じにできる便利ツールがあるらしい。
  • いろいろ苦労したけど、このブログ書くのが開発した1ヶ月後とかだからあんま覚えてない。

favicon

  • <link rel="icon" href="favicon.ico">を書いても表示されなかった
  • どうやらfaviconはサーバー側にアップロードしないといけないみたい
  • 他のサイトを参考にすると、サイト名/img/favicon.icoみたいにすると良いことがわかった
  • Golangで画像をアップロードする方法はこのサイトに書いてあった。以下のように書けば良いみたい。ただ、拡張子がicoだと上手く動かなかった(ここで割と時間使った)。拡張子をpngにしたら上手く動いた。つまり、以下のように書けばfaviconが追加できる(HTML側もいじらなきゃだけど)
func faviconHandler(w http.ResponseWriter, r *http.Request) {
    http.ServeFile(w, r, "relative/path/to/favicon.png")
}

func main() {
  http.HandleFunc("/favicon.png", faviconHandler)
}
  • もしかしたらfavicon用のURLがなくても良かったのかもしれないけど試してないからわからない。
  • faviconKaitoさんに作って頂きました!ありがとうございます!!

その他

時間の表示がおかしい

f:id:nomikura:20180925174033p:plain

  • 7時間早く表示されてしまう。
  • どうやらUTCで表示してるらしい。日本時間で表示したい(ホントは見てる場所によって時間変えたいけどサーバーから処理できるか分からない)。
  • なので日本時間にして表示した。この記事を参考にしたら無事直った。

エラー処理

  • とりあえずアプリは動いたけど、エラー処理がガバガバ過ぎるという指摘を受けた。

  • かなりヤバイ状況で使うらしいpanic()をよく分からずに普通に使っていた

  • hoge, _ := piyo()みたいに、アンダーバーでエラー処理を省いていたりもした。
  • エラーが発生したらfmt.Println()で標準出力に出力したりもしてしまっていた。
  • 他にも、エラー処理はよく分からないので結構適当に書いた
  • よく分からないが、とりあえず全部のエラー処理をlog.Print("適当なメッセージ: %v", err)にした。
  • 適切なエラー処理は未だによくわからない

これから

見た目

  • ファビコン追加したい
  • 表の見た目を改善したい
    • 本当は各サイトのロゴを入れたいけど、ロゴ使用の許可取る必要がありそうで面倒
    • サイトごとに表の色変えると良いのかなーとか思ってる
  • Aboutページとかあるとよかったかも
  • リンクをクリックしたら別タブで開くようにする

処理

  • AtCoderスクレイピング、コードがクッソ汚いから修正したい(できればAtCoderAPI追加してもらいたいけど...)
  • DBを使いたい。DBをローカル環境に追加しないと動作テストができない気がしてる(ちょっとだるい)。あと、お金も追加でかかりそうでつらい。

その他

  • Goでコンテスト情報のAPI提供してフロントのJSからAPIを操作した方が色々できそう?今はHTMLを作って返しているだけなので静的になってしまっているので色々改善したい。
  • 今回はGAEが楽そうだからそれを使ったけど、GCPにはそれ以外にもいろんな機能があるみたい
  • 1年間3万円のクレジットを無料で使うことができるのですが、無料トライアルは残り 321 日で、¥17,422.58 のクレジットがありますとか表示されてしまっている。44日間で12578円使用していることになります。これは破滅の道を歩んでますねー。なので、設定を上手いこと書き換えて無料枠で収まるように工夫しようと思ってます。

さいごに

  • まあそんな感じでとりあえず動くサイトを作ることができました。
  • 記事中で気になることがあれば教えてほしいです。「もっと効率的な方法があるよ~」とか
  • 何も考えずに作るだけなら苦労しないが、修正とかが大変だなーと思った(精神的にも)。今回はとりあえず動くことを目標にしたこともあって、かなりコードが汚い。次に作るときは構成を考えてから書きたい。

Cyber Agent アドテクコンペ2018参加記

まえがき

  • Cyber Agentのアドテクコンペでサーバーサイドとして参加しました
  • みねさんが「参加記書いてOK」みたいなこと言っており、得たものもあったので記事を書くことにしました
  • 技術的なことは僕がよくわからないのであんまり話さないです
  • 自分用に書いたので可読性が死んでますが許してください

参加に至るまで

  • 某サイトにCyber Agentの長期インターン情報が載ってたので応募してみました。面接したら、「経験が浅いから長期インターンは厳しいです。ただ、短期インターンもやってるので参加してみませんか?」と誘われたので参加の意思を表明しました。その後ES出したり面接したりしてアドテクに参加することになりました。
  • コンペではサーバーサイドの実装を担当することになるので、それまでにサイトを1つ作ってみました(これ)。
  • サーバーサイドに触れるのは初めてで、1ヶ月ちょいしかやってないので不安しかなかったです。

0日目(9/20)

  • コンペが始まる前にチームで顔合わせしようということになり、サイゼに集まってみんなで話しました。
  • メンバーは以下のような感じ。
どんな人か
N君 データ分析とサーバーサイドの両方ができるプロ。英語ペラッペラ。
K君 データ分析のプロofプロ。「ぶち上げ」という言葉が大好き
くまさん サーバーサイドのプロ。PHPの使い手
Goがちょっと書ける。サーバーサイドの知識は壊滅的
  • サーバーサイドの経験が浅いとは言え、サイトを1つ作れたからまあなんとかなるでしょとか思ってました。ですが、サーバーサイド担当の相方であるくまさんと構成の話をしたときに悲劇が起りました。なんと彼が何を言っているのか僕には全然分からなかったのです。というのも、僕に知識がなさすぎて専門用語がまったくわからないという現象が発生しました。「わからないならググればいいじゃない!!」といった感じなのですが、専門用語の数が尋常じゃなかったのでググっても間に合わないレベルでした。あと、自分で構成を考えたことが無かったため、どう考えれば良いのかもよく分からなかったです。なのでほとんど技術的な会話ができず、くまさんとN君で構成の話をしてました。ホント申し訳ない...
  • パスタ安くて美味しかったです。

1日目(9/21)

  • 他のチームから強く見られるためにチーム全員で会場入りして強者の風格を見せつけるつもりでした。ですが会場入りしたときに会場が開いておらずアルマゲドンごっこができませんでした。「あのチームやばくね?」とか言われたかった人生でした
  • 最初はいろんな説明がありました。クラウドで使うGCPについて、お金は特に気にせずに使っていいと指示が出ました。太っ腹すぎてビビりました。
  • 午前中は、3日間の予定を組みました。
  • 午後からは実装に移りました。ただ、僕は全然わからないのでほとんどの作業をくまさんに丸投げ状態でした。僕はくまさんの指示待ち状態でした。2人で技術的な話をするのが理想なのですが、僕に話を振られても「すいません。よくわかりません」というSiriみたいな返答しかできず申し訳なさでいっぱいでした。ですが、指示されたGoの実装はまあまあできた気がしています(ホンマか?)
  • 夜はオムカレーを食べました。おいしかったです。
  • その後カフェで作業しました。当初はPythonからGoを呼び出す予定だったので、その辺の処理を書いてました。まあこの処理結局使わなかったんですが...
  • ホテルではcsvを読み込んでデータ加工し、gobファイルに吐き出すといった処理を書いてました。

2日目(9/22)

  • 前日の夜に速度テストして、かなり遅かったらしいのでここで大きく方針を変えます。当初はGoからPythonを呼び出して機械学習させ、その結果を返す感じの処理をする予定でした。ですが、GoからPythonを呼び出す辺りで時間がかかったらしく、APIの一部はDjangoを使って処理することになったみたいです。この文章、何言ってるかよくわかんないと思うんですが僕もよくわかってないです(最悪)。
  • 午前中、くまさんはAerospikeというDBをGoから呼び出す処理を書いてました。僕はSSPからPOSTを受け取って、その内容を加工してJSONを公開するみたいなAPIを書いてました。僕もよく分かってないですが、指示通りのことはたぶんできたと思ってます。
  • 午後はくまさんとペアプロをしました。普段PHPを使ってるくまさんがスムーズにGoを書けるようサポートしました。僕がやったのはそれくらいで、ロジックの部分はほぼくまさんに丸投げでした。
  • Djangoの方もつらそうでした。
  • データ分析は結構順調そうでした。
  • この日は全体的な動作確認ができないまま終わりました。
  • 夜はどうしてもAtCoderに参加したかったので残業はしませんでした。

3日目(9/23)

  • 最終日です
  • DjangoとGoの連携とかをやっていました。僕は特になにもできないので無事動くよう祈りを捧げつつ、自分が分かる範囲でスライドを作ってました。ただ、僕が作ったスライドの完成度があまりにも悪かったため、忙しいくまさんの手を煩わせてしまいました。
  • SSP側を動かし始めて1時間くらい経ったときに、DSPが上手く動くことが確認できたのでわーいって感じでした。まあ僕は特に貢献できてないんですが
  • 午後は発表がありました。僕はくまさんが「彼がGoの実装を手伝ってくれました」と言ったときにペコペコする役をしました。構成や使用した技術に関する説明はくまさんに丸投げです。僕は最終日になっても構成とかを理解できてませんでした。なので頑張ってた3人と並んで発表台に立つのがちょっとつらかったです。他のチームの発表では、聞いたことも無い技術をさも当たり前のように話していて、実力の差を感じました。
  • この後は全員で夕飯を食べました。よくパーティーで見るような立ち食い形式のやつです。こういう形式だとボッチになりやすいので少し苦手でしたが頑張りました。チームメンバー以外とも話せて結構楽しかったです。
  • 最後に結果発表がありました。僕たちは分析賞を取りました。分析賞はデータ分析が秀逸でしたという賞で、僕は1ミリも触れてない部分です。データ分析班がプロでした。賞としてパスケースを貰いました。
  • 各チームの分析結果を見ました。僕たちの班だけ唯一入札処理ができて無くて何も表示されませんでした。メンターの方が「サーバーサイドの処理が上手くできていれば良いところまでいったかもしれないですねー」と言っていたので、それを活かし切れなかったので申し訳なさが半端なかったです。
  • 全ての日程が終了し、最後は社員さんや他の参加者と話しました。いろんな話が聞けてすごい楽しかったです。

さいごに

  • 技術的なことがほとんどできなかったにも関わらず、誰も僕を責めずに「次につなげよう」と言ってくれて嬉しかったです。メンバーに恵まれ、楽しく作業できたと思います。ただ、技術的なことがほぼできなかったのは本当に申し訳なかったです...
  • サーバーサイドの基本的な知識や技術は抑えておくべきだと思いました。というのも、専門用語などがほぼわからずに相方と意思疎通ができなかったからです。分からないことは全部ググればいいと思ってましたが、わからなすぎるとググっても間に合わないことが分かりました。
  • 複数人でGitを使ったのですが、一人で使ってるとadd, commit, pushくらいしか使わないのでpullとかmargeがよくわかんなかったです。これは複数人で開発して覚えるしかなさそう。
  • Cyber Agentの社員さんと話した感じ、すごい楽しそうな会社だなーと思いました。自由なことができて良さげです。
  • アドテクではほとんど何もできませんでしたが、得るものは大きかったです。アドテクを企画して下さった方々、参加者の方々、本当にありがとうございました。
  • いつかリベンジマッチ的なのをひとりでしようかなーって思ってます。

ICPC2018国内予選参加記

ICPCに挑むまで

  • 4月くらいに競プロ部に入って仲間を見つけた。わーい

メンバー

  • IDがわかんないから紹介できないという。全然交流しなかったね。
  • 色は水灰灰でっつ

コンテスト中

A問題

  • 後輩君が通しました

C問題

  • 僕が担当したやつ
  • 累積和と2分探索でいけるんじゃね?おいおい天才かよ...とか思ったけどなんかバグりました

B問題

  • 後輩君にまかせたけど無理って言われたから考えた
  • 実装考えてたら残り時間20分くらいになったので諦めました

2コマ漫画

感想

  • 思ったより自分が弱くてビビった(正直3完はできるとか思ってた)
  • 悔しい
  • 過去問全然解いてないという(は?)。埋めましょう
  • 来年は4完早解きしたいね

DPL_1_C「ナップザック問題」

DPL_1_C「ナップザック問題

考察

  • DPに使いそうな値を考える
    • 今回は01ナップザックみたいに何個目まで選んだかという情報は必要無い
    • 価値と重さが分ればいいかなーってなる
  • 価値と重さだけわかれば良いので1次元のDPでできそう
  • 同じ種類の荷物は何個でも使うことができるため、コイン問題のように考えることができる。
  • なので、コイン問題みたいに解けばできそう
  • 考察終了!


解法

手順

f:id:nomikura:20180616055444p:plain:w300

  1. 上図のようなDPテーブルを作る
  2. DPテーブルを$0$で初期化する
  3. 漸化式を立てて、そのコードを書く

漸化式

$\begin{array}{ll} dp[i] = max(dp[i], dp[i-w[j]]+v[j]) & (j \geq w[j])\end{array}$


コード

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e8;

int N, W;
int v[111], w[111];
int dp[11111];

int main() {
    cin >> N >> W;
    for (int i = 0; i < N; i++) { cin >> v[i] >> w[i]; }

    // DP
    for (int i = 0; i <= W; i++) {
        for (int j = 0; j < N; j++) {
            if (i >= w[j]) {
                dp[i] = max(dp[i], dp[i-w[j]]+v[j]);
            }
        }
    }

    cout << dp[W] << endl;

    return 0;
}


要点

  • DPに必要な情報が何かを考えること。
    • このとき考えるのは答えを求めるのに必要最低限の情報だけにする。
  • コイン問題に帰着できることに気がつくこと。

感想

  • 1次元のDPはだいたいコイン問題に帰着できる説が浮上しつつある(ホンマか?
  • なんとなくで解いたのでまだ確信が持てないという...

DPL_1_B「0-1 ナップザック問題」

DPL_1_B「0-1 ナップザック問題」

解法

f:id:nomikura:20180616043824p:plain:w450

  1. 上図のようなDPテーブルを用意する
  2. テーブルをすべて$0$で初期化する(グローバルに宣言していれば初期化する必要は無い)
  3. 漸化式を立て、それをコードとして書く


漸化式

$$ dp[i][j] = \left\{ \begin{array}{ll} max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]) & (j \geq w[i]) \\ dp[i-1][j] & (j \lt w[i]) \end{array} \right. $$


部分的に見る

f:id:nomikura:20180616055904p:plain:w500

  • いきなり全体的なことを考えると頭が爆発するので一部分に注目してみる
  • $dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]+v[i]])$という式について
    • maxの左側は$v[i]$を選ばない場合を表す
    • maxの右側は$v[i]$を選ぶ場合を表す
    • 両方の値を比較して大きい方が$dp[i][j]$になる


コード

#include <bits/stdc++.h>
using namespace std;

int N, W;
int v[111], w[111];
int dp[111][11111]; // dp[i][j]: 重さ制限jで個数iまで見たときの最大の価値

int main() {
    // 入力
    cin >> N >> W;
    // インデックスを1つずらしている
    for (int i = 0; i < N; i++) { cin >> v[i+1] >> w[i+1]; }

    // DP
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= W; j++) {
            if (j >= w[i]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout << dp[N][W] << endl;

    return 0;
}
  • 便宜上、入力の際に重さと価値のインデックスを1つ先へずらした
  • 集めるDPはdp[i][j] = 遷移元の形にしたい。
  • 読みにくいかもだけど、書き方は他の問題も見て検討する


要点

  • $dp[i][j]$を求めるとき、$dp[i-1][W]$までは既に求められていることが前提となっている。
  • なので、$dp[i][j]$を求めたいときに、それ以前がどんな状態であるかは考える必要が無い。
    • これを頭に置いておかないと考えることが多くて頭が爆発する