名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

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

昨日は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問題は数学的な背景が理解できていなかったので,数学から学び直しですね(白目)

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