naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Beginner Contest 116

1/20(日) 21:00-22:40
(諸事情により21:26から参加)
4完90位*1

A - Right Triangle (100)

ソートして最初2つの積半分(本当はソートしなくてもよい)*2
→AC 27:56 (1:xx)
https://atcoder.jp/contests/abc116/submissions/4055208

備考

shortestがAWKの8バイトのやつだった

$0*=$2/2
  • $0は3辺の長さをスペース区切りで繋いだ文字列だけれど、数値としては最初の辺(一番短い辺)の長さになる
  • $2が二番目に短い辺の長さ。これの半分を一番短い辺の長さに掛けることでこの直角三角形の面積となる
  • そして$0に入っているものが表示される

B - Collatz Problem (200)

シミュレートして既出値が出たらそこ
→AC 31:25 (5:xx)
https://atcoder.jp/contests/abc116/submissions/4055425

C - Grand Garden (300)

高くから水平スキャンして数え
→AC 37:06 (11:xx)
https://atcoder.jp/contests/abc116/submissions/4055766

後で

左から見て行って、前よりいくつ高くなっているか(引き算して)を答えに足していく。低くなった場合は足さない。
それだけで良かった。
→AC
https://atcoder.jp/contests/abc116/submissions/4063018

c=0,l=0,h=0;main(N){scanf("%d",&N);while(N--){scanf("%d",&h);c+=h>l?h-l:0;l=h;}printf("%d\n",c);}

とりあえずC言語のshortest (97bytes)

D - Various Sushi (400)

最初三分探索(種類数決め打ち)と思って考え始めてたんだけど、どの種類を選ぶかを決めるの無理…と思って仕切り直して

  • 種類を問わず大きい順にK枚取る(この時の合計と種類数からスコアを出す)
    • どの種類を何種類取ったか集計しておう
    • 美味しさの小さい順に(種類とともに)取り出せるようにpriority_queueにK枚突っ込んでおく
  • K+i番目に大きいものが未知の種類だったら、これまでの中で一番まずい皿(その種類唯一の皿は不可)を捨ててそれと交換(この時の合計と種類数からスコアを出しベストと比較)
    • これを取らずにそれより後の未知種皿で種類を増やしたほうが良くなるケースは?(ここまでの種類数+1)に最速で到達するのがこれなら心配しなくていい。その「後の未知種皿」では(ここまでの種類数+2)に最速で到達するのに使えばいい。
      • こうして種類数が増えるたびにスコアを出しベストと比較
    • 既知の種類だったら、その種類で取得済みの皿よりまずいのは明らかなので交換メリットなし。無視できる。
    • 何らかの種類の唯一の皿と交換しても、種類数は増えず美味しさ総計だけが減るので交換メリットなし。無視できる。

→AC 76:31 (50:xx)
https://atcoder.jp/contests/abc116/submissions/4057495

後で
  • 各種類の中で最大のやつとそれ以外のやつに分ける
  • 最大のやつだけを降順に並べる。その累積和も取っておく。
  • それ以外のやつは種類関係なく降順に並べる。その累積和も取っておく。
  • 種類数(aとする)を1≦a≦|最大のやつ| まで動かし、最大のやつの大きい方からa個と、それ以外のやつの大きい方からK-a個(取れるなら*3)取ってスコア計算(累積和のお陰でO(1))
  • ソートの計算量が一番大きくてO(N\log N)かな

→AC
https://atcoder.jp/contests/abc116/submissions/4063400

*1:遅延を差し引くと50位前後だけどまあ自分より遅く参加して早く終わってる人とかいるし途中までやってこどふぉに流れた人もいるしあまり意味はない

*2:長辺が3番目に来るのが確定しているのでソートする必要はなかった(3つ目の値を読み込む必要すらない)。

*3:そのチェックを怠ってWAを繰り返した