Arc's blog

競プロなど

競技プログラミングを始めよう(2020年版)

2018年に書いた同タイトルの記事の2020年版です.競プロを始めるにあたって知っておくと良いことのまとめです.

競技プログラミングって何?

端的に言うと,プログラムを書いて数学パズルを解くeスポーツです.競技プログラミングの大会(コンテスト)では,難しい問題を速く解けると高い順位が得られます.

どんな問題が出るかを知りたい方はAtCoder Beginners Selectionを確認してみましょう.

主なプログラミングコンテスト

オンラインを中心に様々なコンテストが開催されています.メジャーなプログラミングコンテストを紹介します.

AtCoder

日本最大級のプログラミングコンテストサイトです.

定期的にコンテストが開催され,それぞれのコンテストの結果に応じて「レート」と呼ばれる数値が増減します.レートが高くなると嬉しくなります.

2020年現在では次のコンテストが開催されています.

  • AtCoder Beginner Contest (ABC)

    • レート増減対象: 0〜1999
    • 概ね週1回開催されるコンテストです.初心者〜中級者向けの問題が出題されます. とりあえずこのコンテストから参加してみましょう.
  • ARC級コンテスト

    • レート増減対象: 0〜2399
    • レート2400未満の人を対象としたコンテストとして,昔はAtCoder Regular Contest(ARC)が開催されていました.このレート帯を対象としたコンテストは現在「ARC級コンテスト」(もしくは単に「ARC」)と呼ばれています.冠スポンサー企業の名前がついたコンテストたちです.
    • 回にもよりますが,ABCの難易度の上限を更に引き上げたような問題構成です(1問目あたりは比較的簡単な問題が出ます).
  • AtCoder Grand Contest (AGC)

    • レート増減対象: 1200〜
    • AtCoder最高難度のコンテストです.2020年6月のAGC045からレート増減対象が1200以上になりました(昔は無制限).

      『 上級者向けのコンテンツです。初級者・中級者の方には難しい問題が多く出題されますのでご注意ください。』 AGC044 トップページ

Codeforces

世界最大級のプログラミングコンテストサイトです.多くのコンテストはJST23時台から2時間ほど行われるため,日本人にとってはつらいかもしれません.たまに18時台スタートのコンテストもあります.

このコンテストサイトでもレートが増減します.問題文は全て英語とロシア語で提供されることに注意.

Google Code Jam (GCJ)

Google社主催のプログラミングコンテストです.年1回行われるコンテストとしては世界最大級です.

オンラインで行われる予備予選と予選3回,そしてリアル会場で行われる決勝で構成されています.(2020年はコロナウイルスの影響で決勝もオンラインになってしまいました)

競プロの勉強をする

競プロが楽しそうに思えてきましたか? 本格的に始めてみたくなったらこの下の記事を読んでみましょう.

言語を学ぶ

競技プログラミングでは様々なプログラミング言語を使えますが,主流はC++です.「使える言語がない!」という場合はAtCoder Programming Guide for beginners (APG4b)C++の学習をしてみると良いと思います.競プロ用途としてのC++の機能はほぼ網羅できると思います.

もし何か使える言語がある場合は,その言語で問題を解いてみましょう.計算量がシビアな問題以外はどんな言語でも解けます.

以下,各プログラミング言語についての個人的な見解です.

  • C++
    • 競プロの主流言語.実行速度の速さ,ライブラリ(STL)の豊富さがメリット.ライブラリを使えばソートを1行で行ってくれる.
  • C
    • 実行速度はC++と同等レベルだが,文字列操作がしんどい.ライブラリが少ない.
    • Cの知識を元にしてC++への移行を考えてもいいと思う.
  • C#, Java
    • ライブラリは豊富.競プロ用途でも十分な実行速度を持つ(らしい).
    • AtCoderの問題はJavaで解けると保証されている(ソース).
  • Python
    • ライブラリは豊富.
    • 実行速度に限界を感じてきたらC++を触ってみると良いと思う.
  • その他
    • よく分かりません…ごめんなさい…

アルゴリズムを学ぶ

ABC300点以降の問題では,問題を解くために何らかのアルゴリズムを記述する場面が増えます.アルゴリズムを勉強するためのおすすめ書籍を紹介します.

アルゴリズム初学者におすすめの本です.豊富なイラスト図解とわかりやすい説明が魅力です.大学でアルゴリズムの勉強をある程度やっている人は,下の本に進んでもいいと思います.

