ARC095に参加した

ARC095に参加しました。CとDを40分くらいでやっつけて、Eに1時間取り組むも解けず。 レートは935→1010になりました。 ようやっとレート4ケタの世界へ。単調増加し続けていきたいものです。

前回の記事：

amalog.hateblo.jp

GCJ 2018 Round1Aに参加した

Google Code Jam 2018 Round1Aに参加しました。上位1500人がRound2に進めるらしいのですが、結果としては1717位で敢えなく敗退。

まぁ今回で強い人は全員消えるはずなので、Round1Bがんばりましょ。

前回の記事：

amalog.hateblo.jp

振り返り

Waffle Choppers

横方向に累積和を取った後に縦方向に累積和を取ると、左上から任意の点までの長方形に何個チョコチップが含まれているかが分かる(盤面の累積和)。

望ましい分割をするためには、縦だけに注目したときも横だけに注目したときもチョコチップが均等に別れていることが必要。 なので、盤面の累積和の右端列と下端行に着目すると、そもそもうまくいく分割が存在するかが分かる。

うまくいく分割が存在するならそれに従って実際に分割してみて、ちゃんとそれぞれの部分にチョコチップが割り振られているかを累積和を参照しながら確認すれば良い。

解きながら「numpy使いたい！」ってn回叫んだ。

def cumsum(lst):
    res = [0]*len(lst)
    res[0] = lst[0]
    for i in range(1, len(lst)):
        res[i] = res[i-1] + lst[i]
    return res

def cumsum2(area):
    height = len(area)
    width = len(area[0])
    res = [[0]*width for _ in range(height)]
    
    for i in range(height):
        for j in range(width):
            if j==0:
                res[i][j] = area[i][j]
            else:
                res[i][j] = res[i][j-1] + area[i][j]

    for i in range(height):
        for j in range(width):
            if i!=0:
                res[i][j] = res[i-1][j] + res[i][j]

    return res

def case(R, C, H, V):
    hcnt = [0]*R
    vcnt = [0]*C
    total = 0
    area = [[0]*C for _ in range(R)]
    
    for i in range(R):
        row = input()
        for j, c in enumerate(row):
            if c=='@':
                area[i][j] = 1
                hcnt[i] += 1
                vcnt[j] += 1
                total += 1

    if total%((H+1)*(V+1))!=0 or total%(H+1)!=0 or total%(V+1)!=0:
        return 'IMPOSSIBLE'

    each = total//((H+1)*(V+1))
    area_cumsum = cumsum2(area)
    h_cumsum = cumsum(hcnt)
    v_cumsum = cumsum(vcnt)

    hcuts = []
    vcuts = []

    for i in range(1, H+2):
        target = total//(H+1)*i
        if target not in h_cumsum:
            return 'IMPOSSIBLE'
        else:
            hcuts.append(h_cumsum.index(target))

    for i in range(1, V+2):
        target = total//(V+1)*i 
        if target not in v_cumsum:
            return 'IMPOSSIBLE'
        else:
            vcuts.append(v_cumsum.index(target))
    
    for i, hcut in enumerate(hcuts):
        for j, vcut in enumerate(vcuts):
            if area_cumsum[hcut][vcut] != each*((i+1)*(j+1)):
                return 'IMPOSSIBLE'

    return 'POSSIBLE'


def main():
    T = int(input())
    for t in range(1, T+1):
        R, C, H, V = map(int, input().split())
        print('Case #{}: {}'.format(t, case(R, C, H, V)))

if __name__=='__main__':
    main()

Bit Party

貪欲っぽくとけば良さそうだなーと思った時点で頭が止まったので飛ばした。貪欲っぽく解けば良かったらしい。無念。

Edgy Baking

区間を持っておくDPで解けば良さそうだと思ったが、時間がなかったのでvisible setだけ通る嘘解法(貪欲)を提出した。

反省

• 実装力が低い。特に少しひねられたDPとかで頭が止まるのをなんとかしたい。atcoderのtypical dp contestとかを解いて出直してきます。

今日はABC・ARCもあるので競プロ漬けの1日にしましょう。

Twitterでふぁぼったリンクを自動でPocketに飛ばしてあとで読む方法

僕の最近の情報収集はかなりの部分をTwitterに依存しています。

興味のある分野が機械学習まわりということもあり、PFNの岡之原大輔さん(@hillbig)をはじめ、 いろいろな人が新しい論文にコメントを付けて紹介してくれています。

Twitterを眺めている時間は研究モードでないので「あとで読む」感覚でふぁぼるわけですが、ふぁぼ欄というのは大変に検索がしづらいという問題点があります。毎回Pocketに保存すればいいのですが、いかんせんタップ数も多くて面倒。

そこで、IFTTTをあさっていた所、

