日記

のみろぐ

主に競プロ日記です

コイン問題

考察

  • 状態変数を考える
  • dp[i円の最小枚数]でいけそう。50000円がMaxだから制約的にも行けそう
  • 次に遷移を考える
  • dp[i] ← dp[i-c[j]] + 1みたいな感じで行けそう。計算量も$O(nm)$で余裕がある。最大で$106$ステップだし

解法

  • dp[i円の最小枚数]という状態を持つ
  • dp[i] ← dp[i - c[j]] + 1という遷移を行う

コード

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

#define int long long

const int INF = 1e15;

int dp[55555];
int c[22];

int n, m;

signed main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> c[i];
  }

  fill(dp, dp+n+5, INF);
  dp[0] = 0;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      if (i - c[j] >= 0) {
        dp[i] = min(dp[i], dp[i-c[j]] + 1);
      }
    }
  }

  cout << dp[n] << endl;

  return 0;
}

メモ化再帰で解いてみる

再帰

  • これはTLE
  • 計算量は$O(mn)$
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

int dp[55555];
int c[22];

int n, m;

int rec(int money) {
  if (money == 0) {
    return 0;
  }

  int ans = INF;
  for (int i = 0; i < m; i++) {
    if (money - c[i] < 0) continue;
    ans = min(ans, rec(money - c[i]) + 1);
  }

  return ans;
}

signed main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> c[i];
  }

  cout << rec(n) << endl;

  return 0;
}

メモ化再帰

  • 蟻本のナップサックのメモカ再帰っぽく書ける
  • 計算量はたぶん$O(nm)$
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

int dp[55555];
int c[22];

int n, m;

int rec(int money) {
  // 終了条件
  if (money == 0) {
    return dp[money] = 0;
  }

  // 計算済みならその値を返す
  if (dp[money] != INF) {
    return dp[money];
  }

  int ans = INF;
  for (int i = 0; i < m; i++) {
    if (money - c[i] < 0) continue;
    ans = min(ans, rec(money - c[i]) + 1);
  }

  // 計算した値をメモする
  return dp[money] = ans;
}

signed main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> c[i];
  }

  fill(dp, dp + n + 10, INF);
  cout << rec(n) << endl;

  return 0;
}

観音堂

考察

  • 状態変数を考える
  • dp[i段目までの組み合わせの個数]で出来そう
  • 次に状態遷移を考える
  • 初期位置から1, 2, 3段目は1通りあるので、dp[1] = dp[2] = dp[3] = 1で初期化する。
  • 遷移はdp[i+1] += dp[i]とかで出来そう

解法

  1. dp[i段目までの組み合わせの個数]という状態を持つ
  2. dp[1] = dp[2] = dp[3] = 1で初期化する
  3. 遷移は以下の通り
dp[i] → dp[i+1]
            → dp[i+2]
            → dp[i+3]

コード

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

#define int long long

int dp[50];
int n;

// 前計算
void init() {
  dp[0] = 1;
  for (int i = 0; i <= 30; i++) {
    for (int j = 1; j <= 3; j++) {
      dp[i+j] += dp[i];
    }
  }
}

signed main() {
  init();
  while (1) {
    cin >> n;
    if (n == 0) break;
    int mult = 3650;
    cout << (dp[n] + mult - 1) / mult << endl; // 切り上げ
  }

  return 0;
}

自分で書いたコード

  • 思いついたまままに書いたコード
  • min(1LL, hoge)は、一度提出してWAが出たから直した部分(ローカルでちゃんと確認しなかった)
  • 切り上げ、最近使わないのですっかり忘れてた

メモ化再帰で解いてみる

再帰のコード

  • これ、$O(3N)$だから通らないと思ったけど通っちゃったよ。えー、なんでー?
#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;

int rec(int stage) {
  // 終了条件
  if (stage == 0) {
    return 1;
  }

  int ans = 0;

  for (int i = 1; i <= 3; i++) {
    if (stage - i < 0) continue;
    ans += rec(stage - i);
  }

  return ans;
}