通称「蟻本」.競プロで用いる主なアルゴリズムが網羅的に掲載されています.上の本より難易度は高め.私の高校の先生は「聖書」と呼んでいました(割と正しいと思います).競プロにハマってきたら1冊持っておくと良いと思います.

問題を解く

AtCoder Problemsというサイトでは,過去にAtCoderのコンテストで出題された問題の一覧や,自分の解いた問題の一覧を確認できます.また,問題の推定難易度を表示してくれます.この推定難易度を参考にしながら問題を解くことができます.

例えば推定難易度(Difficulty)が400である場合,レート400の人が50%の確率で解けることを示します.(ソース)

過去問精選 10 問を読みながらAtCoder Beginners Selectionを解いてみるのもおすすめです.

競プロ関連のおすすめサービス

競プロ関連で私がよく使っている便利なサービスを記載します.

  • AtCoder Problems 既に紹介しましたが再掲.他にもVirtual Contest開催機能(過去問を選んで非公式コンテストを作成できる機能)などがあります.
  • Codeforces Problems 上のサービスのCodeforces版です.
  • ac-predictor AtCoderでのコンテスト中に,現在の順位からレートの増減をリアルタイムで予測してくれるサービスです.tampermonkeyによるブラウザ拡張機能が提供されています.
  • CF-Predictor 上のサービスのCodeforces版です.こちらもブラウザ拡張機能が用意されています.

割と真面目にKaggleをやってみた話

しばらくの間,割と真面目にKaggleをやっていたので記録(とポエム)を残します.

Kaggleに挑戦するまで

どうしてKaggleを始めたか

大学に入学してから機械学習つよつよな人々に会って刺激を受け,機械学習に興味を持ちました. また,競プロ純粋培養ではスキルセット的に不安を感じたこともあり,機械学習をやってみようと考えました.

競技プログラミングの人間が機械学習に手を出そうとすると,当然(?)始めるにあたっての初手は競技機械学習になります.競技機械学習プラットフォームで有名なKaggleに登録しました. 私のアカウントはこれです.

自分のスキル

  • Python3の基本構文はなんとなく書ける
  • 実はTitanicコンペ(Kaggleのチュートリアル的なコンペ)をちょっとだけやったことがある
    • scoreは0.77511がベストでした.ロジスティック回帰で分類したりしていました.
    • 当時はKaggle版蟻本として自分の中で名高いKaggleで勝つデータ分析の技術(長いので以下「Kaggle本」とします)の存在を知らなかったため,よく分からないまま止めてしまいました.今回はその本を入手できたため,これを参考にしながら進めました.

コンペ概要

参加したのはReal or Not? NLP with Disaster Tweetsです. Twitterの英語ツイート本文(以下"Text"),キーワード1 (以下"Keyword"),送信された場所の地名(以下"Location")が与えられ,それらの情報を元に「そのツイートが災害に関連するものか否か?」を予測するものです. 正確に予測できるほど高いスコアが得られます2

やったこと

特徴量の作成

入力データを機械学習ライブラリが処理しやすいように変換します. 具体的には,文字列をベクトルとして表現したりします.

次の処理を行いました.

Textのクリーニング,ベクトル化

文を処理しやすいような形に変換した後,何らかの手法でベクトル情報に変換します. Kaggleで公開されているGetting started with Natural Language Processing A general IntroductionというNotebookを参考にしながら,以下の処理をしました.

  1. "Word"と"word"が別の単語として認識されたりすると嬉しくないので,Textを全て小文字化.
  2. 句読点やURLなどを除去.
  3. "a"や"the"などの,ごく一般的で解析上深い意味を持たない単語(Stopwords)を除去.
  4. ここまでの処理で綺麗になったTextをベクトル化.

ベクトル化には様々な手法があるようですが,今回は最終的にSWEM-maxという物を利用しました. SWEM: 単語埋め込みのみを使うシンプルな文章埋め込みに詳しい説明があります. NotebookやKaggle本にあったTf-Idfという物も試しましたが,あまりスコアが伸びませんでした.

Keywordの変換

Keywordもベクトルに変換します.今回はOne-hot encodingという手法を用いました. KaggleのNotebookだとusing-categorical-data-with-one-hot-encodingが参考になります.

Locationの削除

NLP with Disaster Tweets - EDA, Cleaning and BERTを読むと,データの33%が欠損していることがわかります. 欠損値の適当な埋め方も分からないので削除しました.

