library-checker-problems
library-checker-problems copied to clipboard
yosupo06
Division of Polynomials の問題文が曖昧
（Issueという機能を使ったことがないため、何か使い方が間違っていたら申し訳ございません）
fとgが整数係数であることが明記されていませんが、暗にその条件が課されているようです。
特に多項式の剰余計算は整数係数多項式の範疇で閉じていない（例えばf=x、g=2xの時はqが1/2になる）ので法998244353は有理数の範疇で考えているはずであるため、問題の設定のみから整数係数であることを推測させるのもあまり自然ではないと思います。
そもそも実数などの場合は法998244353という概念が未定義（またはかなり曖昧）であり、そのような未定義項が参照される前に一般の実数ではないことが明確にされているべきだと思います。
更に零多項式の次数は文献によって異なり、例えば次数0として定義する流儀では解が必ずしも存在しないため零多項式の次数を明確にした方が良いと思います。例えば出力形式と整合的にしたい場合は零多項式の次数を-1と定めれば良いと思います。
解決策としては、問題文にfとgが（非負）整数係数多項式でありqとrが有理数係数多項式であることを明記し、更にq,rの各係数の既約分数表示の分母が998244353と互いに素な有理数であり整数に対する法998244353の定義を拡張可能であることを明記し、零多項式の次数の定義を追加すると良いと思います。
このジャッジはAtCoder等と違い、「ライブラリをベリファイする」という用途のジャッジなので、問題文に求められる要件がそもそも異なると考えています。具体的には、「競プロをそれなりにやっていてライブラリをベリファイしたい人が、問題文を読んで誤解を招かない」なら問題文として十分だと考えています。そのため、他のジャッジにある「入力は全て整数です」などの細かい制約も特に書いてなかったりします。
それを踏まえると、特にmod 998244353が拡張可能とかは言及しなくてもいいと思っていて、たとえば https://judge.yosupo.jp/problem/composition_of_formal_power_series のようにF_{998244353}で物事をやっているとかは書いてもいいと思っています
ありがとうございます。ジャッジの趣旨を把握いたしました。競プロに精通している人なら問題文の正確な意味が分かるためにこのような書き方になっているのですね。
一応念のためにお伺いしたいのですが、Print the coefficients modulo 998,244,353.と書いてあっても多項式たちを整数係数とみなした上でその係数をmod 998244353するということは（競プロに精通している人なら）まずなく、最初からF_{998244353}係数であると勝手に解釈し直すということであっておりますでしょうか？ その場合、「誤解を招かない」というよりは「想定通りに誤読してくれる」という方が正確な気がします。
というのも、係数をmod 998244353するよう求めているので、係数自体が最初からmod 998244353されているわけではないことになりますので。（もちろん、998244353がF_{99824435}において0だから最初からmod998244353されているものを更にmod 0をするよう無駄に求めていると言えなくもないですが）
従って問題文のまま解釈すると整数係数または有理数係数の多項式をmod 998244353で出力するという問題設定になり、特に整数係数の場合は解が必ずしもないため問題不成立になります。解がある場合はそれをmod 998244353したものとF_{998244353}における解が一致しますが。（これは不成立だから変えるべきという主張ではなく、競プロに精通している人が誤解を招いていないのではなく想定通りに誤読しているということの説明です）
もう１点、競プロに精通している人の間で零多項式の次数に共通の見解があるということも含意されていると思うのですが、何次として扱うことに決まっているのか差し支えなければ今後の勉強のために教えていただけますでしょうか？
零多項式の次数は、中高数学、大学数学科～などを含む多くの部分で、定義しない / -infty が標準的。たまに -1 という認識です。 deg(0) = 0 と定義する流儀は、無視できる程度にしか存在しないと考えています（中高数学など、そう定義されていない状況なのに 0 は 0 次と勘違いしている人は、無視できない程度に存在すると思いますが）。存在したとしても、1変数多項式除算の定義くらいは主流な定義に歩み寄って解釈していただきたい気持ちがありますね。
係数環を明示すべきというのは私は賛成寄りですが、既存の問題で特に質問が来ずに上手く使ってもらっているようなものに対する対応は、優先度は低くなると思います。（私も、新しく問題やテストケースを増やして verify 問題集としての利便性を高める活動の方により力を入れたいです。） まあ、気が向いたらその他の問題も含めて、もうちょっと問題文をちゃんとするという調整を、私あるいは誰かがするかもしれません。
ありがとうございます。僕も次数は数学だと（未定義を除くと）-∞が標準的なものの１つだと思っていたので、競プロでも-∞が標準であると分かり安心いたしました。
存在したとしても、1変数多項式除算の定義くらいは主流な定義に歩み寄って解釈していただきたい気持ちがありますね。
こちらはそもそも整数係数だと除算ができない（のに整数係数をmod 998244353で出力させている）のがおかしいのではないか、という立場なので１変数多項式除算の主流な定義に歩み寄って解釈をしたつもりだったのですが、何かこちらの誤解がございましたでしょうか？
整数係数だと除算ができないのでしたら、F_p か Q での体上の多項式環を考えている問題だと想定していただくと良いのではないでしょうか。あと一応、歩み寄って欲しいというのは、p-adic さんについての話ではなく、一般にこの問題文を読んで、零多項式の次数が 0 である流儀で解釈することによって問題が正しくないと主張する架空のユーザーに対するものです。
係数環を明示した方が良いということには私は賛成しているので、そのうち書く可能性が高いです。
了解です。ある程度競プロに精通している人であれば、係数をmod 998244353すると書いてあっても最初からF_{998244353}係数であると誤読してくれるわけですね。（そこがそもそもの論点だったので、問題文通りには読まないことが競プロで普通であるのでしたら納得です）
論点をうまく伝えられていなくて申し訳ありませんが、係数環が明示されていないというよりは係数があたかもF_{998244353}でない（mod 998244353を取って初めてF_{998244353}係数となる）かのように明示されていることをむしろ指摘しているつもりでした。こちらの言葉が足りておりませんでした。
私は、有理数係数多項式の各係数を mod p して出力する問題を意図しているのだろうと読みました。そして、それが分かる問題文にした方が良いということに同意もしています。 「F_p 係数多項式が与えられる」という問題文になおす手もあると思っています。 この 2 択を指して「係数環を明示」とかきました。
今の状況で F_p 係数だと読むのが普通というわけでは別にないです。 （まあただ、どのような読み方をしたにせよ、整数制約であることを含めて何を verify させる問題なのかを想像で補ってくれるユーザーが、この問題の対象レベルではほとんどだと思います。事実、これまで多数の質問が寄せられることもなく verify 問題として機能しています）
あとは、競プロユーザーも様々なので、あまり何でも「これが競プロで普通」というように理解しない方が良いと思います。そもそも、yosupo さんからもあったように、一般的なコンテストで求められる質を達成していなくてもとりあえず OK になっているので、この問題文が競プロで普通ではないです。問題文は現状、競プロあるいは Library Checker 標準の質を確保しているというよりも作業者に大きく依存していますし、人手の問題やコスパの問題で十分なメンテナンスが出来ているわけでもないです。
不備の指摘はありがたいですが、競プロでは不備を許容するのが普通であるというような曲解はしないでいただけるとありがたいです。
ありがとうございます。そして言い方が不適当で不快な思いをさせてしまったようで申し訳ございません。先程「誤読する」と書いたのは競プロで不備が許容されるという意図で書いたのではないことをご説明します。
まず上でyosupo06さんにより『競プロをそれなりにやっていてライブラリをベリファイしたい人が、問題文を読んで誤解を招かない』と仰ったのを受けて、それに対し『一応念のためにお伺いしたいのですが、Print the coefficients modulo 998,244,353.と書いてあっても多項式たちを整数係数とみなした上でその係数をmod 998244353するということは（競プロに精通している人なら）まずなく、最初からF_{998244353}係数であると勝手に解釈し直すということであっておりますでしょうか？ 「誤解を招かない」というよりは「想定通りに誤読してくれる」という方が正確な気がします。』と述べました。
これについてうまく意図が伝わらなかったようでどなたも肯定も否定もしていなかったため、改めて「誤解を招かない」のではなくむしろ誤読してくれることを想定しているということを再確認させていただいたという意図です。決して鏡プロでは不備が許容されるという一般論を展開しているわけではなく、今回に限った話として「誤解を招かない」という主張が誤りではないかと指摘しているものです。
また競プロユーザーにも色々な人（例えばライブラリをベリファイする段階まで到達していない初心者の方々）がいることは承知しており、今回はyosupo06さんが「競プロをそれなりにやっていてライブラリをベリファイしたい人」に絞っているためそのようなユーザーを指して「競プロに精通している人なら」と述べておりました。こちらも意図が不明瞭で申し訳ございません。
言葉足らずだったようです すいません。恐らく疑問に思っているのではないかというところを明確にしておくと
- この問題文(+このジャッジの少なくない割合の問題文)はめちゃくちゃです。例えばこの問題文のまま他のジャッジ(e.g. AtCoder)に出題されたら、競プロに精通している人であっても多くの人が文句を言うと思います
- 競プロ界隈では数学の記法がメチャクチャな使われ方をしている… のようなことはないと思います。競プロをやっている人の少なくない割合は数学科とかの出身だったりするはずだからです。
- なので当然、「係数をmod 998244353すると書いてあっても最初からF_{998244353}係数であると誤読する」ルールは競プロにありません。
- こう書いておいてアレなんですが、私に数学系のバックグラウンドはないので、推測です
- ではなぜこのジャッジの問題文はめちゃくちゃなのか？
- 上で書かれているように、コストと優先度の問題です。
- なぜ問題文がめちゃくちゃなのにユーザーは正しい問題を認識できるのか？
- 単純に問題タイトル、問題文、制約、サンプル入出力等から推測しているだけだと思います。「きっとこの問題の入力は全部整数だし、係数をmod 998244353するとしか書いてないけどこれは多項式の係数はF_{998244353}という意味なんだろうな」というエスパーを行っているはずです。
- 繰り返しますが、コンテストの問題の問題文はこのようなエスパーを要求するべきではないですし、このような問題文がコンテストに出題されたら文句がたくさん出ると思います。
色々補足していただきありがとうございます。知りたかった答えは、最後に明確にしていただいたYesの部分でした。こちらの数学的な誤解ではないことが分かり安心いたしました。
一般のコンテストでどうかや、界隈が不備を許容するかどうかや、界隈での記法が妥当ではないかどうかは、今回特に疑問視したり含意したりしたわけでなくあくまで今回の問題が「誤解をまねかない」という主張に関して指摘していたつもりでしたが、どうもお二人のご返信的にこちらの伝える力が著しく乏しく一般のコンテストや界隈への暗黙な批判的含意が濃いコメントとみなされてしまう発言だったようで反省しております。。
これまでは「質問をする際は質問に書いたこと以外に含意はなく批難の意図もない」という界隈にいたため端的に質問とその中で述べた主張に対する理由のみを発しましたが、githubまたは競プロの全体とは限らない一部界隈では質問の仕方の文化自体が違う可能性を考慮し、質問が批判的含意を持つと推測されてしまうことを念頭に置くよう配慮いたします。
具体的にはこれからは聞きたいことを明確にするだけではなく例えば「一般のコンテストでどうであるかはここでは気にしておりません」や「界隈が不備を許容するという認識は持っておりません」などの注意書きを事前に思いつく範囲で明確にするように気をつけます。（批判的な含意の濃いコメントに受け取られてしまっている理由がそこでなく別であればご教示頂けますと幸いです）
批判的かどうかというよりも、問題の読み方や解釈のひとつを「競プロに精通している人であれば」というように大きな集団全体で当てはまることかのように理解しようとしているように感じたので、「あまり何でも「これが競プロで普通」というように理解しない方が良いと思います。」と書きました。
「最初からF_{998244353}係数であると誤読してくれる」については No で、私は有理数係数と解釈したと書いた通りです（ただし、例えばこの説明をもって「競プロの人は有理数係数と解釈するのですね」と理解しないでくださいということです）。なので、指摘されている通りの誤読を期待しているかという点については私の解釈では No ですが、何らかの意味で勝手に問題文を、問題が成り立つように都合よく解釈して問題を利用できるという意味であれば、そういう期待はしています。
「一般のコンテストでどうであるかはここでは気にしておりません」や「界隈が不備を許容するという認識は持っておりません」などの注意書きを事前に思いつく範囲で明確にするように気をつけます
は不要だと思います。
承知いたしました。もちろん過度な一般化（ここでは個人の見解を界隈で普通の見解だと認識すること）をしないことは今後も変わらず気をつけます。特におふた方は界隈でも名のある方々だと存じておりますので、読み方や解釈も問題によっては平均より著しく高度な水準にあることを推測しております。
またバックグラウンドによって推測の方向性が違うことも理解しております。その点についてこちらの言葉が足らずご心配をおかけしてしまったことをお詫び申し上げます。基本的にはただ質問したことの答え（それは回答者に依存しうる）が気になっただけですので、万人の共通の見解であることは期待しておりませんでしたことを明確にさせていただき、ご安心していただければ幸いに存じます。こちらがご回答の意図を汲めていない可能性まで考慮して色々と教えていただき誠にありがとうございます。