2021-03-28

AtCoder Beginner Contest(ABC) 197 D - Opposite の解説

はじめに

この間のAtCoder Beginner Contest(ABC)197のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。使用言語はpythonを想定しています。

D - Opposite

問題文

$x$ 軸の正の向きを右、 $y$ 軸の正の向きを上とする $2$ 次元座標平面上に、 $p_0, p_1, p_2, \dots, p_{N-1}$ の $N$ 個の頂点からなる正 $N$ 角形があります。ここで $N$ は偶数であることが保証され、頂点 $p_0, P_1, p_2, \dots, p_{N-1}$ はこの順に反時計回りに並んでいます。 $p_i$ の座標を $(x_i, y_i)$ とします。 $x_0, y_0, x_{\frac{N}{2}}, y_{\frac{N}{2}}$ が与えられるので、 $x_1, y_1$ を求めてください。

制約

$4 \leq N \leq 100$
$N$ は偶数
$0 \leq x_0, y_0 \leq 100$
$0 \leq x_{\frac{N}{2}}, y_{\frac{N}{2}} \leq 100$
$(x_0, y_0) \neq (x_{\frac{N}{2}}, y_{\frac{N}{2}})$
入力に含まれる値は全て整数である

解答までの道のり

問題文をよく見てみる

まず問題文を見て思うのは、すごく数学チックな問題だということです。 正 $N$ 角形の角度や辺の長さなどの性質が問題解決に役立ちそうです。

実験してみる

今回は入力例2の $N=6, (x_0, y_0)=(5, 3), (x_{\frac{N}{2}}, y_{\frac{N}{2}}) = (7, 4)$ の場合で考えます。この状態を図にするとこうなります。

f:id:fwatty:20210328111053p:plain — 入力例2における図

図からは、 $(x_1, y_1)$ は、

$(x_0, y_0)$ と $(x_{\frac{N}{2}}, y_{\frac{N}{2}})$ を結ぶ対角線の角度から、（図では約 $26.565 ^{\circ}$ ）
内角の大きさの $\frac{1}{2}$ だけ角度を引いた方向に（図では約 $26.565-60 = -33.434 ^{\circ}$ ）
$(x_0, y_0)$ から、辺の長さ $a$ だけ進ませた点であることがわかります。

以上の操作をコードに落とし込ませれば良いと分かります。

必要な知識をググる

問題を解くには

対角線の角度
内角の大きさ
辺の長さ

が必要とわかったので、これらについての情報を集めます。

まず、対角線の角度はアークタンジェントの関数で求められます。ただし、ここには落とし穴があり、 pythonではmath.atanではなく、math.atan2を使わないとゼロ除算によるエラーや、極端に小さい値による除算からの誤差が出てしまいます。 ~~これがなければ4完できたんだけどな～~~

また、Wikiによると、

正 $N$ 角形の内角の和は $\dfrac{180(N-2)}{N}$ でラジアン表記では $\dfrac{\pi (N-2)}{N}$
$1$ 辺の長さが $a$ の正 $N$ 角形の任意の点から $m$ 番目に近い点までの距離は、 $\dfrac{a \sin \frac{m\pi}{N}}{\sin \frac{\pi}{N}}$ である。
つまり、 $(x_0, y_0)$ と $(x_{\frac{N}{2}}, y_{\frac{N}{2}})$ を結ぶ対角線の長さを $L$ とすると、 $m=\dfrac{N}{2}$ となるため、辺の長さ $a$ は $a = \dfrac{L \sin \frac{\pi}{N}}{\sin \frac{\pi}{2}} = L\sin \dfrac{\pi}{N}$ となる。

ということが分かりました。これらのことからコードを組んでいきます。

解答

import math

def LI(): return list(map(int, input().split()))

N = int(input())
x0, y0 = LI()
x_half, y_half = LI()

# (x_0, y_0)と(x_half, y_half)を結ぶ対角線の長さ
L = ((x0-x_half)**2 + (y0-y_half)**2)**0.5
# 1辺の長さ
a = L*math.sin(math.pi/N)
# 対角線の角度
rad = math.atan2((y_half-y0), (x_half-x0))
# 対角線の角度 - 内角の角度/2
theta = rad-0.5*math.pi*(N-2)/N
# 座標を動かす
print(x0+a*math.cos(theta), y0+a*math.sin(theta))

