【参加記録】AtCoder Beginner Contest 119
はじめに
AtCoder Beginner Contest 119に参加した記録です.
A - Still TBD
入力を'/'で分けて項目ごとに比較. なぜか7分も溶かしてしまいました.
S = input() S = S.split('/') if int(S[0]) <= 2019 and int(S[1]) <= 4 and int(S[2]) <= 30: print('Heisei') else: print('TBD')
わざわざ分けなくても単純に辞書順で比較できるそうです.以下解説コード.
S = input() print('Heisei' if S <= '2019/04/30' else 'TBD')
B - Digital Gifts
入力をループで回して加算していく.単位がBTCだったら380000.0を乗算したものを加算.
N = int(input()) in_num = [] for i in range(N): in_num.append(list(map(str,input().split()))) res = 0 for x,u in in_num: if u == 'JPY': res+=float(x) else: res+= float(x)*380000.0 print(res)
C - Synthetic Kadomatsu
時間内に解けず.
解説によると,N本の竹に対して,ABCの竹に使うかどれにも使わないかの4通りの使い方を全探索すれば良いらしいです.
解説ではDFSを使用していました.
以下解説コードに自分用にコメントを追加したもの.
N, A, B, C = map(int, input().split()) l = [int(input()) for i in range(N)] INF = 10 ** 9 def dfs(cur, a, b, c): ''' 深さがNだったら使用MPを評価 N本の竹を使うときに必要な合成回数はN-1のため,最後に-1*10*3(?) 1本も竹を使用していなかったら棄却→MPを無限に使うこととしている ''' if cur == N: return abs(a - A) + abs(b - B) + abs(c - C) - 30 if min(a, b, c) > 0 else INF ''' cur番目の竹に対して ret0:ABCどれにも使わない ret1:Aに使う(合成:MP+10) ret2:Bに使う(合成:MP+10) ret3:Cに使う(合成:MP+10) ''' ret0 = dfs(cur + 1, a, b, c) ret1 = dfs(cur + 1, a + l[cur], b, c) + 10 ret2 = dfs(cur + 1, a, b + l[cur], c) + 10 ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10 return min(ret0, ret1, ret2, ret3) print(dfs(0, 0, 0, 0))
なんとなく作成してみた図(https://www.draw.io/):
参考記事:
blog.192.works
D - Lazy Faith
問題を読むまでに至らず…
コメント
最近はSolversの多い順に300~400点の過去問を解いていましたが,本格的にアルゴリズムの勉強に立ち向かわないとダメそうです.
【Tumblr API】Tumblrのブログやスキ(like)したポストの写真と動画をダウンロードする【Python】
はじめに
最近,Tumblrがアダルトコンテンツを禁止したり,その判定がガバガバ(キツキツ?)なせいで話題になっていました.
そんなことから,以前API関連を試していた時に,TumblrのAPIをいじりかけてそのまま放置していたことを思い出したので,指定したブログや自分がlikeしたポストの写真と動画をダウンロードするコードを試しに書いてみました.
使用したライブラリ
コードを書くにあたって以下のライブラリを使用しました.
- pytumblr
- requests
- beautifulsoup4
- tqdm
pytumblrは公式(多分)で提供されている,Tumblr APIを呼び出すためのクライアントを作成できるライブラリです.
使い方
使い方の説明はリポジトリのREADMEに書いてありますが,APIキーの取得関連についてだけ参考サイトなどを少し記載しておこうと思います.
このコードを使用するにはAPIキーが必要になります.
まずはアプリケーション登録を行ってコンシューマーキーとシークレットキーを取得します.
以下のサイトなどを参考にすると良さそうです.
また,上のサイトにも記載されているOAuth認証のためのトークンとシークレットトークンも必要になります.
プログラムで認証を行って取得する方法もありますが,以下のサイトから取得するのが簡単そうです.
参考:https://github.com/tumblr/pytumblr
感想
今回使用したライブラリの一つであるBeautifulsoup4ですが,スクレイピング関連で使うということで前から耳にしていたものの,使用するのは今回が初めてでした (大したことには使っていませんが).
スクレイピングもいつかやってみたいと思います.
参考・関連記事
AtCoderでレートが初めて緑色になりました
はじめに
2018/12/2のAtCoder Beginner Contest 114でレートが800を超え,初めて緑レートになりました!
その記念として,今までの記録ややったことなどについて書いておこうと思います.
他の方々の記事で既にn回書かれていることが多いですがご容赦ください.
大雑把な今までの記録
開始時
前から興味があったことと,研究室に配属されてPythonを使うことになったのでその練習を兼ねて始めました.
以下の記事を参考に入門しました.
qiita.com
競プロを紹介する際にはとりあえずこの記事を見せればOK!というレベルでわかりやすくまとめられています.
灰~茶
始めた直後はそこそこのペースでA,B問題の過去問をメインに解いていき,時々C問題の過去問も解いていました.
コンテストについては,A,B問題を解くスピードは今ほどなかったものの,C問題の部分点を解けたり,AtCoder Grand Contest(AGC)のA問題が解けたりするなどして,レートが茶色に到達しました.
茶~茶(中)
茶色になった直後に一度灰色に戻ってしまいましたが,その後もたまにC問題が解けたりして,茶色の真ん中あたりのレートにはなっていきました.
しかし,この辺りから研究の方が忙しくなってくるなどして,精進をあまりしなくなってしまいました.
茶(中)~緑
精進はあまりしなくなってしまいましたが,問題に慣れてきたこともあってC問題を解けない場合でもA,B問題をそこそこの速さで解けるようになりました.
そのため,なんとかレートは維持できていました.
そして最近,AGCや企業主催のコンテストによって少しずつレートが上がったり,何回かC問題が解けたりするなどして緑に到達しました.
やったこと
過去問を解く
過去に開催された問題の一覧と自分の提出状況を表示してくれるAtCoder Problemsを利用して過去問を解きました.
基本的にはAtCoder Beginner Contest(ABC)のA,B,C問題をある程度順番に解いていってた感じです.
また,一時期C問題何もわからん状態になっていたのですが,どなたかのツイートで「AtCoder Problemsのソート機能を使って,解いた人が多い順に並べて上位のものから解くと良い」というものを目にしました.
C問題はA,B問題に比べて解法のパターン的なものが増え,発想力が求められると感じます. この方法を使えば,比較的解きやすい問題からパターン的なものの経験を積んでいけると思います.
そして何より,自力で解ける率が高くなるので精神衛生的にも良いです(重要)
便利なライブラリなどを知る
便利なライブラリを知ることでかなり解ける問題が増えました.
Pythonだと
- collections
- itertools
- 累積和,順列,組み合わせなど
- bisect
- 二分探索
- queue(まだ使ったことはない)
- 私はまだ使ったことがありませんが,よく耳にするPriorityQueueが使えるようです
- heapqというものもあるらしい
など.
できるだけコンテストに参加する
やはりコンテストに参加して問題を解くのが一番の練習な気がします.コンテスト中に解法が思いつかないとかなり悔しい思いをするので,解説を見た際の印象も強く残る感じがします.
コンテストは,レート1200未満なのでABCに参加していますが,AGCにも参加していました.AGCは配点の高い問題が多いですが,最初のA問題は200や300点なので解ける可能性があります. AtCoder Grand Contest 027 - AtCoder
A問題だけでもそこそこの速さで解ければ,ABCでC問題が解けた場合と同等以上のパフォーマンスが出ます.
Twitterで競プロ関連の人を観測する
Twitter上には競プロをやっている方々がたくさんいます.
強い人をフォローしていると役立つ情報が得られますし,レートが近い人を見ているとモチベーションを維持できます.
また,コンテスト終了後は参加した方々がTwitter上で自分の解法を解説していたり,他の方と議論していたりと見ているだけでとても参考になります.
ブログに解いた問題を記録してみる
こちらは最近始めたことです.
手間はかかりますがその分復習になりますし,後から見返せるのが良いです.
100均のホワイトボードを買う
競プロ時、何も思い浮かず座っているだけのことが多い茶や緑の人は、まず紙用意して条件などを書き出してみてください
— 31536000 (@CuriousFairy315) 2018年3月31日
紙が勿体無いと思うならホワイトボードでも良いです
ダイソーで両面使えて、しかも片面は格子線が引かれている奴が売ってます
これだけで水色に上がれる可能性はぐっと高くなります
紙と鉛筆よりも気軽に書いたり消したりができるので,解法を考える際のメモに便利です.また,絵や図を描いてみると解法を思いつく場合が多いので重宝しています.片面が方眼になっているのも非常に便利です.
今後
とりあえず茶色に逆戻りしないぐらいのレートを目指したいですね…
アルゴリズムの勉強があまりできていないのでそちらにも手をつけていきたいと思います.
【参加記録】AtCoder Beginner Contest 114
はじめに
AtCoder Beginner Contest 114に参加した記録です.
A - 753
入力が7か5か3だったら'YES'を出力,そうでなければ'NO'を出力する.
N = int(input()) if N == 7 or N == 5 or N == 3: print('YES') else: print('NO')
B - 754
文字列の先頭から順番に3つずつ取り出し,753との差の絶対値を比べていけば良い.
Pythonだと簡単.
S = list(input()) res = 753 for i in range(len(S)-2): X = '' for i in S[i:i+3]: X += i X = int(X) tmp = abs(753-X) if tmp < res: res = tmp print(res)
解説では2行で実装していました.
S = input() print(min(abs(int(S[i:i+3]) - 753) for i in range(len(S) - 2)))
https://img.atcoder.jp/abc114/editorial.pdf
C - 755
(7,5,3)の3桁以上入力の桁数以下の直積集合(?)によって,解説における準七五三数を列挙して条件に合うものの数をカウント.
itertoolsが非常に便利でした.暇があったら使い方のまとめみたいなものを作りたい.
解説によると再帰関数で実装するのが素直な方法らしいです.
import itertools import collections N = input() if int(N) < 100: print(0) exit() product_list = [] for i in range(3,len(N)+1): product_list += list(itertools.product('753', repeat=i)) res = 0 for i in product_list: num = "".join(list(i)) if int(N) < int(num): continue if num.count('5') > 0 and num.count('7') > 0 and num.count('3') > 0: res += 1 print(res)
D - 756
ググったら解けそうな気がしたけど,時間不足&結局方針も間違えていました.
コメント
ここ最近は競プロにあまり触れていなかったので,C問題が解けるか不安でしたが無事解くことができました.
そして今回のコンテストでレートが緑に到達しました.
まだまだC問題も安定して解ける訳ではないので,できる限り陥落しないように精進したいです.