2017-12-05

コードレビューで英語実質ネイティブの人々がよく使ってくるAcronymのまとめ

公用語が英語の会社でコードを書いているので、コードレビューのコメントも英語で来る（それはそう）。よく、英語話者が使うAcronym（頭字語と訳すらしい。代表例はLGTM）がわからなくなるので忘れないようにメモる。

Acronym	意味	別解	備考
AFAIK	As far as I know		アメリカ人のマネージャーは”あふぁいく”みたいに発音していた
AFAIR	As far as I remember		前述のマネージャーはAFAIKとAFAIRの違いは特に気にしたことがないらしい。
IIRC	If I remember correctly
IMO	In my opinion	国際数学オリンピック（International Mathematical Olympiad）	なんでコードレビュー中に数オリの話が出てくるのか
LGTM	Looks good to me
NVM	Never mind	Node Version Manager	なんでJavaのコードレビュー中にnodeの話を始めるのか
RC	Release Candidate	鉄筋コンクリート（Reinforced-Concrete）
SGTM	Sounds good to me

他に何か気が付けば追加する。

2017-06-13

徳山こうせん（not 高専）の標識まとめ

ネタ

高専生ならみんな入力したことのある○○光線ですが，実在する○○光線があります．

それは徳山光線です．ちゃんと証拠の画像もあります．

f:id:blue_jam:20170613005806j:plain

暗くて字が読めなかったので，色味の調整をしていますが，それ以外の画像編集は一切していません．ちなみに，Google マップでも確認できます．

徳山光線は"とくやまひかりせん"と読みます．その名のごとく，旧徳山市（現周南市）と光市を結ぶ道路です．山口県道8号徳山光線 - Wikipediaによると，都濃郡都濃町が徳山市に編入された時に現在の名称になったようです．なお，徳山市が周南市になったときは名称の変更はなかったもよう（周南市でかすぎるんもんね．）

ちなみに，徳山港線（Google マップ）も存在します．山口県道52号徳山港線 - Wikipediaによると，こっちは"とくやまこうせん"と読むらしい．．．

2016-12-18

証明を書こう！

この記事はCompetitive Programming （その2） Advent Calendar 2016 - Adventarの記事として書きました．

この記事に，技術的に有用なことはありません．「証明を書こう！」という話です．

何か月か前に，とある方から次のような質問をされました．

競技プログラミングをやっていて，こういうのがあったらいいなあってものてある？

僕は「ちゃんとした解法の証明がほしい！」と答えました．その後に理由を長々としゃべりましたが，大体次のようなものだったと思います．

解説では解法の方針がざっくりと説明されているだけだから．
（僕の研究室では）重要なスキルの一つに証明を書くことがあるから．（この質問の前に「競プロって研究の役に立ってる？」という質問をされていた．）
（僕は証明無しでアルゴリズムについて話をするとうちの先生方に説教を食らうのに，みんなサボってずるい！）

1つ目の理由は，ざっくりとした説明だけではわかった"つもり"にしかなれないと思っているからです．特に，最近は競プロの問題の難易度がどんどん上がってきていて，「本当にそれでうまくいくの？」と思うような解法がたまにあります．牛ゲーとか，高難易度の貪欲とか「証明があったらうれしいなあ」と思うことがよくあります．なぜその解法でうまくいくのかを確認するには，やっぱり証明を追わないと．

2つ目の理由は，僕の所属している研究室の研究内容に大きく依存しています．僕はアルゴリズム関係の研究室に所属しています．研究室仲間がやっている研究は様々で，マッチングをやっている人もいるし，乱択数え上げをやっている人もいるし，分散アルゴリズムをやっている人もいます．僕らに共通して必要なスキルは"証明を書くこと"です．だから，証明を書く練習がしたいし，そのお手本があったらうれしいというわけです．

ちなみに，この会話の最後に「お前がやればいいんだよ！」というツッコミをいただきました．アドベントカレンダーを書くまでに，問題の証明を書こうと思っていましたが，残念ながら間に合いませんでした．今後，時間が空いたときに何かしら書いていこうと思います．

以上「（僕が）証明を書こう！」という話でした．最後までお付き合いくださった方，ありがとうございます．

2016-06-25

ICPC2017国内予選参加記（引退します）

ICPC

チーム名はyotei_awanaiです．チームメイトのハンドルを知らないので，N君とK君とします．

結果

どう考えても5完セットでした．6完ワンチャンだったと思います．でも3完74位です．