まとめ

アルゴリズムというより数学って感じの問題なので、アルゴリズムを知っていなければ解けないという感じではなく個人的にはとっかかりやすかったです。今回はB問題にめちゃくちゃ時間がかかったため、時間が足りず正解できなかったのが心残りです。なんか、最近C問題よりB問題のほうが難しく感じてしまう・・・。

2021-03-21

AtCoder Beginner Contest(ABC) 196 D - Hanjo の解説

はじめに

この間のAtCoder Beginner Contest(ABC)194のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。使用言語はpythonを想定しています。

D - Hanjo

問題文

縦 $H$ メートル、横 $W$ メートルの長方形の部屋があります。

この部屋に $2$ メートル $\times$ $1$ メートルの区別できない畳 (長方形のタイル) $A$ 枚と、 $1$ メートル $\times$ $1$ メートルの区別できない半畳 (正方形のタイル) $B$ 枚を敷き詰めます。 $2$ メートル $\times$ $1$ メートルの畳は縦長にも横長にも使うことができます。

敷き詰める方法は何通りあるでしょうか？

なお、 $2A+B = HW$ であることが保証されます。また、回転や反転を行うことで初めて一致するような敷き詰め方は区別します。

制約

入力はすべて整数
$1 \leq H, W$
$HW \leq 16$
$0 \leq A, B$
$2A+B=HW$

解答までの道のり

問題文をよく見る

今回の問題文をよく見てまず思うことは、HやWの最大値が小さいということです。このことから、泥臭い全探索でも正解できそうだということがわかります。

具体的な解法を考える

全探索できそうだとは言いましたが、どうやって全探索をするか、つまり、ありうるタイルの敷き詰め方を網羅するかが問題となります。

ここで、知っている人は深さ優先探索(DFS)が候補に上がってくると思います。（逆に言えば知らないと解けない） DFSをどうやってやるかを考えると、図のように

半畳をそのまま置く
畳を横に置く
畳を縦に置く

という動作を部屋の一番左上 $(0, 0)$ から右へ移動しながらやっていくという方法が思いつきます。（昨日の僕は思いつきませんでした・・・）

f:id:fwatty:20210321123511p:plain — 今回の問題におけるDFSのイメージ

そして、コードは下のようになります。コードの解説はコードのコメントアウトにありますが、 DFSの具体的な動作を理解するには、実装してみるのが一番らしいので、気が向いたら実装してみてください。

def LI(): return list(map(int, input().split()))

H, W, A, B = LI()

used = [[False]*W for _ in range(H)]

def dfs(i, j, a, b):
    # 畳が残っていないときは置けない
    if (a<0 or b<0): return 0
    # 横の座標が部屋の幅を超えたら下に移る
    if j==W:
        j = 0
        i += 1
    # 縦の座標が部屋の高さを超えたら終了
    if i==H: return 1
    # (i, j)がすでに埋まっていたら (i, j+1)の座標に移る
    if used[i][j]: return dfs(i, j+1, a, b)
    
    res = 0
    used[i][j] = True
    # (i, j)に半畳を置くとき
    res += dfs(i, j+1, a, b-1)
    # (i, j)から(i, j+1)にかけて畳を横向きに置くとき
    if j+1<W and used[i][j+1]==False:
        used[i][j+1] = True
        res += dfs(i, j+1, a-1, b)
        # 探索から戻ってきたときにおいていたのを戻す
        used[i][j+1] = False
    # (i, j)から(i+1, j)にかけて畳を縦向きに置くとき
    if i+1<H and used[i+1][j]==False:
        used[i+1][j] = True
        res += dfs(i, j+1, a-1, b)
        # 探索から戻ってきたときにおいていたのを戻す
        used[i+1][j] = False
    # 探索から戻ってきたときにおいていたのを戻す
    used[i][j] = False

    return res

print(dfs(0, 0, A, B))

