ICPC 2018 国内予選 参加記

はじめに

ACM-ICPC 2018 Asia Yokohama Regionalにチーム super_ikd で参加しました。結果はABCの3完103位でした。

チーム

チーム名:super_ikd

メンバー
  • niyarin さん

    研究が忙しそう!

  • srup さん

    問題の解法検索したらブログがよくヒットする!

  • ikd (自分)

コンテスト

  • BとCとDの問題文を印刷します
  • 事前に話し合っていたとおり、Aをniyarinさん、Bをsrupさん、Cをikdがやります
  • ikdがCを誤読してる間にniyarinさんがAを通します (00:08:11)
  • srupさんがBの解法(方針)をniyarinさんに伝えて、ほどなくしてniyarinさんが実装を始めます。ikdはまだ誤読をしています。srupさんはDとEを読んでいる?
  • 誤読に気づいて、ちょっと問題が簡単になりました
  • O(n), n≦109 の解法ができてsrupさんに説明すると、よさそう感を共有できたので紙に簡単なコードを書いていきます
  • Bの実装がつらくなったそうなので、一旦交代してikdがCを書きます
  • 紙に書いておいたのを書き写すだけなので簡単です。バグります
  • printfデバッグしてもよく分からなかったので、適当に不等号のイコールを取ったり外したりするとサンプルが合います
  • テストケースをダウンロードして手元で実行すると、O(n)だけあってすぐには終わりません。10秒くらい待ってると結果が出力されます。簡単なケースを見つけて、出力が手で解いたのと一致しているのを確認して提出します。通ります (01:17:25)
  • niyarinさんがBのバグの原因が分かったとのことで実装を再開します
  • またまたsrupさんにDの解法を説明すると、よさそう感を得られたので実装を詰めます
  • 実装無理では・・・
  • ...
  • ...
  • ...
  • niyarinさんがBを通します (02:16:28)
  • ikdがパソコンの前に座ってDを書きます。niyarinさんとsrupさんはEを考えています
  • 書けません
  • ...
  • ...
  • ...
  • コンテストが終わります

おまけ

全問題はここから見られます → All Problems

C問題を担当したのでそれについて書きます。

C問題の概要

入力として整数$b$が与えられます ($1\le b\le 10^9$)

$\displaystyle\sum_{i=l}^{r}i=b$となるような$l, r$のうち、$r-l$が最大のものを求めてください

解法

条件を満たすl, rのうち、lが最小のものを答えればよさそう。

区間[l, r]の和がbを超えるような最小のrはlに対して単調なので尺取り的にやるとO(b)

実装
#include<iostream>
using namespace std;

int main(){

  while(true){
    int b; cin>> b;
    if(b==0) break;

    for(int l=1, r=1, sum=0; l<=b; ){
      while(sum<b) sum+=(r++);
      if(sum==b){
        cout<< l<< " "<< r-l<< endl;
        break;
      }
      while(sum>b) sum-=(l++);
    }
  }

  return 0;
}

雑なこと

yukicon-historyを作った - poのブログで書いた以外のことを書きます。

料金

Flexible Environmentを使うと、どうやっても料金が発生しそうな感じです。いまは1日300円くらいかかってます。高すぎ。

稼働していない時はインスタンスをオフにしておけばコストが抑えられそうですが、Flexible環境(の、少なくともrubyのランタイム)では常時1つ以上のインスタンスが立っていないといけないみたいです。

Standard Environmentを使って、Always Freeの範囲に収まるように稼働させれば、無料にできるはずです。

しかし、Standard環境ではrubyが使えないので、そのまま移行はできません。

無料トライアルでもらえる30,000円分のクレジットが尽きるまでにはStandard環境に移さないと終わりですね。

ここから追記

Google App Engine (GAE) をStandard環境にしたとしても、Cloud SQLを使っていると定額で料金が発生します(月1000円くらい?違うかも)。なので、基本無料で動かすには次の2つの方法が考えられます。

  • Google Compute Engine (GCE) のf1-microインスタンスを作成して、そこにrubyMySQLなどをインストールする
  • GAEのStandard環境でCloud SQLではなく、Cloud Datastoreを利用する

後者を試してみたいと思います。

追記ここまで 2018-06-28

うまくいきました (更新 2018-07-07)

Heroku

GCPというか、GAEにデプロイするのに3日くらいかかった*1んですが、HerokuならGetting Started on Heroku with Rails 5.x | Heroku Dev Centerを見れば5分くらいで終わります。しかし、無料プランで使えるDBのrecord数の最大が10,000で、微妙に超えてしまったので今回は使えませんでした。

実際に上限を超えると、

10,000行超えてるから、減らさないとアプリ止めるよ

みたいなメールが来ます(来ました)。

スクレイピング

スクレイピングというか、パースというか分かんないですが、今回のケースでは結構簡単でした。

  1. Chromeで順位表のページを開いてF12で開発者ツールを開く
  2. 取りたい情報付近のHTML Elementで右クリック、XPath*2をコピー
  3. NokogiriでXPathを使って良い感じにやる

Nokogiriのドキュメント読んでも全然分かんなかったんですが、サンプルコードからエスパーすると適当に使えます。正規表現もちょっと使えるようになりました(1文字以上の任意の文字、とか)。

rails

railsはver. 5からAPIモードができたみたいで、通常のと何が違うのか分からないけど、それを使いました。rails new my-app --apiとすればいいです。

はじめブラウザからアクセスして開発・デバッグしていたのですが、いちいちfaviconが無いことを怒られて嫌になったので途中からcurlコマンドを使いました。今まで、perlの亜種みたいなのだと思ってました(違いますね)。

curlで取得したjsonはそのままだと人間に見にくいので、jqを使うと多少ましになります。curl http://example.com | jqというふうに使えます。

React+TS

ライブラリの使い方がよく分からなくても、VSCodeでF12を押して「定義へ移動」を使いまくるとなんとなく使えることが多いです。

ただ、型定義ファイルが用意されてないとつらい(はず)です。

react-router-dom

/user/[:id] とかのルーティングや、example.com/?name=bob とかのquery parameterを使えるようにするやつです。本家はreact-routerなんだけど、たぶん上のをnpm installすると自動で付いてくるんだと思います。

アプリ全体を<BrowserRouter></BrowserRouter>で囲っておいて、コンポーネントをrenderするときに<Route component={MyComponent}/>とします。そうすると、propsとしてlocationやhistoryが渡されるので、props.location.searchで文字列?name=bobが取り出せます。また、query parameterを付与するときはprops.history.push({search: 'name=bob'})などとします。

javascript

axios

HTTPリクエストをすると、処理が非同期*3になってわちゃっとするんだけど、Promiseってのを使うと解決できるそうです。でもPromise使うのむずいから、axiosができました。捏造かもしれん。

axios.get('http://example.com').then((results)=>{ ... })

とすると、resultsの中に応答結果が入って、それを使って{ ... }の部分で処理ができます。リクエスト1回だけならこれでいいんだけど、複数回したいときとかどうするのか分かってないです。

CSSフレームワーク

Semantic-UI-React

Semantic-UI を使いました(見た目が好きなので)。

サンプルは<Form.Input />とかになってるけど、<FormInput />ってしないとちゃんと動かない気がします。

onChange / handleChange のヘルパーっぽい機能があってちょっと助かりました。

*1:そして、インスタンス数の設定とかをするのにも3日くらいかかった...

*2:XPathが何かは知らない...

*3:並行処理とは違うの?