• Automatically save in Pocket the first link in a Tweet you like - IFTTT

というそのものずばりなアプレットを見つけました。

TwitterとPocketを認証しておけば、Twitterでふぁぼったツイートの最初のリンクを自動でPocketに飛ばしてくれてストレスフリーでよろしい。

いいぞー

難点としては、引用ツイートを含んでいた場合や画像つきの場合にも作動してしまうことですかね。 僕はPocketはとりあえずほいほい放り込む主義なので多少ノイズが混じっても問題ないですけど、人によっては気になりそうです。

Google Code Jam Qualification Round 2018に参加した

ラボの助教+ラボ同期に誘われてGoogle Code Jam 2018の予選に参加しました。

まるまる1日使うコンテストは初めてだったので、どういうテンションで望めばいいか全く分かりませんでした。 結果的に問題を見てから4時間くらい放置してAmazon Prime Video見てしまったので若干反省しています。

パスしたかコンテスト中に分かるVisible Caseとコンテストが終わってから分かるHidden Caseが存在するのは面白いですね。 4問すべてのVisible Caseが通れば予選突破が確定するシステムもなかなか良いと思いました。

一方でサーバーが激重だったりうちのネット回線がカスだったりしたせいでsubmit連打してたらWAがたくさん生えて辛かったです。

振り返り

Saving The Universe Again

前にShootを固めるほどダメージが下がること、後ろのShootの方がダメージが大きいこと、を考えて、文字列を後ろから舐めてCを後ろに追いやれば良い。

初Google Code Jamだったこともあり、python3.6以降でしか使えないfstringを使って1回WA+隣り合った2つしか交換できないのを見落としていて1WA。

def calc(P):
    ans = 0
    damage = 1
    for c in P:
        if c=='S':
            ans += damage
        elif c=='C':
            damage *= 2
    return ans

def swap(P):
    for i in reversed(range(len(P))):
        if P[i-1:i+1] == 'CS':
            return P[:i-1] + 'SC' + P[i+1:]
    return None
    
def main():
    T = int(input())
    for i in range(1, T+1):
        D, P = input().split()
        D = int(D)
        cnt = 0

        while calc(P)>D:
            cnt += 1
            P = swap(P)
            if P is None:
                cnt = 'IMPOSSIBLE'
                break
        
        print('Case #{}: {}'.format(i, cnt))

if __name__=='__main__':
    main()

Trouble Sort

擬似コードが問題文中に書かれているので愚直に実装して、あとはsort使ったやつと比較しておしまい…… だと勘違いして計算量の見積りをしなかったためHidden CaseでTLE。

追記：偶数番目と奇数番目のリストをソートして、前から順に比較するだけで通る。

Go Gopher

インタラクティブな形式の問題。

長方形の形をマスに固定して、周囲が塗られたマスが少ない順にクエリを投げていけば通る。

テスト用にtesting_tool.pyが配られているので、そのテストケースを上限いっぱいにして通ることを確認。

import sys
import math

def main():
    t = int(input())
    for i in range(t):
        a = int(input())
        w = math.ceil(a/3)
        area = {i:0 for i in range(2,w)}
        checked = set()
        while True:
            # query
            x = min(area, key=lambda x: area[x])
            print(x, 2, flush=True)

            # update
            x, y = map(int, input().split())
            if x==0 and y==0:
                break
            if x==-1 and y==-1:
                sys.exit()
            if (x, y) not in checked:
                checked.add((x, y))
                for j in [-1, 0, 1]:
                    if not 2<=x+j<=w-1:
                        continue
                    area[x+j] += 1
            
if __name__=='__main__':
    main()

Cubic UFO

立方体を射影した面積に対応する回転角を求める問題。 scipyとかの非標準ライブラリが使えるか分からなかったのでニュートン法で解くことに。numpyとかscipyとか使えるんですかね？？

のときは軸まわりだけ回せばOK。陰は縦、横の長方形になる。 面積最大になるのはのとき。

のときは軸まわりに回した状態から軸回りに回転させれば良い。形としては六角形。 面積最大になるのは回転させた時。 (投影図かなにかを書きながら六角形の面積を考えると) 最終的にはとして、 を満たすを探す問題に帰着される。

でも、これ手元でテストするのが難しい(面倒くさい)と思う。Visible CaseとHidden Caseで全くロジックが違うってどうなんだ？ うまい方法ある人は教えてください。

from math import *

def newton(f, g, x, eps=1e-8):
    while abs(f(x)) > eps:
        x -= f(x)/g(x)
    return x

def rotate(x, y, z, rx=0, rz=0):
    # rotate around x
    y, z = y*cos(rx)-z*sin(rx), y*sin(rx)+z*cos(rx)
    # rotate around z
    x, y = x*cos(rz)-y*sin(rz), x*sin(rz)+y*cos(rz)
    return (x, y, z)