まとめ

DFSというアルゴリズムを理解した上で、それを応用するという問題が出たということで、個人的には AtCoderの灰・茶と緑・水色の壁を見せつけられたような気がします。やっぱり実装の経験を積むことが重要ですかね。気長に頑張りたいと思います。

2021-03-14

AtCoder Beginner Contest(ABC) 195 B - Many Oranges の解説

はじめに

この間のAtCoder Beginner Contest(ABC)195のB問題に苦戦したので、復習を兼ねて簡単な解説を書きます。使用言語はpythonを想定しています。 AtCoder Ploblemsによると ABC195ではB問題のほうがC問題より難しかったみたいです。

問題文

みかんがたくさんあります。どのみかんの重さも $A$ グラム以上 $B$ グラム以下であることがわかっています。（みかんの重さは整数とは限りません。）

この中からいくつかのみかんを選んだところ、選んだみかんの重さの合計がちょうど $W$ キログラムになりました。

選んだみかんの個数として考えられる最小値と最大値を求めてください。ただし、このようなことが起こり得ないなら、かわりにそのことを報告してください。

ただし、 $1 \leq A \leq B \leq 1000, 1 \leq W \leq 1000$ である。

解答までの道のり

問題文をよく見る

問題文をみて気になる語句は「みかんの重さは整数とは限りません。」という所。これらを念頭に置くべきなのかもしれません。

実験してみる

B問題の入力例1では参考にならなさそうなので、入力例2つまり、 $(A, B, W) = (120, 150, 2)$ で考えてみます。ここで重要なのが、AtCoderでは出力例の下にある解説は大体こちらを騙して混乱させようとしてくるということです。私は今回、この戦略にまんまと引っかかり、苦戦する羽目になりました。~~みかんの重さを整数にしやがって・・・~~

まず、数が最小のときを考えます。出力例では、最小の数は14なので試しに、1000Wを13や14で割ってみます。

$2000/13 \simeq 153.8 \geq B, 2000/14 \simeq 142.9 \leq B$ である事がわかります。（みかんの重さは少数でも良かったのでした）

よって、 $\dfrac{1000W}{n} \leq B$ が成り立ち、これを変形すると $n \geq \dfrac{1000W}{B}$ となります。

同様に数が最大の時を考えると、 $n \leq \dfrac{1000W}{A}$ が成り立つみたいです。

では、以下のように書けばよいのかというと、そうでもないみたいです。

def LI(): return list(map(int, input().split()))
 
A, B, W = LI()
W *= 1000
 
max_ans = int(W/A)
 
if W%B==0:
    min_ans = int(W/B)
else:
    min_ans = int(W/B) + 1
 
print(min_ans, max_ans)

これでは入力例3 $(A, B, W)=(300,333,1)$ が出力例のUNSATISFIABLEとならず、 $(3, 4)$ となってしまいます。このとき、 $\dfrac{1000W}{A} = 1000/3 = 333.33\cdots \geq B$ となってしまっています。よって、コード中の表現を借りれば、W/max_ans>BとなってしまうときにUNSATISFIABLEとすればよいとわかります。

解答

def LI(): return list(map(int, input().split()))
 
A, B, W = LI()
W *= 1000
 
max_ans = int(W/A)
if W/max_ans>B:
    print('UNSATISFIABLE')
    exit()
 
if W%B==0:
    min_ans = int(W/B)
else:
    min_ans = int(W/B) + 1
 
print(min_ans, max_ans)

感想

AtCoderでは出力例の下にある解説は大体こちらを騙して混乱させようとしてくるということを心に刻みつけていればもっと早く解けたかもしれないですね。

2021-03-07

AtCoder Beginner Contest(ABC) 194 D - Journey の解説

はじめに

この間のAtCoder Beginner Contest(ABC)194のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。使用言語はpythonを想定しています。

D - Journeyの問題文

頂点 $1$ から頂点 $N$ までの $N$ 頂点からなるグラフの頂点 $1$ に高橋君がいます。今このグラフに辺は $1$ つも張られていません。高橋君は以下の操作を繰り返します。

操作 :

