高度合成数 早見表

競プロで 10^n 以下最大の高度合成数を知りたいことが多いので。一覧

桁 #約数 高度合成数 素因数
1 4 6 2,3
2 12 60 2,2,3,5
3 32 840 2,2,2,3,5,7
4 64 9240 2,2,2,3,5,7,11
5 128 83160 2,2,2,3,3,3,5,7,11
6 240 720720 2,2,2,2,3,3,5,7,11,13
7 448 8648640 2,2,2,2,2,2,3,3,3,5,7,11,13
8 768 91891800 2,2,2,3,3,3,5,5,7,11,13,17
9 1344 931170240 2,2,2,2,2,2,3,3,5,7,11,13,17,19
10 2304 6983776800 2,2,2,2,2,3,3,3,5,5,7,11,13,17,19
11 4032 97772875200 2,2,2,2,2,2,3,3,3,5,5,7,7,11,13,17,19
12 6720 963761198400 2,2,2,2,2,2,3,3,3,3,5,5,7,11,13,17,19,23
13 10752 9316358251200 2,2,2,2,2,2,3,3,3,5,5,7,11,13,17,19,23,29
14 17280 97821761637600 2,2,2,2,2,3,3,3,3,5,5,7,7,11,13,17,19,23,29
15 26880 866421317361600 2,2,2,2,2,2,3,3,3,3,5,5,7,11,13,17,19,23,29,31
16 41472 9097423832296800 2,2,2,2,2,3,3,3,3,3,5,5,7,7,11,13,17,19,23,29,31
17 64512 74801040398884800 2,2,2,2,2,2,3,3,3,5,5,7,7,11,13,17,19,23,29,31,37
18 103680 897612484786617600 2,2,2,2,2,2,2,2,3,3,3,3,5,5,7,7,11,13,17,19,23,29,31,37

おまけ：タイ

桁 #約数 合成数 素因数
1 4 8 2,2,2
2 12 72 2,2,2,3,3
2 12 96 2,2,2,2,2,3
4 64 7560 2,2,2,3,3,3,5,7
6 240 831600 2,2,2,2,3,3,3,5,5,7,11
6 240 997920 2,2,2,2,2,3,3,3,3,5,7,11
8 768 73513440 2,2,2,2,2,3,3,3,5,7,11,13,17
8 768 98017920 2,2,2,2,2,2,2,3,3,5,7,11,13,17
8 768 86486400 2,2,2,2,2,2,2,3,3,3,5,5,7,11,13
9 1344 735134400 2,2,2,2,2,2,3,3,3,5,5,7,11,13,17
10 2304 9311702400 2,2,2,2,2,2,2,3,3,5,5,7,11,13,17,19
15 26880 978217616376000 2,2,2,2,2,2,3,3,3,3,5,5,5,7,7,11,13,17,19,23,29
16 41472 8086598962041600 2,2,2,2,2,2,2,2,3,3,3,5,5,7,7,11,13,17,19,23,29,31
17 64512 96172766227137600 2,2,2,2,2,2,3,3,3,3,3,5,5,7,11,13,17,19,23,29,31,37
17 64512 90974238322968000 2,2,2,2,2,2,3,3,3,3,3,5,5,5,7,7,11,13,17,19,23,29,31

おまけ：デカいやつ

桁数 約数の個数 高度合成数
19 161280 9200527969062830400
20 245760 92005279690628304000
21 368640 989056756674254268000
22 552960 9297133512737990119200
23 860160 92971335127379901192000
24 1290240 985496152350226952635200
25 1966080 9854961523502269526352000
26 2764800 98549615235022695263520000
27 4128768 872164094829950853082152000
28 6193152 9593805043129459383903672000
29 8957952 99775572448546377592598188800
30 13271040 950542574818669103079134726400
31 19660800 9505425748186691030791347264000
32 28311552 78419762422540201004028614928000
33 41287680 927967188666725711881005276648000
34 59719680 9650858762133947403562454877139200
35 88473600 96508587621339474035624548771392000
36 127401984 812899257272051723607760622343648000
37 181665792 9754791087264620683293127468123776000
38 264241152 96328561986738129247519633747722288000
39 382205952 834847537218397120145170159146926496000
40 530841600 8883634049888071919493477334512166560000
41 778567680 92389794118835947962732164278926532224000
42 1132462080 948772116528046081001903379325899388608000
43 1585446912 9250528136148449289768557948427519038928000
44 2264924160 99700136578488842345283346777496594086224000
45 3185049600 997001365784888423452833467774965940862240000
46 4529848320 9295120425625267455575647407255836310192576000
47 6341787648 90627424149846357691862562220744404024377616000
48 9059696640 957397403839402547924291682947351139949835328000
49 12683575296 9334624687434174842261843908736673614510894448000
50 18119393280 87123163749385631861110543148208953735435014848000

