尺のブログ?

やりたいことをやりたいです

ratedになれなかった問題たち(サブタイトル:くBCの問題を作るときに注意していること)

(この記事は、くそなぞなぞ Advent Calendar 2020 #kusonazo_advent の 多分 13 日目くらい の記事として執筆されました。)

はじめに

こんにちは、Suunn こと尺です。普段はくそなぞなぞ Beginner Contest(くBC)の多くの回でwriterをやっています。
くBCは現状新規writerの受け入れ態勢はありませんが、私としてはwriterを増やして、もっと自分がコンテストに参加できるようにしたいと考えております。そこで、今回は私がくBCの問題を作る上で考えていることを記事にしたいと思います。
というわけで、なぞなぞの問題が没になった理由を、実例とともに紹介していこうと思います。

注:例として出した問題の答えは白字にしてありますので、各自反転して確認してください。

case1: 特定の知識を要求する

Q1.丸顔のポケモンってなーんだ?(くAFC-C)

A1.カオガエン(顔が円なので)

Q2.多い家電量販店ってなーんだ?(くAFC-D)

A2.コジマ(好事魔多しなので)

以上の2問は考察が非自明で、面白い問題だと思います。(自画自賛) ですが、Q1はガオガエンというポケモン、Q2はコジマという家電量販店のCMを知っていることが要求されます。(参考: https://www.youtube.com/watch?v=5xWac9BjQmg)ちょうどこの記事が公開される数日前に、某テレビクイズ番組で特定の漫画の知識を要求する問題が出題され、このような問題を出すことの是非について紛糾がありました。このような知識を要求する問題が解けなかった場合、知識を持っていなかったことを反省するのではなく、「解けた人が運よくそれを知っていただけ、ずるい」という感情が生まれることが想像されます。


(競技)プログラミングなどの知識を要求する問題も、ここに分類されます。

Q3.どんなケースでWAになっているか言えなくなる病気ってなーんだ?

A3.口内炎(コーナー言えん)

Q4.古くなって変な音が出る図ってなーんだ?

A4.ボロノイ図


回答には特別な知識が必要ではなくとも、そう見えるものも避けた方がよいでしょう。

Q5.コートジボワールのやみふくろうってなーんだ?

A5.ヤムスクロ

風来のシレンというゲームにやみふくろうというキャラクターが登場しますが、この問題はそんなことを知らなくても一応解けます。ですが、「風来のシレンが回答に関係あるのでは?」と考えてしまうと、詳しくない人は全く無駄な検索に多くの時間を費やすことになるでしょう。


Q6.牛から逃げる祭りが行われる都市ってどーこだ?(くAFC-I)

A6.パンプローナ

クイズはなぞなぞではありません。

case2: 問題文が作れない

Q7.ハンガリーでかつて使われていた岡山弁ってなーんだ?(くAFC-L)

A7.ぺんげー

Q8.前髪が禿げていく速度について議論する学問分野の香水ってなーんだ?

A8.O(デコ)論

Q9.悟りを開いた討論者の曲ってなーんだ?(くそなぞなぞAGC004 提案問題)

A9.羅漢パネラー

以上の問題は、パースやもじり自体の面白さにはそこまで大きな問題はないのですが、適切な問題文を作ることが難しいため没になっています。

case3: しょうもない

Q10.毛の生えた赤ちゃんなーんだ?(くAFC-J)

A10.ケバブ

Q11.歯抜けのスリッパなーんだ?

A11.スキッパ

Q12.羊の手紙なーんだ?

A12.メーメール

Q13.お金持ちに噛みつくパスタ屋なーんだ?

A13.ガブリ長者

全部しょうもないですね。


似たようなものに、無理があって正解が出なさそうなパターンもあります。

Q14. 1.4くらいの針ってなーんだ?

A14.ルードニ

Q15.最強の道具なーんだ?

A15.相手無(敵なしなので)


考察が面白くないパターン。

Q16.積もっている解析学ってなーんだ?

A16.堆積学

Q17.持っているといいことがある4Kテレビってなーんだ?

A17.恩恵テレビ

複合語の片方を似た言葉に変えるだけみたいなのはあまり面白くないと思います。


面白くないのにはこういうパターンもあります。

Q18.5つの綴りで書かれる音楽ってなーんだ?

A18.ゴスペル

Q19.すっぱいものが集まってできた蒸気ってなーんだ?

A19.酢チーム

Q20/21/22.妊婦の/少数派の/色々なお茶ってなーんだ?

A20/21/22.マタニ/マイノリ/バラエティー

スを「酢」に読み替えるような1文字のパースや、tyをお茶に解釈したりするのは、無限に作れてしまう分必然性みたいなものがなくて面白くないです。

case4: 倫理的な問題がある

特定の対象を馬鹿にしたり、差別したり、風評をばらまいたりしているように解釈できてしまう虞のある出題です。

Q23. 遅れているインドってなーんだ?

A23.ビハインド

Q24.集団で怒ってる文字ってなーんだ?

A24.グルムキー文字

Q25.血と油が流れている川ってなーんだ?

A25.チグリス川


言葉遣いが悪かったり、ダークだったりなものもあります。

Q26.海に近い岩場をこき下ろす物質ってなーんだ?

A26.炭化水素

Q27.B級映画で術式を誤って修道院に人喰いの魔を召喚してしまったときのスーパーマーケットなーんだ?

A27.成城石井

case5: その他

ミスリーディング

Q28.生姜の小学校なーんだ?

A28.ジンジャー小学校

生姜っ校は想定WAなのですが、間違いであると言い切れる理由も存在しません。


そのまますぎて問題として不成立

Q29.クリーム煮を作る北欧神話の英雄なーんだ?

A29.クリーム煮る


画像

Q30.

A30.ズワイガニ

画像問題は多分出せません、知らんけど


記事書くの飽きた


おしまい

AtCoderで黄色になるまでにやったこと

やったこと

青になる

(一部の超人を除くと)青にならないと黄色になれません。青になる方法はこの記事を参照してください。
suunnch.hatenablog.com

Codeforcesに出る

こどふぉをやりました。時間が遅くて大変でしたが、コンテストに出る練習になってよかったと思います。あとAtCoderでは鍛えにくい実装の訓練になりました。青と紫を行ったり来たりしています。(苦手なので)

ライブラリを整備する

基本的な数学(Combinationの計算など)や、ダイクストラ法などのグラフアルゴリズムをライブラリ化しました。毎回考えて書くより楽になりました。(なんだかんだバグらせがちなので)

自分を天才だと思う

天才だと思うと700点が解けるようになります。冗談です。ですが、解けないと思ってしまうと解けないので天才だと思いましょう。

やらなかったこと

使わなかったアルゴリズムやデータ構造

セグメント木、フロー、木DP、Grundy数、文字列アルゴリズム、包除原理

以上の事項は結局AtCoderでコンテスト中に使って問題をACしたことはないと思います。黄色はそんなもんです、AtCoderなので(えー)(ごめんなさい)。橙になるにはいるんでしょうか。

AtCoderで青になるまでにやったこと

年末のAGC030で、AtCoderで青になることができました。2018年中に青になれたのが嬉しいので、青になるまでにやったことをまとめていこうと思います。

・過去問を解く

ABC-D、AGC-Bの400〜600点問題を積極的に、7割くらい埋めました。400を埋めきってない人でも、解きやすい500~600点問題はそれなりに存在するのでやっていくといいと思います。

・バチャをやる

AtCoder Virtual Contest様にて、何度か「青になりたい!」というタイトルのバーチャルコンテストを開きました。近いレベルの人をたくさん集めて難しめのバチャをやると、ライバルの存在やコンテストの戦い方が意識できて良かったと思います。参加してくださったみなさま、どうもありがとうございました。

・蟻本を買う

大学の教科書に蟻本が置いてあったので、つい買ってしまいました。今のところ辞書的な活用法しかしていませんが、すごく便利で良い本だと思います。

・標準的な機能を学ぶ

水色には300点早解きor時々400点に成功で上がれますが、青を狙うにあたって400点問題は落とせません。ですが、400点以上の問題になると、さすがにif文とfor文、配列だけで実装しきるのは(不可能ではないはずですが)難しい問題が増え、プログラミング初心者には厳しいものがあります。

ここでは、「私が」知って見える世界が変わった標準的な機能を紹介していきたいと思います。ちなみに私はJavaを使ってるので、みなさんの言語には似たようなものがないかもしれません、なかったらごめんなさい。

・HashMap

学んだのは緑時代ですが、これは最強クラスのデータ構造と思います。値の範囲が大きいデータを、何回出てきたか数えられたり、座標圧縮をしたり、Objectから整数への対応などを簡単に作ったりすることができます。神。
素因数分解なんかもやりやすい。

・TreeMap

キーを取り出すときに、ソートがされていて嬉しいHashMapです。

・Queue、Stack

幅優先探索深さ優先探索に使うイメージが強そうですが、これもめちゃくちゃ便利です。道中でものを拾って、「古い」or「新しい」ものから順に使うというようなことがしたいときに便利です。

・Deque

一番古いのも新しいのもすぐ取り出せます。時々使いたくなる問題があります。

・Priority_queue

Queue、Stackの上位互換(計算時間を除けば)。かなり強いと思います。これがないと解けない問題、多いんじゃないでしょうか。便利すぎて「いいの?」ってなりがちです。

・ListやSet、Map型の配列

グラフ系の問題などを解くにあたっては半分必須っぽい気がします。

・拡張for文

これもグラフ系の問題には必須っぽいです。ある頂点から伸びてる辺を全部見るなどできます。MapのKeySetなども全部さらえます。嬉しみ。

・bit演算

bit系の問題を解いたり、bitDPをするときに、「うーん、2のi乗で割って、それを2で割ったあまりを...」みたいなのがめちゃくちゃ簡単に書けて、しかも高速に動作します。

・Class

Pairなどを作れます。Pairが欲しくなることはめちゃくちゃ多いので…

・Comparator

整数を逆順にソートしたいくらいなら−1倍したものをぶち込んで、実際に使うときに元に戻せばいいのですが、Objectをソートしたくなる時があります。そんなときにComparatorが使えるといいですね。

・入出力高速化

JavaのScannerやSystem.out.println()は遅く、問題によってはここを改善するだけでTLEが取れることもあります。
AtCoder Express 2(入力60万個、出力10万個)でテストすると、入出力高速化だけで1359msが302msまで改善しました。
詳しくはご自分で調べてください。

・基本的なアルゴリズム、データ構造を学ぶ

AtCoderは典型そのままはあまり出ませんが、問題を言い換えていくと典型になることは無数にあります。そんなとき、解けたのに書けない…ってなると悲しいし、上がるはずだったレートをみすみすドブに捨てる行為になることも多々あります。そんな悲劇を回避するために、典型アルゴリズムは書けるようにしたほうが良さそうです。

再帰

使えると嬉しいです。メモ化再帰のDPは、問題によってはforで回すより脳死で書けたりします(回す順番を考えなくていいので)。いくつかの変数をグローバル変数にすると引数が少なくて済みそうです。

・二分探索

書けると嬉しいです。値の検索だけでなく、何かを決め打ちすると可不可を判定するだけの問題になったりするときにも使えます。

・最短経路アルゴリズム

ワーシャルフロイド、ベルマンフォード、ダイクストラ全部使えるようになっておくと良いです。400点問題に全部あったはずです。茶色の頃の話ですが、ダイクストラで簡単に解けるとわかった問題が、全く何も書けずに虚無をしたことがあります。

・Union-find木

これも400点程度でも時々使う問題が出ます(良く考えるとBFSやDFSでも良かったりするものもありますが)。経路圧縮だけなら割と書きやすいです。

・他

BIT、セグ木、平衡二分探索木、フローなども勉強(写経)しましたが、AtCoderで青になるのに使うことはあまりなさそうではあります。当然やっておいて損はないと思います。

最後に

黄色目指して頑張ります!!!!!!!!!!!!!!!!!!!!!!!!

AtCoder Beginner Contest 106

ABC106に参加しました。

A

注意に「道の位置が変わっても…」とあるので、
道の位置を右下に寄せてしまっていいです。
こうすると、面積が(A-1)(B-1)であることが簡単に分かります。

B

200以下には105,135,165,189,195しかないです。
このうちN以下のものの数を調べればいいです。

C

5000兆日もあれば2でもめっちゃ増えます。
よって、K文字目まで全部1なら1、そうでないなら最初に出てきた
1以外の数字が答えになります。
ただ、Kが10の18乗だとK文字目まで調べてる暇はないです。
ここで、制約の(Sの文字数)<=100が活躍します。
つまり、K>100のときは、必ずSの中で、1でないものがあります。
その1でないものの中で最初に出てくるものが答えです。
実際には、(Sの文字数)<Kの時も、K文字目までが全部1かどうか
調べるには不具合があります。
ここも解決する楽なやり方としては、
「初めて出てくるSの中の1以外の文字の種類と、それがSの何文字目にあるか」を調べます。
そして、「そもそも1以外の文字が出てこないか、または初めて1以外の文字が出てくるのはK文字目以降」なら1を出力,
そうでないなら最初に出てくる1以外の文字を出力すればいいです。

D

Qは100000以下ですが、Nの2乗もせいぜい250000で、
考えられるpとqの組み合わせは、p<=qの条件からその半分と少しになるので、
すべてのpとqの組み合わせについて答えを求めてしまって構いません。
一般のp ,qの組について答えを求める方法を考えましょう。
「p番目以降に始まってq番目までに含まれる列車の数の和」は、
「各i=p,p+1,p+2…qに対してi番目から始まってq番目までに含まれる列車の数の和」です。
さらに、「i番目からq番目までに含まれる列車の数」は、
「各j=i,i+1,i+2…qに対してi番目から始まってj番目に終わる列車の数の和」です。
なので、まず2次元配列dを用意します。
そして、各L,Rに対してd[L][R]を1だけ増やします。
これで、「i番目から始まってj番目に終わる列車の数」が用意できました。
次に、各iに対して、jをiから始めて1ずつ増やしながらd[i][j] = d[i][j-1] + d[i][j]とすると、
「i番目から始まってq番目までに含まれる列車の数の和」が求められます。
次に、各qに対して、iをqから始めて1ずつ減らしながらd[i][q] = d[i+1][q] + d[i][q]とすると、
「p番目から始まってq番目までに含まれる列車の数」が求められます。
あとはQ回d[L][R]を出力すれば終わりです。