(今高橋君がいる頂点も含めた) $N$ 個の頂点の中から $1$ つランダムに選ぶ。各頂点が選ばれる確率は全て $\frac{1}{N}$ であり、選択は操作毎に独立である。
今高橋君がいる頂点と選ばれた頂点の間に無向辺を張り、選ばれた頂点に移動する。

グラフが連結になるまでに行われる操作の回数の期待値を求めてください。

ただし、 $2 \leq N \leq 10^ 5$ である。

解答までの道のり

問題文をよく見る

まず問題文を見て思うのが、「グラフが連結ってどういう意味？」ということです。（無知）どうやらグラフが連結というのは「任意の重複しない2頂点を選択したときに、それらを結ぶパスが存在すること」です。つまり、図のようなことを言っています。

f:id:fwatty:20210307102353p:plain — 連結と非連結

この図を見るにどうやら今回の問題ではグラフが連結になるということはすべての頂点を1回以上選択するというのに言い換えられるということがわかります。少しとっつきやすくなったかな・・・？

実験してみる

なんか $N=2$ ではあまり参考にならなさそうなので $N=3$ で考えます。

・・・わからない！ AtCoderの公式の解説を見ても、これはどうやら知っているかどうかが決め手となる問題みたいです。

必要となる知識

これは公式解説に詳しいことが載っているのですが、

「確率 $p (p \neq 0)$ で成功する試行を、成功するまで行うときの試行回数の期待値は $\frac{1}{p}$ である。」

というものです。

知識を持った上で実験

$N=3$ で考えます。 $N=3$ で、すべての頂点を1回以上選択するルートは $1 \rightarrow 2 \rightarrow 3$ 、 $1 \rightarrow 3 \rightarrow 2$ があります。 今回は問題の性質上、頂点 $1$ 以外の区別はしなくても良いので、 $1 \rightarrow 2\mbox{か}3 \rightarrow \mbox{余り}$ という感じになります。

まず、 $1 \rightarrow 2\mbox{か}3$ のとき、このように遷移する確率は $\frac{2}{3}$ なので、期待値は $\frac{3}{2}$ となります。

次に、 $2\mbox{か}3 \rightarrow \mbox{余り}$ のとき、このように遷移する確率は $\frac{1}{3}$ なので、期待値は $3$ となります。

これらを足し合わせると $\frac{3}{2} + 3 = 4.5$ となります。

解答はこれを $N$ に拡張するだけですね。

解答

N = int(input())

ans = 0
for i in range(1, N):
    ans += N/(N-i)

print(ans)

感想

こんな短い解答なのか・・・。まあ知らなきゃ解けない問題なのでクヨクヨせずに次は頑張ろう！

2021-03-02

TexClipの数式中に日本語を入れたいときはmboxを使おうという話

TexClipとは

TexClipを知っていますか？ Texclipはブラウザ上でTexのコマンドを数式に変換して画像化してくれる優れもので、画像化した数式をパワポとかに貼り付けて使えます。これがあればクッソ使いにくいパワポの数式入力から解放されてQOLが爆上がりします。

TexClipの欠点

表したい数式の中には場合分けの条件が複雑だったりして、日本語で書きたいときがあると思います。しかし、TexClipは外国のサイトなので日本語をそのまま入力すると文字化けしてしまいます。例えば、TexClipに