ARC116Eとxmas16Hの関係性

競プロ

このツイートによると、ARC116E は xmas16H を少しいじると解けるらしいです。
かなりびっくりしたので証明をしようとしてみたら出来ました。

これら２つの問題はいずれも整数 N, K と N 頂点の木が与えられます。
（xmasの方は重み付きですが、重みなしの問題で考えます）

ARC116Eの概要

K 頂点選んで、各頂点から選ばれた頂点までの距離の最大値を最小化せよ

xmas16Hの概要（ちょっと変えてるけど）

K+1 頂点選んで、選ばれた頂点間の距離の最小値を最大化せよ

双対感があると言われれば、そんな気もしなくはない？

これらの問題の答えをそれぞれ X, Y とすると、 X = \lceil Y/2 \rceil が成り立つことを証明します。

とりあえずサンプルとしてパスグラフを考えてみると、

  • X = \lceil (\lceil N/K \rceil -1)/2 \rceil
  • Y = \lfloor (N-1)/K \rfloor = \lceil N/K \rceil -1

となり、たしかに成り立っています。（厳密に書きましたが、だいたいで良いです）

X \geq \lceil Y/2 \rceil と X \leq \lceil Y/2 \rceil に分けて証明します。

X \geq \lceil Y/2 \rceil

2X+1 \gt Y を示す。

ある頂点から距離 X 以内の頂点の集合をエリアと呼ぶことにする。
エリアから 2 つの頂点を選ぶと、それらの距離は 2X 以下になる。
ARC116E で X を達成する解を 1 つとると K 個のエリアで全頂点が被覆できるため、
互いの距離が 2X+1 以上になるように頂点を選ぶとき、高々 K 頂点しか選ぶことができない。
よって、 2X+1 \gt Y。

X \leq \lceil Y/2 \rceil

2(X-1)+1 \leq Y を示す。

ARC116E の判定問題は以下のアルゴリズムで解ける。

  1. 根を適当に選んで根付木にし、以下を繰り返す
  2. 残っている頂点のうち最も深いものを v とする
  3. v の X 個上の祖先を選び、距離 X 以内の頂点を候補から消す

一方、xmas16H の判定問題は以下のアルゴリズムで解ける。

  1. 根を適当に選んで根付木にし、以下を繰り返す
  2. 残っている頂点のうち最も深いものを v とする
  3. v を選び、距離 Y-1 以内の頂点を候補から消す

これらのアルゴリズムは 3. のみが異なるが、実は挙動はほぼ同じである。
特に、 Y が奇数の場合は X=(Y-1)/2 とすると完全に等しい。
祖先を選ぶか v を選ぶかの差は"祖先"以下の部分木内でしか生まれないが、
いずれにせよ"祖先"以下の部分木内の頂点は全て候補から消されるため、等しくなる。
（最も深いものを v としているのが効いている）

ARC116E の答えが X であることから、 X-1 で上記のアルゴリズムを実行すると K+1 個以上の頂点が選ばれるはずである。
つまり xmas16H で Y=2(X-1)+1 としたときの判定問題は True となるはずであり、 2(X-1)+1 \leq Y が示された。

ちなみに 2X+1 \gt Y の方も同じように示すことも出来ますね。

まとめ

片方の問題の任意の解からもう片方の問題の解への良い感じの写像とかを見つけたかったけど、それは分からなかった。
Y が奇数のときに判定アルゴリズムが等価なのがポイントだったか。

Y が偶数のとき / 辺に長さがあるときも、辺上に架空の頂点があると思えば ARC116E のアルゴリズムが適用出来て、それを整理すると結局 xmas16H の想定解みたいな感じになるような気がしてきた。

ダイクストラ法のよくあるミスと落し方

ダイクストラ法、正しく書けてますか？
ダイクストラは少しのミスですぐ計算量が壊れたりするのですが、テストケースによっては意外に落ちにくく間違いに気づかないこともあります。
この記事では、よくあるミスとその撃墜ケースを紹介していきます。

この記事はどちらかと言うと問題準備をする方に読んでほしい記事です。
writerをする際は、ここで紹介する撃墜ケースをテストケースに入れるようにすると良いと思います。
SではなくTを始点にするという小手先技が考えられるので、逆向きバージョンも入れておくと尚良いでしょう。

ジェネレーターも置いておきます。
コード中の定数を書き換えたり入力で取れるようにしたり、出力形式を変えたりして使ってください。
念の為生成されたテストケースにもちゃんとvalidatorをかけて下さい。


目次

  • 既に見た頂点のcontinue忘れ： O(N^2)
  • 最大ヒープを使う： O(2^N)
  • 負辺のあるグラフで使う： O(2^N)

