ここでビジュアライザを使うと、盤面Aの外縁部の値を、盤面Bでは多く取りこぼしていることに気付きました。そこで、まず最初に盤面Bの全体にまんべんなく山を設置することで、盤面Bの外縁部の値が小さくなることを防げるのではないかと考えました。具体的には、盤面Bを5x5の小エリア400個に分割し、それぞれの真ん中に高さ75の山を並べました。このパラメータが結構シビアで、結果に意外と影響しました。これで9.9823e9点。ここまでで大体5時間経過です。

次に、終盤で盤面Bのマス目が盤面Aのマス目を許すときに、スコアが最良となる山の高さhを1から100まで全探索して決定するロジックなどを入れました。手調整が必要なパラメータがいくつか増えてます。これも効いて、9.9901e9点まで来ました。

次に、これまで作成した各山の高さを±5の範囲で全探索して、もっともスコアが上がるhに修正する、山登りによる最適化処理を処理時間いっぱいまで行うようにしました。これも効いて、9.9946e9点。6時間半経ってようやくこの問題で何をすればよいか分かってきました。

さらに山のx位置, y位置をそれぞれ±2、つまり今の山の位置を中心とした5x5のエリア内でスコアがもっとも上がる山の位置を全探索するコードを追加しようとしたんですが、WA連発で時間を浪費したのが非常に痛かったです。バグの原因はhの有効範囲[1, 100]とx, yの有効範囲[0, 99]を誤って混同していたしょうもないミスでした。終了15分前くらいになんとかバグがとれて、9.9971e9点。

最後に、山の高さの探索範囲を±2に狭める調整をして時間に追われるように提出して、9.9972e点。これが最終スコアでした。

感想と反省

終了後の動画解説を見たところ、方針をそれほど大きく外してはなかったのが良かったです。しかしいかんせん最適化処理の必要性に気づくのに6時間半かかったのはちょっと遅すぎでした。もう少し早くこの段階にたどり着けていたとしたら、山の位置・高さを変えたときのスコア計算の高速化（現状はすべて愚直にO(N²)の計算）、パラメータ調整、焼きなましの導入など打つ手は合ったかなと思います。

2018-02-15

第2回 RCO日本橋ハーフマラソン予選参加記

programming contest

第2回 RCO日本橋ハーフマラソン予選 - 第2回 RCO日本橋ハーフマラソン予選 | AtCoder に参加しました。結果は16位で、青コーダーの自分にしては健闘。去年の本戦のパラレル | AtCoderでも2位という今後二度と取れそうもない順位が取れてしまっていたので、適当な解法をいかに早く投げるかが重要なこの形式は自分に合っているのかもしれません。

以下、問題Aと問題Bの思考ログです。実際はAとBを行ったり来たりしていました。

問題A - ゲーム実況者Xの挑戦

とりあえず完全ランダムに移動する解を投げて、6499点。

次に試したのは、制限時間いっぱいまで「ランダムな盤面選択＋ランダムに移動」を試して、点数がベストなものを選ぶ解法です。これで19677点。しばらくの間、なぜかマップの番号が1始まりであると勘違いしていたことが原因で点数の計算が合わず苦戦。実装完了まで1時間くらい無駄にしてしまいました。

次に、制限時間いっぱいまで「ランダムな盤面選択＋greedyに移動」を何度も試して、点数がベストなものを選ぶ解法を実装しました。ここで「greedyな移動」とは、上・下・右・左のうち、罠にかからない方向であり、かつ、コインがもっとも多くとれる方向を選ぶ移動法です。これで119800点。

終了間際に、「100個の盤面のうちよい盤面だけからランダム選択した方がスコアが上がるのではないか」と考えました。初期位置から取得可能なコインの数が多い盤面を良い盤面と定義し、100個の盤面から良いm個の盤面のみを使う方法を実装しました。しかし手元でmの値をあれこれ変えてもあまり効果は出ず、むしろスコアが下がることも。かろうじてスコアが上がった m = 95 を採用して、124540点。これが最終スコアで、52位でした。

心残り

本番中にvisualizerで挙動を確認すると、周囲にコインがなくなったときにプレイヤーの位置が振動してしまっていました。本番中に試しに2手読みを実装しましたが、かえってスコアが低下しました。バグがあったと思われます。

あと、たまにはランダムにプレイヤーを移動させることや、最終ターンが近づいたときに死人がでることを許容して移動させるようにすることも試そうと思っていましたが、記憶から落ちていたのと時間がなかったのとで実装できませんでした。

問題B - ゲーム実況者Xのデフラグ