モデルの作成

特徴量を入力して予測結果を出力する「モデル」を作成しました. Kaggle本が勾配ブースティング木(GBDT)というアルゴリズムを推していたのでそれに倣いました. ライブラリはXGBoostを使いました.このライブラリもKaggle本で詳しく紹介されています.

使い方がPython: XGBoost を使ってみるにまとめられていたので参考にしました.

訓練データ(そのツイートが災害に関連するかどうか事前に分かっているデータ)でモデルを作成し,できたモデルでテストデータ(災害に関連するかどうかわからないデータ)の予測結果を出力します.

パラメータチューニング

XGBoostの挙動を決めるハイパーパラメータを調整しました. 手動でやると辛いので,チューニングを自動化するフレームワークを用いました.今回はOptunaを使いました. パラメータの調整範囲などはKaggle本を参考にしました.

チューニングによってPublic Leaderboardのスコアが0.78220から0.79652に伸びました.その後チューニング過程を可視化し,パラメータの調整範囲を変更するなどしてさらなるチューニングを試みましたが,これ以上伸びませんでした.

結果

一般的なKaggleのコンペでは,Public LeaderboardとPrivate Leaderboardという2つの順位表が存在します. コンペ期間中は予測結果の何割か3で算出したスコアに基づくPublic Leaderboardが更新され,コンペ終了後に残りの予測結果で算出したスコアに基づくPrivate Leaderboardが公開される,というシステムになっています. 最終結果として用いられるのはPrivate Leaderboardの方です.

Public Leaderboardのために過学習したモデルを用いて上位になっていても,Private Leaderboardでは順位がとんでもなく落ちている...ということになりかねないワクワク要素です(当然,逆にPrivate Leaderboardで順位が上がることもあります).

このコンペはPrivate Leaderboardが公開されませんでした. ちょっとよく分かってないのですが,ランキング計算外のコンペ(チュートリアルのTitanicなど)ではPrivate Leaderboardが公開されないのかもしれません......

ということで最終結果は一応0.79652ということになります. 3/26現在3403人中1718位で,上から数えて51%の位置でした4. 予測結果の提出は今もできるようです.

f:id:arcslab:20200326224614p:plain

ちなみにGoogle Cloud AutoMLを用いたモデルで上位入賞すると賞金がもらえたそうですが,少し調べた所AutoMLがブラックボックス過ぎた(個人の感想)ので止めました.勉強にならないので......

感想

スコアを0.8に乗せたかったので残念でしたが,Titanicコンペよりはそれっぽいことをできたのかなと思います. 自然言語処理の基本的な手法を知ることができました. Kaggleで勝つデータ分析の技術機械学習コンペを体系的に学ぶ上で非常に良いと思うので,これから始める人は買いましょう(ダイマ).

コンペ終了後に気づいたんですが,どうやらこのコンペもチュートリアルの一種だったようです5. 次回は公式コンペに参加しようと思います.

今後の課題

  • アルゴリズムの中身を理解する
    • 今回はAPIを叩くだけの人になってしまったので.
  • Notebookについて
    • Notebookに全てのコードと考察を書くのは無理があると分かったので,運用を改める.
    • "Notebook JSON is invalid"と言われ,KaggleにNotebookをアップロードできなくなってしまったので解決する(ググっても情報が出てこない......).
  • アンサンブルなど
    • 複数のモデルを組み合わせて性能を上げる手法.これには手を付けられなかったのでやってみる.
  • 実行環境について
    • RAM16GBで足りなくなってしまったのでビビった(Jupyter Notebookの使い方に問題があるような気もするが).また,一般的な4Core CPUだとパラメータチューニングにはどうしても時間がかかる.GCPを使えるようにならないといけないかもしれない.

  1. ツイートに「キーワード」なんて情報は含まれてないような気がします… 「キーワード」はどこから入手した情報なのか結局わかりませんでした.

  2. 正確に言うとF1 scoreという指標です.単純な正答率ではありません.

  3. どのデータがPublic Leaderboardのために用いられているかを参加者が知ることはできません.

  4. 実は「コンペの入出力データのソースを入手して比較する」というチート手法を用いて満点を取っている人がいるようです(ソース).そのため本来の自分の順位はもうちょっと上です(は???)(チュートリアル扱いのコンペらしいので仕方ないね)

  5. “Getting Started"にカテゴライズされているコンペはチュートリアル扱いらしい(ソース).Titanicコンペ以外にチュートリアルがあるとは思ってなかった……