引退 & JAG入会待ったなし．

結論

コミュニケーション大事
練習大事
平常心大事

準備

秘密の数は836705．

チームメイト全員と顔を合わせることができたのは，予選本番前の30分前でした．原因が体調を崩しまくった僕のせいです．チームメイトの皆さん本当にごめんなさいでした．

チームメイトにはお詫びになんばん往来をあげました．東京の人に渡す予定だったのに，会えなくて余らせていたものだったのはここだけの秘密です．

環境は，本番前日に決まりました．本当に何やってるんだろうね．．．他の二人は慣れない環境（Win+MSYS2）に戸惑っていたようです．はじめから，アジア地区ではUbuntuだから，Ubuntuでやるよ～とかアナウンスをしておくべきだった．

流れ

A問題

K君単独．問題概要は知らない．開始8分でAC

B問題

N君．当確判定がわからなかったみたいなので，適当にアドバイスしました．（のこりの票を全部2番目の人に入れるんだよ～みたいな）開始47分でAC

C問題

篩う． N君がB問題を解き始めてた時には紙コーディング終わってました．ファイルの更新時間によると，B問題を提出してから10分でACしてたみたいです．

D問題

K君が一生懸命考えていたので，すこしアドバイスをしました．今考えると，僕も一緒にじっくり考えていた方がよかったと思います．

E問題

EはEasyのE（解けるとは言っていない）．問題をちゃんと読むとパスかサイクルになることがわかる．パスやサイクルに対する操作を悩んでいる間に時間切れ．

でも，そもそも辺のコストの計算を間違えている（体積にしてた）とか結構問題があった．もっと落ち着こうな．

F問題

無向グラフ同型判定は～みたいなことは知っていた．時間足りず

G問題

わーい幾何だー

H問題

知らん．

今年度の参加記は以上

最後のICPCを終えて

高専時代を合わせると計4回ICPC国内予選に参加しました（高専時代に登録だけして参加できなかったやつを除く）．アジア地区予選へは計2回進出しました．

楽しかった思い出も，苦い思い出もあります．今後参加する人の参考になるかもしれないので，

楽しかった思い出

夏合宿

夏合宿は全日程参加を1回，飛び入り（コンテスト時に混ぜてもらっただけ）を1回しました．

競技プログラミング漬けになれるのは，JAG合宿だけ！別の学校の同じぐらいの強さの人と部屋が同室になるので，話がはずんだりします．

交通費だけで30,000円以上かかったけどな！たしか，雑費を含めて40,000円~50,000円ぐらいかかった．でもそれだけの価値があったと思う．

アジア地区予選

オンサイト独特の雰囲気があっていい．いろいろな人（学生も，企業の人も）とも話ができる．

小中高の全校集会での偉い人のお話は全く聞く気がなかったけど，アジア大会でのスピーチだと思うとありがたみが一気に増すぞ！

焼肉

企業賞おいしかったです． $\sqrt{29}$ さんごちそうさまでした．

交通費まで出していただいて．．．

苦い思い出

解答権喪失

稀にみる悲しい状況です．初めての国内予選で経験しました．

WAだったらまだ大丈夫ですが，あの画面はやばいです．頭の中が真っ白になります．本当に．マジで．トラウマ．

これは極端な例かもしれませんが，普段は普通に書けるコードも，本番で制限時間が付くと急に書けなくなります．（僕がとても緊張に弱いというのもあるでしょうが）

落ち着けるルーチンがあったらよかったかもしれません．

練習するときは，制限時間を付けたり，あえて集中できない環境でやったりするのもいいかも？

僕は他の人の声や，キーボードの打鍵音がかなり気になるタイプなので，耳栓とかを持ち込んだ方がよかったかなと思います．（ルール上平気かは要確認．アナウンスが聞こえなくなるので注意）

健康管理

今年とか極端な例ですが，心身の健康は大切です．コンテストに限った話ではないですが，健康は大切にしましょう．深夜コンテストに参加しまくって，昼間寝て太陽の光をまったく浴びないなんてことがないように．（昼夜逆転しても平気な人は参加してどうぞ）

2016-05-04

SRM 690(Div.1 Easyのみ)

ケアレスミスでEasyを落としました．（何やってんだか．）

解いた問題

Easyのみ.120点ぐらいでの提出だった．

問題概要

整数 $N$ と $K$ が与えられる．（ $1\le N\le 100, 1\le K\le 15$ ）

