日記

のみろぐ

主に競プロ日記です

WindowsでGraphillionの環境構築

はじめに

  • これを参考に環境構築していく
  • 詰まった部分が多かったのでメモ。
  • 結局どういう手順を通るのが最適なのかわからないのでやったことを全部書いた。読みづらい。
  • もっと簡単にインストールするする方法があったら教えてほしい。

モチベーション

  • 組み合わせ爆発のおねえさんを救うことができる。
  • 動画では10×10の組み合わせの数え上げに25万年かかってるけどGraphillionを使えば一瞬で終わる。かなり古い動画だけど今更使うの?時代遅れじゃない?とか言わないでほしい。

環境

  • Windows 10
  • プログラミング系のソフトは何も入っていない状態(コンピュータをセットアップしたばかりなので)

1. Anacondaをインストールする

手順

  1. windows用のAnacondaをダウンロードする。

  2. AnacondaのPATHを通してどこからでもPythonを使えるようにする。

2.Graphillionの実行に必要なツールをインストールする(これいらない)

  • WindowsではVisual C++ 2015 Redistributable Packagesをダウンロードする必要があるみたい。
  • 確かGraphillionは後ろでC++が動いてるから必要なんだと思う。
  • 結局後でアンインストールするのでインストールする必要はなかった。本当に必要ないかどうかはわからないが、こいつをアンインストールしてもGraphillionが動くのでたぶん問題ない。たぶん。
  • 一応手順を書いとく

手順

  1. ダウンロードをクリックすると「vc_redist.x64.exe」と「vc_redist.x86.exe」のどれをダウンロードするするかというチェックボックスが出てくる。

  2. x64は64ビット版でx86は32ビット版(この数字クソみたいにわかりづらいので何とかしてほしい)。

  3. このコンピュータは64ビットなので「vc_redist.x64.exe」を選択する。するとインストーラーがダウンロードされる。

  4. インストーラーを実行するとセットアップが完了する。

3. Graphillionをインストールする(これが大変)

手順(これが理想らしいけどこんなスムーズに進まなかったんだけど)

  1. ソースコード(tar.gz または zip ファイル)を https://github.com/takemaru/graphillion からダウンロードする
  2. アーカイブを展開し、ソースコードディレクトリ(setup.py があるディレクトリ)に移動する
  3. python setup.py build を実行してビルドする
  4. (任意) python setup.py test -q でテストを行う
  5. sudo python setup.py install を実行してインストールする

僕がたどった手順

