blogskol

思わず声に出して読みたくなるブログ

くそ謎解き003 解説

問題

挨拶

毎年恒例くそ謎解きも今年で三年目ですね．
一年目は正解でないかな？と思ってコンテスト時間を24時間にしたのに6分27秒で解かれ，二年目は少し難化させたつもりが4分2秒で解かれました．
今年はさらに難化させたつもりですが，もう学習したので「今回のでも10分は持たないかもな」と心の準備をしていました．

2分30秒　なんで？

A 問題は提出用の自明枠のつもりで，B問題単体で最低でも5分は確実に持つと思っていたので，1分41秒で B が通されたのには流石に唖然としました．

問題の難化が参加者のインフレに全く追いつけていませんね．（そもそも難化していないのか？）

解答と解説

A

答え
うまい（美味い）
解説
コーラは美味いので．
上手い・下手と書かずにひらがなで書いてあるのがヒントのつもりらしい．

ありの方は全て末尾に「ぼう」をつけると別の単語になるというカスフェイクがあります．
くそ謎解きだから実は「コーラ棒」という商品があるってオチだろ！みたいな浅はかな思考の参加者がいると嬉しいな〜と思って出しました．

ペナが二個以上ついている人間がいる時点で「あり」も「なし」も答えじゃなさそうなことが分かっちゃうね．

B

答え
にふ（二歩）
解説
行ごとに見ると全てカタカナで書いた時に裏回文になっている．

「レリ」を裏返して逆から読むと「ニフ」になるので答えは二歩．

裏回文として使える文字を全て列挙した時にラ行が全部あることに気づいたので無理やり出しました．
謎の文字列「らろる」「れり」がいい感じにくそ謎解き感あると思います．

感想

解ける人間がいるけどいい感じに難しいくそ謎解きを作るの難しすぎ！
ノリで始めただけで別に謎解き経験とかもないしね．

今回のが爆速で解かれたのって実は裏回文が謎解き界隈の高度典型だからだったりしますか．．．？
そうでもないと流石に説明が付かないと思います．
あるいは俺のツイートが実は超有名だったか．

前回・前々回と一問コンテストにしてしまい参加者の人数を把握出来なかったので今年は自明枠？の A 問題を生やしたんですが，実は普通に難しかったみたい．
僕の中ではかなりくそ謎典型を出したつもりだったんですがそうでもなかったらしい．
毎回上位が強すぎるせいで感覚がバグっていたが一般人は解けないのが普通かも．
みんなの誤提出が気になり過ぎる．

来年こそは10分持つ謎を作るぞ！

ARC163-D Sum of SCC

頂点番号が小さい方から大きい方へ向けられた辺を large edge と呼ぶことにする.
g(t,n,m) : 頂点集合 [n], large edge が m 本, 強連結成分が t 個のトーナメントグラフの個数とする.
答えは \sum_t t\times g(t,N,M) である.

まず g(1,n,m) について考える.
頂点集合 [n], large edge が m 本 であるグラフの個数は E=\binom{n}{2} として \binom{E}{m} と表せる. 従って、

\displaystyle g(1,n,m)=\binom{E}{m}-\sum_{t\geq 2} g(2,n,m)

が成立する.

次に g(t,n,m) から g(t+1,*,*) への遷移を考える. トーナメントグラフの強連結成分はパスグラフであることに注意して、最後の強連結成分を追加することを考える.