まず、基本のダイクストラの実装は以下のようになります。
（getDist関数が本体です）

既に見た頂点のcontinue忘れ

26行目の if (dist[v] != d) continue; を忘れるミスです。
うっかり忘れがち。
以下のようなケースで O(N^2) になります。

f:id:snuke:20210222102212p:plain

頂点 2~6 の部分が x 個ある場合：

1. 頂点 1 を始点とする
2. 頂点 2~6 が順に舐められ、毎回 dist[7] が更新される
3. 頂点 7 の番が来た頃には、キューの中に頂点 7 が x 個溜まっている
4. 頂点 7 をキューから取り出す度に x+1 本の辺を舐める

という流れになります。
（しっぽが付いているのは「dist[T] が確定したらbreak」枝刈り対策）

最大ヒープを使う

21行目の priority_queue<P, vector<P>, greater<P>> を priority_queue<P> のようにしてしまうミスです。
C++に不慣れな場合によくやってしまうミスかも知れません。
C++のpriority_queueは最大値がtopに来る仕様となっているため、比較関数を逆にしなければなりません。

このミスをしても一応正しい答えは出ますが、以下のようなケースで O(2^N) になります。

f:id:snuke:20210222074515p:plain

dist[2] が 127 から 1 ずつ減っていきます。

ちなみに、このケースで「pair<距離,頂点> ではなく pair<頂点,距離> にしてしまう」というミスも落とせます。

別パターン（おまけ）

頂点数の制限が超絶厳しい場合は以下のようなケースが良いでしょう。

f:id:snuke:20210222091517p:plain

頂点 i から頂点 j へ 2^{i-1} - 2^j の辺を張っています。
こうすることで「頂点 v を飛ばすとコストが 2^{v-1} 増える」という状況が実現できます。
挙動としては、頂点 4 から頂点 0 へのパスが辞書順に試されるような感じになります。

負辺のあるグラフで使う

負辺のあるグラフでは（負閉路がなくても）ダイクストラは使えません。
おとなしくBellman-Fordなどを使いましょう。
以下のようなケースで O(2^N) になります。

f:id:snuke:20210222084229p:plain

こちらも dist[13] が 63 から 1 ずつ減っていくはずです。

ちなみに、更新回数がちょうど X になるグラフを構築する問題が IPSC2015 で出題されていました。

おまけ（定数倍）

dist[v]を更新するのを、キューに入れる時ではなく取り出した時にするとコードは少し短くなるのですが、距離を更新しない余計な情報をキューに突っ込んでしまうことになり、定数倍で落ちたりするので気をつけましょう。
Dijkstraの定数倍 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

秋分コンテスト 準備/裏話編

競プロ 雑談

解説/講評編の続きです。

コンテスト運営の裏話などを記録しておきます。

メンバー紹介

イカれたお誕生日メンバーを紹介するぜ！

kagamiz

KCSの開発者にして、伝説の「帰ってきたお誕生日コンテスト」のwriterの１人でもある。KCSは偉大。今回は「帰ってきた」リスペクトの問題案が多かった印象。

japlj

お誕生日コンテスト運営常連。お誕生日よりは真面目寄りの「Xmasコンテスト」の運営常連でもある。ユーモア溢れるフレーバーテキストに定評があり、最近は小説に挑戦しているという噂がある。今回は文字・日本語系が多かった印象。

snuke

お誕生日コンテスト運営は「帰ってきた」「New Year」以外皆勤賞。japlj氏と同じくXmasもAtCoder回は皆勤賞。パズルっぽい問題と小ネタ系が多いと思う。

tozangezan

お誕生日コンテスト運営は「帰ってきた」以外皆勤賞。地理・言語学などに明るい。地理系・嫌がらせ系の問題が多い印象。（嫌がらせと言いつつちゃんと納得感がある所が憎めない）

こうして見ると、運営陣のお誕生日開催経験豊富すぎて草。

開催までの流れ

他の３人の間でお誕生日コンテストをやろうみたいな話が出ているところに、混ざりました。
参加するか/運営するかで迷いましたが、前回のNew Year Contestは優勝したので今回は運営かなーと決心しました。

日程が秋分に決まったのは、候補日をとりあえず決めようとなったときに、土日は急にratedコンテストが入ったりしがちなので祝日にしようということで、一番近い祝日を探した所、9/21,22だったからです。
個人的には翌日も祝日の方がいいかなーとちらっと思って敬老の日に投票しましたが、なんか秋分になりました。
お誕生日コンテストに敬老要素はあんまりないし、何より「秋分コンテスト」の響きが良すぎる。

7月

7/26にslackに加入。
最初の頃はspreadsheetに問題案を各々書き込んで行ってて、自分が入った時にあったもの（で出題されたもの）は

  • 絵しりとり（恒例なので）
  • adblock（後のあみだくじ）
  • Date Formatter
  • １枚絵から問題を推測するやつ
  • Introduction to ESP
  • Integer Choice

