読者です 読者をやめる 読者になる 読者になる

水面下の夢

競プロやイラストに興味があります.メインブログがここ.ソシャゲの話はこっち(http://ameblo.jp/0n0-yumechi/).ブログアイコンはYaQ(@8_9_00)さんから.

今日の競プロ(2015/04/12) というかABC 021に参加した感想

AtCoderABC Python 競技プログラミング

昨日はABCでしたね.Googleの方でもなにかやっていたらしいですけど,英語得意ではないし,時間も取れそうにないので,参加するのやめちゃいました… ダメだなあ.

ABC 021 A

A: 足し算 - AtCoder Beginner Contest 021 | AtCoder


足し算.もちろんすべて1で出力しました.桁が大きくなった場合ですが,ビットを上手く計算すればできそうですね.

N = int(input())
print(N)
for _ in range(N):
    print("1")

Submission #383276 - AtCoder Beginner Contest 021 | AtCoder

(subtask1だけ遅いんだけど何があったのかな.)

ABC 021 B

B: 嘘つきの高橋くん - AtCoder Beginner Contest 021 | AtCoder


グラフの問題かなあと思ったけど,サンプル入力と結果を見ていると解説スライドの通りですが,こんな法則があります.
YESになるのは,出発する街,あなたの街,移動した街の集合で各数値が現れる回数が1回以下.
NOになるのはそれらの集合で一つの値でも2回以上現れた時.
(言葉にすると上手く書けないやつだ!)

出発する街を1, あなたの街を3,移動した街を2,4,2,7とすると,これらの集合は{1, 3, 2, 4, 2, 7}になりますね.すると,2回2に行っていることになるので,これは最短と言えず,NOになります.

pythonで実現するなら,setを上手く使えば実現できますね.

N = int(input())
a, b = map(int, input().split())
K = int(input())
l = list(map(int, input().split()))
print("YES" if not (a in l or b in l or K != len(set(l))) else "NO")

Submission #383467 - AtCoder Beginner Contest 021 | AtCoder

ABC 021 C

C: 正直者の高橋くん - AtCoder Beginner Contest 021 | AtCoder

ぼくが実装したヘボい幅優先探索は,TLEが発生してダメでした.
もう少し最適化しないとダメですね.

ちなみに幅優先探索を使って解けないこともないようなので,今度リベンジしなきゃな.
(高速な探索アルゴリズムを覚えないとなあ)



というわけで,ABC 021はC問題が超えられず,終了.
131位でした.C問題は遅い方法とはいえ,思いついてはいたのだから,もう少し上手くやってACとれたんじゃないかと思い,若干消化不良.
D問題は数学的な背景が理解できていなかったので,数学から学び直しですね(白目)

いやあ,大学生活,今更ながらもっと数学勉強しとけばよかったなと後悔してます.
学ぶことが尽きそうにもないので,ずっと学び続けていきたいですね.