くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > 参加ログ > AtCoder Beginner Contest 183 参加ログ・感想

AtCoder Beginner Contest 183 参加ログ・感想

参加ログ AtCoder 競プロ

個人的に試験を受けた日だったのと、携帯の機種変があったので開始時間に間に合わず今回は不参加。あとから復習した

内容

  • Python3でやっている。
  • 参加ログ。
  • 所感。
  • コンテスト中に何を考えたか。
  • コンテスト後に解説をみたり、少し整理したりしたくらいの内容。
  • 問題の詳細で細かく書こうと思うものは別記事とする。

結果

多分本番だとCまでできたかなくらい。 Bが幾何のネタだったのは珍しい感じがした。

どう考えたか + α

問題

A - ReLU

問題タイプ：条件分岐 文意から{\displaystyle 0}より大きければ{\displaystyle x} {\displaystyle 0}以下であれば{\displaystyle 0}とすればいい

x = int(input())
if x > 0:
    print(x)
else:
    print(0)
B - Billiards

問題タイプ：幾何 この反射の問題は、ゴールの点をx軸に対して対称な点とスタートの天を結んだときの{\displaystyle y=0}のときの{\displaystyle x}の値を出せばいい。 具体的には、

  • [:tex:{\displaystyle y = ax + b}]で{\displaystyle y=0}なので、{\displaystyle x=-b/a}となる。
  • {\displaystyle a}は、スタートとaは対称な点の傾き。
  • {\displaystyle b = y - ax}なので、適当に与えられた点のどちらかを代入する。
sx, sy, gx, gy = map(int, input().split())
a = (sy-(-gy)) / (sx-gx)
b = sy - a * sx
ans = -b / a
print(ans)
C - Travel

問題タイプ：順列・全探索

内容的は、 * 単純に２番目以降のすべての順列を洗い出す（今回はitertools.permutationsを使った）。 * 最初は {\displaystyle t}の一番初めのが選択されるようにする。
* そのパターン全てで目的のを計算をする。
* 最後は選ぶべきものの、１へ移動する時間を足す。
* {\displaystyle k}とおなじになるカウントを計算するだけ。
* 解説のPythonコードは最後のところも含めて一般的に解いてたけど、そんなふうには書けないので、最後だけ確定的に別処理にした。 （ _sum += t[pattern[n-1]][pattern[0]]の部分）

別記事にする必要もないと思う。

import itertools

n, k = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
# 2つ目以降の動きだけ順列作る
num = list(range(1, n))
patterns = itertools.permutations(num)
cnt = 0
for pattern in patterns:
    # patternの１つ目は必ず0番目を選ぶようにする
    pattern = [0]+list(pattern)
    _sum = 0
    for i in range(n-1):
        _sum += t[pattern[i]][pattern[i+1]]
    # 順列の最後では1を必ず選択する。（index==0）
    _sum += t[pattern[n-1]][pattern[0]]
    # kと一致したらカウントしておく
    if _sum == k:
        cnt += 1
print(cnt)
D - Water Heater

問題タイプ：累積和

ちゃんと読んでないけど、累積和で解く問題。 itertools.accumulateでエイ！だと思う。

そのうち別記事にしようと思う。

追記：

考え方書いた。全然itertools.accumulateでエイ！じゃなかった。（まぁそれでもできるけど）

普通にすべての人のスタートとエンドで使う量をいい感じに記録して頭から足し合わせて制限きたら終わりっていうだけ。

blacktanktop.hatenablog.com

おわりに

今回は、リアルタイムに参加してないんだけど、たぶんCまでだったと思う。

参考になる書籍

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

書籍は読み終わったので、Pythonで章末問題をこなしていっている。

blacktanktop.hatenablog.com