最初は焼きなまし系の最適化問題かなと思いましたが、よく見ると、データの書かれているセクタ数16000に対してスワップ回数が4000回なので、半数以上のセクタは一度も移動されないということに気付きます。なので、以下の操作を4000回繰り返す解法に割と素直に行き着きました。

全データセクタについて、フラグメントスコア（＝そのセクタの前のセクタとの距離と、そのセクタの後のセクタとの距離の和）を計算
フラグメントスコアが最大のデータセクタを選ぶ
選んだデータセクタのswap先を全通り試し、もっとも全体のフラグメントスコアが改善するswap先を見つけ、そことswapする

最初はswap先を空セクタに限定することでプログラミングの難易度を下げ、225356点。次に、swap先をすべてのセクタから求め、380776点。これが最終スコアで、7位となりました。最終解の提出直後は一瞬総合5位くらいになれたので、このときがいちばん興奮しました。

心残り

何らかのランダム性を追加してスコアが上がらないかとも一瞬考えましたが、Aの検討を優先しました。

次回に向けたメモ

「コードに加えた変更」と「手元のサンプルでのスコア」と「サーバのスコア」とをメモっておく。すると、手元のサンプルでのスコアをもとにサーバのスコアが予想できるようになる。各提出タイミングでのコードもコピーしてとっておくとよい。
上の状態を作るために、できるだけ早めに解答を作ってサーバに投げたい。とはいえ、あまりに簡単な解だと時間のムダかもしれず匙加減が難しい
手元のサンプルは基本的に最初からジェネレータに封入されている1個で十分
Emacsはやめて最初からVisual Studioを使おう

参考URLs

RCOスタッフによる模範回答

ハーフマラソン予選、私の回答です。A:302527/B:426768 （時間は無制限でやってます）https://t.co/wfufJsDS1c https://t.co/NuBijfvEQK
— 2018年こそ夏バテにならない (@tomerun) 2018年2月13日

2018-01-03

このブログのユーザー属性

hatena 雑文

このブログも早いもので開設から8年ほど経っていて恐ろしいことです。たまには定点観測のためにGoogle Analyticsで取得したユーザーに関する情報を記録しておきたいと思います。以下のデータはすべて2017年全体を対象に取得しました。

年齢と性別

f:id:minus9d:20180103210715p:plain

34歳以下の利用が多く、合計で72.35%です。45歳以上は8.18%しかいません。このブログはほとんどプログラミングの実際的な記事しかないことから考えるに、やはり45歳以上で現役でプログラミングを続けることは難しいのでしょうか。

性別は実に92.4%が男性で、女性は7.6％のみです。理系女子の就職事情と理系に人気の職業・業界はどこ？ - 工学スタイルによると機械・電気・情報系の学科の女性比率は5％～8％程度であり、この比率と同等です。今後女性率が増えてくれることを望みます。

言語

このブログには日本語記事しかないため、当然ながらjaとja-jpのみで96.13%を占めます。en-usが3.52%で続きます。

地域

やはり当然ながら日本が最多で98.10%。次がUnited Statesで0.59%です。

98.10%を都道府県別に細分化したときのTop 10は以下の通りです。Top 10のみで98.10%のうちの81.07%を占めている計算であり、人口比を考慮しても偏りが激しいです。IT企業や大学の所在地の偏在を反映しているのだと推測します。

都道府県	比率
東京都	38.34%
神奈川県	13.48%
大阪府	8.45%
愛知県	5.50%
京都府	2.88%
福岡県	2.72%
千葉県	2.66%
兵庫県	2.56%
埼玉県	2.44%
北海道	2.04%

デバイス

以下のように圧倒的にPCからのアクセス比率が高いです。世間と比べると異常です（参考：サイトのデバイス割合は業種によってどのくらい違うのかを調べてみた《Google Analytics》｜リスティング広告の運用代行ならカルテットコミュニケーションズ）

デバイスカテゴリ	比率
デスクトップ	97.86%
タブレット	1.69%
モバイル	0.44%

ブラウザ

Chromeが強いです。

ブラウザ	比率
Chrome	52.66%
IE	21.68%
Firefox	15.15%
Safari	5.80%
Edge	4.07%
Opera	0.35%

OS

世間に比べるとWindowsのシェアが若干低いです。（参考：Linux、Windows 10が増加 - 8月OSシェア | マイナビニュース）

OS	比率
Windows	76.61%
Macintosh	14.97%
Linux	6.76%
iOS	0.85%
Android	0.67%
SunOS	0.07%

Windowsに限定すると以下の比率です。

OS	比率
7	53.51%
10	38.15%
8.1	7.46%
Vista	0.42%
XP	0.25%

