Mister雑記

競プロ記事がメインになりますが、内容は気分次第です。

超自己流! 競プロ解説記事の書き方

この記事はCompetitive Programming (2) Advent Calendar 2018の6日目の記事になります。

先日はiwashi31さんによるWhat COMPETITIVE PROGRAMMING Gives You の日本語訳でした。

はじめに

初めましての方は初めまして、Misterと申します。競技プログラミング(アルゴリズム)が趣味のしがない大学生です。 精進の一環として、はてなブログにて主にAtCoderという競技プログラミングサイトの問題の解説記事をいくつか上げています。

解説記事というのは、簡単に言うと「その問題をどう考察し、どう実装して解いたか?」を主題にした記事のことです。 本記事ではそんな解説記事をどうやって、そして何を意識して書いているかを解説します。いわゆる「解説記事の解説記事」です。

注意事項として、タイトルに「超自己流」とある通り私の解説記事の書き方は完全に自己流となっています。そのため一般的な解説記事にはそぐわないような性質があるかもしれませんが、ご了承ください。

目次

解説記事の構成

今まで何度か解説記事を書いてきた上で、記事全体の構成というのはある程度テンプレ化されてきています。 ここではそのテンプレの各項目、

  1. イントロ
  2. 問題概要
  3. 解説
  4. 実装例
  5. 感想

について簡単に紹介していきます。

イントロ

解説に入る前の導入及び雑談的なものです。例えば下のような一言コメントがそれに当たります。

コンテスト記事などでは入ることがよくありますが、最近はあまり入れていません。

それとここに問題ページへのリンクを貼るようにしています。

問題概要

問題文を要約したものと制約です。

AtCoderは元の問題文がかなり短くてそもそも要約できないことが多々ありますが、Codeforcesのような英語かつ長い問題文のときは読者の負担を減らすことができます。

ただ要約しすぎて原文とは全く趣が異なる文章が生成されることもよくあるので、その辺は悩みどころです。 私は問題を解く上で不要な要素は極力省いていますが、問題空間を把握しやすくする要素は残すようにしています。

そして忘れてはいけないのが制約です。制約は解法を考える上で決定的になりうる要素なので、毎回欠かさずに書くようにしています。 その方が後々考察を述べる上でも好都合です。

解説

考察の過程、及び論理的な解法の導出です。

これはあくまで個人的な意見ですが、解説記事の読者が求めているのは主に以下の2点だと考えています。

  • どのような考察の流れで解法に辿り着いたか
  • Editorialのギャップを埋める補足、あるいはより分かりやすい解法

上の2点はできるだけ入れるようにしていますが、一方でこれらは言語化が難しいことが多いです。場合によっては潔く言語化を諦めて文章量を減らしたりしています。

解説での重要なテクとして、図を挿入することが挙げられます。図は情報量が文章の比ではないので、上手く使えば解説の量を減らしつつ質を高めることができます。

特にグラフ問題では強力なケースが多く、例えばこの記事は図に相当力を入れています。

ただし図を描くには相応の労力がかかるので、費用対効果と要相談です。図を描かなくて済むならそれが一番いいです。

やるだけ?

よくコンテスト後のTLを見ていると「はい」「やるだけ」といった感想がよく流れてきます。本人にとっては考察をするまでもない、自明な解法という意味です(多分)。 精進ログ的な記事ならそれだけでもいいのですが、解説記事と銘打っている以上これらの単語で済ませることだけは絶対にしないように心がけています1

とはいえABC-A,Bではそう感じる問題も少なくありません。そういった問題の解説では、実装する上で便利なテクニックなんかをもしあれば書くようにしています。

実装例

解説に基づいたプログラムの実装例です。ここのやり方については解説記事でも大きく以下の2つに分けられます。

  • コードを本文に埋め込む
  • 提出ページへのリンクを貼る

前者は流れが自然になる一方で、後者は記事全体の文章量が減ってスッキリするといった利点があります。私は前者派です。

マクロ

私が実装例を載せる上で独自に心がけていることがあります。それは「マクロを一切使わない」ことです。 というのも知らない構文に会う度に定義元を探すという作業は、読み手にとって非常に高コストかつストレスになると思っているからです。

ということで私が実装例に書くコードは

  • using namespace std
  • using ll = long long

以外のマクロは一切使っていません。それに加えて必要以上のincludeもしないようにしています。

それでも本番で出したコードをわざわざ整形するのは手間です。というわけで私はこれを意識し始めてから、コンテスト本番でもほとんどマクロを使わなくなりました。可読性が上がって一石二鳥ですね。

感想

その問題の難易度推定や知見、反省を3行くらいでまとめたものです。

正直なくても全然いいのですが、気分で書いてます。

解説記事ができるまで

以上で解説記事の枠組みの解説は終わりです。

続いて、1つの解説記事ができるまでに私がどういった作業工程を踏んでいるかを大まかに解説します。

問題を解く

当然ながら解けない問題の解説は書けません。解けたとしても解説記事を書くか否かは正直モチベ次第です。2