C++で浮動小数点型を扱うときのメモ(精度比較,精度設定)

(Qiitaを退会したため,同名の記事をQiitaからはてなに移行しました) AtCoderで問題を解いていたら、浮動小数点関連のC++の仕様でつまずいたのでメモ。

精度比較してみる

サンプルコード

#include<iostream>
#include<cstdio>
#include<iomanip>
using std::cout;
using std::cin;
using std::endl;

int main(void){
    double pi=3.1415926535898;
    double kilopi=3141.5926525898;

    cout<<"pi---------------"<<endl;
    cout<<"cout "<<pi<<endl;
    cout<<"cout (set(10))"<<std::setprecision(10)<<pi<<endl;
    cout<<"cout (fixed,set(10))"<<std::fixed<<pi<<endl;
    printf("printf %f\n",pi);
    printf("printf (%%.10f) %.10f\n",pi);

    cout<<std::defaultfloat<<std::setprecision(6);
    cout<<endl;

    cout<<"kilopi---------------"<<endl;
    cout<<"cout "<<kilopi<<endl;
    cout<<"cout (set(10))"<<std::setprecision(10)<<kilopi<<endl;
    cout<<"cout (fixed,set(10))"<<std::fixed<<kilopi<<endl;
    printf("printf %f\n",kilopi);
    printf("printf (%%.10f) %.10f\n",kilopi);
    
    return 0;
}

出力

pi---------------
cout 3.14159
cout (set(10))3.141592654
cout (fixed,set(10))3.1415926536
printf 3.141593
printf (%.10f) 3.1415926536

kilopi---------------
cout 3141.59
cout (set(10))3141.592653
cout (fixed,set(10))3141.5926525898
printf 3141.592653
printf (%.10f) 3141.5926525898

分かること

  • coutはデフォルトで 「整数部、小数部合わせて6桁
  • printfはデフォルトで 「小数部6桁
  • マニピュレータstd::setprecision(n)を使うことで「整数部、小数部合わせてn桁」にできる
  • マニピュレータstd::fixedを使うことで「小数部n桁」にできる(小数部がn桁未満だった場合、0で埋められるみたい)
  • マニピュレータstd::defaultfloatを使うことでリセットできる(std::setprecision()で指定したものはリセットされないみたい。要手動リセット)
  • マニピュレータを使う際は#include<iomanip>が必要

簡単なバグ回避策

一番最初にstd::cout<<std::fixed<<std::setprecision(10)としておけば、浮動小数点型を出力する時に全て小数部10桁にできる、との情報をTwitterで教えてもらった。競技プログラミングをする限りではこれで全く問題ない。

参考資料

MaryCore 【C++】小数点の桁数を指定する方法と注意点【cout/iostream】 蒼色工房 printf出力書式まとめ

C++で構造体やクラスをソートする方法まとめ

(Qiitaを退会したため,同名の記事をQiitaからはてなにコピーしました)

C++でクラスや構造体の入ったvectorコンテナをソートする時、「何と何を比較してソートするのか?」を定義しないといけない。幾つか方法があったので自分なりにまとめてみる。

その1 演算子オーバーロード

ソースコード

#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

struct Info
{
    std::string name;
    int age;

    Info(std::string inputted_name, int inputted_age)
    {
        name = inputted_name;
        age = inputted_age;
    }
    bool operator<(const Info &another) const
    {
        return age < another.age;//年齢を比較
    };
    //2つのconstを付けないとコンパイルエラーになるので注意!!
};

int main(void)
{
    std::vector<Info> info;
    info.push_back(Info("foo", 17));
    info.push_back(Info("bar", 80));
    info.push_back(Info("baz", 30));

    std::sort(info.begin(), info.end());//ソート実行

    for (auto itr : info)
    {
        cout << "age:" << itr.age << " name:" << itr.name << endl;
    }

    return 0;
}

出力

age:17 name:foo
age:30 name:baz
age:80 name:bar

解説

operator<を定義しておく方法。sortする時に(暗黙的に)呼ばれたstd::lessoperator<を利用して比較を実行する、と理解している。

operator>を定義しておけば降順ソート(std::greaterを使う方法)もできる。

その2 比較関数を定義する

ソースコード

struct Info
{
    std::string name;
    int age;

    Info(std::string inputted_name, int inputted_age)
    {
        name = inputted_name;
        age = inputted_age;
    }
};

