AtCoder 低難易度地雷問集

この記事は東京高専プロコンゼミ① Advent Calendar 2022の9日目の記事です。

8日目の記事はこちら

qiita.com

はじめに

弊ゼミで何かと新入生の教育に使われがちなAtCoderですが、AtCoderの問題の中には、

「この問題、配点に対して難しすぎないか？」

と思うような問題がめちゃくちゃあります。

特に初心者が解くような低難易度帯でそんな問題に出会ってしまった日にはトラウマもの。

今回はそんな罪深き問題たちをいくつか危険度順にピックアップ！
自信のある人は解いてみてね

（PCの人向け）問題のネタバレになる部分は黒塗りにしてあります。カーソルを合わせると読めるようになります。

目次

全体的に難しい

最近(2022/07あたりから？)のAtCoder Beginner Contestの問題

昔は「A問題（1問目）ではfor文を使わせない」みたいな暗黙の了解があったが、最近のコンテストにそんなものはない。

AtCoder Regular Contest・AtCoder Grand Contestの問題

初心者が参加することはあまり想定されていないのだろうが、同配点のBeginner Contestの問題と比べると明らかに難しい。

危険度★☆☆

A - Intersection (100)

2つの区間の和集合の長さを求める問題。

100点としてはかなり場合分けが大変。

B - Number Box (200)

数字が書かれたトーラス状に並ぶマス目の好きな場所を選ぶ。そこから好きな方向に決められた回数まっすぐ進み、通ったマス目の数を並べてできる数字の最大値を求める問題。

全探索できる。ただマス目の形が特徴的かつ進める方向が8方向あり、実装が相当重たい。（深夜までプログラム書いてる弊ゼミの人は得意かもしれない。）

C - Digital Graffiti (300)

平面上のマス目のいくつかを黒く塗ることで描かれた多角形が何角形かを求める問題。

問題文が長く、また答えも紛らわしいため、正しく問題を理解するのだけで一苦労。

危険度★★☆

A - Exponential or Quadratic (100)

1以上10^9以下の整数nが与えられ、2^{n} \gt {n}^2かどうかを判定する問題。

素直に2^nを計算しようとするとオーバーフローするのでうまい方法を考えないといけないが、初心者はそもそも2^{10^9}がオーバーフローすることに気付かない気がする。

B - Multiplication 2 (200)

非負整数A_1, A_2, \cdots , A_Nが与えられるのでA_1 \times A_2 \times \cdots \times A_Nを求める問題。ただし、計算結果が10^{18}を超えるときは代わりに-1を出力する。

ただ掛け算をして10^{18}を超えたら計算を打ち切るだけに見えるが、x \times A_i \gt 10^{18}か判定するときx \times A_iの計算でlong long型がオーバーフローするので、代わりにx \gt \frac{10^{18}}{A_i}かを判定する必要がある。

A - Simple Math 2 (300)

AtCoder Regular Contestの問題。
\lfloor \frac{10^N}{M} \rfloorをMで割ったあまりを求める。Nは1以上10^{18}以下なので、直接求めることはできない。高度な式変形を要求される。

危険度★★★

A - Jogging (100)

高橋くんと青木くんの動きが与えられるので、X秒後にどちらが多く進んでいるかを判定する問題。

問題は単純だが動きがかなり曲者で、A秒間B \mathrm{\,[m/s]}進み、C秒間休憩という動きを繰り返す。

進んだ距離を2重ループで愚直に出す方法と場合分けして計算で出す方法があるが、どちらも適正者には不可能。

B - Robot Arms (200)

数直線上に長さL_iの腕を自在に動かせるロボットがN体並んでいるので、互いの腕が干渉しないようにロボットを必要最小限の数取り除く問題。

区間スケジューリング問題という問題に帰着させることができるが、適正には無理。
というか区間スケジューリング問題をそのまま出題したとしても、適正には無理。

地雷回避の方法

AtCoder Problemsにだいたいの問題の推定難易度が載ってるので、みんなはちゃんと簡単な方からやりましょう

まとめ