概要
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) なので大丈夫!
最後にちょっと脱線
このブログについて、本当は勉強したことをまとめていって自分用のノートにするつもりだったけど、気づいたら競プロの参加記になってた件。
まとめたいネタはいくつかあるんだけど、どうも、人が見て分かるような体裁にまとめるのが苦手というか、意外と骨が折れることが分かった。
記事にまとめるのより、過去問にチャレンジした方が楽しい ^^;。
まあ、無理せず、自分のペースでやればいっか。