bool cmp(const Info &a, const Info &b)
{
    return a.age < b.age;
}

int main(void)
{
    std::vector<Info> info;
    info.push_back(Info("foo", 17));
    info.push_back(Info("bar", 80));
    info.push_back(Info("baz", 30));

    std::sort(info.begin(), info.end(),cmp);//比較関数cmpを使用してsort

    for (auto itr : info)
    {
        cout << "age:" << itr.age << " name:" << itr.name << endl;
    }

    return 0;
}

出力

age:17 name:foo
age:30 name:baz
age:80 name:bar

解説

sortする時に利用する関数を自力で作っておく方法。

不等号の向きを逆にすれば降順ソートになる。

その3 ラムダ式を使う

ソースコード

struct Info
{
    std::string name;
    int age;

    Info(std::string inputted_name, int inputted_age)
    {
        name = inputted_name;
        age = inputted_age;
    }
};

bool cmp(const Info &a, const Info &b)
{
    return a.age < b.age;
}

int main(void)
{
    std::vector<Info> info;
    info.push_back(Info("foo", 17));
    info.push_back(Info("bar", 80));
    info.push_back(Info("baz", 30));

    std::sort(info.begin(), info.end(), [](const Info &a, const Info &b) {
        return a.age < b.age;
    });//比較関数をラムダ式で作る

    for (auto itr : info)
    {
        cout << "age:" << itr.age << " name:" << itr.name << endl;
    }

    return 0;
}

出力

age:17 name:foo
age:30 name:baz
age:80 name:bar

解説

比較関数をラムダ式としてsort()の所に記述しただけ。シンプルな関数なのでラムダ式で書いたほうが分かりやすいかも?

その他

std::priority_queue()等にも使える。ダイクストラ法を使うときなどに役に立つかもしれない。

AtCoder Regular Contest E - TrBBnsformBBtion + この手の問題に対して汎用的に使えそうなテク

問題概要

原文はこれ

'A'と'B'からなる文字列$S,T$に対して,次の操作を任意の順番で何回でも行える.

  • 文字列中の1字を選ぶ.それが'A'なら'BB'に,'B'なら'AA'に置換
  • 部分文字列'AAA'か'BBB'を1つ選んで消す

文字列$S,T$($1 \leq |S|, |T| \leq 10^{5}$)が与えられるので,次の$q$個 ($ 1 \leq q \leq 10^{5}$) のクエリに答えよ.

  • $(a,b,c,d)$に対して,部分文字列$S[a,b]$を$T[c,d]$にできるか判定せよ

解法

解説AC.部分文字列について「'A'を1,'B'を2に変換し,それらを合計して3で割ったあまり」が等しければ変換可能.累積和を計算しておくと高速化できる.

本題

天才変形に見えてしまって困ったが,kmjpさんの記事を読むと典型テクニックっぽいことが分かる.以下では記事を参考にしながらこのテクニックをまとめてみる. (不備があれば教えてもらえるとありがたいです......)


$S$を適当な集合とする. 「$a \in S$を,操作の集合$M= \lbrace m|m: S \rightarrow S \rbrace $ によって $b\in S$ にできますか」問題を高速に解くテクニックとして,次のものは汎用的に使えそう.

  1. 評価用写像$f:S\rightarrow\mathbb{N} \ s.t. \ \forall m\in M,f(a)=f(m(b))$を用意する
    • 計算が十分に高速である必要がある
  2. $L$を $ M $ の元から成る操作の順列(うまい説明ができない...)として,次が成り立つことを確認する: $$ \forall (x,y)\ s.t.\ x\in S \land y \in S \land f(x)=f(y) , \ \exists L s.t. L(x)=y$$

(評価値が同じであれば相互に変換可能であることを示している)

このとき,$f(x)=f(y) \Rightarrow \exists L\ s.t.\ L(x)=y $であり,$f(x)\neq f(y) \Rightarrow \nexists L \ s.t.\ L(x)=y$である.$f(x)$の計算によって操作方法の存在判定を高速に行うことができる.

$$ \forall (x,y) \ s.t.\ x\in S \land y \in S \land f(x)\neq f(y) , \ \nexists L \ s.t. \ L(x)=y$$

も成立しているか確認しないとまずそうだが,$f(x)\neq f(y)$であれば,

$$\forall L,f(x)=f(L(x))\neq f(y) (\because fの定義) \ \therefore \nexists L \ s.t.\ L(x)=y$$ が成り立つので大丈夫.

