30歳で競プロに目覚めた霊長類のブログ

ウホウホ (競プロの世界にやってきました。がんばります。)

DISCO presents ディスカバリーチャンネル コードコンテスト 2017 予選

概要

2019卒枠が100人と、その他の100人が本戦に進めるコンテスト。
本戦の告知(DDCC | ディスカバリーチャンネル)を見たら、イベントがすごく豪華。
特に対談のメンバーがすごい。皆憧れの人ばかり。
(将棋界と将棋プログラムのトピックは、ここ何年か、個人的に追いかけているので)
厳しいだろうけど、何としても本戦出たい!って思いで参加しました。

結果

A,B,C の3完。タイム10:20。222位。
C問題までは自分的にベストなパフォーマンスだった。
D問題は1submitしたけど、考察力が足りずWA+TLE。
その他枠の人、100人ぐらい辞退してくれないかな〜??。。
まあ、そんな訳ないので、来年までに力をつけてリベンジするか。。

A,B問題

特に難しいポイントがないので省略。
ダースの12倍がグロス、その12倍がグレートグロスという単位があるのを初めて知った。

以下、 私の回答
A - DDCC型文字列
http://ddcc2017-qual.contest.atcoder.jp/submissions/1656175

B 鉛筆
http://ddcc2017-qual.contest.atcoder.jp/submissions/1656644

C 収納

C: 収納 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 | AtCoder

N <= 100000 本の棒があって、長さCのケースに収納していくとき、ケースの最小数を求める。
ケースには1本か2本入れられて、2本入れる場合は[2本の和 + 1]の長さが必要。

以下、私の回答

N,C = map(int,input().split())
src = [int(input()) for i in range(N)]
src.sort()
 
l = 0
r = N-1
ans = 0
while l <= r:
    if src[l] + src[r] + 1 <= C:
        l += 1
    ans += 1
    r -= 1
print(ans)

ソートして左右から貪欲でいけた。
一番長いのを一番短いのと一緒に詰めることができれば、2本しまう。
そうでなければ、一番長いのを1本しまう。

例として、入力例1の C=10, L=[2,8,4,5]の場合。

  • ソートする。L=[2,4,5,8]
  • 2+8+1 > 10 で、8は単独で入れるしかないので、8をしまう。ans=1, L=[2,4,5]
  • 2+5+1 <= 10で、2と5が両方入るので、両方しまう。ans=2, L=[4]
  • 最後に4をしまう。ans=3

こんな感じ。

実際は、lとrの2つのインデックスを操作すれば、配列の要素を消すことなく、シミュレーションできる!
計算量は、

  • ソートにO(NlogN)
  • 貪欲なシミュレーションがO(N)

O(NlogN) なので大丈夫!

最後にちょっと脱線

このブログについて、本当は勉強したことをまとめていって自分用のノートにするつもりだったけど、気づいたら競プロの参加記になってた件。

まとめたいネタはいくつかあるんだけど、どうも、人が見て分かるような体裁にまとめるのが苦手というか、意外と骨が折れることが分かった。
記事にまとめるのより、過去問にチャレンジした方が楽しい ^^;。

まあ、無理せず、自分のペースでやればいっか。