1 ~ 100 までの整数のうち， $K$ 個の数 $u_1, u_2, ..., u_K$ を選び，どのように $v\in \{-1,0,1\}^K$ を選んでも， $\sum_i u_i v_i$ が $N$ にならないようにする．

解法

等差数列 $a + d(i-1)$ でよさそう．

このように数列をとると，どう選んでも， $b a + c d$ （ $b,c\in \mathbb{Z}$ ）にしかならない．この形では， $\operatorname{gcd}(a,d)$ の倍数しか作れないということは一般常識．

よって， $a$ と $d$ を変化させて適当な数列を作る．

念のため， $N$ と $K$ を変化させて全通り試すと， $N=60$ ， $K=15$ でこの方法ではうまくいかない．最も長く作れて，14個（ $a=7,d=7$ とする)．よって，この時だけ1を追加すればよい．．．はずだった．

ミスしたところ

初項 $a$ ，公差 $d$ の等差数列の $a$ 以上 $e$ 以下の項の個数は， $\lfloor (e-a)/c\rfloor+1$ でえられる．

int k = (100 - a) / d ;

はい．見事に+1を忘れました．

解法では， $N=60,K=15$ がコーナーケースと言いましたが，これだと $K=14$ の場合もできないと判定してしまいます．

それだけだったらよかったのだが， $N=60,K\ge 14$ のときに，1と""2""を加えるようにしてしまった．この2つを足すと3になって， $-3 \equiv 60 \pmod{7}$ となってしまう．加えるのであれば，8（7を法として1と合同）とかにすべきだった．．．

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ALL(c) (c).begin(),(c).end()

ll gcd(ll x, ll y){
    return y == 0 ? x:gcd(y, x % y);
}

struct WolfCardGame {
  int N;
  int K;
  vector<int> createAnswer(int _N, int _K) {
    N = _N, K = _K;
    for(int a = 1; a <= 100; ++a){
        for(int d = 1; d <= 100; ++d){
            if(N % gcd(a,d)){
                int k = (100 - a) / d; //ミス その1
                if(k >= K){
                    vector<int> ret(K);
                    for(int i = 0; i < K; ++i){
                        ret[i] = a + d * i;
                        if(ret[i] >= 100) cout << "oops" << endl;
                    }
                    return ret;
                }
            }
        }
    }
// ミス その2
    vector<int> ret(K);
    for(int i = 0; i < 13; ++i) ret[i] = 7 + 7 * i;
    ret[13] = 1;
    if(K == 15){
        ret[14] = 2;
    }
    return ret;
  }
};

// Powered by Greed 2.0-RC

実は，ミスその1については気が付いて，修正もすんでいたが，前のままでも問題ないと思って提出していなかった．出力判定関数も書いていたのに，そもそもその判定関数が間違っているという．．．

もっと落ち着いて問題を解こうな．

2016-05-01

TopCoder部のカレンダーをGoogleカレンダーで（そこそこきれいに）見る

カレンダーを公開しました．AtCoderのイベントはAtCoder社さんのカレンダーをお使いください．

githubにあげました． TopCoder部のカレンダーを開くのさえ億劫になってきている今日この頃．コンテストの予定がGoogleカレンダーに表示されるようになれば，コンテストにも出たくなるのではないかと考えた．

先駆者がいた． f:id:blue_jam:20160501101206p:plain

せっかく開始時間を明記してあるんだから，終日のイベントでなく，時間を決めうちしてほしいと思った．

サーバを持ってたら，cronでGoogleのAPIたたいてごにょごにょしたり，iCalendarの内容を再度編集したiCalendarを生成するのCGIプログラムを作ったりすれば何とかなるのかもしれないが，サーバを持ってない．

調べてみると，Google Apps Scriptでcronっぽいことができるらしい．（参考）

（JavaScriptほとんど使ったことない．．．）

最終的に，

TopCoder部のカレンダーをインポートしたカレンダーと，出力先のカレンダーを用意しておくと，
Google Apps Scriptで作ったプログラムが，TopCoder部のカレンダーを適切に編集し，出力先のカレンダーに書き込んでくれる

というようになった．GASはトリガーという，一定間隔で決まった関数を呼び出す仕組み（？）があり，それを設定しておくと自動で追記を編集してくれる．

AtCoderはGoogleカレンダーを公開してくださっているので省いた． HackerRankにもGoogleカレンダーにインポートできるカレンダーがあったけど，いろいろなものが登録されすぎてて混乱するので保留．

結果はこんな感じ

f:id:blue_jam:20160501103040p:plain