signed main() {
  while (1) {
    cin >> n;
    if (n == 0) break;
    int ans = (rec(n) + 3650 - 1) / 3650;
    cout << ans << endl;
  }

  return 0;
}

メモ化再帰のコード

  • 蟻本のナップサックのメモ化再帰みたいに書ける
#include <bits/stdc++.h>
using namespace std;

#define int long long

int n;
int dp[55];

int rec(int stage) {
  // 終了条件
  if (stage == 0) {
    return dp[stage] = 1;
  }
  
  // 一度求めた値の場合、メモしたやつを返す
  if (dp[stage] != -1) {
    return dp[stage];
  }

  int ans = 0;

  for (int i = 1; i <= 3; i++) {
    if (stage - i < 0) continue;
    ans += rec(stage - i);
  }

  // 値を求めたらメモる
  return dp[stage] = ans;
}

signed main() {
  // 前処理
  fill(dp, dp+33, -1);
  rec(30);

  while (1) {
    cin >> n;
    if (n == 0) break;
    int ans = (dp[n] + 3650 - 1) / 3650;
    cout << ans << endl;
  }

  return 0;
}

感想

  • 状態変数考えて遷移書いたらなんか上手くいった。問題文に「値が大きくなる」と書いてあったので、この遷移で値大きくなるのか〜?みたいに思った(実際大きくなったけど)
  • なんでただの再帰で解けるんだ?計算量的に無理では?

AtCoderにおける言語ごとの提出率

まえがき

調査結果

  • 下の円グラフは、AtCoderでACした提出の言語ごとの割合です。
  • C++は6割を占める圧倒的シェア数です。

言語ごとの提出割合(円グラフ)

C++競技プログラミングをすることの利点

結論


  • この下はおまけ

提出言語ランキング詳細

  • 以下の表はAtCoderでACした提出の言語ごとのランキング詳細です。
  • ACした提出は全部で1413562個でした。
順位 言語 提出数 割合(%)
1 C++ 895284 63.335
2 Python 193847 13.713
3 Java 96232 6.808
4 C 54129 3.829
5 Ruby 42918 3.036
6 C# 35346 2.5
7 Haskell 17511 1.239
8 Rust 10057 0.711
9 D 8873 0.628
10 PyPy 6509 0.46
11 Go 6186 0.438
12 PHP 5652 0.4
13 JavaScript 4399 0.311
14 Scala 4385 0.31
15 Perl 3992 0.282
16 OCaml 3440 0.243
17 Kotlin 3093 0.219
18 Pascal 2806 0.199
19 Bash 2786 0.197
20 Nim 2652 0.188
21 Text 2416 0.171
22 Common Lisp 1437 0.102
23 Awk 1365 0.097
24 Brainfuck 830 0.059
25 Julia 740 0.052
26 Fortran 732 0.052
27 Scheme 728 0.052
28 Sed 551 0.039
29 Perl6 528 0.037
30 Octave 515 0.036
31 F# 439 0.031
32 Visual Basic 423 0.03
33 Clojure 355 0.025
34 IOI-Style C++ 328 0.023
35 Crystal 305 0.022
36 TypeScript 264 0.019
37 Swift 243 0.017
38 Standard ML 238 0.017
39 COBOL - Free 232 0.016
40 Objective-C 210 0.015
41 Lua 178 0.013
42 MoonScript 152 0.011
43 LuaJIT 88 0.006
44 COBOL - Fixed 63 0.004
45 Ceylon 54 0.004
46 Unlambda 51 0.004

調査について

調査したもの

  • AtCoderにおける言語ごとの提出率

使用したもの

調査方法

  • プログラムでAPIを叩いて結果を集計した。
  • 言語はGoを使用した

ソースコード

package main

import (
    "encoding/json"
    "fmt"
    "io/ioutil"
    "log"
    "net/http"
    "sort"
)