2017-12-20

Travis CIでC++11, C++14のコードをビルド

C++

昔Travis CIでC++11のコードをビルドしたとき（参考：Travis CI にて、C++11のソースをgccとclangの両方でビルドする - minus9d's diary）やたら大変だったのですが、いつのまにかUbuntuのバージョンが14.04に上がったらしく、前よりは簡単にできるようになりました。

以下では、g++とclang++の両方でC++11またはC++14のコードをビルドする例について示します。

C++11の場合

デフォルトでgcc 4.8.4 と clang 5.0.0が使えるので、特に工夫しなくてもC++11が使えます。

以下のMakefileと

CXX = g++
CXXFLAGS = -W -Wall -std=c++11
TARGET = main

$(TARGET): main.cpp
  $(CXX) $(CPPFLAGS) $(CXXFLAGS) $^ -o $@

以下の.travis.yml

language: cpp
compiler:
    - clang++
    - g++
script:
  - make CXX=${CXX}
  - ./main

をレポジトリ直下に置けばOKです。ここで、yamlファイルの変数${CXX}には、travisが勝手に適切な値を入れてくれます。

このコードのソースとテスト結果です。

C++14

clang 5.0.0はC++14対応していますが、gcc 4.8.4はC++14対応していないため、対策が必要です。

以下のMakefileと

CXX = g++
CXXFLAGS = -W -Wall -std=c++14
TARGET = main

$(TARGET): main.cpp
  $(CXX) $(CPPFLAGS) $(CXXFLAGS) $^ -o $@

以下の.travis.yml

language: cpp

matrix:
  include:
  - compiler: clang++
  - compiler: g++
    addons:
      apt:
        sources:
          - ubuntu-toolchain-r-test
        packages:
          - g++-5
    env:
      - MATRIX_EVAL="CC=gcc-5 && CXX=g++-5"

before_install:
   - eval "${MATRIX_EVAL}"

script:
  - make CXX=${CXX}
  - ./main

をレポジトリ直下に置きます。g++の方のみ追加オプションを利用してg++5を使えるようにしています。

このコードのソースとテスト結果です。

参考

Building a C++ Project - Travis CI

2017-12-14

北大日立マラソン2ndに参加しました

programming contest

1stに引き続きHokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017に参加しました。1stより十分な時間をとって臨んだおかげで、最終提出時18位、最終テスト後19位。目標としていた上位25%に滑り込めました。

考え方

序盤は迷走しましたが、中盤から以下の3つのフェーズに分けると考えやすいことに気付きました。

フェーズ1. GemvをV個のグループに分割
フェーズ2. GemvのV個のグループと、グラフGのV個の頂点との最適なマッピングを探索
フェーズ3. Gemvのグループ分割を微妙に変えてスコア向上

自分の感覚では、フェーズ1 > フェーズ2 > フェーズ3の順にスコアに影響がある感じがしました。

フェーズ1. GemvをV個のグループに分割

なるべく各グループが他のグループと多く接するように分割するほどスコアが向上する傾向にあることに気付いたので、このフェーズにもっとも力を入れました。

例えば各グループをサイズ１として以下のように並べると、各グループは最大でも他の8グループとしか隣接できません。

ABCD
EFGH
IJKL
MNOP

しかし各グループをサイズ2として以下のように並べると、各グループは最大で他の11グループと隣接できるようになります。

ABCD
BADC
IJKL
JKLK

今回は、「異なるグループ同士の隣接数の総和」をポテンシャルという名前で呼び、このポテンシャルが大きくなる分割方法を検討しました。

各グループを斜めで配置して互いに交差させると隣接数が多くなりそうだということには気づきましたが、これをうまくルール化するのが困難でした。大雑把に書くと、以下のように何通りかグループ分割法を試し、実際にポテンシャルを計算（これはすぐできる）し、もっともよいグループ分割法を採用するという方法を取りました。

for i = 1, 3, ... 
  左上から右下まで、長さiの直線をとれるだけとる
  右上から左下まで、長さiの直線をとれるだけとる
  もしまだ十分な数のグループが分割できていなければ、できるだけ直線になるように適当にグループをとっていく

そして最後に、各頂点をあるグループから他のグループに変えることでポテンシャルが上がるかどうかを山登り的にチェックして、若干ポテンシャルの値を追い込みました。頂点が所属するグループを変えても連結性が保たれるかどうかは、その頂点の近傍８ブロックを見てチェックしました。例えば

* A *
* A *
* * A

という3x3グラフの中央に着目したとき、このAを他のグループに変えると、少なくともこの3x3領域内ではAの連結性が破られてしまうので、Aの所属は変えません。次に

