2025-12-18

QRコードを本当に目だけで読むときに覚えると便利なこと (α版)

こちらの記事は、エンジニア作業飲み集会 Advent Calendar 2025 17日目の記事です(ごめんなさい遅刻しました🙇‍♂️)。

はじめに

この記事は何？

この記事では QRコードを 目だけ (つまり、メモ使用禁止) の状況下で読もうとするとき、「何をどうやって覚えればいいか」を書いています
なので、QRコードの計算式を紹介で留めず、なるべく解釈しようとしています
書いてあることをそのまま使ってもいいですが、読者各自が自分なりに覚えやすいように再解釈されることを想定しています
なるべく補いましたが、基礎的な内容の説明がないことがあるため、内容の難易度は高めです

注意事項

この記事の有効性は十分に示されていない α 版です(言い訳: 自分で実験有効性検証が間にあいませんでしたごめんなさい) 。過度に期待しないでください
筆者が1人でとりあえず考えただけの内容です。特に学術的裏付けがある覚え方とかでもないです
初心者向けなので、なるべく人間にできるように努めていますが、覚えなきゃいけないことはどうしてもあるので、頑張ってください
数字モード・英数字モード・漢字モードの読み方・覚え方はないです、ごめんなさい
もしなにか間違っていたらご指摘ください
QRコードは株式会社デンソーウェーブの登録商標です

(多分)必要な前提知識

QRコードの基礎的な用語についての知識(「バージョン」「誤り訂正レベル」など)
QRコードのなんとなくの構造や作り方

対象読者

他の人がどうやってQRコードを目で読んでいるか気になる人
これからQRコードをメモあり or メモなしで読めるようになりたい人
QRコードが好きな人
UTF-8 が読めるようになったので活用したい人

はじめに
そもそもなぜ目でQRコードを読むのか？
目で解読するために見る場所
① バージョンを特定する
- 理屈について
②「誤り訂正レベル」と「マスクパターン」をみる
- 「誤り訂正レベル」の復元の仕方の覚え方
- 「マスクパターン」の復元の仕方の覚え方
小休止
③ モードを確認する
④ 文字数を確認する
- 文字数を表すbit数
- 読む場所を特定する
⑤ 内容を見ていく
まとめ
参考文献

そもそもなぜ目でQRコードを読むのか？

セキュリティが叫ばれる昨今、危険なQRコードが世にはあります *1 。

安易にQRコードを読むわけにはいかない。しかし、中身は気になってしまうのが人間の性である。手元にメモなどもない、写真を取ることもできないとき、そういう時はどうしますか？

そう、目だけでQRコードを読むしかありませんね。あと読めたらなんかネタになって面白いかなって。

目で解読するために見る場所

大まかに、①～⑤の箇所を順番に見ていく

① バージョンを特定する

② 「誤り訂正レベル」と「マスクパターン」をみる

ーーここまで初級者向けーー

③ モードを確認する

④ 文字数を確認する(※マス数は正確ではない)

⑤ 内容を見ていく

① バージョンを特定する

覚え方は簡単で(比較的)読みやすい箇所である、一番簡単なパート。

ずばり、1本の「タイミングパターン」の黒マスの数を数えて、2で割った商を求めればよい。

つまり、1本の「タイミングパターン」の黒マス*2の数を $a$ とすると、 $\lfloor a/2 \rfloor$ ( $a/2$ の切り捨て) の値がバージョンとなる *3。

下図の例だと、1本の「タイミングパターン」の黒マスクの数が5なので、 $\lfloor 5/2 \rfloor = 2$ と計算されて、このQRコードは「バージョン2」であることがわかる。

理屈について

なぜこの考えで計算できるのかを書いておく。

QRコードのバージョンを $v$ とすると、QRコードの一辺のマスの数は $21 + (v - 1) * 4$ になる。つまり、「最小のバージョン1が21。バージョンが1つ上がるごとに、4マス増える」ということである。これは後でも使うので、これも覚えておこう。

これを逆に、「QRコードの一辺の長さ」を $l$ として $v$ を求める式として整理すると、 $v = (l - 21)/4 + 1$ となる。ようは、「21から何回4が足されたか」ということである。なので、辺のマス目さえ数えられれば、目的のバージョンが求められる。

しかし、ここで問題が発生する。QRコードはその性質から、「黒マスや白マスが連続する」ことがある。同じ色のマスが連続すると、思った以上に数えにくくなる。実際、上図にあるようなの2番目に小さいQRコードであるバージョン2 (1辺 25マス)でも、青枠で数を数えようとするのは大変である。ここで、「ファインダーパターン」の周りのマス目の数がバージョンごとに固定であることに着目し、さらに「タイミングパターン」があることに気がつくと*4、タイミングパターンのマス目の数を $l'$ とすると、「ファインダーパターン」(1つ外の白マスを含め)のマス目の数は 8 なので、 $l = l' + 8 * 2$ になる。

さらに、タイミングパターンの黒マスの個数を $a$ とすると、どんな場合も $l'$ は奇数かつ黒マスのほうが多いから、白マスの個数は $a - 1$ 、なので $l' = a + (a - 1) = 2a - 1$ 。よって、 $l = 2a + 15$ 。これをさっきまでのバージョン計算式に入れて整理すると、 $v = (2a - 6) / 4 + 1 = (2a - 2) / 4 = (a - 1) / 2 = \lfloor a / 2\rfloor$ となる。

