AtCoder Beginner Contest(ABC) 197 D - Opposite の解説
はじめに
この間のAtCoder Beginner Contest(ABC)197のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。 使用言語はpythonを想定しています。
D - Opposite
問題文
軸の正の向きを右、軸の正の向きを上とする次元座標平面上に、の個の頂点からなる正角形があります。 ここでは偶数であることが保証され、頂点はこの順に反時計回りに並んでいます。の座標をとします。が与えられるので、を求めてください。
制約
- は偶数
- 入力に含まれる値は全て整数である
解答までの道のり
問題文をよく見てみる
まず問題文を見て思うのは、すごく数学チックな問題だということです。 正角形の角度や辺の長さなどの性質が問題解決に役立ちそうです。
実験してみる
今回は入力例2の の場合で考えます。 この状態を図にするとこうなります。 図からは、 は、
- とを結ぶ対角線の角度から、(図では約)
- 内角の大きさのだけ角度を引いた方向に(図では約)
- から、辺の長さだけ進ませた点であることがわかります。
以上の操作をコードに落とし込ませれば良いと分かります。
必要な知識をググる
問題を解くには
- 対角線の角度
- 内角の大きさ
- 辺の長さ
が必要とわかったので、これらについての情報を集めます。
まず、対角線の角度はアークタンジェントの関数で求められます。
ただし、ここには落とし穴があり、
pythonではmath.atan
ではなく、math.atan2
を使わないと
ゼロ除算によるエラーや、極端に小さい値による除算からの誤差が出てしまいます。
これがなければ4完できたんだけどな~
また、Wikiによると、
- 正角形の内角の和はでラジアン表記では
- 辺の長さがの正角形の任意の点から番目に近い点までの距離は、である。
- つまり、とを結ぶ対角線の長さをとすると、となるため、辺の長さはとなる。
ということが分かりました。 これらのことからコードを組んでいきます。
解答
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問題のほうが難しく感じてしまう・・・。
AtCoder Beginner Contest(ABC) 196 D - Hanjo の解説
はじめに
この間のAtCoder Beginner Contest(ABC)194のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。 使用言語はpythonを想定しています。
D - Hanjo
問題文
縦メートル、横メートルの長方形の部屋があります。
この部屋にメートルメートルの区別できない畳 (長方形のタイル)枚と、メートルメートルの区別できない半畳 (正方形のタイル)枚を敷き詰めます。メートルメートルの畳は縦長にも横長にも使うことができます。
敷き詰める方法は何通りあるでしょうか?
なお、であることが保証されます。 また、回転や反転を行うことで初めて一致するような敷き詰め方は区別します。
制約
- 入力はすべて整数
解答までの道のり
問題文をよく見る
今回の問題文をよく見てまず思うことは、HやWの最大値が小さいということです。 このことから、泥臭い全探索でも正解できそうだということがわかります。
具体的な解法を考える
全探索できそうだとは言いましたが、どうやって全探索をするか、つまり、ありうるタイルの敷き詰め方を網羅するかが問題となります。
ここで、知っている人は深さ優先探索(DFS)が候補に上がってくると思います。(逆に言えば知らないと解けない) 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の灰・茶と緑・水色の壁を見せつけられたような気がします。 やっぱり実装の経験を積むことが重要ですかね。気長に頑張りたいと思います。
AtCoder Beginner Contest(ABC) 195 B - Many Oranges の解説
はじめに
この間のAtCoder Beginner Contest(ABC)195のB問題に苦戦したので、 復習を兼ねて簡単な解説を書きます。 使用言語はpythonを想定しています。 AtCoder Ploblemsによると ABC195ではB問題のほうがC問題より難しかったみたいです。
問題文
みかんがたくさんあります。どのみかんの重さもグラム以上グラム以下であることがわかっています。(みかんの重さは整数とは限りません。)
この中からいくつかのみかんを選んだところ、選んだみかんの重さの合計がちょうどキログラムになりました。
選んだみかんの個数として考えられる最小値と最大値を求めてください。ただし、このようなことが起こり得ないなら、かわりにそのことを報告してください。
ただし、である。
解答までの道のり
問題文をよく見る
問題文をみて気になる語句は「みかんの重さは整数とは限りません。」という所。これらを念頭に置くべきなのかもしれません。
実験してみる
B問題の入力例1では参考にならなさそうなので、
入力例2つまり、で考えてみます。
ここで重要なのが、AtCoderでは出力例の下にある解説は大体こちらを騙して混乱させようとしてくるということです。
私は今回、この戦略にまんまと引っかかり、苦戦する羽目になりました。みかんの重さを整数にしやがって・・・
まず、数が最小のときを考えます。出力例では、最小の数は14なので試しに、1000Wを13や14で割ってみます。
である事がわかります。 (みかんの重さは少数でも良かったのでした)
よって、が成り立ち、これを変形するととなります。
同様に数が最大の時を考えると、が成り立つみたいです。
では、以下のように書けばよいのかというと、そうでもないみたいです。
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が出力例のUNSATISFIABLE
とならず、
となってしまいます。
このとき、となってしまっています。
よって、コード中の表現を借りれば、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では出力例の下にある解説は大体こちらを騙して混乱させようとしてくるということを心に刻みつけていれば もっと早く解けたかもしれないですね。
AtCoder Beginner Contest(ABC) 194 D - Journey の解説
はじめに
この間のAtCoder Beginner Contest(ABC)194のD問題が解けなかったので、復習を兼ねて簡単な解説を書きます。 使用言語はpythonを想定しています。
D - Journeyの問題文
頂点から頂点 までの頂点からなるグラフの頂点に高橋君がいます。今このグラフに辺はつも張られていません。 高橋君は以下の操作を繰り返します。
操作 :
(今高橋君がいる頂点も含めた)個の頂点の中からつランダムに選ぶ。各頂点が選ばれる確率は全てであり、選択は操作毎に独立である。
今高橋君がいる頂点と選ばれた頂点の間に無向辺を張り、選ばれた頂点に移動する。
グラフが連結になるまでに行われる操作の回数の期待値を求めてください。
ただし、である。
解答までの道のり
問題文をよく見る
まず問題文を見て思うのが、「グラフが連結ってどういう意味?」ということです。(無知) どうやらグラフが連結というのは「任意の重複しない2頂点を選択したときに、それらを結ぶパスが存在すること」です。 つまり、図のようなことを言っています。 この図を見るにどうやら今回の問題ではグラフが連結になるということはすべての頂点を1回以上選択するというのに言い換えられるということがわかります。 少しとっつきやすくなったかな・・・?
実験してみる
なんかではあまり参考にならなさそうなのでで考えます。
・・・わからない! AtCoderの公式の解説を見ても、これはどうやら知っているかどうかが決め手となる問題みたいです。
必要となる知識
これは公式解説に詳しいことが載っているのですが、
「確率で成功する試行を、成功するまで行うときの試行回数の期待値はである。」
というものです。
知識を持った上で実験
で考えます。 で、すべての頂点を1回以上選択するルートは、があります。 今回は問題の性質上、頂点以外の区別はしなくても良いので、という感じになります。
まず、のとき、このように遷移する確率はなので、期待値はとなります。
次に、のとき、このように遷移する確率はなので、期待値はとなります。
これらを足し合わせるととなります。
解答はこれをに拡張するだけですね。
解答
N = int(input()) ans = 0 for i in range(1, N): ans += N/(N-i) print(ans)
感想
こんな短い解答なのか・・・。 まあ知らなきゃ解けない問題なのでクヨクヨせずに次は頑張ろう!
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*}
と入力してしまうと、画像は のようになってしまいます。
mboxを使おう
ここで、日本語をちゃんと表示するために\mbox{}
を使いましょう。
\mbox{}
の使い方は簡単で日本語を{}の中に入れるだけです。
実際に
\begin{align*} BP = \left\{ \begin{array}{ll} 1\mbox{より小さい値} & (\mbox{翻訳文の長さ}<\mbox{参照文の長さ}) \\ 1 & (\mbox{翻訳文の長さ}\geq\mbox{参照文の長さ}) \end{array} \right. \end{align*}
と入力すれば画像は となり、ちゃんと日本語が表示されます。
まとめ
TexClipの数式の中に日本語を入れるときは\mbox{}
を使おう!
AtCoder Beginner Contest(ABC) 193 C - Unexpressed の解説
初めに
この間のAtCoder Beginner Contest(ABC)のC問題が解けなかったので、復習を兼ねて簡単な解説を書きます。 使用言語はpythonを想定しています。
C - Unexpressedの問題文
整数が与えられます。以上以下の整数のうち、以上の整数を用いてと表せないものはいくつあるでしょうか? ただし、は整数でである。
解答までの道のり
まずは問題文をよく見る
この問題分を見て私みたいな素人が真っ先に思いつくのがありうるに対してが以下かどうかをカウントするという方法です。 しかし、競プロでは秒で程度しか計算できないため、今回のという制約の中ではこの方法は取れません。 よって、もう少しスマートな解法を見つける必要があります。
実験してみる
スマートな解法を見つけるために実験をします。 とりあえず20までの整数を並べて考えてみましょう。
並べてみてわかることは、
- で表せる数は少ない
- 複数ので表せる数もある
ということです。 これらをもとに解答を考えてみましょう。
解答の道筋を考える
まずで表せる数は少ないということから考えてみましょう。 で表せる数は少ないということからは、 工夫して条件を絞れば全探索ができるかもしれないという事がわかります。
早速条件を絞ってみましょう。
まずについて、なので、が成り立ちます。
よってということがわかります。
なので、であり、計算量的には問題ありません。
次に、について、かつなので、 が成り立ちます。
なので、であり、計算量的には問題ありません。
更に、複数ので表せる数もあるということを考えてみましょう。
今回のケースでは、重複をカウントはしないということは問題文からわかります。
重複をカウントしないといったら・・・set
ですね。
よって、set
に値を入れていくことでで表せる数をカウントできるとわかります。
コーディング
前項で解答の道筋がわかったので、コーディングしてみましょう。
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))
これが解答となります。
感想
いざ解答を考えてみると、なんでこんな問題がわからなかったのか・・・となりますね。 実験 → 解答の草案 という流れを着実に考えれば容易に解けた問題だと思います。 同じ轍(てつ)は踏まないようにするぞ!