この問題について適用すると,

  • $S:=$'A'と'B'からなる文字列の集合
  • $M:=$問題文中の2つの操作からなる集合
  • $f:=$(文字列中の'A'の数+文字列中の'B'の数$\times 2$) $mod\ 3$
    • $\forall m\in M,f(x)=f(m(x))$を満たしている
    • 評価値の計算は累積和を使うことで高速化できる
  • 公式editorialを読むと2番の命題は真であることが分かる

である.

慣れてないと$f$を作るのが辛そう.

ACコード

これ

その他

mathjaxを導入したんですが,「文字列$S$,$T$($1\leq|S|,|T|\leq 105 $)」 みたいになってしまうので解決策をお持ちの方は教えてください... 解決しました

PandocとMarkdownで快適執筆環境を作る

文書を書く際、MS Wordで体裁を整えて提出 or .docxを直接提出する事が多いと思います。しかし実際に書いてみると、

  • Wordが重い
  • 直接書くと体裁が崩れがち
  • 白背景嫌い

などの問題が発生しました。そこで、Markdownで執筆して.docx形式にエクスポートする環境を整えました。それに関してのメモです。

この手の話は既出ネタなので、他の方の記事も読んでみてください。

Markdownって何?

本来はHTML文書を簡単に作るために開発された言語です。Markdown単体で読んでもそこそこ読みやすく、また書きやすいです。この機会に覚えてみるのもいいと思います。

詳しくはMarkdown - Wikipediaなどを参照。

使用するソフトウェア

Pandoc

Pandoc - About pandoc

Markdown→.docxに限らず、(色々な入力形式)→(色々な出力形式)への変換を実現するソフトウェア(雑)。

Bear(などのMarkdownエディタ)

軽くて目の疲れない物を選びましょう。

ソフト自体の説明は別記事におまかせします。Pandocについては多様なフォーマットに対応!ドキュメント変換ツールPandocを知ろう - Qiitaを読めば分かります(記事とても良かったです。ありがとうございました)。

MS Word

レイアウト確認用。

環境構築

ソフトをインストールする

環境と好みに合わせてどうぞ。MarkdownエディタにはBearやVSCodeなどがあります。

Pandocの出力スタイルを作る

PandocがMarkdownを.docxに変換するときに使うスタイルを設定します。

ドキュメント変換ツールPandoc:ユーザーズガイドを熟読して分かったマニアックな使い方 - Qiitaの「ODT/docxの参照用スタイルファイル」項を参照。

ここで指定したファイルのスタイルが変換時に使用されます。

Wordの「スタイル」について

フォント、フォントサイズ、文字色などの設定をまとめたものが「スタイル」です。文書中で同じスタイルを使った文字は全て同じ書式設定になります(それはそう)。

Markdownファイルが

# 見出しA
## 見出しA-a
本文a
# 見出しB
## 見出しB-b
本文b

のようになっていた場合、「見出しA&見出しB」「見出しA-a&見出しB-b」「本文a&本文b」にそれぞれ同じスタイルが適用されます。文の書式を直接いじるのではなく、スタイルをいじることで、書式の揃った見やすい文書を作ることができます。

一番最初に書いた「体裁が崩れがち」な原因の多くは「スタイルを使いこなせていない」のが原因なのかな、と勝手に想像しています(ぼくもあまりわかってない)。一度設定してPandocに任せれば、スタイル設定を自動でやってくれます。

Markdownで書く

軽量エディタはいいぞ。黒背景はいいぞ。

.docxに変換する

Terminal/コマンドプロンプトを開き、Markdownファイルのあるディレクトリ上で

pandoc -f markdown -t docx -o (出力ファイル名) (入力ファイル名)

を実行します。詳しいコマンドはPandoc ユーザーズガイド 日本語版 - Japanese Pandoc User’s Associationを参照。

このコマンドは”From markdown To docx”みたいな意味になります。

出来上がったもの

完成直前のこの記事をPandocで変換してPDF化したものがこちらになります。

まとめ

Word直書きに戻れる気がしません。

他にも色々な活用方法があります。Pandocを使いこなしていきましょう。おわり。

Google Code Jam 2019 Qualification Round に参加したよ

GCJ予選に参加してきました。AB満点で41点でした。予選通過です。