したがって、タイミングパターンの黒マスの個数さえ分かれば、あとは2で割るだけで済むわけである。お手軽！、脳に優しい！

②「誤り訂正レベル」と「マスクパターン」をみる

「誤り訂正レベル」と「マスクパターン」は、「形式情報」を表すbit列の最初の 5 bit に収められている。最初の5bitは "10101" でマスクされているので、外す*5。交互にマスクを外すことに慣れておけば、思い出せやすくなる、と思う。

5bitのうち、最初の2bitが「誤り訂正レベル」で、後半が「マスクパターン」。

「誤り訂正レベル」の復元の仕方の覚え方

「誤り訂正レベル」は L→M→Q→H の順番に復元能力が高くなる。

「Low → Medium→ High で、 M と H の間に Q」 と覚えるとよい。

ちなみに復元能力も L → M → H で約2倍ずつ増え(7%→15%→30%)、 Q は 25% なので M と H の間になる。Q は Quarter (¼ = 25%) と考えると、復元能力含めて覚えやすい？*6

「誤り訂正レベル」のbit列 0(00), 1(01), 2(10), 3(11) が、具体的にどのレベルに当てはまるかという順番は、そのbit列が表す数字の順番に M → L → H → Q (上下2つにわけてそれぞれの順番が逆転している) と覚える。

なお、本記事ではマスクを外して考えたが、マスクを外さずに対応表が作成されることも多い。

「マスクパターン」の復元の仕方の覚え方

「マスクパターン」は、見たまま白黒を01に置き換え、2進数の数字として読めばOK。3桁で0-7までなので、難しくない。ここまでは。

（「マスクパターン」の覚え方は必要なところでやります覚悟しましょう）

小休止

なんとここまでで、QRコードを外で見て「このQRコードは『2-Mのマスクパターン1だねぇ～』と言える」ようになった。これでも一般には驚かれるので、これであなたもQRコード芸人になれるようになったわけである！ (？)……もう一つ、以外とここまでは、実はそんなに難しくないこともわかっていただけたことだと思う。見てるマスも多くても 5 + 13 マス程度で、覚える規則も 10101 のマスクと M → L → H → Q ぐらいである。ぜひ、QRコードを見かけたら試してほしい。

ということで、以下が本編 (？) である。

③ モードを確認する

ここから、より深くQRコードを読んでいく。

まずは右下4マスを読んでわかる「モード」を確認する。これは、どんなサイズでも確定で右下4マスなので、比較的難易度が低い。

ということで、ここからは「マスクパターン」と対峙する必要がある。

マスクパターンを覚える (全体像)

「マスクパターン」は、前述の通り全部で 8 通りである。具体的な形は下の図を参照。

これを以下のように関連性を持ってまとめると、大体 3(+1) パターンに分けられる。

覚えにくい時は、 0xx パターン + 100 からまずは覚えるとよい。

マスクパターンを覚える(「意味 or 形で覚える (101, 110, 111)」パターン)

やはり一番の鬼門はここだろう。式もやや複雑で難しい。この状態で覚えるのは難しいので、とりあえずまずはこれらを解きほぐして、覚える手がかりを上げてみる。

なお、マスクを外すときに「効率よく図形を作り上げる方法」についても解説するので、ここではあくまで「形を覚えること」を主眼にして書いてある。

6×6の図形の繰り返しになり、斜め方向軸に対称

101, 110, 111パターンを 6×6 の図に表すと下図のようになる。
実は、この6×6の形のものが繰り返されていることがわかる。式で考えると、 $i, j$ をあらかじめ $\mod 6$ をとっていても値が変化しないことからわかる。これ以降、 $i, j$ はあらかじめ $\mod 6$ を取られており、 0-5 までの値しかとらないこととする。

更に、 iとjを入れ替えても値が変わらない、つまり i=j軸に対して対称であることもわかる。

なので、漫然とみるとわからなかった図形は「たった 6×6 で表せて、しかも斜め方向軸に対称である形である」ところまで捉えられるようになった。これでもし完璧な形を忘れたときも、この事実を補助輪にすることで思い出しやすくなる(はず)。

各論: 101パターン

式で書くと、

$(ij)\mod 2 + (ij)\mod 3 = 0$

この式を解釈すると、 「 $ij \mod 6 = 0$ 」となる。

なので、以下のいずれかを満たす箇所がマスクになる

「 $i = 0$ 」 or 「 $j = 0$ 」(図左側の左)
「 $i = 3 かつ jが偶数$ 」 or 「 $j = 3 かつ iが偶数$ 」 (図左側の右)

これらを合わせて、図右側のような図形が得られる。

各論: 110 パターン

式で書くと、

$( (ij)\mod 2 + (ij)\mod 3 ) \mod 2 = 0$

101 パターンから、「左辺を全体で $\mod 2$ をとったもの」になっている。

この式を解釈すると、 「 $ij \mod 6 \le 2$ 」となる。

以下のように表に値をまとめてみると、なんとなく同値になることがわかると思う。マスクになるのは、 $a+b$ が偶数になるところなので、 $ij \mod 6$ が2以下のものが該当している、ということである。