あたり。そこから僕が自分のストックから

  • ピクトセンス
  • シークワーサー
  • 正の平方根

と軽いジャブを打って、すぐピクトセンスが実施される。
その後、

  • novel（小説のやつ）
  • Soup 2（スープのやつ）
  • play （戯曲のやつ）

が追加される。（まさかこれらが全て出題されるとは...）

8月

じわじわと問題案が追加されたりしていたり、一部問題案の準備（J、手紙、adblock、chessなど）が行われていたりした。
そして８月中旬、静かに、しかし確実に流れを動かした出来事が起こった。

f:id:snuke:20200924092757p:plain:w480
「修正するのか、残念」ではないが？（後々kagamizを苦しめることになります）

8/22にコンテストページが生え、少し問題準備が加速。
同時にkagamiz氏によるKCSの開発も行われる。

  • ?/??：verdict機能（提出結果のコメント欄的なやつ）が実装される
  • 8/22：特殊採点機能が実装される
  • 8/29：ジャッジにpython-chessがインストールされる
  • 8/29：画像をgithubに上げるだけでKCSにアップロードできるようになる

最初期にKCSに置かれたのはadblockだった。
この頃のadblockはあみだくじではなく、例の鹿の絵のやつでバナー画像は入力に関する情報だった。
「画像２枚とも見えてからの方が本番すぎて、してやられた感が薄い」という指摘によって、この問題がadblockから独立する。

定期的に「帰ってきたお誕生日コンテスト」の話題で盛り上がる。
f:id:snuke:20200924092845p:plain
f:id:snuke:20200924092848p:plain:w300

9月

japlj氏がSoupの準備で激help状態になっていた。
そして9/6、ついにスープがslackに投下される。（その後もAIのトレーニング作業は続く...）

トップページのスタッフのコメントとかも書かれたりする。
japlj氏の怪文書コメントに含まれる「秋」の個数が最終的な問題数に偶然一致してて後に驚くことになる。

問題：以下の会話はどの問題に関するものでしょう？

人物１ 『たまには問題文を普通にします』
人物２ 『問題文「は」普通だった』

答え：嗚呼、恍恍惚惚　曠古、杲杲煌煌、兀兀甲骨

9/10

このあたりから準備作業が加速する。
小説が完成する。kindleに入れて読んだ。すごかった。
kagamizがスープとの長い格闘の末、ついに正解していた。
僕はかなり諦め気味でコナミコマンドを入力したが、何も起きなかった。
これがきっかけでスープにクエストが追加される。（今見たら「上上下下左右左右BA」でもクエストキー来るようになってるー！）

