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

A - Abundant Resources (200)

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

B - Big Integers (200)

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

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)

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

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'