ということを踏まえて、例によって6×6の図形を書こうとする。一番左のマス目には $ij \mod6$ を記入してある。そこから 2以下の場所を塗ると、目的の図が得られる。

しかし、これだとまだ覚えにくい*7ので、これを図の右側のように考えてみる。考え方は2通りできる。

101パターンから、塗られる箇所が増えると捉える (左側)
(式のことは忘れ、) 十字のパート (オレンジ) と、3マスのL字が4つのパート (緑) として考える *8 *9

各論: 111 パターン

式で書くと、

$( (i + j)\mod 2 + (ij)\mod 3 ) \mod 2 = 0$

110 パターンから、「 $(ij) \mod 2$ 」が「 $(i + j) \mod 2$ 」に変わっている。

この式を解釈(ほぼ直訳)すると、「 $i + j が奇数$ 」 $xor$ 「 $ij を3で割った余りが1でない$ 」となる。

下図の左側に、6×6のマス目に「 $(i + j) が奇数$ 」と「 $ij を3で割った余りが1$ 」の位置に1を入れたものを掲示する。右矢印の先が $xor$ をとったもので、これが求める図形である。

実は、よく見るとこのマス目を 3x3 の小さい塊でみると、実は2種類の模様しかないことがわかる。しかも、片方がもう一方の反転した図形であることがわかるので、実質1種類の反転市松模様で構成されていることがわかる。この1種類の図形も「3×3の(0, 0), (2, 0), (0, 2)の3個所だけ塗られたもの」と比較的覚えやすい。作り方も、1×1の市松模様から、 (1, 1) と (2, 2) (つまり $ij \mod 3 = 1$ の場所) を反転したものとして、思い出しやすくなっている *10。

マスクパターンを外す

これで一通り「マスクパターン」は少しは手に馴染んできたと思う。

それでは、実際にマスクを外すことを考えていこう。

さほど大きな差があるわけではないが、全部で3パターンに分けて考えてみる。

具体的に話す前に、 "基準点" という概念を導入する。この概念は私が勝手に言っていることで、特に参考文献があるわけではない。簡単に言うと、繰り返しのパターンが見られるときの (i, j) = (0, 0) と同値になる点のことである。要はこの点から今までの図形を描けばいい、という話である。前述の 3パターンは、"基準点" にあたるものが、それぞれ「 $i, j$ がともに 2, 3, 6 の倍数である」箇所に対応している*11。

なので、これからはまずは "基準点" を探し、そこを中心にして図形を描く、という話を繰り返す。

マスクパターン000, 001

"基準点" は $i, j$ がともに 2 の倍数の点である。

モードのマスクを外すだけであれば、一番右下の点を "基準点" と思って適応するとすればよい。

マスクパターン010, 011

"基準点" は $i, j$ がともに 3 の倍数の点である。あとは図の通りに線を引く。マスクパターンを覚えた通り、 000, 001 とは線の引き方が入れ替わっている(あと縦と横も)。

マスクパターン100, 101, 110, 111

"基準点" は $i, j$ がともに 6 の倍数の点である。少し複雑なので、それぞれでもう少し詳細に図に記載してある*12。

"基準点" の位置

ここでは、 "基準点" をどう探すかを考える。QRコードは右下から読むため、右下、つまり、 $i, j$ としては上から考えることになる。なので、 $i, j$ の最大値、つまりQRコードのサイズを知る必要がある。

これはすでに紹介した、 $21 + 4* (バージョン- 1)$ を使う(0-indexedに注意)。

例えば、右下部分で対角線上に6の倍数の基準点がくるパターンを探すと、下図のようになる。サイズが4ずつ増えることから、実は右下の基準点の位置は3パターンしかない。なので、難しいマスクはいっそのこと全パターン覚えきってもいいかもしれない。

モードを読む

ようやく「モード」を読む準備が整った。右下の4マスに「マスク」をとき、指定の順番で 4bit を読む。これが「モード」を表すbit列になる。

モードの種類

bit列が表す「モード」は、順番に並べると以下の8通りになる:

0001: 数字モード
0010: 英数字モード
0011: 構造的連接モード
0100: 8ビットバイトモード
0101: FNC1 (1番目の位置) モード
(0110 はない)
0111: ECI モード
1000: 漢字モード
1001: FNC1 (2番目の位置) モード

各モードの詳細についてはここでは触れないが*13、 8ビッドバイトモードだけでも確実に覚えてほしい。よく見るQRコードにはURLが入っており、URLが入ったQRコードは十中八九このモードになっているからだ*14。

モードの覚え方

ほとんど推敲していない内容であるが、整理すると以下のような構造になっていると思われる:

1 (0001)～ 9 (1001) (6を除く) に値がある
QRコードの基本である4モード (数字・英数字・8ビットバイト・漢字) は popcount が 1 (0001, 0010, 0100, 1000)
FNC1 ECI モードは (0001を除く) **01
特殊なモード(構造的連接・ECI) は **11

④ 文字数を確認する

ここまでで、ようやくモードを読むことに成功した。