GCJ予選のルール

  • 全4問。
  • それぞれの問題はいくつかの小課題に分かれている。
  • それぞれの小課題には「点数」「Visible か Hidden か」が決まっている。
    • Visible: 採点結果がコンテスト中に通知される
    • Hidden: 採点結果はコンテスト中に通知されない
  • 100点中30点をとれば予選通過。
  • コンテストは27時間開催される。

問題

ネタバレ防止のため、最初に全ての問題文を載せてからAとBの解法を載せます。

A - Foregone Solution

問題文(意訳)

以下の問題がT個与えられるので、全て答えよ。

1つ以上の桁に4を含む自然数Nが与えられる(例: N=4, 434, 4444)。どの桁にも4を含まない自然数の組(A, B)の中で、N==A+Bを満たす物の1つを答えよ。

サンプル

  • N=4のとき、(A, B)=(1, 3)
  • N=434のとき、(A, B)=(232, 202)

制約

全テストセット

  • 1<=T<=100
  • 実行時間制限: 10 sec
  • メモリ制限: 1 GB

Test set 1 (Visible, 6 pts)

  • 1<N<10^5

Test set 2 (Visible, 10 pts)

  • 1<N<10^9

Test set 3 (Hidden, 1 pt)

  • 1<N<10^100

B - You Can Go Your Own Way

問題文(意訳)

以下の問題がT個与えられるので、全て答えよ。

南北方向Nマス、東西方向Nマスで構成された平面がある。

はじめに、Lydiaが南への移動と東への移動を繰り返して、北西の角のマスから南東の角のマスまで動いた。あなたは、Lydiaの移動方法と1度も重ならないようにして、同じように南への移動と東への移動を繰り返し、北西の角のマスから南東の角のマスまで動きたい。具体的には、

Lydiaの移動ルートに「マスAから隣接するマスBへの移動」が含まれるとき、あなたは「マスAから隣接するマスBへの移動」をすることはできない。しかし、あなたは「マスAから隣接するマスCへの移動」をすることはできる。

平面のサイズN、Lydiaの移動ルートを表す文字列P(南への移動はS、東への移動はEで表される)が与えられるので、あなたの移動ルートを表す文字列yを1つ答えよ。

サンプル

GCJ公式の図を参照(Lydiaは青、あなたのルートはオレンジです)。

このとき、N=5, L=“EESSSESE”, y=“SEEESSES”である。

制約

全テストセット

  • 1<=T<=100
  • 実行時間制限: 15 sec
  • メモリ制限: 1 GB
  • Lydiaが北西の角のマスから南東の角のマスまで動くことは保証される。すなわち、Pには文字SN-1個、文字EN-1個含まれる。

Test set 1 (Visible, 5 pts)

  • 2<=N<=10

Test set 2 (Visible, 9 pts)

  • 2<=N<=1000

Test set 3 (Hidden, 10 pts)

  • 最大10個のテストケースで 2<=N<=50000
  • それ以外のテストケースで2<=N<=10000

C - Cryptopangrams

問題文(意訳)

以下の問題がT個与えられるので、全て答えよ。

pangramと呼ばれる、26種のアルファベット全てを少なくとも1回用いて作られた特殊な文字列がある(例: “the quick brown fox jumps over the lazy dog”)。あるpangramを、以下の手順で数列として暗号化した。

  1. Nを決める。
  2. N以下の素数を26個決める。
  3. 26個の素数を昇順にソートする。
  4. 最小の素数A、次の素数B、...最大の素数Zを割り当てる。
  5. pangramを用意し、文字を全て大文字にして、空白を削除する。これを平文とする。
  6. 手順4で構成した文字と素数の対応に従って、平文を数列に変換する。便宜上、この数列をp[]とする。
  7. 暗号数列c[]を、c[i]=p[i]*p[i+1]を満たすようにして構築する。
  8. c[]が暗号化されたpangramの数列である。要素の個数はLである。

N, Lと、L個の暗号数列の要素が与えられるので、暗号数列を復号し、もとのpangramを出力せよ。

サンプル

例としてGCJを暗号化する(注: この文字列はpangramではない)。

'C'→5, 'G'→17, 'J'→29 と対応している場合、

p[0]==17, p[1]==5, p[2]==29

であり、

c[0]==17*5==85, c[1]==5*29==145

である。

制約

全テストセット

  • 1<=T<=100
  • 実行時間制限: 20 sec
  • メモリ制限: 1 GB
  • 25<=L<=100
  • 復号するとpangramになることが保証されている

Test set 1 (Visible, 10 pts)

  • 101<=N<=10000