\begin{align*}
BP = \left\{
\begin{array}{ll}
1より小さい値 & (翻訳文の長さ<参照文の長さ) \\
1 & ( 翻訳文の長さ\geq 参照文の長さ)
\end{array}
\right.
\end{align*}

と入力してしまうと、画像は

f:id:fwatty:20210302111544p:plain — mboxを使わなかった場合

のようになってしまいます。

mboxを使おう

ここで、日本語をちゃんと表示するために\mbox{}を使いましょう。 \mbox{}の使い方は簡単で日本語を{}の中に入れるだけです。実際に

\begin{align*}
BP = \left\{
\begin{array}{ll}
1\mbox{より小さい値} & (\mbox{翻訳文の長さ}<\mbox{参照文の長さ}) \\
1 & (\mbox{翻訳文の長さ}\geq\mbox{参照文の長さ})
\end{array}
\right.
\end{align*}

と入力すれば画像は

f:id:fwatty:20210302111557p:plain — mboxを使った場合

となり、ちゃんと日本語が表示されます。

まとめ

TexClipの数式の中に日本語を入れるときは\mbox{}を使おう！

2021-02-28

AtCoder Beginner Contest(ABC) 193 C - Unexpressed の解説

初めに

この間のAtCoder Beginner Contest(ABC)のC問題が解けなかったので、復習を兼ねて簡単な解説を書きます。使用言語はpythonを想定しています。

C - Unexpressedの問題文

整数 $N$ が与えられます。 $1$ 以上 $N$ 以下の整数のうち、 $2$ 以上の整数 $a, b$ を用いて $a^ b$ と表せないものはいくつあるでしょうか？ただし、 $N$ は整数で $1 \leq N \leq 10^ {10}$ である。

解答までの道のり

まずは問題文をよく見る

この問題分を見て私みたいな素人が真っ先に思いつくのがありうる $a, b$ に対して $a^ b$ が $N$ 以下かどうかをカウントするという方法です。しかし、競プロでは $2$ 秒で $10^ 8$ 程度しか計算できないため、今回の $1 \leq N \leq 10^ {10}$ という制約の中ではこの方法は取れません。よって、もう少しスマートな解法を見つける必要があります。

実験してみる

スマートな解法を見つけるために実験をします。とりあえず20までの整数を並べて考えてみましょう。

$n$	$a^ b$	$n$	$a^ b$
$1$		$11$
$2$		$12$
$3$		$13$
$4$	$2^ 2$	$14$
$5$		$15$
$6$		$16$	$2^ 4, 4^ 2$
$7$		$17$
$8$	$2^ 3$	$18$
$9$	$3^ 2$	$19$
$10$		$20$

並べてみてわかることは、

$a^ b$ で表せる数は少ない
複数の $a^ b$ で表せる数もある

ということです。これらをもとに解答を考えてみましょう。

解答の道筋を考える

まず $a^ b$ で表せる数は少ないということから考えてみましょう。 $a^ b$ で表せる数は少ないということからは、 工夫して条件を絞れば全探索ができるかもしれないという事がわかります。

早速条件を絞ってみましょう。

まず $a$ について、 $2 \leq b$ なので、 $a^ 2 \leq a^ b \leq N$ が成り立ちます。

よって $a \leq \sqrt {N}$ ということがわかります。

$1 \leq N \leq 10^ {10}$ なので、 $1 \leq \sqrt {N} \leq 10^ {5}$ であり、計算量的には問題ありません。

次に、 $b$ について、 $a^ b \leq N$ かつ $2 \leq a$ なので、 $b \leq \log_a N \leq \log_2 N$ が成り立ちます。

$1 \leq N \leq 10^ {10}$ なので、 $0 \leq \log_2 N \leq 10\log_2 10$ であり、計算量的には問題ありません。

更に、複数の $a^ b$ で表せる数もあるということを考えてみましょう。今回のケースでは、重複をカウントはしないということは問題文からわかります。 重複をカウントしないといったら・・・setですね。 よって、setに値を入れていくことで $a^ b$ で表せる数をカウントできるとわかります。

コーディング

前項で解答の道筋がわかったので、コーディングしてみましょう。

import math
 
N = int(input())
 
# a**2 <= a**b <= N --> a <= N**0.5
max_a = int(N**0.5) + 1
# a**b <= N --> b <= log_a(N) <= log_2(N)
max_b = int(math.log2(N)) + 1
 
s = set() # 2**4 と 4**2 のような重複を消したい
for a in range(2, max_a):
    for b in range(2, max_b):
        val = a**b
        if val > N:
            break
        s.add(val)
 
print(N-len(s))

これが解答となります。

感想

いざ解答を考えてみると、なんでこんな問題がわからなかったのか・・・となりますね。実験 → 解答の草案という流れを着実に考えれば容易に解けた問題だと思います。同じ轍（てつ）は踏まないようにするぞ！