残念なお知らせだが、記事が間にあってないしそもそも作ってなかったので、これ以降は 「モードが数字・英数字・8ビットバイト・漢字モードのいずれかである」ものだけについて記載する。それ以外がもうちょっとだけ別の手順が入る*15。

文字数を表すbit数

このあとのbit列には、何文字データが入ってるか、のデータが入っている。ただ、このデータが何bitで表されているかは、「バージョン」と「モード」で変化する。具体的には以下の表のようになっている。一番少なくても、8bit 分は読む必要がある。

読む場所を特定する

QRコードのバイト列の読み方(基礎)

さて、ここで改めてQRコードのデータがどういう順番で入っているかを考える。QRコードのデータがどう入っているかは、ちょっと調べればたくさんでてくると思うので、あえてここでは説明しない。

ざっくりいうと、右下からスタートして上下しつつ左に向かって読んでいくことになる。

また、文字数を表すbit列は、モードをあら合わすのbit列の次に来ることが決まっている。それでは、文字列を表すbit列は、(例えば8bitなら) 5～13bit となる。

実は、これは間違いである。データの入っている順番はそのとおりであるが、 "正しい" データの順番はそうではないことがある。

QRコードのバイト列の入り方

QRコードは、「バージョン」と「誤り訂正レベル」によっては、データの並び順を1byte単位で入れ替える処理が入ることがある。イメージとしては、順番通りに並べられたトランプを、山ごとに(後のカードが下になるように)1枚ずつ配っていき、最後に最初の山から順番に上になるように山を積み上げる、というような動きになる。このときの山のことを「ブロック」と呼ぶ。「ブロック」の数と各「ブロック」に何byteずつ割り当てられるかは、「バージョン」と「誤り訂正レベル」によってまちまちである(下表)。ある程度は法則はあるので *16、「バージョンごとのbyte数合計」と「ブロックの数」さえ覚えることでも多少は対応はできると思う。

なお、ここでバージョン6までしか表に作っていない。理由は表がきれいに見えて覚えやすいのがここまでだからである*17。あと、ブロックをまたいだ読解がそろそろ人間には困難なことが予想できたため、ブロック数の上限を一旦4までとしておいた。テストプレイもやりたくない。

文字数を読む

ここまでやれば、マスクを外しながら適切な場所が読めるようになっているはずである。なので、あとはビット列を文字列として作ったものを 表記のまま 2進数として読めばOKである。

適切な場所を拾う具体例をいくつか出しておく。例えば、4-MのQRコードで8ビットバイトモードであったなら、文字数を表すbit列は、QRコードの右下から 「5-8bit」＋「17-20bit」をこの順に結合した8bitの数字が答えになる。6-Hの数字モードなら、「5-8bit」+「25-30bit」の10bitの数字が答えになる。

なお、2進数→10進数への変換は、上の桁(読んだままの桁)から足し算していくのが意外と楽……だと思う*18。

⑤ 内容を見ていく

さて、ここまで数字・英数字・8ビットバイト・漢字モードが生き残ってきたがここからは、8ビットバイトモードのことだけを考える*19。さらに、8ビットバイトモードは UTF-8 であることを想定する*20。

ここからは正直うまく整理できていないが、一応、私が覚えていると便利だと思うことは、

011 から始まるなら、「後ろの5桁番目のアルファベット小文字」、 010 から「アルファベット大文字」
0xxxxxxx なら、ASCII のなにかと思う
「1110xxxx 10xxxxxx 10xxxxxx」の繰り返しは日本語であることを疑う (諦めて調べる)
それ以外は諦める

ということである。

というのも、実は後覚えるべきことは UTF-8 のことである。ものにもよるが、結局 ASCIIコードを覚えて、日本語の UTF-8 (ひらがな・カタカナ・漢字) とおぼえていくことになると思う。なので、ここから先は別の偉大なる先人を頼ることにして、ここでの詳細な話は控えようとおもう。

「アルプス一万尺」で
Exclam, quoting, number, dollar,
Percent, and, 'pos, paren,
Paren, aster, plus sign, comma,
Minus, dot, slash, colon.
Semi, lesser, equal, greater,
Question, at, brack, backslash,
Bracket, xor, under, backquote,
Brace, pipe, bracelet, tilda.
で記号順を覚えた
— はすじょい (hsjoihs) (@hsjoihs) 2020年2月21日

IME が発明されず、PCに文字を入力するにはコードポイント丸暗記が必須スキルになっていた世界線の小学校教育「はい皆さんいいですか、B列の覚え方は『枷に掘る』、『枷に掘る』です。昔は悪いことをした人の足に足枷というのを付けていました。そこに溝を掘って逃げようとする悪い人を思い浮かべて」 pic.twitter.com/YY6CrCTiRe
— はすじょい (hsjoihs) (@hsjoihs) 2022年8月21日

まとめ

ということで、これまでの流れをまとめるとこのようになる。

「タイミングパターン」の黒マスを数えて、2で割って「バージョン」を求め、
「形式情報」を表すbit列の最初の 5 bit を読んでマスクを外し、「誤り訂正レベル」と「マスクパターン」を特定し、
「バージョン」からサイズを求めて、「マスクパターン」の形を思い出しながら右下の4マスのマスクを外して、「モード」を特定し、
「バージョン」と「誤り訂正レベル」から「ブロック」の数を思い出し、適切な場所から「マスクパターン」の形を思い出しながらマスクを外しつつ、「モード」に応じて適切なbit数を拾って、「文字数」を特定し、
最後に、「ブロック」の数に応じた場所から抜き出して「マスクパターン」でマスクを外して並べたbyte列に対して、UTF-8 のことを思い出しながら具体的な文字列に戻していく