// 言語ごとのAC数を表す構造体。APIを叩いて受け取るJSONがこの形式
type AcceptedCountForEachLanguages struct {
    UserID   string `json:"user_id"`
    Language string `json:"language"`
    Count    int    `json:"count"`
}

// 最終結果の構造体
type Result struct {
    Language string
    Count    int
}

func main() {
    // GETリクエストを送る
    response, err := http.Get("https://kenkoooo.com/atcoder/atcoder-api/info/lang")
    if err != nil {
        log.Fatal(err)
    }

    // JSONを構造体のスライスにパースする
    var acceptedCountForEachLanguages []AcceptedCountForEachLanguages
    byteArray, _ := ioutil.ReadAll(response.Body)
    json.Unmarshal(byteArray, &acceptedCountForEachLanguages)

    // 言語ごとの提出数をカウントする
    languageCount := make(map[string]int)
    for _, user := range acceptedCountForEachLanguages {
        languageCount[user.Language] += user.Count
    }

    // ソートするために構造体の配列を作る
    var results []Result
    for language, count := range languageCount {
        results = append(results, Result{Language: language, Count: count})
    }

    // resultをカウントが多い順にソートする
    sort.Slice(results, func(i, j int) bool {
        return results[i].Count > results[j].Count
    })

    // 結果を出力する
    for _, result := range results {
        fmt.Println(result.Language, result.Count)
    }

}

AtCoder Virtual Contest Tweet ButtonっていうChrome拡張作ったよ!!

AtCoder Virtual Contest Tweet Button

まえがき

作ったものについて

f:id:nomikura:20181204221448p:plain
使用時のスクショ

概要

  • AtCoder Virtual Contest Tweet ButtonというChrome拡張機能を作りました
  • その名の通り、AtCoder Virtual Contestのコンテスト内容を簡単にツイートできるボタンです。

  • Chromeウェブストアからダウンロードできます。

  • AtCoder Virtual Contestのコンテストページで拡張機能のアイコンをクリックすると、内容が自動で補完されたツイート画面が表示されます。
  • 使ってみてね!!(急にフレンドリー)

作った動機

  • バーチャルコンテストを開くことをTwitterで呼びかけるとき、いちいちコンテスト内容を打つのが面倒だったので作った
  • たぶんnotさんにお願いすればツイートボタンを作っていただけたと思うのですが、どうしてもChrome拡張機能を作ってみたかったので作っちゃいました。ごめんなさい!!!

開発ログ

  • HTML, CSS, JSの知識があれば大丈夫という事前知識があったので楽勝だろうと思ってたけど意外と苦労した。
  • ソースコードGitHubに載ってます
  • 以下の文章はChrome拡張を1日触っただけの人間が書くものなので正確性は保証しません。

拡張機能の大枠を作る

  • 公式ページにはプロジェクトファイル内にmanifest.jsonを書けばとりあえず動くみたいなことが書いてあった。ここに次々と追加していく感じなんだろうなーといった感想だった。
  • ただ、公式ページではいきなり知らないAPI使い出すし、マニフェストファイルの書き方もピンことなかった。もっと簡単な例あるだろ...って感じだけど、Google天才集団の知能に僕が追いつけてないだけなので泣きながらググりまくりました。えーん。
  • ググりまくって、マニフェストファイルの書き方も少しわかってきたので、実装に移ります。

HTMLからコンテスト情報を取得する

  • これができないとなにもできないのでいちばん最初に取り掛かった
  • ツイートに必要な情報は、「タイトル」、「時間」、「説明」、「URL」の4つ。最初はペナルティ情報も必要だと思ったけどバチャにおいてペナルティは重要じゃないので省いた。
  • 該当部分のソースコードは以下のような感じ。
<h1 class="page-header">
    ゴリラジオ体操第141
    <small class="pull-right">ペナルティ5分 / 2018-12-05 06:25:00 ~ 2018-12-05 07:10:00</small>
