naoya_t@hatenablog

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

企業コン埋め

ABC/ARC/AGC以外の企業主催コンテストなんかも埋めていく

気になったやつだけメモ

CODE THANKS FESTIVAL 2017(Parallel)

D - Bus Tour (300)

M -(kN mod Mの最小)
kN mod M の最小はgcd(N,M)では
なので
M - gcd(N,M)で
→AC
https://beta.atcoder.jp/contests/code-thanks-festival-2017-open/submissions/2927364

CODE FESTIVAL 2016 Final (Parallel)

B - Exactly N points (300)

  • 1までを使う: 1が作れる
  • 2までを使う: 2,3も作れる
  • 3までを使う: 4,5,6も作れる
  • 4までを使う: 7,8,9,10も作れる
  • nまでを使う: n(n-1)/2+1 〜 n(n+1)/2 が作れる

こうやって作る時、すべての数が作れる上、使う最大の数は最小化できる。
で、例えば8を作りたい場合
8を作れるのは「4までを使う」場合なので、4を使って残り4
4を作れるのは「3までを使う」場合なので、3を使って残り1
1を作れるのは「1までを使う」場合なので、1を使って残り0
というわけで、1,3,4を使えば8が出来る
xが与えられたときにいくつまでを使うのを見ればいいかというのは
n(n+1)/2=2x を解いて
n=ceil(√(2x+1/4)-1/2)
で大きい順に貪欲に持っていけばいい
→AC
https://beta.atcoder.jp/contests/cf16-final-open/submissions/2927273

COLOCON -Colopl programming contest 2018- Final(オープンコンテスト)

A - ファイティング・タカハシ (300)

RLEしておいて、最初と途中(N-2)と最後の行に気をつけて計算するだけなんだけどはまった

  • Bで始まったり終わったりしていたらくっつかないとか
  • 全部Aのときは特殊だとか
  • 最後のA+を途中に回しててN=1で落ちたりとか

WA(4)
AC
https://beta.atcoder.jp/contests/colopl2018-final-open/submissions/2927481


第3回 ドワンゴからの挑戦状 予選

B - ニコニコレベル (300)

RLEしておくとよいかな
貪欲に取ってしまうと ????525 みたいなの(len=6)を取りこぼす
252???252 どっちに?をつなぐのが有利?
可能な状態(高々2つ)を持ち回る必要性
WA(3), TLE(1)
→AC
https://beta.atcoder.jp/contests/dwacon2017-prelims/submissions/2927671