[n+n'] を A,B に分割する方法であって、

\displaystyle |A|=n, |B|=n', | \{ (a,b) \in A\times B \mid a \lt b \} | = e

を満たすものの個数を v(n,n',e) とする
v は頂点 n+n' を A,B のどちらに追加するかを考えることで n+n' の昇順に求める事が出来る.

追加する強連結成分の頂点数と large edge をそれぞれ n',m' とすると、以下の配る DP が考えられる.

\displaystyle g(t+1,n+n',m+m'+e) += g(t,n,m) g(1,n',m')v(n,n',e)

したがって g(t,N,M) を求める事が出来る.
以上の漸化式は t に依存していないことに注目すると \sum_{n,n',m',e} g(1,n',m')v(n,n',e) を前計算しておくことが可能で、本番はこれで通した.

直代理記事

AtCoder の色と実力の関係について、AtCoder 社長本人が書かれたそこそこ有名な記事があります。

chokudai.hatenablog.com

ヒューリスティックの色に関して社長がこんなツイートをしていました。

AtCoder 社長という肩書きで記事を書く場合適当なことは当然言えず、何を書いても一定数の外野からは批判をされるので大変でしょう。
なので僕が代わりに書くことにしました。

灰色

コンテストに参加すればなれます。
実力的な保証は一切ないです。

茶色

簡単な貪欲が書けると茶色になれます。

緑色

動的計画法などで貪欲より少し改良した解を書けると緑色になります。 センスのいい人間だと貪欲だけでもなれます。

水色

焼きなまし法やビームサーチなど、ヒューリスティック用のアルゴリズムを1,2個覚えると水色になれます。 アルゴリズムのレートが青〜黄色程度あると動的計画法の高速化などで、上記のアルゴリズム無しで到達する人もいます。

青色

この辺から化け物しかいないので説明をサボります。僕もここです。

黄色

頭おかしいです。ここに行きたいです。最早意味もない気がするので問題も貼りません。

橙色

サボりました。

赤色

化け物です。そもそも海外に3人しかいないです。世界でも18人しかいません。

終わりに

ヒューリスティックはアルゴとレートの仕組みが異なっていて、アルゴ以上に色と実力の関係を出すことは難しい気がします。
短期コンと長期コンでも測ってる実力全然違うと思いますし。
「こういう問題を解けるタイプの人材が欲しい」と思った時は AtCoder に依頼してその問題ベースの企業コンを開いてもらうのがおすすめです。

くそ謎解き002解説

問題
第一回*1
予備知識を全く要求しない訳ではないですが、誰でも解ける問題なのでまだの方は是非先に挑戦してみてください

挨拶

毎年恒例のくそ謎解きを今年も開催しました
去年は「これ解ける人全然いないだろうな〜」と言いながら、せめてもの情けでコンテスト時間を24時間にして開催したところ 6分27秒 で解かれたので、今年はもう少しだけ難易度を上げることにしました
タイトルに「くそ」と付いているのでどれだけ難易度を上げても怒られることが無いのがこのコンテストのいいところです
とはいえ24時間誰にも解かれないと寂しいところですが...









4分2秒で解かれました
これそんなに簡単なのか

去年も今年も運営の shop_one には事前に問題を確認してもらい「これ解ける人いるのかな」といった会話をしているのですが、2年連続で裏切られた形になりましたね



解説




数字 × アルファベット = 数字 の謎の式が書かれています
一見するとアルファベットに特定の数を割り当てる問題にも見えます
F=2 と考えて 30 を提出した人も多かったのでは無いでしょうか
これが正解でないことから、式は計算問題などでは無く、もっと別の意味があることがわかります

ここで、数字とアルファベットの組みとして表せるものを考えてみることにします*2
そういえばこの問題はくそ謎解き002 A 問題ですね？

本問題を扱うサイト Shitforces では公式レートが付くコンテストがいくつか開催されており、特に「くそなぞなぞ Beginner Contest（くBC）」は来たる 2022/12/31 に第 23 回を迎える息の長い大会です
くBC では例えば以下のような問題が出題されています（ネタバレ注意）


くBC 001 C
問題 : かつて京都にあった、監視を学ぶ2年制の大学ってなーんだ？
答え : ろくはらたんだい

くBC 001 F
問題 : ニッチな法ってなーんだ？？
答え : にしんほう

くBC 011 E
問題 : 非道な行為に遭遇してしまうのって何時？
答え : れいじ

と言うわけで、今回の謎は答えが数から始まるくBCの問題を表していました
従って、謎の答えは

くBC 015 F
問題 : あなたが命令する鳥ってなーんだ？
答え : しじゅうから

より、40 となります

感想

去年謎解きを出したことを思い出し、30分程度で急いで作問を行いました
今年の方針は「回文を出さない」です
くBC の答えを見つけるのに苦労するかなと思ったのですが、しっかりした参加記をつけている方がいらっしゃったので簡単に見つけることが出来ました
問題が出来上がったのが 17 時前で、そこで初めてshop_one にコンテストを開きたいと連絡をしたのですが、その日の 21 時からのコンテストサイトを 18 時には作ってくれました
いつも仕事が早く、本当に頭が上がりません
今回の問題はローラーすれば当てられてしまうと言う懸念点があり問題文内で提出制限を設けたのですが、これも彼のアイデアです

冒頭にも書いた通り出題時はほとんど解かれないと思っていたのですが、5分も持たなかったですね...
過去問の答えと照らし合わせる時間も考えると本当に一直線に解かれてそうでとても驚きました
分かってしまうと簡単な問題にも見えるけどねぇ

去年くそ謎解きを開いた時の反省事項として「難しい問題一問だけのコンテストは参加者数が分からない」と言うのがありました
shitforces の順位表からは「正解者数」と「誤答者数」しか分からず、「未提出者数」は分からないからですね
これは結構困ったので次回開催時は簡単な問題も入れようと思っていたのですが、すっかり忘れてました
逆に提出制限つけちゃったから適当に答えづらくて、こちらが認識していない参加者がそれなりにいるんじゃないかと思っています（願望も混ざっていますが）
簡単に 15 \times 2=30 と言う誤答が導けるのが不幸中の幸いでしたね、完全に偶然ですが
今後一問コンテストなどを開く人は気をつけてください

それでは、来年のくそ謎解きで会いましょう

*1:解説

*2:謎解きの解説ってどうしても流れが唐突になるな

模擬地区予選2022

引退してるけどチームメイトと出ることに
コピぺや同時コーディングの禁止を完全に失念しており参加したことをかなり後悔
ワシも若い頃 2回程 ICPC に出たのじゃが、あの頃はコピペも同時コーディングもありだったんじゃ...

コンテスト

A

shakayami がすぐに通してた

B

se1ka2 が読むも英語に負けたので俺が読む
読解するとやるだけなので丁寧に実装して通した

C

中国人郵便配達問題であることはわかる

問題名うろ覚え

se1ka2 が郵便配達問題は最小重みマッチングだと言う
最小重み一般マッチングは人間が書くものでは無いと主張すると、se1ka2 が二部グラフにしてくれた
そのまま蟻本写経して MCF を含めて全て実装してくれた 偉すぎ賞授与
デバッグを手伝っていると se1ka2 が構造化束縛や emplace を知らない事が判明 偉すぎ賞剥奪
バグを治すと通った そこそこ偉い賞授与

D

O(N^2 \log N) の LIS をやればいいんだろうな〜とは思うが、詰めたくなくてしばらく放置
dp[k][j] : 長さ k の数列で一個前が j のもののうち二個前が一番小さいもの として vector< map<int,int> > dp(N+1) を作成
各 map が勝手に単調減少になると思っていたが、WA が出たので操作を付け足して AC

E

末尾2個だけ覚えれば良いので O(N^2) は思いつく
少し時間を置いてからもう一度見ると、ただの分割統治 FFT であることに気が付くが、FFT も書きたく無いし TL もそれなりに厳しそう
実装が空いたら書いても良いと思ったが最後まであかず

F

重複はロリハで簡単にチェック出来る
同型判定に悩んでいたが、天才のひらめきにより解説と同じ方針でロリハで判定出来ることに気づく
気合いで実装するも WA
hash の衝突であってくれ〜と叫びながら激ヤバ実装で hash を無理やり三つに増やすと通った

G

やばすぎて誰も手を付けず
そらそう

H

SCC しても DAG の処理どうするねんと思っていたが、se1ka2 が DAG はパスになると言って通す
パスになるの典型知識の見た目してるけどどうなんだろうな
と言うか見たことある気がする

I

色々悩んだけど俺は分からず
se1ka2 が解けたっぽいが K と実装を奪い合い結果的には両方通らず

J

shakayami がボロノイ図と言うが知らず
なんとなく強い人間はサクッと通しそうな見た目に見えたが 0AC らしい

K

shakayami が天才で、ロリハが出来ることを思いつく
二人で紙で実装を固めておき、I から実装を奪い書くもバグしまくり
コンテスト後も20分やり続けようやく sample が合うようになったので出すもジャッジは止まっていた

ただ書き上げたのは少なくともロリハの mod に 998244353 を使っている時点でダメっぽい
base をランダムに3つ使っている（mod は面倒だったので使い回し）から衝突はしないと思ったが、文字列長が 998244353 を越えるため、どんな base であろうと 998244353 を落とせるテストケースが入っているとのこと（他に有名 mod 二つ狙い撃ちされているらしい）
文字列長が mod を越えるケース初めて見たかも

L

重心を根にして部分木の同型判定をすれば良いことまでは分かる
適当に部分木の情報を使って数次元の hash 作れば良いだろうなと思い、実装が空いたら書こうと思っていたが最後まで空かず

ABCDFH の6完12位

感想

幾何以外きちんと（一部あっているか分からないのもあるが）解法が出ていたのはかなり成長を感じる
Modint が何回か活躍したので前半に書いておいたのが偉かった気がするが、たくさんの CE の原因にもなった
良問多くて、本当に問題枯渇しているのか？と言う感じ
ただ重実装多く無い？運営は同時コーディングやコピペを禁止したことを忘れているだろ
あと想定では無いのかもしれんが hash を取らせる問題が多い
簡単に複数次元 hash を作れる道具を持っておくと良さそう
昔に比べてだいぶ環境を整えたので、debug 関数やランダムケースハックなどが使えないのかなり辛かった
コンテスト後にやったカルカソンヌが面白かった
初見のボドゲは後から反省点が色々見つかるのでまたそのうちやりたい

数学論文をtexで書く時の備忘録

検索するといくらでも出てくるが、初めて論文を書いた（書いている）人間の生の声として

エディタ

スペルの補完機能や、PDFをリアルタイムで表示してくれる機能は個人的に必須

筆者はプログラミングで普段使いしている vscode をそのまま使っている
スペルミスを教えてくれる拡張機能があるので、入れると良い
スペルが間違っていると次以降同じ単語を書く時に補完が効かなかったり、逆にずっと間違った方に補完されたりする
正しいスペルの候補を出してくれたり、ソフト側が知らない単語（専門用語など）はその場でワンクリックで教えられるので非常に使いやすい
他の環境についてはどのようなものがあるかは分からないが、何かしら自動でスペルチェックする機能は使うべき

その他 vscode で良いと思った点は

  • PDF 側を⌘を押しながらクリックで tex の該当箇所に飛べる
  • tex 側のラベルのある場所にカーソルを合わせると PDF の該当箇所に飛ぶボタンが出てくる
  • @を使う事で簡単にギリシャ文字が打てる（あんまり使わない）

などがある

自動でバックアップを取ったり、複数人で同時に編集出来るエディタもあるらしい
俺もそういうのが良かった
色々調べたり、先人に聞くのが大切

ラベル

Lemma や Theorem には必ず label を付ける
後で参照するかどうかに関わらず付けた方が良い
理由としては、

  • その定理が何についてのものかが後からぱっと見で分かる
  • 折り畳んでいても内容が分かる
  • 参照先でも何を参照しているのかがぱっと見でわかる
  • 定理を一言で書き表そうとする際に理解が深まることがある
  • ラベルにカーソルを合わせる事で PDF の該当箇所に飛べる

などが挙げられる

ラベルを付ける際は \label{lemma:augmenting path} の様に、最初に lemma: や theorem: のようなカテゴリを付けると良い
これをするメリットとしては、

  • 名前の衝突を避ける（例えば、augmenting path についての定義と定理でラベルの名前が衝突しない）
  • 参照の際エディタの補完候補を絞れる（参照する定理のラベルの名前を忘れていても、とりあえず theorem: まで打てば補完候補が減り見つけやすい）
  • 定理が後から（より強い結果を発見するなどして）補題に変わった際、Theorem のまま参照してしまう自体を防げる

最後のについてもう少し具体的に書く
Theorem \label{A} をTheorem \ref{A} と書いて参照していたとする
その後定理が補題に格下げされた時、Lemma \label{A} とだけ書き直して、参照先では Theorem \ref{A} のままにしてしまうことがある
このミスは、初め Theorem \label{theorem:A} 、Theorem \ref{theorem:A}と書いておけば、格下げの際は Lemma \label{lemma:A} と書き直すため、参照先でTheorem\ref{theorem:A} のままにしてしまっていても、「theorem:A と言うラベルは存在しない」と言うエラーによって気づけるようになる

表記とか

なるべく既に論文で使用実績のある表現を用いる
英語で数学論文を書く人の為のチートシートみたいなものがあると便利
単語を打ち込むと arxiv の論文でその単語が使われてる箇所を検索してくれるサイトなんかもある（一緒に使う前置詞などを知るのに便利）

同じ表現が連続することを過度に恐れない
文法的に間違ったりしていなければそこまで問題はない
書き直すにしても、そこの表現に力を入れるのは全部書き終わってからで良い

数式も文の一部と思って句読点を付ける
数式モードで 2,3 個の数式を書く時などもきちんと , や . を付ける

表現が分からない箇所は飛ばしたり適当な機械翻訳を書くのではなく、日本語をそのまま書いておく
日本語で書かれている箇所は後から見つけやすく、何を書きたかったのかも一目でわかる
下手に機械翻訳の英文などで埋めてしまうと、後から見返した際ぱっと見で気付きにくい