くろたんく雑記帳

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

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

AtCoder Beginner Contest 184 参加ログ・感想

参加ログ AtCoder 競プロ ABC

正直今日のCDの方が昨日のABよりよっぽど難しいと感じた。

内容

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

結果

4分でAB完。Cは迷路っぽく考えなきゃなのかなと思ったがパッと思いつかないから確率問題のDへとりあえず手を付ける。具体的な策が講じられず終了...Orz完敗感。

どう考えたか + α

問題

A - Determinant

問題タイプ：式をそのまま実装

文意から{\displaystyle a \times c - b \times d}を計算。

a, b = map(int, input().split())
c, d = map(int, input().split())
ans = a*d - b*c
print(ans)
B - Billiards

問題タイプ：条件付きの文字列判定 初期に持っている得点{\displaystyle x}に成功不成功を示す文字列{\displaystyle S}がoのときは+1、 xのときは-1、ただし手持ちの得点が0だったら-1しない。そのまま実装。

n, x = map(int, input().split())
S = input()
for s in S:
    if s == 'o':
        x += 1
    elif s == 'x' and x >= 1:
        x -= 1
print(x)
C - Super Ryuma

問題タイプ：パリティ

そもそも問題を見たときに迷路っぽいと思った時点で駄目で、パリティの条件分けだったOrz

移動のパターンの数式を見てこれをパッと思いつかないな。もう少し、考えて別記事にする。

D - increment of coins

問題タイプ：確率・DP・メモ化

ただの確率の問題と思ったが、DPとの組み合わせだった。

金貨を引く確率×金貨を引いた時の操作回数の期待値＋ 銀貨を引く確率×銀貨を引いた時の操作回数の期待値＋ 銅貨を引く確率×銅貨を引いた時の操作回数の期待値

というのをDPで解くということ。別記事にする。

追記： lru_cacheを使うと超便利っていうのがわかった。

blacktanktop.hatenablog.com

おわりに

今回は、完敗って感じ。 Cは特にぱっとパリティをイメージできなかった。DもDPっぽいなと思ったがどう実装すべきかわからず、まだまだ。一応素早くABを解けたことを評価されたのかパフォーマンスはABを解いただけにしては高めでRatingは少し上がった。もう少しで沼から抜け出せそう。

参考になる書籍

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

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

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

7章までPythonで章末問題をこなしていっている。

blacktanktop.hatenablog.com