コンテスト時間をまじめにとるなら，コンテストサイトのAPIをたたいたほうがよさそうだけど，怠けてる．

Googleカレンダーを公開したら，ほかの人も幸せになれると思ったけど，公開するとメールアドレスがさらされる問題を解決できてないので非公開のままにします．

スクリプトのプロパティにsrcCalendarIdとdstCalendarIdを追加し，それぞれにTopCoder部カレンダーをインポートしたもののIDと，出力先のカレンダーのIDを書き込む必要があります．スクリプトのプロパティにignoreAtcoderを追加し，空でない文字列を入れるとAtCoderのイベントは追加されなくなります．トリガーには，calendarUpdateを追加してください．

たぶんgithubにあげる．

function calendarUpdate() {
  // プロパティからIDを読み取る
  var scriptProperties = PropertiesService.getScriptProperties();
  var srcCalendarId = scriptProperties.getProperty("srcCalendarId");
  var dstCalendarId = scriptProperties.getProperty("dstCalendarId");
  // カレンダーの取得
  srcCalendar = CalendarApp.getCalendarById(srcCalendarId);
  dstCalendar = CalendarApp.getCalendarById(dstCalendarId);
  
  ignoreAtCoder = Boolean(scriptProperties.getProperty("ignoreAtCoder"));
  
  // 全部は見えないらしいので，先1か月のを調べる．
  var now = new Date();
  var oneMonthFromNow = new Date(now.getTime() + (30 * 24 * 60 * 60 * 1000));
  var srcEvents = srcCalendar.getEvents(now, oneMonthFromNow);
  
  // 各イベントについて処理
  var re = new RegExp("[0-9][0-9]:[0-9][0-9]");
  for each(var e in srcEvents){
    var date = e.getTitle().match(re);
    var title = RegExp.rightContext.trim();
    var startTime = new Date(Date.parse(e.getStartTime().toLocaleDateString() + " " + date));
    
    // AtCoderを無視する設定で，AtCoderのイベントならchokuDie
    var atcoder = isAtCoderEvent(title);
    if (ignoreAtCoder && atcoder) continue;
    
    // 終了時刻を計算
    var duration = getDurationByTitle(title);
    var endTime = new Date(startTime.getTime() + duration * 60 * 1000);
    
    // 重複チェック
    var res = checkDuplication(title, startTime);
    if (res == null) {
      dstCalendar.createEvent(title, startTime, endTime);
    }
    else {
      res.setTime(startTime, endTime);
    }
  }
}

/*
 * タイトルからコンテストの長さを適当に取得する．当然間違う．
 */
function getDurationByTitle(title) {
  durationDictionary = {
    "SRM":90,
    "AtCoder Regular Contest": 90,
    "AtCoder Beginner Contest": 120,
    "Codeforces": 120,
    "yukicoder": 120
  };
  for (var key in durationDictionary) {
    Logger.log(title.indexOf(key));
    if(title.indexOf(key) >= 0)
      return durationDictionary[key];
  }
  return 90;
}

/*
 * 登録が重複しているか確認する
 * 重複しているなら，そのインスタンスを返す
 */
function checkDuplication(title, startTime) {
  var events = this.dstCalendar.getEventsForDay(startTime);
  for each(e in events){
    if(e.getTitle() == title)
      return e;
  }
  return null;
}

/*
 * AtCoderのイベントかどうか
 */
function isAtCoderEvent(title) {
  return title.indexOf("AtCoder") >= 0;
}

更新情報

5月3日：Googleカレンダーを公開しました．（ついでに，ブログの文体も少し変わっている．）

2015-06-30

ACM-ICPC 2015 こくないよせんさんかき

ぼくはAもんだいをとおしました．

ぼくがAをとおしたあとは，くりんぺっとさんがB,Cをとおして，
しゅんかんてきにいちいになりました．

そのあと，EやFをおもにかんがえましたが，ほうしんがまとまらず，
すわっているだけになりました．

きょすくんが「Hがやるだけにみえる」といったあと，
くりんぺっとさんが「ざあつ，だいくすとら，やるだけ」とつぶやいたあと，
じっそうしてとおしていました．
くりんぺっとさんは，かみだとおもいます．

15いでよせんはつうかしましたが，ぜんぶ，ほかのふたりのおかげです．
ぼくはずっとすわっているだけで，とってもつらいおもいをしたので，
アジアちくよせんでは，もっとチームにこうけんしたいです　まる

ごめん