26問突破（[問題の出現）が間近となる。
f:id:snuke:20200924092937p:plain:w300
（後にめちゃくちゃ壊れます）

9/13

リチャード\d+世が完成。問題文を眺めて「あっ、これ予想以上に不可能なやつ来たな」と思った。
これを2:46に通したcatupperまじですげぇよ...（結局単独AC）
twitterにシークヮーサーのやつが流れててあ〜となる。

そしてついに26問の壁を突破する。
f:id:snuke:20200924093018p:plain:w480
僕はこれを見て密かに「a問題が見たい...」と思ってしまった。思ってしまったんだ。（犯行予告）

9/14

pictureが難しすぎると話題に。
元の画像これだからな。
f:id:snuke:20200924063741p:plain
僕もほとんど分かってはいたけど「フェンスを置くたびに１円かかる」だと思ってて分からなかった。
各所からのツッコミにより現在の絵に改善されました。感謝して下さい。

f:id:snuke:20200924064718p:plain
S問題の話題からKCS自由過ぎるやろｗって話になって、軽い気持ちで、
f:id:snuke:20200924093027p:plain
こう言ったら、現状の機能だけでも実現できることに気付き、実装...
もっとコンテスト中に気づいてびっくりして欲しかったね。
\ 問題のジャッジがなんかおかしいので調査してもらった所、KCSがめちゃくちゃに壊れていることが判明。（それはそう）
これはkagamizは悪くない、snukeとかいう頭のおかしいお誕生日野郎が明らかに悪い。

9/15

f:id:snuke:20200924093031p:plain:w360
　　　　　再　　　　　犯
「a問題が見たい」じゃあないんだよ。（でもaは壊れなかった）

a問題が見たかった僕は怒涛の３連投（数列クイズ、Echo、くそなぞなぞ）
前２つは「次回に温存しようかな〜」くらいのものだったけど、くそなぞなぞは即席でひねり出したまさにクソ問題です。
まぁでも「くそなぞなぞ」が問題一覧に並んでたら嬉しいよね？
ただ内容は「秋分」から即興で作った４問とストックにあったのから競プロ要素があるのを出しただけなのでかなり質は低めだったと思います（反省）
「鉄アレイ」はまあまあかな？「スタッフオーバー苦労」はそこそこ好きだったんだけど、なんかガチ勢によるとどっかで見たことあるらしくとても悲しい。
ストックにはちゃんと面白いくそなぞなぞもあるので、いつかお披露目したいね。
あと、Echoは性質上100ケースくらいは欲しいけど、ジャッジキューを苦しめる要因の１つになって申し訳なかったね。

ここら辺までで細かい部分以外の問題準備は終了した。

9/16

THE EMPTYを追加し、無事a問題達成。
と思っていたらtozanがRealtime Tozangya（後のR問題）を隠し持っていたらしく、b問題達成。
これで問題数が決まったので、配点決定および問題並べ替え閣議を実施。
結構色々話した気がするけどdiscord通話なので記録は残っていない。
問題順は、意外に結構ちゃんと理由がある配置が多いので考察してみて。

宣伝もこのあたりから開始。

9/17

絵しりとり実施
トップページのコメントをちゃんと書いたりmarquee実装したりする。

9/18

japlj氏がtester業をちょっとやってた

  • ピクトセンスの答えに誤字
  • 沖縄の想定解がpythonのre.matchを使っていたせいで「シークヮーサーズ」みたいのもyesになってた（逆に先頭は大丈夫なんだね）
  • バスの複数解を発見

運営一緒にやってていつも思うけど、優秀過ぎる・・・

9/19

f:id:snuke:20200924073634p:plain
あみだくじを画像解析で解いて遊んだ。（おわかりいただけただろうか）
手紙とかも解いた。楽しかった。
自分もスープ解いときたいなーと思ったけど全然駄目で、おもむろに質問相手を変更しました。
その結果、入力全部（２進or３進で一桁ずつ特定していけばO(桁数)回で全部特定できます）と、一部の出力が分かった。
けど、OEISで歯抜け検索ができないと思っていて解けなかった。（_を使うと良かったんですねぇ〜）
（これのおかげでOEISという単語を思いつけてなんとか解けたけど）

9/21

みんはやを使って宣伝をしたりした。
こんな"すごい"のをぶつけられた参加者がいかに驚いてくれるか、ワクワクして来ました。

9/22

当日。
色々ありすぎるので別記事に分けようかな。

KCS開発記録 by kagamiz

  • 9/9：特殊採点機能が改善される
  • 9/11：verdictがhtmlに対応する(草)
  • 9/13：ジャッジコードをpythonでも書けるようになる（chessで使った）
  • 9/14：\ 問題により壊れた色んな場所を修正
  • 9/19：ジャッジコードの自動コンパイル機能（これまではkagamizが手動でやってて申し訳無さがあった）
  • 9/21：提出制限機能が実装される

いまだかつてこんなに周到に準備したお誕生日コンテストがあっただろうか？
April Fool Contest 2015なんか準備期間１日ぞ？

各問一言コメント

  • A: Introduction to ESP Returns １問目に置くのはかなり不親切でだけど性質上ここにしか置けなかった。hosさん早すぎ。
  • B: Self Introduction これすき。真のwelcome枠。
  • C: ピクトセンス 提案した。いい感じの辞書を探すのが難しいので定番化は厳しそう。
  • D: ゴーストバスターズ これは伝説。いや、クソ長問題文とかは思いつくけど諦めるでしょ。実現させてしまうjapljさんすげぇ。しかもクオリティがめちゃくちゃ高くて、普通に小説として楽しめたし、ヒントの散りばめ方も絶妙。まだ解いてない人も是非解いて欲しい。
  • E: スープ これもやばい。いや、その発想はあっても諦めるでしょ。実現させてしまうjapljさんすげぇ。フレーバーテキストはこれが一番好きで、読み終わってからスープと対面したときにワクワクした。（まぁその後ゴポゴポ言ったり変色するだけのスープにイライラすることになるんですけど）
  • F: THE EMPTY 定番シリーズ。過去のやつよりかなり簡単め、だと思ったんだけど９人しか解いてないのか。カモフラージュが上手すぎたかな〜。まず大量の謎通知を見て「ここには何かあるぞ」と疑う、それがお誕生日力。
  • G: くそなぞなぞ ごめん。
  • H: 手紙１ 同じ文字に対するバリエーションが多すぎるし似た形も多いしでむずい。分かりやすいところから埋めると芋づりました。
  • I: 手紙２ こっちは入力がしやすくテキスト検索ができて楽。なんだけど同じ漢字に複数の読みがある（簡単な文字ほど多い）し、長いのが大変。手紙シリーズの解読作業純粋に楽しかった。
  • J: J J
  • K: Integer Choice これ思った以上に好きだった。小説に無意識に誘導された38が４人いるの草。あと、なんでよりによって2で被るんだｗ
  • L: Sqrt これ小粒枠だったけど、苦労した人はめちゃ苦労してそうだった。とりあえずググってみる、っていうのは典型テクなのかもしれない？
  • M: I like this コレヤベー
  • N: |n| わけも分からず通す人いそう。ちゃんと典型テクであるところの「ソースを見る」をするとちゃんと気付けるのが面白くて好き。
  • O: 沖縄 ググれば分かるシリーズ。マルチバイトの闇に飲まれた人かわいそう。
  • P: Bus Travel ここからtozan地理ゾーン。好きな人にはめっちゃ刺さる。
  • Q: Tozangya 知識をフル動員してあれやこれやを検索するのを試していく問題。見つけたときは脳汁やばそう。好きなシリーズだけど、自分には前提知識も忍耐力もないので厳しい。
  • R: 私は秋分を知る。 これ面白いね。ネトストは楽しい。なんというかストーリー性があるのが良いよね。
  • S: Cat nuke' Challenge はい。
  • T: |あ|み|だ|く|じ| これ手作業でやる気にならなかったんですが、意外と手作業勢多くてすごいなぁ。本題の罠は巧妙で好き。
  • U: 帰ってきた Picture 「グリッドに町・木・木を食う鹿・柵があって、柵を１個増やせて、何か金になるものを最大化する」という情報から、これらの要素を上手く絡ませられる問題設定を考えると普通に分かる。入力に '.' があることが書かれていないけど、なかったら柵を増やしようがないので察せる。そんなに無理問ではないと思うんだけどなぁ。
  • V: String Achievement 暇人向け。'a'*1000がおいしい。
  • W: ああこうこつこつこつこうここうこうこつこつこうこつ ググったり目grepしたりすると意外に結構見つかる。各は似た字が多くて苦労した。禽だけgive upした。
  • X: Legacy A+B 表示できないので合ってるか全然わからないのが怖いね。（実際、ほぼ正解なのにバグで落としてる人がいた）
  • Y: A/B Problem アルゴリズムで殴るか、言語知識で殴るか。これをノーペナで解くhosって人、何？
  • Z: Chess チェス楽しいよ。（あんまり強くないけど）
  • [: Cheat こんなこと出来るコンテストサイト他にある？KCSは神。
  • \: Date Formatter いいえ。
  • ]: 数列クイズ パズル界隈の人から教えてもらったネタ。OEISって間違ってることあるんですね〜
  • ^: 🐿 解説に貼ったけどtwitterで流れてきた何かの発表スライドで知った。こういうトリビア的なのも問題として出題できるのも競プロ形式の魅力。
  • _: Echo 地味にこういうセット情報を扱いやすい形に変換するパートを素早くやる能力が実用的だったりする。おすすめはテキストエディタで矩形選択とかマルチカーソルとか使う方法かな？
  • `: リチャード 間違いなくかなりの力作だし面白いネタだけど、解きたい見た目は、してないかな〜...(catupperすげぇ) 観賞用。
  • a: Shiritori 2020' 11はごめん。
  • b: クエスト 五里霧中はむずいよね...。四字熟語という情報すらないし。沖縄はソースを見た人いなかったんかな？一日千秋は１人いて嬉しかった。

秋分コンテスト 解説/講評編

programming 競プロ

秋分コンテスト

秋分コンテストを開催しました！
スタッフ：japlj,kagamiz,snuke,tozangezan

あの伝説のジャッジシステムKCSが復活し、またこうして新たなお誕生日コンテストが開催されたことを喜ばしく思います（？）

ただ復活しただけでなく新たな進化を遂げ、自由度がさらに高まったKCSでwriter陣は大暴れをいたしましたが、びっくりしていただけたでしょうか？
その上で、楽しんでいただけた問題が１つでもあったならば幸いです。

自作問題解説

F - The Empty

過去のお誕生日コンテストの定番シリーズで、どこかに隠されたキーワードを探すという問題です。
例えば、問題ページのhtmlのコメントとか、問題ページに限らずトップページのどこかとか、隠し場所は色々考えられます。
ただ、ほとんどの隠し場所はすでにHackerRank時代にやり尽くしているので、今回はKCSにしかない場所に隠すことにしました。
というわけで、通知一覧をご覧ください。

ちなみに、https://kcs.miz-miz.biz/static/2000/the-empty.html にURLをエスパーしてたどり着くとクエストキーが得られます。（４通りの表記ゆれをカバーしてます）
さすがに無理だろうと思っていましたが、案の定たどり着いた人は０でした。
KCSは画像だけでなくhtmlもアップロードできるんですねぇ〜〜

G - くそなぞなぞ

想定解

  • 秋分（それはそう）
  • 秋分の日（分数として読むだけ）
  • 重文（ちなみに例文はwikipediaを参照しました。「しげふみ（小惑星）」の項にちょっと笑った）
  • 大田区（オータム）
  • 鉄アレイ（鉄array）（ちなみに漢字で「鉄唖鈴」とも書くらしい）
  • メンブレン（面がブレないので）
  • コアタイム（そのまま読む）
  • スタッフオーバー苦労（「ふ」と「く」をswap）

２番で「一日千秋」を連想して「千分の一」と答えるとクエストキーが得られます。
１人くらいは通じ合える人がいるかな〜と思っていたら、１人いて嬉しい。

L - Sqrt

正は10^40なので、100000000000000000000(10^20)が答えです。
「垓」という答えを見て「たしかに」となりました。たしかに。

元ネタは、結構前に競プロ関係ないところから流れてきたツイートで、「正の平方根」をぐぐると...？

O - 沖縄

ja.wikipedia.org
の図をご覧ください。
正規表現を使うと楽です。
ただし、C++でやる場合は気をつけて下さい。
https://kcs.miz-miz.biz/contest/2000/code/103529
このコードどこがおかしいかわかりますか？
実は "ー?" の部分が駄目で、"ー" はマルチバイト文字なのでその最後の1バイト分にしか '?' がかからなくてすごいことになるっぽいです。
（"(ー)?" ならok）

ここにも実はクエストがあって、ソースを見て画像のURLを見ると、この画像はかぼすであることがわかります。
いらすとやでシークワーサーの画像を探してきて、そのファイル名からURLをエスパーするとクエストキーが得られます。
ちなみに似たシリーズとしてすだちの画像もいらすとやにあるらしく、こっちにアクセスするとさらにクエストキー入手です。
tozangezan考案で、最初ちゃんとシークワーサーの画像を問題文に貼ってたのにも関わらずなぜかすだちの画像のURLにアクセスしようとしたらしい（当然そんなものは置いてなかった）
（それにしても "fruit_shi-kuwa-sa_shikuwasa.png" って言う命名なんなんだ？）

ちなみにこの図はQuizKnockで知ったんだっけな。コンテスト数日前にtwitterでも流れてて「あっ...」ってなったけどまぁいいやとなった。


Y - A/B Problem

ジャッジコードでソースコードを取得できる機能がKCSに生えたということで、お誕生日コンテスト用問題ストックにあったのを放出。
'/' を使わず割り算をする問題です。
pythonやc++で "div" を使うという解法もありますが、"div" を含む場合は50点にしました。
それ以外にもいくらでもやりようはあります。
例えばO(log A)でアルゴリズムの力に頼って足し算と掛け算だけでやるのもありです。
他にもpythonのevalを使って print(eval(input().replace(' ',chr(47)*2))) とやるのもありですね。
#define waru di##v とかもありですね。

Z - Chess

個人的にチェスが結構好きなので出題してみました。
海外では一番メジャーなボードゲームなだけあって、チェスネタはプロコンでもたまに出題されますね。

  1. 右上のルークとナイトが入れ替わっています 棋譜
  2. キャスリングを使います。チェックがかかっているということは今は黒の手番なはずなのでparityをずらす必要があるんですが、ルークかクイーンを２マス動かせばずらせます。 棋譜
  3. ダブルチェックがかかっているということは最後の手はディスカバードアタックなんですが、アンパッサンを使うのが唯一の手段です。 棋譜
  4. デザイン重視。ただ、ポーンをすれ違わせるのは駒を犠牲にしなければ出来ないので、うまくやらないと供物(?)が足りないので頑張って下さい。 棋譜
  5. なんかすごいことになってますがプロモーションを使えばクイーンを量産できます。あとは最終盤面から１手前の状況を推察することを繰り返せば目標は見えてくると思います。黒のビショップ(白マス)かクイーンが必要になって「あれ？足りなくない？」となるかもしれませんが、こちらもプロモーションを使えば作れますね。 棋譜
  6. トリプルチェックは普通のチェスでは不可能です。そこでバリアントルールに手を出します。この問題はAtomic Chess（駒を取るとその８近傍のポーン以外の駒が吹き飛ぶ）を使うとかなり短い手数で実現できます。 棋譜 （最短手数だと思っているんですが、これより早くトリプルチェックを実現する方法があったら教えて下さい）
  7. こちらはキングがなくてもうめちゃくちゃです。キングがなくても良いのはAntichess（駒を全部取られたら勝ち、ただし駒を取れるときは取らないといけない）くらいです。ただし、Antichessで提出しようとすると「NGワード:anti」と言われます（「否定的な単語は使わないようにして下さい」と問題文に書いてありますね？）そこでジャッジコードを見るとpython-chessを使っているので、ドキュメントを読んでみるとAntichessに似たルールのSuisideとGiveawayが使える事がわかるのでこれを使いますが"Suiside"は当然NGワードなのでgiveawayを使うとACです。 棋譜 （lichessにはAntichessしかないのでAntichessで代用）（ドキュメントを読まなくても、Antichessの別名を普通に検索して片っ端から試してみるというのも手ですね）

ちなみに初期盤面がジャッジコード内でしっかりチェックされていることを考えると他のバリアントはCrazyhouseしか使えなさそうですが、これもなんかFENに持ち駒の情報が付いてしまって使えません。

別解

python-chessの実装を読んだりすると「パス」に相当する "z0" (null move) というのが使えるようで、これは自分のキングにチェックかかってようが可能みたいで、これを使うと大体なんでもやりたい放題になります。
全く予想外でしたね... これは参加者の方が一枚上手でした。

別解２

実は６もAntichessで頑張れば解けるみたいです。（ただしgiveawayで提出する必要はある）
これを見つけて感動したので、急遽クエストキーを追加しました。（その後 z0 解にクエストキーが取られてびっくりした）

別解３

なんと、準備作業中の棋譜が見れたことに気付きました。

あと、入力中にミスった場合は右の欄の記録を右クリックでdelete from hereを選ぶと元に戻せます。

[ - Cheat

意外と気づかれないもんですねぇ。
yesと答えた後に得点を書き換えようとしてみて下さい。
びっくりしてもらえましたか？
仕組み（白文字）：KCSはVERDICTにhtmlコードを仕込めるのでそこにjsをガッツリ書きました

ちなみに、変な出力をすると "Answer Yes or No." と言われるので、"Yes or No" とそのまま答えるとクエストキー "kuso_mitaina_parse_wo_suruna" が得られます。

] - 数列クイズ

OEISして終わり！かと思いきや、OEISが間違っています。しかもかなりガバ。
この数列は、へやわけというパズルで中央の正方形の部屋に最大いくつ黒マスが入れられるか、というやつです。
解法としては

  • 適当に±1してみる（一番楽）
  • 「へやわけ 黒マス 最大」みたいな感じでググってここなりここにたどり着く
  • パズル盤面作成ツールで右クリックして数字の最大値を見る。（こんな機能ついてたんですね(驚) さすがに空中の長方形部屋限定ですが）

historyのところに修正提案がちゃんとあるらしい（情報提供：amylaseさん）

ちなみに似たのがもう一個あって、そっちもはちゃめちゃ。

^ - 🐿

C++でLISを普通に求めると良いです。
良いんですが、提出すると「#{}[]を使っちゃ駄目」と言われます。ソースコードで遊ぶ系その２です。

部分点解法

トライグラフを使う。
ただしこれは「やっぱりC++17じゃないと部分点」と言われます。（C++17ではトライグラフは使えない）

満点解法

代替トークン（ダイグラフ）を使う。
普段からこれを使ってプログラミングをすると楽しい気分になれそうですね！

参考：みんな代替トークン使とる。使てへんのお前だけ。


_ - Echo

競プロ。
とりあえず提出してみると、-135点が来ます。
よく見ると、testsetが大量に設定されており、その中には負の配点のものもあります。
つまり、正解するテストケースを上手く選ぶ最適化問題というわけです。

構造をよく見ると、

  • set_???：２〜５個のケースからなる、正の配点
  • penalty_??：１個のケースからなる、負の配点

という構造になっています。
この最大化はmincutに帰着できます。
詳細に解説はしませんが、この問題などが参考になるのではないでしょうか？

ちなみに、ちゃんとテストセットの構造を見て計算しないとなかなか正の点すら得られません。
なんとなく得点効率が良さそうなやつだけ選ぶ貪欲で100点ちょいが来ます。
マラソンでも満点行けるんかな？と思ってましたがちゃんと焼き鈍したりしないと意外に満点はきついっぽい？（199で止まる人がちらほら）

ちなみに最小化は多分多項式とかでは解けないと思いますが、IP（整数計画問題）に落としてソルバを使えば爆速で答えが求まります。（-1644点 (笑)）
-1644点を取った人はclimpetさんただ一人でした。（クエストを設定しようと思ってましたが、キーワードを与える方法がなくて断念しました）

ちなみに最適解は２通りだけみたいです。（14,24,42をflip）

ちなみにHackerRank恒例の負の得点はKCSは対応していません。（順位計算時に0とのmaxが取られる）
というかHackerRankが異常で、なんで「負の得点が取れて、一回取ってしまうと撤回不可能」みたいなことができるかというと、「問題の点数は0~1の実数で出して、順位計算時にそのmaxを取ったものに配点の値を掛ける」というシステムだから（多分）です。