Test set 2 (Hidden, 15 pts)

  • 101<=N<=10^100

D - Dat Bae

問題文(意訳)

以下の問題がT個与えられるので、全て答えよ。

これはインタラクティブ問題である。

ID 0,ID 1,...ID N-1 を与えられたコンピュータがN台ある。これらのコンピュータにN桁のビット列を与えると、戻り値として、与えたビット列と同じN桁のビット列が返ってくる。

しかし、B台のコンピュータが壊れてしまったため、戻り値がN-B桁しか返ってこない。この戻り値は、与えられたビット列から、壊れたコンピュータのIDに対応する桁を削除したものである。具体的には、

N=5, B=2, ID 0とID 3 のコンピュータが壊れているとき、

  • 01101を与えると111が返ってくる
  • 00110を与えると010が返ってくる
  • 01010を与えると100が返ってくる
  • 11010を与えると100が返ってくる

あなたは、コンピュータに対してN桁のビット列を最大F回送信することにより、どのコンピュータが壊れているかを調べたい。

はじめに、整数N, B, Fが与えられる。その後、あなたは、コンピュータに対して、次のクエリを最大F回送ることができる。

  • N桁のビット列を送信する。不正な入力である場合は-1が与えられる。そうでなければ、N-B桁のビット列で構成された戻り値が与えられる。

また、どのコンピュータが壊れているかわかった場合、次のクエリを1回だけ送ることができる。

  • 壊れているコンピュータのIDを、空白区切りでB個送信する。間違っている場合は-1が与えられる。正解している場合は1が与えられ、次のテストケースのジャッジが始まる(もしくはACになる)。

制約

全テストセット

  • 1<=T<=100
  • 実行時間制限: 20 sec
  • メモリ制限: 1 GB
  • 2<=N<=1024
  • 1<=B<=min(15, N-1)

Test set 1 (Visible, 14 pts)

  • F==10

Test set 2 (Hidden, 20 pts)

  • F==5

解法

A - Foregone Solution

Test set 1

方針

O(N)が間に合うので、A=i, B=N-iとして全探索すればよい。

数nを1桁ごとにstd::vectorの要素として追加するライブラリがあれば、4が使われているかの判定はすぐにできる。なかったら作る。

AtCoder基準の体感難易度

ライブラリがあれば200点

Test set 2

例としてN=434を考える。 各桁に4または0以外の数が出現しない自然数Sと、各桁に4が出現しない自然数Tのうち、N==S+Tを満たすような組を求める(この場合、S=404, T=30。この組はNを一桁ずつ確認することで求められる)。 そして、A=S/2+T, B=S/2にすれば良い。なぜならば、

  1. 明らかにA+B==Nである
  2. Bの各桁は2か0のいずれかである
  3. S/2の各桁は2か0のいずれかであり、Tを足したときに桁の繰り上がりは発生しない

からである。

これによりO(Nの桁数)で求められる。

AtCoder基準の体感難易度

300点上位〜400点下位

Test set 3

Test set 2 の操作は、N,A,Bを文字列として考えたときに、

  • N中のそれぞれの文字cに対して
    • c=='4'ならA+='2' , B+='2'
    • c!='4'ならA+=c , B+='0'
  • Bの最初の方で連続している無駄な0を削除する

という操作をすることと等しい。

文字列化することでオーバーフローの心配がなくなった。

AtCoder基準の体感難易度

300点上位〜400点下位 実装はset 2 よりも楽

B - You Can Go Your Own Way

Test set 1, 2

略。3を解きに行ったほうがわかりやすいので

Test set 3

方針

Lydiaが南に動いたら自分は東に、Lydiaが東に動いたら自分は南に動けば良い。

こうすることで二人の移動ルートが「北西の角と南東の角を結んだ対角線に対して対称」になる。ルートが直交することはあっても重なることはないのでAC。O(N)

AtCoder基準の体感難易度

300点。体感ではAより楽

C - Cryptopangrams

解けてないです ごめんなさい

Test set 1 は素数列挙してゴリ押し因数分解するだけなはずなんだけどなぁ…

D - Dat Bae

あまり考えてないです ごめんなさい

二分探索をうまく使えば解けそうな気がしました

その他雑記

  • 問題閲覧画面ですが、ブラウザ内エディタが強制的に問題文の横に出現する仕様でした。正直いらないです。
  • スマホコーディングはつらいです。
  • GCJ Round 1もがんばります。