それでもABC onlyはできるだけ解説記事を書くようにしています。コンテスト終了時刻に投稿できるのが一番の理想なので、20〜40分で全完して残り時間でせっせと書くというのが最近のパターンです。くれぐれもコンテスト終了前に投稿しないようにしましょう。

下書き

解説を書くと決まったら次は下書きです。

書く順序は基本的に上から順番です。概要と実装例はそこまで手間ではないのですが、解説の項は難儀することがよくあります。実装例も解説次第で変わることがあるので、やはり上から書くのが一番やりやすいでしょう。

一通り書き上げるまでにかかる時間ですが、全容を把握できている問題なら30分、図が入るとプラス30分くらいです。一方で解説が難しかったり図が大量に入るときは2時間程度もザラにあります。

HackMD

解説記事の下書きですが、私ははてなブログの執筆ページで直書きしているわけではありません。 ではどこで下書きを書いているかというと、HackMDというツールです。

HackMDはオンラインのmarkdown専用テキストエディタのようなものです。書き始めるのが楽で、リアルタイムプレビューができたり自動保存もしてくれる優れものです。3 今ではHackMDで一旦全部書き上げてから、それを整形したものをブログに投稿するという形式を採っています。整形方法については後で述べます。

そしてこの記事も例外ではありません。下書きのHackMDリンクを貼っておくので、参考までにどうぞ。https://hackmd.io/s/SkfUg7mk4

それとHackMDで下書きをする上で注意点が1つ。HackMDのドキュメントはeditableの状態で公開してしまうと、全世界のユーザーがアクセス可能になります。それがコンテスト中なら盛大なネタバレになってしまうわけです。それを防ぐためにも、公開範囲は毎回editableからprivateに変更しておきましょう。

Illustrator

構成の解説の項でも述べた通り、効果的に解説をするために図を挿入することがよくあります。私は図を描くのにAdobe Illustratorというソフトを使っています。有料でお値段もそこそこしますが4、イラスト描画ツールの中では相当高性能なものです。

ただし個人的にこのソフトを競プロの解説に使うのはあまり気に入っていません。というのも、新規にファイルを作って描画して保存して書き出して...というのが結構手間だからです5。こればかりはどうしようもないと割り切っていますが、もっと手軽に使えるツールがあればぜひ教えていただきたいです。

整形、投稿

HackMDで書き上げた下書きは、はてなブログのフォーマットに合うように整形しなくてはなりません。 私ははてなブログmarkdown記法を選択しているので、大部分は下書きのままでも大丈夫です。しかし問題なのは数式で、全ての$$[tex:]に変えるなんて作業を毎回手でしていたら気が狂います6

そこで「退屈なことはPythonにやらせよう」よろしく、専用のプログラムを自作しました。それがこちら。

import sys

in_code_block = False
in_math_block = False
in_math_line = False

lines = sys.stdin.readlines()

output = ""

for s in lines:
    if s[:2] == "$$":
        if in_math_block:
            output += "]</div>\n"
        else:
            output += "<div style=\"text-align: center\">[tex: \displaystyle "
        in_math_block ^= True
        continue

    if s[:3] == "```":
        in_code_block ^= True
        output += s.replace("=", "")
        continue

    if in_math_block or in_code_block:
        output += s
        continue

    for c in s:
        if c == "$":
            if in_math_line:
                output += "]"
            else:
                output += "[tex: "
            in_math_line ^= True
        else:
            if in_math_line:
                if c == "^" or c == "_" or c == "\\":
                    output += "\\"
            output += c
print(output)

このプログラムにHackMDで書いた下書きを標準入力として与えると、はてなブログのフォーマットに合わせたものが標準出力として出てきます。使いたい方はご自由に使っていただいて構いませんが、いかなる不具合があっても責任は取りません。

後はURL、カテゴリ、トップ画像を設定して投稿ボタンを押せば投稿完了です。

最後に

以上で本記事の内容は終わりになります。ここまで読んでいただきありがとうございました。

また重ね重ねになりますが、あくまでこの記事の内容は「超自己流」です。 日頃の精進のログを取るのなら各個人に合った書き方というのがありますし、その方が長続きするでしょう。 それでも「精進ログをつけてみたいけど、どうやって記事を書けばいいか分からない」という方々にとって、本記事の内容が少しでも参考になれば幸いです。

明日はty70jの「競プロにおける Processing の利用+おまけ」です。お楽しみに!


  1. あと個人的にこの表現が好きじゃないというのもあります。

  2. 本ブログの投稿頻度からお察しの通り、最近はモチベが低めです。

  3. 難点を挙げるとすれば、オンラインでないと使えないこととプレビューの都合上時々重くなることでしょうか。それを差し引いてもとても優秀なツールだと思います。

  4. 学生は安めの年1万強で買えます。大学生協なりで取り扱っていると思うので、学生のうちにいかがでしょうか。

  5. あと正直言って操作方法が分かりにくい。

  6. 昔は全て手作業で整形していました。今考えると正気ではないです。