表題のAPIがはてなブックマーク件数取得API - Hatena Developer Centerに掲載されていました。2018年06月05日に追加されたばかりのhttp://api.b.st-hatena.com/entry.countというAPIを使えばよいそうです。
当ブログの場合、api.b.st-hatena.com/entry.total_count?url=http%3A%2F%2Fminus9d.hatenablog.com%2F にアクセスすると以下の結果が得られました (2018-07-04現在）。595件ものブックマークありがとうございます。
{"url":"http://minus9d.hatenablog.com/","total_bookmarks":595}
Div.2に落とされた直後のSRMで、自己最高の4位を取ることができました。本当は同時開催のTCOに出るつもりだったところ操作ミスでSRMにエントリーしてしまっていたのですが、結果オーライでした。記念のスクリーンショット。
本番では解けなかった1000のMajoritySubarrayが勉強になったので解法をメモしておきます。
数列の長さが100000なことから、すべての部分文字列でシミュレーションするのは計算量的に無理です。
公式ブログSingle Round Match 735 Editorials - Topcoder 2.0 にわかりやすい解法があります。まず、ある数字に着目して、その数字がmajority elementである部分数列を数えることだけを考えます。数列中に着目する数字が現れれば+1, 現れなければ-1して新たな数列を作成すると、この数列中の任意の2要素の大小関係を見るだけで、その部分数列に"majority element”が存在するかを判定できるようになります。これができれば、BITやセグメントツリーなどのデータ構造を使って、"majority element”が存在する部分数列の数を高速に数えられます。詳しくは以下に貼るソースコード中の説明を見てください。
この「ある数列の部分数列が条件を満たすかどうか、2要素の大小関係を見るだけで判定できるような数列を作れれば、BITで数え上げができる」という部分は他にも応用ができそうだと思いました。
// 公式解答を見た // https://www.topcoder.com/blog/single-round-match-735-editorials/ // 配列Aの構成要素はせいぜい50なので、各構成要素ごとに考えればよい。 // 次のような配列Aで、'o'が支配的になる部分配列の数を考える // // oxxooxo // 0123456 (idx) // // 配列Bを以下のように構成する。 // B[0]=7 (すべての要素が0以上になるよう下駄を履かせる) // a[i]が'o'であればb[i+1]=b[i]+1, 'o'以外であればb[i+1]=b[i]-1 // すると配列Bは以下のようになる // 78767878 // 01234567 (idx) // b[j] < b[i]となるj < iのペアを探す。このとき aの部分文字列[j, i)は'o'が支配的になっていることがわかる。 // 列挙すると以下のようになる。 // (j, i) = (0, 1), (0, 5), (0, 7), // (2, 5), (2, 7), // (3, 4), (3, 5), (3, 6), (3, 7), // (4, 5), (4, 7), // (6, 7) // // このようなペアの数は、BITを使うと効率的に求められる。 // たとえば B[5]に注目すると、これより左にある、B[5]より小さい値であるようなidxの数が、BITにより効率的に求められる #include <iostream> #include <sstream> #include <string> #include <cassert> #include <cmath> #include <climits> #include <cstdio> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <functional> #include <numeric> #include <iomanip> #include <cstring> #include <fstream> using namespace std; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; #define REP(i,n) for(int i = 0; i < (int)(n); ++i) #define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i) #define ALL(c) (c).begin(), (c).end() #define SIZE(v) ((int)v.size()) #define pb push_back #define mp make_pair #define mt make_tuple using namespace std; class MajoritySubarray { public: vector<ll> F; int fenwick_sum(int i) { // BITのこと。実装は蟻本と同じ int s = 0; while (i > 0) { s += F[i]; i -= i & -i; // i & -i: 1, 2, 4, 8, 16, ...のうち、iを割れる最大の数 // 言い換えると、iの一番右に立っているビットに等しい } return s; } void fenwick_add(int i, int val) { while(i < (1<<18)) { F[i] += val; i += i & -i; } } long long solve(ll N, ll seed, ll MOD) { vector<ll> As(N); REP(i, N) { As[i] = (seed / 65536) % MOD; seed = (seed * 1103515245 + 12345) % 2147483648; } F.resize(1<<18); ll ans = 0; REP(x, MOD) { fill(ALL(F), 0); int bal = N; REP(i, N) { fenwick_add(bal, 1); if (As[i] == x) { ++bal; } else { --bal; } ans += fenwick_sum(bal - 1); } } return ans; } long long getCount(int n_, int seed_, int m_) { ll n = n_; ll seed = seed_; ll MOD = m_; return solve(n, seed, MOD); } };
TopCoderのプラグインGreed（詳細はTopCoder の強欲プラグイン、Greed を使う！）で自動生成したコードをVisual Studioでビルドすると以下のようなエラーが出ます。
error C2872: 'data': あいまいなシンボルです。 note: 'std::ifstream data' である可能性があります。 note: または 'data'
これが指すコードは以下です。
using namespace std; ifstream data("MajoritySubarray.sample"); string next_line() { string s; getline(data, s); return s; }
エラーの原因は、<string>ヘッダで提供されるstd::dataという関数と名前がバッティングしていることでした。コード中のdataをdata2と変えるとビルドが通りました。
当たり前ですが、ちゃんとしたコードではそもそもusing namespace std;しないようにしましょう。
Linuxには「2種類のクリップボードのようなもの」があるということを今更明確に理解しました。
一つ目の「クリップボードのようなもの」は、Windowsなどでおなじみの"clipboard buffer"です。たとえばChromeにて、文字列を選択してCtrl + Cでコピー、Ctrl + Vでペーストという例のやつです。端末(Terminal)の場合はCtrl + C, Ctrl + Vがほかの用途で予約されているので、かわりにCtrl + Shift + Cでコピー、Ctrl + Shift + Vでペーストになります。
二つ目の「クリップボードのようなもの」は、"primary selection"とよばれるものです。例えば、端末にてマウスで文字列を選択したあと、Chromeの検索窓にてホイールクリックをするだけで、選択した文字列がコピーされます。
"primary selection"の方を意識して使うようにするとわずかながら作業速度が上がるかもしれません。
シェルスクリプトでハイフンを2つ繋げた'--'の意味を最近はじめて知りました。これはオプションの打ち止めを意味します。
たとえばtouchコマンドで-hという空ファイルを作成しようとして
$ touch -h
とすると、-hがtouchコマンドのオプションとして解釈されてしまうため、下記のようにエラーが出てしまいます。
$ touch -h touch: ファイルオペランドがありません Try 'touch --help' for more information.
ここで--の出番です。--の後ろにある文字列はtouchのオプションではないことを明示できるので、以下のようにすることで-hという名前の空ファイルを生成できます。
$ touch -- -h
引き続き、書籍 CUDA BY EXAMPLE を読み進めています。
Chapter 4のジュリア集合 - Wikipediaを描画するプログラムjulia_cpu.cuをビルドするのにやたら苦労したので、やったことをまとめておきます。OSはUbuntu 16.04 LTSです。
まず、gl/glut.hがシステム上に存在しないことからGLUTを入れる必要があることが分かったので、sudo apt-get install freeglut3-devでインストールしました。
次に、nvccコマンドで以下のようにビルドを試みますが、失敗します。
$ nvcc julia_cpu.cu -lglut ../common/cpu_bitmap.h(49): warning: conversion from a string literal to "char *" is deprecated ../common/cpu_bitmap.h(49): warning: conversion from a string literal to "char *" is deprecated /usr/bin/ld: /tmp/tmpxft_00006f4f_00000000-10_julia_cpu.o: シンボル 'glDrawPixels' への未定義参照です libGL.so.1: error adding symbols: DSO missing from command line collect2: error: ld returned 1 exit status
まず、共有ライブラリ周りに問題がないかを調べました。libglut.soをlocateコマンドで探すと、/usr/lib/x86_64-linux-gnuにあることがわかります。
$ locate libglut.so /usr/lib/x86_64-linux-gnu/libglut.so /usr/lib/x86_64-linux-gnu/libglut.so.3 /usr/lib/x86_64-linux-gnu/libglut.so.3.9.0
このlibglut.soが依存するライブラリをlddコマンドで追うと、すべてのライブラリに到達できているように見えます。（もし見つからない依存ライブラリがあれば"not found"とは表示される）
$ cd /usr/lib/x86_64-linux-gnu $ ldd libglut.so linux-vdso.so.1 => (0x00007fff910f7000) libGL.so.1 (0x00007f476d237000) libX11.so.6 (0x00007f476cefd000) libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007f476cbf4000) libXi.so.6 (0x00007f476c9e4000) libXxf86vm.so.1 (0x00007f476c7de000) libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f476c414000) libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007f476c210000) libGLX.so.0 (0x00007f476bfe0000) libGLdispatch.so.0 (0x00007f476bd12000) libxcb.so.1 (0x00007f476baf0000) /lib64/ld-linux-x86-64.so.2 (0x00007f476d723000) libXext.so.6 (0x00007f476b8de000) libXau.so.6 (0x00007f476b6da000) libXdmcp.so.6 (0x00007f476b4d4000)
次に、もう一度最初のエラーメッセージで検索をかけると、How to compile codes on CUDA OpenGL interop from the book CUDA BY EXAMPLE by Jason Sanders & Edw - NVIDIA Developer Forumsがヒットしました。これによると、-lGL -lGLUを加えるという回答があります。
最初は-lGLを追加から始めます。以下のコマンドを試しますが、今度はlibGL.soが見つからないと言われてしまいます。
$ nvcc julia_cpu.cu -lGL -lglut ../common/cpu_bitmap.h(49): warning: conversion from a string literal to "char *" is deprecated ../common/cpu_bitmap.h(49): warning: conversion from a string literal to "char *" is deprecated /usr/bin/ld: -lGL が見つかりません collect2: error: ld returned 1 exit status
しかし、 /usr/lib/x86_64-linux-gnu/には libGL.soという名前のシンボリックが存在していたはずだから、libGL.soが見つからないと言われるのは心外です。このシンボリックリンクが指す先をfileコマンドで調べると、リンクが壊れていることがわかりました。
$ file /usr/lib/x86_64-linux-gnu/libGL.so /usr/lib/x86_64-linux-gnu/libGL.so: broken symbolic link to mesa/libGL.so
なので、以下のように手動でlibGL.soのリンクを張り直しました。（注意：自己責任でお願いします）
$ sudo mv libGL.so libGL.manually-moved.so $ sudo ln -s libGL.so.1.0.0 libGL.so
このあともう一度サンプルをビルドすると、警告は出たままですが無事ビルドが通りました。
$ nvcc julia_cpu.cu -lGL -lglut ../common/cpu_bitmap.h(49): warning: conversion from a string literal to "char *" is deprecated ../common/cpu_bitmap.h(49): warning: conversion from a string literal to "char *" is deprecated
苦労の末の戦果品として以下を捧げます。
おまけで julia_gpu.cuのビルドについても触れておきます。プログラム中の
cuComplex( float a, float b ) : r(a), i(b) {}
の行を
__device__ cuComplex( float a, float b ) : r(a), i(b) {}
と書き換える必要がありました。（参考：c - CUDA Errors while running "CUDA By Example" julia_gpu.cu - Stack Overflow）
少し古い本ですが書籍"CUDA BY EXAMPLE"を読み始めました。
サンプルコードにある
#include "../common/book.h"
の場所が分からなかったのでメモ。現在ではCUDA By Example | NVIDIA Developerの "Download source code for the book's examples (.zip)" をダウンロードするとbook.hが入手できます。