T = int(input())
for i in range(1, T+1):
    A = float(input())
    x = 0.5
    d45 = pi/4
    print('Case #{}:'.format(i))
    if A <= sqrt(2):
        theta = newton(
            f=lambda theta: sqrt(2)*cos(d45-theta)-A,
            g=lambda theta: sqrt(2)*sin(d45-theta),
            x=0
        )
        # print(degrees(theta%(2*pi)))
        print(*rotate(0.5, 0, 0, theta))
        print(*rotate(0, 0.5, 0, theta))
        print(*rotate(0, 0, 0.5, theta))
    else:
        alpha = acos(1/sqrt(3))
        theta = newton(
            f=lambda theta: sqrt(2)/2*cos(theta)+sqrt(6)/2*cos(alpha-theta)-A,
            g=lambda theta: -sqrt(2)/2*sin(theta)+sqrt(6)/2*sin(alpha-theta),
            x=0
        )
        # print(degrees(theta%(2*pi)))
        print(*rotate(0.5, 0, 0, d45, theta))
        print(*rotate(0, 0.5, 0, d45, theta))
        print(*rotate(0, 0, 0.5, d45, theta))
        

反省

• 問題文が長いので、ストーリーとかを省いて問題をシンプルに書きなおすべき。
• 問題の根幹に関わる読み落としはNG。日本語でさえ読み飛ばすのだから、英語なら尚の事。丁寧丁寧丁寧に読む。
• 計算量の見積りは必ずやる。目の前にわかりやすい解法がぶら下がってても飛びつかない。
• (休日の貴重な4時間をニコニコ動画に費やさない)

僕のTwitterがまさかのレイバンったので、抹消するスクリプトを書いた

ついに先日僕もTwitter乗っ取られデビューしました。お恥ずかしい限りです。 リプライが飛んでしまった方々、すみませんでした。

レイバンｗｗｗすみませんｗｗｗ

— えじ (@SakuEji) 2018年4月6日

せっかくだからレイバンのサングラス買ってくれよな！

— えじ (@SakuEji) 2018年4月6日

レイバン本体には罪はなく、スパムやってるヤツが悪いのは間違いないのですが、レイバンはもはやスパムという印象しかないですね……

さて、Twitter乗っ取りはいくつか種類があり、主要なパターンとしてはパスワード流出や連携アプリなどがあるようです。レイバンは前者らしいですね。 僕も慌ててパスワード変更しました。他のサービスと共通ではないので、どこから流出したのか気になるところです。

パスワードを変更した後に残されたのはフォロワーの皆様に送りつけた70件あまりのツイートでした。 手動でぽちぽち消すのはさすがに気が滅入るので、退屈なことは全てpythonに任せようの方針でスクリプトを書いてなんとかすることにしました。

家に帰ったらレイバンのサングラスに関するツイートを消すスクリプト書くので許してヒヤシンス

— えじ (@SakuEji) 2018年4月6日

股関節痛いのもだいたいレイバンのせい

— えじ (@SakuEji) 2018年4月6日

そんで書いたスクリプトがこちら。

外部ライブラリとしてはtweepyを利用しています。 レイバンスパムは短縮リンクを展開して判定しようかとも考えましたが、面倒だったので大量にリプライを付けていたらスパムということにしました。（短縮リンクの展開はrequestsを使えばできると思います）

使いたい方は Twitter Application Management で自作アプリを登録し、APIキー・APIシークレット・アクセストークンなどを発行してお使いください。

これさえあれば何回レイバンっても大丈夫！

レイバンった人はあらゆるWebサービスのパスワードなどを見直しましょう。

ARC094に参加した

今日やったこと:

1. 昼過ぎに起きる
2. Google Code Jamの問題をチラ見
3. 4時間くらいAmazon Prime Videoと戯れる
4. 重い腰を上げてGCJ解き始める
5. ARC094に参加
6. GCJ予選突破確定

そんなわけでARC094に参加しました。C問題だけ解いて498位。レートは847→935となりました。はやく水色になりたい。

振り返り

C問題

最大のやつと残り2つとの差の合計を見る。1回の操作につき差が2ずつ縮まることを考えて、合計が偶数なら2で割ればOK。奇数なら最大のやつを増やす操作が必要。

a, b, c = sorted(map(int, input().split()))
diff = (c-a)+(c-b)
if diff%2==0:
    print(diff//2)
else:
    print(diff//2+2)

D問題

基本的には通り存在して、AとBが近い時に場合分けが必要なことまでは分かったが、場合分けを1通り見逃して撃沈。

反省

最初に全部問題を読みましょうという気持ち。DよりEの方が遥かに簡単でした。

あとはじっくり考える前にコード書き始めるのは良くない癖だと思いました。