これで、晴れてQRコードの中身を目だけで読むことができる、はず *21。

覚えることがたくさんで大変だね！！！、そんなときにこの記事のことを思い出して、そこから記憶を引っ張り出せたならとても嬉しいよ！！！

どうやって覚えてるかみんなも教えてね！！！

参考文献

(抜粋だけど) 規格書: JISX0510:2018 情報技術－自動認識及びデータ取得技術－ＱＲコードバーコードシンボル体系仕様

*1:電車内の広告に関係ない第三者のQRコードが勝手に貼られてたりとか、道案内かと思ったらPaypayの支払いコードだったとか……

*2:本当はマスではなく「モジュール」というが、言いやすいので本記事ではマスと呼ぶ

*3: 一旦、バージョンはさほど大きくないものを想定する (バージョン6とかぐらいまで、理由は後述)。当然だが、バージョンが大きくなると数えることが難しくなるので、別の工夫が必要になる。もしもっと大きなバージョンのことを考えるなら、「アライメントパターンの数を数える」などの工夫が必要になる……かもしれない

*4:「タイミングパターン」を見れば数えやすいというアイディアは、フォロワーの人から知った(ありがとうございました)。

*5:xorを取ること

*6:なお、私は「QはQRコードのQ！！！」で覚えている

*7:個人の感想です

*8:ごめんなさい、人によっては全然色の見分けつかないかも……

*9:私はこれで覚えている

*10:このあたりの記述の仕方、うまく群論とかで考えると最初の式から計算できるんだろうな、とか思っているが、そのあたりに詳しくないので誰か数学強い人書いてほしい(他力本願)

*11:最初は対角線上が探しやすいが、それ以外でも使えることは意識している

*12:このあたりの覚え方は、正直内容を読みながら行うには少々相性が悪い気がしている。とはいえ、どんなときでも思い出しやすくするため、α版ではこう書くことにした

*13:気になる人は規格書を読もう！

*14:時点でECIモードであることが多い、と思う (と言ったら、QRコード仲間のフォロワーには同意を得られなかった)。なお、データはない。いずれ調べて統計をとっても面白いのではと思っている。

*15:気になる人は規格書を読もう！

*16:仕様書に記載されているのではなく、観察から

*17:バージョン7に入ると、ブロック数はLが2、Mが4、Qは6、Hが5となる

*18:多分そこそこの確率で10の倍数になるからかも (32 + 8 とか、64 + 16とか)

