HUPC2023 Day2 作問について
HUPC2023 Day2の問題セットを農工大（に関わりのある人たち）で提供しました。
作問作業について
hr.icon
今回初めてGitHub Actionを用いたCIを組んでみました。
メリット・デメリットどちらもありそうです。
メリット
ミスが防げる。実際何回か救われました。
GitHub上でrimeの結果が確認できる
フォーマット・コーディングスタイルの類を自動で指摘できる（特にHTMLの書き方）
デメリット
自動チェックのミスが見つかる場合がある
これはチェックスクリプトを寝かせて秘伝のソース化することでなくせそう（？）
手元・GitHub Actions・AOJそれぞれで実行速度が異なるため、TLの調整が大変
GitHub Actions、遅いです
致命的ではないものの、定数倍高速化系の問題だと辛いです
自動チェック時のみTLを緩める設定を書いたらいいかも
プライベートリポジトリだと総実行時間の制限がある
これのせいでプッシュしまくったらやばいかなーという気持ちが生えてしまいます。実際には余裕でしたが……
んぐ.icon制限超過してもお金払う設定しない限り払われないので安心してください。Actionsが止まるだけです
あと、今回は導入してないですが、Pull Requestのテンプレートを作ってもいいかもしれません。
各ブランチに対して、作問状況のチェックリストをつくるとかしたら嬉しそう。
A問題
hr.icon
作問初心者の後輩が作ってくれた問題です。
農工大の近くにある三鷹は国立天文台があることで有名で、良いテーマだな～と思いました。
$ N個の数の最小公倍数求めるの難しいと思っていて、B問題より難しいと思う人もいそうだなーって思ってました。
B問題
hr.icon
簡単枠です。
もともと$ \mathrm{round}(\log_{10}{N})\ \ (1 \leq N \leq 10^9) で出すつもりだったのですが、ボツになってしまいました。
$ N の桁数を $ d とします。$ \mathrm{floor}\log_{10}N = d - 1 です。また $ \log_{10}N は $ N が $ 10^{d - 1} \leq N \lt 10^{d - 1 + 0.5} を満たすとき小数第一位が切り捨てられ、そうでないとき切り上げられます。両辺二乗すれば整数で扱えるので誤差なく求めることができます。
$ \left( 10^{d - 1 + 0.5} \right)^2 = 10^{2d -1}が$ N=10^9のときlong longだとオーバーフローしてしまうので、ここだけ条件分岐する必要があるのが面白ポイントでした
round(log10(n)) って書いたらACしてしまうことがあとから分かってボツになってしまいました
このような例が他に見つからず、$ \sin{\theta^\circ}に変更されました
$ \sin{\theta^\circ}じゃ微妙かなーA問題より簡単かなーとか思ったんですが、意地悪ではないものの、ところどころ引っ掛け・勘違いポイントがあり、まあちょうどいい感じになったかなと思います。
C問題
hr.icon
むずかしいです。
結構通されててびっくりしました。
D問題
hr.icon
むずかしいです。
D, E, Hのどれかが残るんだろうな～と予想してましたが、I並に解かれててびっくりです。
E問題
hr.icon
ad-hocな考察が求められる問題です。典型的にはxorの基底とか考えたくなりそうですが、実は関係あったりするんですかね？よくわかってません
僕はこういう問題なかなか生やせないのですごいなーって思ってました。
F問題
hr.icon
とってもむずかしいです。
G問題
hr.icon
簡単枠のうち最も後ろの問題です。
オンサイトなこともあってAtCoder茶色くらいの実力の人も楽しめるようにということで少し多めに簡単枠を入れました。
とはいえ、角行の斜めのラインをどう管理するかは、初見だと結構難しい気がします。
将棋好きなので生えました。問題文ミスごめんなさい。
H問題
hr.icon
有志コンといえば構文解析だろうということで、昨年に引き続き作問しました。
1次元構文解析はこの世にたくさんあります が、どれも構文解析が難しいというよりは、構文解析した後が難しい問題が多く、それだとわざわざ構文解析として出してもな～という気持ちに。
そういうわけで、2次元構文解析出したいなーという思いになってこのような問題になりました。
この問題、ただ見た目がいかついだけで、やり始めれば解けるんだろうな～と思わせておいて、実は構文解析パートが非自明なのが面白いです。
すべての | について対応関係をはっきりさせなくても良いところが面白い（もちろん最終的には決定できますが）
Twitterで感想を眺めていると、$ 1 \times 1行列式だと仮定→$ 2 \times 2行列式だと仮定→$ \cdots→$ n \times n行列式と仮定と、徐々にサイズを大きくしていくみたいな解法があって、それも面白そう。実装は大変そう。
I問題
hr.icon
validatorしました。DPしてくださいと書いているのでDPをする。結構頑張らないといけない。
Twitterで見た（気がする）$ A'B'C'A''を$ A'B'と$ C'A'' \rightarrow A''C'に分けてDPするの楽そう。
後で実装してみます。
総評
hr.icon
ほとんど簡単枠とはいえ、僕の問題多めに採用されて嬉しかったです。
問題文ミスどうやったらなくなるかな～～