error: Microsoft Visual C++ 14.0 is required. Get it with "Microsoft Visual C++ Build Tools": https://visualstudio.microsoft.com/downloads/
  • どうやらMicrosoft Visual C++ 14.0ってやつが必須らしい。とりあえず表示されたURL(https://visualstudio.microsoft.com/downloads)にアクセスする。
  • そのページでは、Visual Studio 2019のダウンロード画面が表示される。これをダウンロードしろってことか?よくわからんがこれをダウンロードすればpython setup.py buildを実行するのに必要な周辺ツールが全部インストールされるんだろう。ということでVisual Studio 2019をダウンロードする。
  • VS2019のインストーラーを実行するとオプションとして何かインストールするかを尋ねられる。なんかいろんなやつが表示されてよくわからんなぁ。そういえばさっきのエラーメッセージで「Microsoft Visual C++ 14.0 is required」って言われたしそれぽいやつをインストールするかぁ。ということで、表示された項目の中で「MSVC v140 - VS 2015 C++ ビルド ツール (v14.00)」が一番それぽいのでこの項目にチェックをつけてインストールを開始した(これが必要なのかどうかは最後までよくわからなかったけどたぶんいらない)。
  • さて、さっきエラーメッセージで言われたツール(VS2019)は入れたし完璧。python setup.py buildをもう一度実行する。すると、メッセージがたくさん出てきた。インストールが進んでるっぽい画面。お!これは成功したんじゃね?適当にツール入れるだけで成功させるとか天才かもしれんわ。
  • 失敗する。
  • メッセージはさっきとかわらずerror: Microsoft Visual C++ 14.0 is required. Get it with "Microsoft Visual C++ Build Tools": https://visualstudio.microsoft.com/downloads/だった。や、お前さっきツール入れたやん。なんでそこで失敗するねん。

  • よくわからんくなって適当にググってたらこの記事にたどり着いた。文章量多いけどとりあえず「Windows 10 SDK 」ってやつを入れないとだめらしい。僕は「MSVC v140 - VS 2015 C++ ビルド ツール (v14.00)」が必要そうだと思って入れたけど、本当に必要なのは「Windows 10 SDK 」だったみたい。ノリで環境構築を進めるとこういうことが起きる。VS2019の画面で新しいツールをインストールする画面に移動する。Windows 10 SDK を探すと同じような名前のやつがいくつか出てくるけど、とりあえず「Windows 10 SDK (10.0.17763.0)」を選択してインストールする

  • そして、python setup.py buildを実行する。成功してくれ~
  • 失敗する。
  • でもさっきまで出てたerror: Microsoft Visual C++ 14.0 is required. Get it with "Microsoft Visual C++ Build Tools": https://visualstudio.microsoft.com/downloads/は消えた。どうやらこの問題は解決したようだ。

  • 今回出たエラーは以下の通り。たぶんAnaconda3のファイルが開けないっていうエラーメッセージ。なので、c:\users\<name>\anaconda3\include\にパスを通す。なんか成り行きでc:\users\<name>\anaconda3\include\C:\Users\<name>\Anaconda3\ScriptsC:\Users\<name>\Anaconda3\DLLsにもパスを通した。これはグラフ列挙アルゴリズムのp152に書いてあったパス。必要かどうかわからんけど追加しといた。

c:\users\<name>\anaconda3\include\pyconfig.h(203): fatal error C1083: include ファイルを開けません。'basetsd.h':No such file or directory
  • そして、python setup.py buildを実行。4回目なのでそろそろ成功してくれ。

  • 失敗する。

  • 今回のエラーメッセージは以下の通り。rc.exeが実行できないらしい。なんじゃそのファイル。
LINK : fatal error LNK1158: 'rc.exe' を実行できません。
  • いろいろググるこの記事が出てくる。なんかrc.exeが競合してるらしい。この記事にはパスを変えて優先度を変えるみたいなことがかいてある。でも僕の環境には記事に書いてあるようなパスがそもそも存在しない...でも、競合という単語を聞いて一応思い当たる節があった。それは、たぶん必要だろうと思ってインストールしたいろんなツール。たぶん似たようなツールを入れたから競合を起こしてるんだろなぁと思ったので、とりあえずVisual C++ 2015 Redistributable Packagesでインストールしたものをアンインストールした。これはインストーラーをダブルクリックするだけで「アンインストールする」という選択肢が出てきたので3秒で完了。
  • そしてpython setup.py buildを実行する。5回目だぞ。わかるよな?そろそろ空気読んで成功してくれ。
  • 失敗する。
  • エラーメッセージはさっきと変わらずrc.exeが実行できないというもの。うーん、なんでだろ。
  • ググりまくると、この記事が出てきた。僕が知りたいことドンピシャじゃん。神か?

  • やることは、あるフォルダにあるrc.exercdll.dllを別のフォルダに移動させることらしい。

  • 僕の場合はC:\Program Files (x86)\Windows Kits\10\bin\10.0.17763.0\x64にあるrc.exercdll.dllC:\Program Files (x86)\Microsoft Visual Studio 14.0\VC\binにコピーした。
  • そしてpython setup.py buildを実行する。6回目の挑戦。頼む~。成功してくれ~
  • 成功~
  • 手順3まで終了したので、次は手順4のpython setup.py test -qを実行する。任意らしいけど一応やっておく。そんで、これも成功する。
  • 手順5はsudo python setup.py installの実行らしいが、cmdではこれを実行できない。sudoが存在しないって言われる。なので、python setup.py installを実行する。成功する。やったぜ!!
  • これでインストールのすべての手順が終了した。2,3時間くらいかけてしまった。疲れた。

使ってみる

  • NetworkXとMatplotlibを入れた。任意らしいけど、チュートリアルで使うらしい。本当に必要かはよくわからんがとりあえず入れておいた。
pip install networkx
pip install matplotlib
from graphillion import GraphSet
import graphillion.tutorial as tl
GraphSet.set_universe(tl.grid(10, 10)) # 10×10のグリッドをセットする
paths = GraphSet.paths(1, 121) # グリッドの左上と左下を指定してパスを探索する
paths.len() # パスの総数を出力する。1568758030464750013214100と出力されるはず
  • 動画と同じ結果が出力されたのでGraphillionをちゃんと動かせてるみたい。やったぁ

コイン問題

考察

  • 状態変数を考える
  • 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;
}

感想

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

react-native log-iosがしたい

問題

  • react-native log-iosをしてもログが取れない

解決策

react-native-log-iosの使い方

$ yarn global add react-native-log-ios # インストール
$ react-native-log-ios <project-name> # ログ取り開始

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

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