全国統一プログラミング王決定戦本戦

atcoder.jp
主催／日本経済新聞社　共催／AtCoder　協賛／TRI-AD，CISCO
2/17(日) ＠東京ドームホテル大宴会場「天空」
f:id:n4_t:20190217151752j:plain

予選500位に入ったので決勝大会後のイベント＆懇親パーティーに呼ばれて参加してきました。
f:id:n4_t:20190218181009j:plain
問題文は最初公開されていなかったのだけれど、本戦終盤頃にPDFで公開されたのでKindleに入れてちびちび考えていました。*1

chokudai社長 + PFNの秋葉さん西川さんのトークショーの後、上位３名によるエキシビション（20分8問のコンテスト形式＋chokudai氏の実況）があって凄く面白かったし刺激的でした。
8問全完した準急さんのキー入力はめちゃ速いです。

500人懇親パーティーは美味しい食事＋色々な人と話せて楽しかったです。
f:id:n4_t:20190217194643j:plain:w400
というわけで、本戦＋エキシビションの問題を見ていこうと思います。

本戦

Tasks - 全国統一プログラミング王決定戦本戦
問題名の頭文字がABCDEFGHになってる
とりあえず問題を読んだ範囲の考察だけメモ

A - Abundant Resources (200)

区間の始点終点を1つずつ動かしながら区間総和を変更していく尺取り的なやつをN本同時にやればよさそう

B - Big Integers (200)

単に2つの数をK進法で比較するだけの問題なのでは
- 正規化が必要かな？と思ったけど $0\le A_i\le K-1, 0\le B_i\le K-1$ だからそのままで良さそう

C - Come Together (300)

どのマスを終点にすればそこへのマンハッタン距離の合計を最小化できるか
終点を全探索は無理だけど、xを二分探索とか三分探索とか、yを全探索（あるいはこちらも二分 or 三分探索とか）できそう
絶対値なので決め打ちしたx,yより前の分と後の分で分けて（それぞれ累積和を使ってまとめて）演算できそう
ていうかxとyを独立して処理できそう
HW-K だと1e10で無理だけど全部埋まっていた場合の合計からKの分を引く感じかな

D - Deforestation (500)

ある区間を消す感じ？
遅延セグ木使う
- 区間に対する追加、区間の合計、区間のクリアが必要

E - Erasure (700)

幅K以内で切り分けるんだけど
N=5000だからnext_permutation的なやつじゃなくてDPかな

（ここまで見た）

F - Flights (900)

（見てない）

G - Greatest Journey (1200)

（見てない）

H - Homework Scheduling (1500)

（これは本戦で誰も通してなかった）

エキシビジョン

全国統一プログラミング王決定戦エキシビジョン - AtCoder
こちらは実況とかあるしヒントありということで。
Pythonで書いてみる*2

A - Prefix Array (200)

1から|S|までの数を出力していくだけ？

→AC

s=raw_input()
for i in range(len(s)):
    print(1+i)

B - 二乗 (200)

(int)sqrt(N)

→RE
あ
import math
→AC

import math
a=int(raw_input())
print int(math.sqrt(a))

C - 11で割った余りの計算方法 (200)

問題文につられずに N%11

→AC

a=int(raw_input())
print a%11

D - 辞書順最小の数 (200)

/10{N-1}/

→AC

a=int(raw_input())
s=['0']*a
s[0]='1'
print ''.join(s)

E - スーパーFizzBuzz (300)

やるだけ？

→AC

n=int(raw_input())
for i in range(1, 1+n):
  t = []
  if i%2==0:
    t.append('a')
  if i%3==0:
    t.append('b')
  if i%4==0:
    t.append('c')
  if i%5==0:
    t.append('d')
  if i%6==0:
    t.append('e')
  ts = ''.join(t)
  if ts == '':
    print i
  else:
    print ts

F - コラッツ問題 (300)

これはネタバレがあった
サンプルケース2にf(N)=1000となるNが示されているから
そこからコラッツしていけばいい
→WA
あ
P=1のとき0を返すようになってた
直して
→AC

f = [None] * 1001

mx = 10000000000000000
n = 1000
f[n] = 1789997546303
f[0] = 1 # or 0

while n > 1:
  x = f[n] 
  tmp = mx+1
  if x % 2 == 0:
    tmp = min(tmp, f[n]/2)
  else:
    if 3*x+1 < mx:
      tmp = min(tmp, 3*x+1)
  if tmp > mx:
    import sys
    sys.stderr.write('ERROR at %d\n' % n)
  f[n-1] = tmp
  n -= 1

P = int(raw_input())
print f[P]

G - 回文スコア (400)

偶数（ペア）が取れる文字を全部+ペアからあぶれた文字があれば1つ、で1つ作る
残りのあぶれ文字を1つずつ

→AC

from collections import Counter
s = raw_input()
ct = Counter(s)
ev = r = 0
for i in range(26):
    c = chr(0x61 + i)
    ev += int(ct[c] / 2) * 2
    r += ct[c] % 2

if r > 0:
    ev += 1
    r -= 1
 
L = ev*ev + r
print L

H - 8^kゲーム (500)

Nが1e18まであるから単純にシミュレーションとかDPとかしてたら死ぬ

（準急くんは小さめの数で実験してた）

実験してみる

mm = {}

def tak(n):
    if n in mm:
        return mm[n]

    mm[n] = 0
    if n == 0:
        return mm[n]

    c = 1
    while c <= n:
        if tak(n-c) == 0:
            mm[n] = 1
            break
        c *= 8

    return mm[n]

def g(n):
    r = n % 9
    if r == 8:
        return 1
    else:
        return r % 2

for n in range(10000):
    T = tak(n)
    G = g(n)
    if T != G:
        print n, T, G, 'x' if T!=G else ''

実験の結果、N % 9 が8なら勝ち、8未満なら(N % 9) % 2が1なら勝ちみたい
→AC

def g(n):
    r = n % 9
    if r == 8:
        return 1
    else:
        return r % 2

n = int(raw_input())
print 'Win' if g(n) == 1 else 'Lose'

*1:本番ではネットワークトラブル回避のため問題文が紙で配られたそうです。

*2:python2ですごめんなさいごめんなさい

naoya_t@hatenablog

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