* A *
* AA
* * A

という3x3グラフの中央に着目したとき、このAを他のグループに変えると、Aの連結性は保たれるので、Aの所属は変更可能だと判断できます。

フェーズ1の心残りとしては以下があります。

どのグループにも属さないままとなった頂点をうまく他のグループに属させて、全体のポテンシャルを底上げする方法を追求できなかった。
極端に隣接数の小さいグループが存在してしまいがちだった。場合によってはパーフェクトボーナスを取る妨げになった可能性がある。
パーフェクトを狙うのであれば、入力グラフの各頂点の次数のヒストグラムを考慮して、グループ分割方法を考える必要があったかもしれない。

フェーズ2. GemvのV個のグループと、グラフGのV個の頂点との最適なマッピングを探索

フェーズ2は焼きなましのようなもので探索しました。

まず、フェーズ1のグループ分割は完全に固定して、各グループをノード、グループ間の隣接関係をエッジとする新たなグラフGemv'を作ります。そして、グラフGの頂点と、グラフGemv'との頂点とのマッチングをあれこれ試し、スコアの最適化を狙いました。

操作は頂点のスワップです。5回に4回はランダムにスワップ（ただし、確実に何らかのスコアが発生する頂点を選ぶ）、5回に1回はもっともスコアが上がりそうな頂点を選んでスワップ、という戦略を取りました。

このフェーズは25秒程度実行しました。それなりに高速化したつもりですが1億回程度しか試行できず、上位陣に遠く及びません。上位陣との差分が何なのか研究が必要です。

また、多分初めて焼きなましをしましたが、最後までコツがよく分かりませんでした。以下のようルールに落ち着いたのですが、スコアが大きく下がるのをまったく許容できていないところに改善の余地があります。

スコアが向上すれば100%遷移
スコアが-1のみ低下するときは、確率th1 (序盤100% -> 中盤0.01% -> 最終盤0%）で遷移
スコアが-2か-3低下するときは、確率th2(序盤から中盤まで0.001%, 最終盤0%) で遷移

フェーズ3. Gemvのグループ分割を微妙に変えてスコア向上

以下のアルゴリズムでグループ分割方法を山登りで変えました。

頂点を一つランダムに選択
もしその頂点のグループを変えて連結性が保たれる保証がなければ1.に戻る
頂点の周囲8箇所のうちどれかをランダムに選び、そのグループに属させる。
もしスコアが上がれば採用
1. に戻る

上記3.で周囲8箇所全通りやっていたつもりが、1箇所しかできていませんでした…。ここでもっと頑張ればスコアが上がることは盤面から分かっていましたが、時間の関係で切り捨てました。

また、除去してもスコアに影響がない点を除去するのも、面倒で省略しました。

感想

アイデアを一つずつ実装して着実にスコアを改善できた達成感と、上位との非常に大きなスコア差からくる敗北感とが8:2くらいな気持ちです。特にフェーズ1のグループ分割に関してはもう少しアイデアを出す余地があったのではないかと思います。例えば hakomo さんの

合議greedyで頂点集合集合を決めて、第１回と同じ焼きなましをしました

GIFが合議greedyの1つで平均隣接数ができるだけ大きく、次いで分散が小さくなるパターンをがんばって探しました pic.twitter.com/t0pH04xWAm
— hakomo (@hakomof) 2017年12月12日

などは実装量も軽そうで、自分でも思いつきたかったアイデアでした。

コード

汚くて恥ずかしいんですが貼っておきます。最終提出版を少しだけ手直しして力尽きたものです。

https://gist.github.com/minus9d/177b1031aee831a4a0d9e7b77a94aaa5

2017-12-13

北大日立マラソン2nd　参加記のまとめ

programming contest

前回に引き続き、Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017 の参加記を勝手ながらまとめました。見つけ次第追記します。

順位	atcoderのID	URL
1	yosss	AtCoder 北大日立マラソン 2nd 参加記 (yosss), twitter
2	yowa	AtCoder 北大日立マラソン 2nd 参加メモ (yowa)
4	C7BMkOO7Qbmcwck7	Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017 : EvbCFfp1XB
6	hakomo	twitter
8	tomerun	北大日立新概念マラソンでやった高速化色々 - TopCoderの学習のお時間 - TopCoder部, twitter
9	logicmachine	twitter
14	kotamanegi	twitter
17	y_kawano	twitter
18	koyumeishi	twitter
19	minus9d (自分です)	北大日立マラソン2ndに参加しました - minus9d's diary
20	WahrGrowth	twitter