天下一参佰点問題 講評

珠玉の300点問題を集めたバーチャルコンテスト、「天下一参佰点問題」を今週開催いたしました。

https://not-522.appspot.com/contest/5672431989555200

精進は1週間単位で見ているので利用したAtCoder Virtual Contestの中の人の想定とは違った運用をしてしまったなーとは思いつつ、場所をお借りしたAtCoder Virtual Contestにはたくさんの感謝を送りたいと思います。

最終日5日目の段階で現在開かれているコンテスト一覧からミュートされたので、やはりあまりよくないことだったのだろうと思います。ですが直接の警告がない限りはなにかやるときはこれぐらいのスパンでやるつもりです。先ほども申し上げたとおり精進は1週間単位なので。

以下講評。細かい解説は公式の解説放送等を参照してください。

Sugar Water (ABC074C)

キーワード : 全探索

開幕注意力。これを通しただけでもこのバチャコンやった甲斐があった。

状態を分かりやすく表現することはできなさそう、また解析的にも解けなさそうというところから全探索を疑う。 全探索と分かってもなお、浮動小数の丸め誤差に苦しまされることになる。

砂糖を入れることができない場合、水だけ入れるのが答えになるので注意（1敗）。

解答。この頃のテンプレートはまだまだ穴が多い。 atcoder.jp

All Green (ABC104C)

キーワード : permutation全探索

忘れた頃に出てきては適正者を慌てさせるpermutation全探索。ICPC用にライブラリ化しておくべきとの知見も得られたしここに置いたのは正解だったと思う。

指数オーダーと同じく微妙な制約がそれと匂わせることが多い。それでもこれは見抜くのに手間がかかる部類の問題だが。

全部解かないと目標を達成できない場合の処理を間違えて1WA。

解答 atcoder.jp

String Transformation (ABC110C)

キーワード : 発想 注意力

Synthetic Kadomatsuとこの問題が、ロケハン時に解法が思い浮かばなかった2問。制約的に明らかにO(|S|)なのでその線で探すも鳴かず飛ばず。

Sample3はダミーで本当に大事なのはSample2。Sample2を先頭/末尾からいくら削れば変換できるようになるかを考えてようやく勘違いに気づいた。分からないものに当たったときに簡単なものから試していくということは厳に戒めておきたい。

解答 atcoder.jp

Sequence (ABC059C)

キーワード : DP……のようなお気持ち

DP枠！　と思って出したしかつてDPで解いたのに実はDPじゃなかったやつ。発想にはDPっぽいものを使うので一応DP。

最近はABCのC問題にもDPが出るようになってインフレ前最難候補だったコイツも落ち着いたか。

解答 atcoder.jp

Synthetic Kadomatsu (ABC119C)

キーワード : kⁿ全探索

2ⁿ全探索の場合はただ単にbitを見るだけでよいので簡単だ。それ以上の全探索の場合、配列をk進数の各桁に見立てて下から値を伝播させていくのがやりやすいかと思う。

O(N)くらいの解法がありそうなんだけどなぁ。

解答 atcoder.jp

Base -2 Number (ABC105C)

キーワード : 数学

某青コーダーと会話したときに「これは500点問題」ということで一致した-2進数。当然今回のボスとして設定した。が、あっさり解かれてしまい世俗との乖離が感じられた。

ある桁のbitをそれ以上のbitの桁だけを用いて表現することはできない、という事実に気づけるかがポイントになってくる。それに気づいてしまえばあとは貪欲に導くだけだ。幸いにしてコーナーケースは存在しない。

解答 atcoder.jp

終わり

水色でも全完が厳しそうなセットをと考えて作ったが、水色以上は平然と全完してきてレベルの高さを見せつけてくれた。私自身も辛くも全完することができた。String Transformationは本当に危なかった……。300点問題とはいえ、断じて簡単ではないので解けなくても落ち込まないでほしい。ここに出てきたpermutation全探索も、最近300点問題によく出る累積和も、かつては400点問題で出ていたものだ。

なお、個人的に最も苦手な300点問題であるSnuke Festival (ABC077C)は個人差度合いがひどすぎるために収録を見送った。これも教育的な典型であることには変わりがないので意欲のある人は取り組んでみて欲しい。

atcoder.jp