*19:それ以外は8ビットバイトモード……、というかUTF-8とまっっっっっったく違うルールでデコードを行っていく必要があるため、後回しにすることにした。気になる人は規格書を(ry

*20:実は、8ビットバイトモードであるなら UTF-8 とは限らない……、まぁそれはどの文字列に対してもだけれど

*21:冒頭に書いた通り、まだ試すことができていない。みんなも最初は無理せずメモを使おう

2025-05-02

第二回マスターズ選手権参加記

まえがき

2025年に開催された「第二回マスターズ選手権」の参加記です。

本戦会場にいた人なら通じると思いますが、あのVRチームです。

チームメイトのあめんばーさんが先に参加記を書かれていてるので、この参加記では私視点の情報を書いていこうと思います。

amentorimaru.hatenablog.com

予選

予選までにしたこと

大体の流れはあめんばーさんの記事どおりです。

去年は数週間前にメンバーが決まっていたので、それなりに準備を行っていたのですが、今回はかなりギリギリでメンバーが決定したので、直前にさらっと打ち合わせたぐらいになりました（Discordのメッセージ履歴みたら、ABC感想会後の午前2時～3時ぐらいでやってたらしい）。

予選本番

昨年と同じく、VRChatで考察・戦略を相談してからそれぞれの実装に入りました。

ビジュアライザとBをやったらしいです。

Bで何をやったか覚えてなかったけど、とりあえず貪欲して(731M)、そのあと運ぶ順番を雑に2optした(737M)らしいです。

「VRC競プロ部」で60位でしたーー
ビジュアライザとB（とA）やりました_(:3」∠)_
今回もVRCで作戦会議してました
#AtCoderマスターズ選手権2025 pic.twitter.com/oasXMAQDrs
— テッド/妹尾@VRC競プロ部 (@cleantted_s) 2025年3月2日

本戦までの話

手法とかの勉強

今年も本戦に出場できると決まったところでしたが、正直なところ力不足はかなり感じてました。

予選を含めてですが、AHC は出ても簡単な貪欲となんちゃって焼きなましをするぐらいしかできておらず、ちゃんと手法が使えた試しがありませんでした。

特に、確率の問題については、（あめんばーさんも苦手という話もあり、）昨年のマスターズ本戦でも全く手も足も出なかったということもあり、多少でも対策はしておきたい気持ちがありました。

ということで、terryさんとkakumiさんのAHFの資料や、 thumder さんの AHC典型解法シリーズにお世話になりながら、改めて基本的な考え方や焼きなまし・ベイズ推定・ビームサーチに触れていました。

AtCoder Heuristic First-step Vol.1 講義スライド - Speaker Deck

AtCoder Heuristic First-step Vol.1 講義スライド(山登り法・焼きなまし法編) - Speaker Deck

AHC典型解法シリーズ第2弾「焼きなまし法」 #AtCoder - Qiita

AHC典型解法シリーズ第3弾「ベイズ推定」 #AtCoder - Qiita

AHC典型解法シリーズ第4弾「ビームサーチ」 #AtCoder - Qiita

解説を見つつ、一通りの実装をしてみるところまではやって、それなりに勉強にはなりました。が、やり方があまりよくなく、自分で実装しても結局そこまでスコアが伸ばすことはできず、本番で上手く使えそうという手応えは得られませんでした……。最初は、もしかしたらもっと簡単な問題で、上位の人の実装を真似してスコアが伸びていくのを実感していくようにしたほうが良かったかもしれないです。

pahcer

今回、本戦で非常にお世話になったツールです。使い始めも（少しだけわからない点はありつつも）すんなりと使えました（とはいえ、結局チューニングまでは活用できていませんでしたが……）。

terryさん、ありがとうございました！！

AHCのテストケース実行ツール、pahcer v0.2.0をリリースしました！

mac版にて途中でテストケースが止まってしまう問題等が修正されています。
また、AHC042などで平均スコアの変化が分かりづらかったことを受け、小数点以下まで表示されるようになりました。

是非ご活用ください！ pic.twitter.com/91Fic50eGp
— TERRY (@terry_u16) 2025年2月13日

HMDの話

一番の話題であるだろう（かつ、私が一番話したい部分である） HMD の話をします。

本戦に参加してない && 私やあめんばーさんをフォローしてない人にとっては「なんの話？」となるかもしれないので、簡単に説明すると、 本戦会場に2人でHMD(Meta Quest3)を持っていって使っていました。

実は去年本戦に出るときから、 HMD を持っていこうかという話はちらっと出てはいました。そのときは結局持っていきませんでしたが……。今年は本戦に進むことが決定した時点で、 HMD を持っていくこと割と本気で検討していました。（あめんばーさんはともかくとして、少なくとも私の）実力としても人数としても、他のチームと比べて不利であるのは間違い状況で、自分たちの実力を確実に出せるようにはしておきたい、と考えていました。普段から「VRC競プロ部」での活動で3D空間内でペンを使った考察していたこともあり、お互いの認識を揃えるには紙の上で議論するよりも、慣れているVRChatで議論したほうが効果が高いだろうと予測していました。そういうこともあり、自分たちの実力を出す(ある意味普段通りやる)ということで、 HMD を持っていくという選択肢を取るしかないだろう、と考えていました（それなりに悩みはしましたが）。

amentorimaru.hatenablog.com

さて、普通ではないことなので、それなりの筋は通す必要があります。まずはルールの確認です。少なくとも、 HMD の使用を直接禁止するようなものはありません（それはそう）。事前に明確に禁止されていることは、「ネットワークに負荷をかけるような手法でファイルを共有すること」でした。少なくとも、VRChat をやるだけなら、例示されているような巨大なバイナリをやり取りするようなほど、ネットワークには負荷はかけないはずでした。もし回線が集中して問題が起きる可能性があるなら、「テザリングを行って、会場のWi-Fiの回線を圧迫しないようにする」ことにしました*1。とはいえ、どこまでの負荷ならOKかはわからないので、当日確認して許可はとることにしました（なんだかんだで、決断するのは直前になってしまったので、当日許可を取ることなりましたが……）。

もう一つ、HMD を使う上で気をつけなければいけないのは、周りの参加者への影響です。当然ですが、 HMD を使っている間は周りことが見えません。なので、他の参加者の邪魔にならないような使い方をする必要があります。具体的には、「椅子に座ったまま使用する」ことにしました。会場に入った段階で、チームごとのテーブルの間隔が結構あったので、これは問題なく達成できそうだと確認していました。

あと、VRChat は外部に接続するサービスです。ですので、もちろんですが、チームメンバー以外が考察している様子を見れてはいけません。なので、「チームメンバー以外がVRChatで会話ができないような状態」にする必要がありました。これについては、予選のときもそうでしたが、 VRChat の機能で都度その場にいる人の許可がないと同じ場所に入れないような状態（分かる人向け: privateインスタンス）にしていたので、本戦でも同じようにしました。

ということで、運営の方に、「回線に負荷をかけないよう、私用の端末からのテザリングで通信を行うこと」「HMD使用中は、移動はせず座ったまま使用すること」「VRChatでは、チームメンバー以外が参加できないような状態にすること」の3つと、「運営の判断があれば、すぐに使用を中止すること」を条件として提示しました。テザリングについては、むしろ無線の混線のほうが懸念だったらしく、私用端末は使わないほうがよいかもしれないとの話はありましたが、問題があったらすぐに中止するということで、一旦それで許可を取ることができました（本当にありがとうございました）。……その後、コンテスト開始前にあらためて私用端末での通信をOFFにしてほしいとの連絡の際、特別に私達のチームだけ許可するというアナウンスが全体になされたことで、思いがけず注目されてしまいましたが……*2。

これで、晴れて本戦中に HMD を使うことになりました。改めて、運営の皆さまの柔軟なご対応と他の参加者の皆さまのご理解、深く感謝いたします。

本戦の話

本戦中の大体の話は、あめんばーさんの記事を見てもらえればと思います。

私視点の話を付け加えると、

確率がでなかったことに感謝する
ビジュアライザはそんなに時間をかけないようにして作成（とはいえ合計1時間ぐらいかかったけど）。ちなみに結局 LLM は使わず
ビジュアライザ作成の合間にD問題を作成、30分ぐらいでPythonで作って投げた。やっててよかった作問経験
ビジュアライザが一段落したあと、あめんばーさんのA問題の（両手同じにして、順番に近いものを取っていく）貪欲を改善することに（この時点ではAは654M）。TSPっぽくすればなんとかなるかなと思い、 2optをすることに*3
~~あめんばーさんのメンタルケア~~*4
が、色々と齟齬があって、C++ から Rust にほぼ手動で変換することに。参考にしていた提出からのバグ修正も必要になって、2optできるようにリファクタし終えた段階で残り20分に
時間がないので、雑な2optを書いた。が、どこかバグっていてそもそも全部拾えなくなっていた。最後の1分でバグに気づき、30秒で修正して手元で実行せずに投げて、わずかに伸ばした (679M)

ということで、最終結果は 21位でした。昨年度から見ると大躍進です。いや本当に頑張ったと思う。

（本戦のあと、懇親会や二次会がありましたが、ごめんなさい割愛します。話した方々、ありがとうございました！！）

ふりかえって

ふりかえって、やっぱり AHC は「ただ手法を使うだけでは全く歯が立たない」ということを感じています。

結局予選も本戦も、ちょっとした 2opt を実装しただけ、しかも、ほとんどスコアが改善しない、という結果になっていました。本戦のA問題に至っては、チーム全体でいうと下から2番目の結果でした。（言語違いによるハンデはあったとしても、）実装速度にもAHCの実力としても、やはり個人としては課題が残る結果になったかなぁと思っています。「問題の性質にあわせて、正しい手法を正しく使う」ことが大事なんだと改めて思いました。

チーム戦としては、それなりの成績は残せたので、また来年も挑戦します。上手く言ったら、また HMD も持っていきます。

改めて、AtCoderの皆さまとスポンサーの皆さま、参加者の皆さま、本当にありがとうございました！

*1:後述しますが、これは運営が懸念していたものとは違って、逆効果だった可能性はあります

*2:この対応は、他チームからすると「あれは許可されていいのか？」、という話になってしまうので、必要なアナウンスだったと思っています。

*3:見返してて初めて気がついたけど、予選でも2optしていた

*4:なお、本音をいうと私の一番の役割はこれだと思ってました。前述している通り、私の実力が足りない分、あめんばーさんが実力を出せるような状態にすることが不可欠だろう、と考えていました。勝負事での「平常心」、大事

2024-04-09

AtCoderの出題前のDifficulty推定についてのメモ

読む人向け: 思考内容を雑にメモったものです。内容の正確性はありません。批判などはご自由に。発展させてくれるとなお良い。

memo:

AtCoderのABCにおける、出題前のDifficulty推定について、どうやれば精度が上がるかを考える。

Difficulty = どれだけコンテスト中に参加者が解ける割合があるのか、ということを考える必要がある。ざっと以下の点を考慮には入れたほうが良さそう。

考察強度・知識強度・実装強度
- ”難度" ではないのは、個人の感覚による判断によってしまうことを避けた
推定正解率・推定AC時間・推定ペナ率
問題配置

以下詳細

考察強度: どう考えればよいか、どの程度深い考察が必要になるかによるもの。adhoc系はここが高くなる？、dp系の問題もこっちに寄ってくるかもしれない。

知識強度: 知識がないと解けないようなもの、典型があると大幅に解きやすくなるものがここ？（典型により解きやすくなる、は指標分けたほうがよい？）、例えば「最小値の最大値は二分探索」など。検索しやすさや類題の有無・既出とかも影響する？

実装強度: 実装する際に、実装量が多くなったりバグが生まれやすいかどうか（コーナーケースが多いは「考察強度」にはいる？）。ややこしい全探索とか、グラフ探索系とかが当てはまるかも？

推定正解率: 「問題単体でコンテストに出たら、こんぐらいの人が正解するかもね～～～」という感覚値、推定Difficultyを見積もるぞって言われて考えられてるの多分ここだけ

推定AC時間: ACするまでにかかる時間、考察強度と実装強度によりそう。（知識強度が足りない場合はそもそも解けないか膨大に時間がかかることになると思われる）

推定ペナ率: コーナーケースの引っかかりやすさ（考察強度）、バグりやすさ（実装強度）が影響しそう。

問題配置: 以上を見積もったうえで、問題配置による影響度を考慮するための項。考察・実装強度が高いDより、知識強度がやや高く考察・実装強度が低いEのほうが解かれるやつを考慮したい。

主張としては「考察・知識・実装軸で問題考えてみない？」という話と、「問題配置の影響を考えてみない？」という話がある。

多分もうちょい細分化するとかしてうまいこと「解くとはどういう要素が影響するのか」を詰めれたら。

2023-02-05

ABC288D 別解法メモ

前書き

なるべく愚直な操作でなんとかする解法です。（実質的には同じかもしれませんが、）mod $K$ での累積和を使っていません。

コンテスト中、解法が思いつかずになんとかして無理やり解く方法を考えたもので、綺麗な解法ではないです。

公式解説を読むほうが勉強になると思います。

問題

atcoder.jp

考え方

$l_i=1$ であれば、左から順に可能な限り0にしていき、0にできない残り $K-1$ 個が0になっているかを確かめればよい
$l_i \ne 1$ であるときは、一旦左から順に0にしていったあと、左から 元の数列の値に戻していく ことを考えていく
すると、 $l_i$ から $K-1$ 個については、0ではない値になる

「左から0にする」操作のあと、「左から元の数列に戻す」ということをすると、0で初期化された長さ $r - l + 1$ の数列に範囲の右から $K - 1$ 個の値と左から $K-1$ 個の値をそれぞれ足した数列ができる
範囲の長さが以上のとき:
- 範囲左右端の値の間は、 $r - l + 1 - 2 (K - 1) = r - l - 2K + 3$ 個の0で埋められることになる
- ここで、 $0, \dots, 0, a$ (0はK個)は、操作で $a, 0, \dots, 0$ にすることができる*1
- つまり、 $r - l - 2K + 3$ 個の0は、 $(r - l + 3) \% K$ 個でも同じになるため、最終的にできる数列の長さは $3(K-1)$ 以下にできる
あとは、できた数列に対して愚直に操作を実行して、すべて0にできるか確かめればよい
計算量について:
- 範囲の両端の $K-1$ 個の値の事前計算: $\mathcal{O}(NK)$
- 愚直に作った数列が0にできるか確かめる計算量: $\mathcal{O}(K^2)$
- よって、全体で $\mathcal{O}(K(N + QK))$ で解ける

AC提出

atcoder.jp

なお、

D問題、あまりにも頻出・有名過ぎるのでDに置かれてる系だと思うので、知らん人が初見で解けないのは仕方ない気はする。
— chokudai(高橋直大)🐙🔥@AtCoder社長 (@chokudai) 2023年2月4日

https://

あ、一応。典型の考え方も含めて。「この問題そのものが有名」という話ではない。
・区間に足し引きする問題は、imos法の逆の考え方で、始点・終点に足し引きする問題に変換できる
・足す区間が一定（長さK）の場合は、modKが同じ場所しか互いに影響を与えないので独立で考えられる
の2つが典型
— chokudai(高橋直大)🐙🔥@AtCoder社長 (@chokudai) 2023年2月4日

ということだそうなので、こちらの考え方を持っておいたほうが活かせる気がしています。

https://twitter.com/chokudai/status/1621872224465727489?s=20&t=rGTI6O6y-GB3eZShdcJysg

*1:本当はもっと強い主張ができる（公式解説参照）。なぜこれがわかったのに、解説のやり方が思いつかなかったのか……

2023-01-19

ABC260 精進メモ

問題

atcoder.jp

思考過程

長ければ長いほど、とりあえず条件は満たせるので、どこまで「短くできるか」ということを考える。となると、おそらく各区間の端っこの部分で、ここでどうなるかを考える。

最初に、区間の「 $A_i$ の最大値」と「 $B_i$ の最小値」を考えてみる。が、いまいちピンとこない（入力例1だとなにか言えそうだが、入力例3だとよくわからない）。「 $A_i$ の最大値」と「 $B_i$ の最小値」のどちらが大きいかは入力によりそうなので、この値からなにかいうのは難しそう。

では端からどちらか選んでみることを考えてみるとどうか？
入力例3の1つ目(と2つ目)の区間で "1" を選ぶとする。すると、どこまで長くしなければいいか考えてみると、「1よりも大きい中で最大の区間の端のどちらか」である。この場合は "5" になる。ということで、"1"始まりの良い数列の長さは、長さが5から9まで1つづつある。

つぎに、5つ目の区間で "2"を選ぶ、つまり始まりを"2"にすることを考えると、2つ目の区間では"1"が選ばれなかったため、 "7"を選ぶ必要がある。つまり、最低でも"7"以上まで伸ばす必要がある。

こう考えていくと、「良い数列の左端を固定したとき、選ぶ必要のある数の中での最大値が、右端になりうる最小値」として考えられる。ある区間については、最初は $A_i$ が選ばれる候補であるが、良い数列の左端の数字が $A_i$ を超えてしまった場合は $B_i$ が候補になる。最小の $B_i$ よりの大きい数が左端の数字になったら打ち切る。

ということで、候補の数は最大で $N$ 個で、入れ替えが生じるものに対して最大値が取れればいいので、sorted_setを使えば高速で判定が可能になる。Pythonであれば、tatyamさんのSortedSetを使って、追加・削除で $O(\sqrt{N})$ 、最大値の取得に $O(\log{N})$ でできるので、全体として計算量は $O(N\sqrt{N} + M\log{N})$ でできる。
あと、作れる長さを範囲で足し算するのは、imos法*1を使うことで $O(N)$ でできる。