</h1>
<p>基本的に平日毎朝、決まった時間にABCのB~Dをやってます。誰でも歓迎です!</p>
  • h1タグにpage-headerってクラス名がついている。なので、document.getElementsByClassName('page-header')とすればいい感じのデータが取れる。
  • コンテストの説明文は、h1タグの下にある。これを取ってくる方法をググったところ、nextElementSiblingというのがあった。headerTag.nextElementSiblingみたいなコードを書いたら説明文を取得できた。

アイコンのクリックを検知する

  • 当初はページ内にツイートボタンを置く予定だった。だが、HTMLの書き換えが原因でページの挙動がおかしくなったりするのがこわかった。なので、拡張機能のアイコンをクリックしたらツイートするウィンドウが表示される形式にしようと思った。
  • アイコンの検知は、バックグラウンドで行う。マニフェストファイルのbackgroundの項目にJSファイルを追加して、そこに実装する。バックグラウンドの処理はずっと走ってるらしい。なので、バックグラウンドでユーザーの動きを検知するんだろうなーって感想。
  • 実装はだいたい以下のような感じ。
chrome.browserAction.onClicked.addListener(() => {
    // クリックされた時の処理を書く    
);

ツイート画面を開く

  • アイコンのクリックを検知したらツイート画面を開く処理を書く。
  • ツイートを開くには大体以下のような感じの処理を書く。これを書くと、新しいウィンドウが開く。
const url = 'https://twitter.com/intent/tweet?text=' + 'ここにツイートする文章を入れる';
window.open(url, null, 'ここでウィンドウの大きさとかを指定');

HTMLから取得した情報をツイート画面に反映させる

  • これがいちばん大変だった。すべてバックグラウンドで処理できると思っていたが、これはファイルをまたいだ処理が必要だった。ファイルをまたいだ処理はAPIを使用して行う。
  • Chrome拡張でとっても役立つAPIのまとめ」と「Chrome拡張でruntime.sendMessageのコールバックがうまく動作しない理由」の2つの記事を元に処理を書いた。公式ドキュメントみてもよくわからん。
  • いろいろ頑張った結果、裏処理と表処理をつなぐコードは以下のようになった。バックグラウンドでクリックを検知すると、content側に処理を投げる。content側ではHTMLから情報を取得する処理が走る。そして、それをツイート画面に反映させる。おしまい。ちょっと説明が雑になったが、処理部分は全部書き終わった。

情報を送る側(background)

chrome.browserAction.onClicked.addListener((tab) => {
    chrome.tabs.sendMessage(tab.id, {
        command: "create_tweet",
    },
    (msg) => {
        console.log("result message: ", msg);
    })
});

情報を受け取る側(content)

chrome.runtime.onMessage.addListener((msg, sender, sendResponse) => {
    // 処理
});

Chromeウェブストアにアップロードする

感想

  • そんな感じで、無事アドカレ間に合いました!!よかった!!
  • 1日中拡張機能触ってたのですごい疲れた。
  • なかなか動かなかったりしたからすげー焦った。やばいwwおわんねえwwwwみたいな気持ちだった
  • その分、動いた時はくっそ嬉しかったですが
  • 今まで手が出せていなかった拡張機能だったけど、アドカレをきっかけに触ることができて満足。かぎつきくんありがとう!!

  • 自分の作ったものがストアに載るのすげー面白い。感動した。

  • またなにか作りたい気持ちになりましたとさ。

追記

  • 僕の思いがnotさんに通じたようで、AVCにツイートボタンが実装されました!!僕の拡張は忘れても僕のことは忘れないでください!! のみより
  • 公式のハッシュタグが#AtCoderVirtualContestだったので、ハッシュタグをそれに合わせました!(もともとは#AtCoder_Virtual_Contestだった。その際、manifest.jsonの記述を"version": "0.0.1"から"version": "0.0.2"に変更した。そうしないとアップロードでエラーが出た。

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を使ってみたい