読者です 読者をやめる 読者になる 読者になる

証明を書こう!

この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの記事として書きました.

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

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

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

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

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

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

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

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

以上「(僕が)証明を書こう!」という話でした. 最後までお付き合いくださった方,ありがとうございます.

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だったらまだ大丈夫ですが,あの画面はやばいです.頭の中が真っ白になります.本当に.マジで.トラウマ.

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

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

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

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

健康管理

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

SRM 690(Div.1 Easyのみ)

ケアレスミスでEasyを落としました.(何やってんだか.)

解いた問題

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

問題概要

整数  NKが与えられる.( 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_iNにならないようにする.

解法

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

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

よって,adを変化させて適当な数列を作る.

念のため,NKを変化させて全通り試すと,N=60K=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については気が付いて,修正もすんでいたが,前のままでも問題ないと思って提出していなかった. 出力判定関数も書いていたのに,そもそもその判定関数が間違っているという...

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

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

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

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

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

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

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

調べてみると,Google Apps Scriptでcronっぽいことができるらしい.(参考

JavaScriptほとんど使ったことない...)

最終的に,

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

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

AtCoderGoogleカレンダーを公開してくださっているので省いた. 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カレンダーを公開しました.(ついでに,ブログの文体も少し変わっている.)

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

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

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

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

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

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


ごめん

ACM-ICPC 2014 アジア地区予選東京大会 参加記

日記

オリセンで開かれたICPCアジア地区予選に参加してきました.アジア地区予選に出場するのは個人でも学校でも初の経験でした.
結果は4完29位(大学別24位)でした.29位だったのでリクルートさんからNiku Awardをいただきましたありがとうございます.

チーム編成

  • 僕(よわいソルバ)
  • たこくん(ソルバ)
  • マスコット(vimrc,テンプレート打ち込み,目diff,お茶くみ)

大体の流れ

開始前

前日からわかっていたことだが,周りが強豪ばっかでこわい.向かいがkatou(東工大),斜め前がprimasta(京大),右隣がnekonyaso(筑波),右斜め後ろがUTouto@Kyoto(東大)とかどんないやがらせですか...本番中みじめになる予感しかしない.

開始~AB解くまで

マスコットにvimrcとテンプレートを打ち込んでもらう.たこくんと一緒にA問題を読み,方針の確認.どうやら,前の方から詰めていくだけっぽい.たこくんに書いてもらうことにし,僕はB問題を読み始める...紙って配られないの?

B問題は構文解析しないといけない可能性も考えたが,左側から順番に計算する方法は単純なループで計算でき,掛け算を優先する方法は先に掛け算記号の処理をすればいい.結局その方針で解くことに.

A問題をたこくんがサブミット→WA.ちょっと時間がかかりそうだったので印刷して代わってもらう.Bを実装し提出,AC.たこくんが条件のミスを発見.訂正し提出→AC.

FとCを解くまで

AB正解したので僕はCを読み,たこくんには後ろの方からざっくりと問題を読んでもらうように指示を出す.
ここでC問題の読み間違えが起こり,依存関係が入口に遠い方から,入口に近い方にしかない(c < d)という条件を忘れてしまう(僕のミス1回目).「他のチームがいっぱい解いているのに,こんなに難しいの?」とか思ってた.ここでだいぶ時間を使ってしまう.

スコアボードを確認すると,Fを解いているチームが結構ある.詰まってしまったのでFを読んでみる.グラフっぽい問題,クラスカル+橋の列挙でいけるなぁと思い,たこくんにライブラリの打ち込みを頼む.(僕のミス2回目.マスコットにやってもらうべきだった)

たこくんがライブラリの入力を終了し,実装に移る.ここでふと気が付く.
「この二辺連結成分のライブラリ...どうやって使うんだっけ?」
幸い,うろ覚えの使い方でよかったのだが,ここで一気に混乱してしまい,実装がうまく進まない.
一端PCから離れて考え直したり,冷静になろうと思ってペットボトルで頭を殴ったりしてた.
ぐだぐだ悩みながら実装を行い,何とかAC.この段階でC問題を他のチームがかなり解いてる.

やっぱりCって簡単なんだよなーと思い,問題を読み直す.しばらくして,c < dの条件に気が付く.なんだC問題簡単じゃん→実装→AC.

後でコーチに聞いた話だと,Cを飛ばしてFを解き最下位争いをしている僕らのチームが一瞬取り上げられたらしい.

終わりまで

「軽食食ってきまーす.」と言って問題とともに去る.Gを解いているところが結構あったので,Gの解法を考えてみる.なんだかSegment Tree使いそうな気配がビンビンする.でもよくわからないなぁとか思ってた.
階乗に戻ると,たこくんがD問題をやっている.いろいろ質問されたが,変なことを言ってしまう(僕のミス3回目).ここでちゃんと対応していれば,5完できていたのですごく失敗だったと思う.
終了間際に,たこくんがDの実装を完了し,提出→WA.これは直せないかなーと思いながらも最後まであがくがACできず.

反省

初の参加で,かつ,全員開催日前後に何らかのタスクを抱えていて練習できてなかったのがつらかった.
そして,僕のワンマンチームだとずっと思い込んでいたのが失敗だった.たこくんをもっと有効活用してあげられたらもっと上を狙えたのかなぁと.完全に采配ミス.

目標の4完は達成できたのでよかった.しかし,順位では下から数えた方が圧倒的に早いので悔しい.
唯一の救いはリクルートさんがNiku Awardをくれたこと.

僕のわがままに付き合ってくれた,たこくん,マスコット(あおこ)さん,先生,ありがとうございました.肉がもらえるらしいので許してください.

来年からは,九大から参加することになる予定なので,足を引っ張らないように頑張りたいと思います.それまでにいっぱい練習しておかないと.

ICPC-JAG Day4 Problem F

ICPC JAG

解説では,Suffix Array + Range Minimum Queryでの解法が紹介されていましたが,僕はクエリ先読み + Aho-Corasick法で通しました.というか,Suffix Arrayよくわかってない.

ある人には,「クエリ先読みするなよ」と言われました.

概要

文字列SとQ個のクエリが与えられる.
i番目のクエリは2つの文字列x[i], y[i]で表現され,クエリに対してSの部分文字列の中でx[i]で始まりy[i]で終わるものを探す.

方針

クエリを先読みし,オートマトンをつくり,Sの中でx[i]が初めに出現するところと,y[i]が最後に出現するところを探す.
Sと全てのy[i]を前後逆にしてしまえば,両方とも全く同じアルゴリズムでよい.

Aho-Corasick法のマッチングを全部取っていくのは無駄.例えば,a, aa, aaa, ... みたいなケースが来たときに,aの判定を真面目にやると計算量が大きくなって時間的にもメモリ的にもつらい.これを改善するため,各状態について受理された文字列の判定は1回だけしか行わない.その時点で受理された文字列があるかの判定は,失敗したとき用のリンクを使って根か,既に判定済みの状態に到達するまでさかのぼることで行う.

ライブラリ写して,ちょっと手を加えて,簡単な実装やるだけだった.ライブラリになっているとはいえ,そこそこ実装コストがある.ただ,聞いた話だとSuffix Arrayも似たようなぐらいの実装量が必要になるらしい.そこにRMQの実装も加わるので,実装コストはこっちの方が若干軽いのかもしれない.

#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define ALL(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;

string S;
int m;
vector<string> vx, vy;

struct PMA{
    int id;
    PMA *next[30];
    vector<int> accept;
    bool flag;
    PMA() { fill(next, next+30, (PMA*) NULL); flag = false; }
};
void buildPMA(const vector<string> &words, vector<PMA*> &vp){
    int n = words.size();
    PMA *root = new PMA();
    root -> id = 0;
    vp.push_back(root);
    int count = 1;
    for(int i = 0; i < n; ++i){
        PMA* v = root;
        int m = words[i].size();
        for(int j = 0; j < m; ++j){
            int c = words[i][j] - 'a'+1;
            if(v->next[c] == NULL){
                v->next[c] = new PMA;
                v->next[c] -> id = count++;
                vp.push_back(v->next[c]);
            }
            v = v->next[c];
        }
        v->accept.push_back(i);
    }
    queue<PMA*> Q;
    root->next[0] = root;
    for(int c = 1; c < 27; ++c){
        if(root->next[c] != NULL){
            root ->next[c]->next[0] = root;
            Q.push(root->next[c]);
        } else root->next[c] = root;
    }
    while(!Q.empty()){
        PMA *v = Q.front(); Q.pop();
        for(int c = 1; c < 27; ++c){
            if(v->next[c] != NULL)
                Q.push(v->next[c]);
            PMA *r = v->next[0];
            while(r->next[c]==NULL) r = r->next[0];
            if(v->next[c] != NULL)
                v->next[c] ->next[0] = r->next[c];
            else
                v->next[c] = r->next[c];
        }
    }
}
void searchfirst(const string &s, const vector<string> &word, vector<int> &r){
    vector<PMA*> vp;
    buildPMA(word, vp);
    PMA *p = vp[0];

    for(int i = 0; i < s.size(); ++i){
        p = p->next[s[i]-'a'+1];
        PMA *q = p;
        while(!(q->flag)){
            EACH(j, q->accept){
                r[*j] = i-word[*j].size() + 1;
            }
            q->flag = true;
            q=q->next[0];
        }
    }
}
int main(){
    cin >> S >> m;
    for(int i = 0; i < m; ++i){
        string x, y;
        cin >> x >> y;
        reverse(ALL(y));
        vx.push_back(x);
        vy.push_back(y);
    }
    vector<int> rx(m, -1), ry(m,-1);
    searchfirst(S, vx, rx);
    reverse(ALL(S));
    searchfirst(S, vy, ry);
    for(int i = 0; i < m; ++i){
        int idx = S.size()-ry[i];
        if(idx < rx[i]+vx[i].size() || rx[i] < 0 || ry[i] < 0){
            printf("0\n");
        }
        else{
            printf("%d\n", (S.size()-ry[i])-rx[i]);
        }
    }
    return 0;
}