2018-06-25

ARC099に参加した(210位)

競プロ

f:id:ejinote:20180624151041p:plain

ARC099に参加しました。210位でレートは1304→1429になりました。久しぶりのコンテスト参加で緊張しましたが、Dをそれなりに早く解いたのがよかったっぽいです。

そういえば先日書いた記事がホッテントリに載りました。結構うれしいものですね。

amalog.hateblo.jp

振り返り

C - Minimization

最小値が1なので、全要素を1にすればよい
1回適用すると1がK-1個増える

1を中心に左右に1を広げていくイメージで解きました。1の左右それぞれについて端から最適な回数で処理をして、1の周りの余りはよしなにやる感じ。

import math
n, k = map(int, input().split())
A = list(map(int ,input().split()))
print(math.ceil((n-k)/(k-1)+1))

D - Snuke Numbers

手で書いても全く分からなかったので実験しました。

import matplotlib.pyplot as plt
%matplotlib inline

def digit_sum(i):
    return sum(map(int, list(str(i))))

scores = [i/digit_sum(i) for i in range(1, 50000)]
plt.figure(figsize=(10, 5))
plt.scatter(list(range(1, 50000)), scores, s=1)
plt.show()

f:id:ejinote:20180625171837p:plain

規則性があることがわかります。ちなみにスコアがジャンプするのは繰り上がりが起きるときなので、XXX999みたいな数にだけ着目すればよいと分かります。

XXX999みたいな数それぞれについて、次のやつとの比較を行って、だめだったら消せば良いと思います。

実装は鬼汚いです。

def digit_sum(i):
    return sum(map(int, list(str(i))))

def score(head, tail):
    return num(head, tail)/digit_sum(num(head, tail))

def num(head, tail):
    return int(str(head)+tail)

k = int(input())
tail = ''
head = 0
cnt = 0
last = 0
while True:
    head += 1
    if score(head, tail) <= score(head+1, tail):
        if num(head, tail) > last:
            print(str(head)+tail)
            last = num(head, tail)
            cnt += 1
            if cnt == k:
                break
    else:
        head = 0
        tail += '9'

E - Independence

辺をできるだけ少なく切断して2つのクリーク(部分グラフがすべて完全なグラフ)に分割すればよい
補グラフを取ると少し見通しが良くなって、補グラフにできるだけたくさん辺を足して完全二部グラフにする問題に変換することができる
補グラフをとった時点で二部グラフでなければ達成不可能。
辺はいくつでも足していいので、補グラフを連結成分分解して成分の集合を2つにまとめて完全二部グラフにすることができる。
クリークの辺の数は頂点数で決まり、辺を多くするなら頂点を多くすれば良い。ただ、頂点集合が2つあるので、2つをできるだけ同じサイズにすればよい。
うまいまとめかたを探すためにDP

みたいな感じで解けると思います。僕は実装が間に合いませんでした。

感想

Dが早く解けたのでレートもあがり万々歳です。たのしいですね。

そろそろ証明からは逃れられなそうなので、普段から軽く証明することは意識したいと思います。

2018-05-30

Kaggleで使えるpandasテクニック集

Python データ解析 Kaggle

f:id:ejinote:20190112195735j:plain

PythonでKaggleなどのデータ分析を行う際、pandasでゴリゴリ作業をすることが多いかと思います。

最近知って「めっちゃ便利やん！」ってなったものをまとめておきたいと思います。全部の関数にドキュメントへのリンクを付けたので参考にしてください。

今回も検証にはTitanicのデータセットを用います。また、文中でのdf.hoge()はpandasのDataFrameのメソッドであることを、pd.hoge()はpandasの関数であることを表します。

df = read_csv('input/train.csv', index_col=0)
print(df.shape)
df.head()

f:id:ejinote:20180530220813p:plain

2018-05-27

ARC098に参加しました (726位)

競プロ

f:id:ejinote:20180527175257p:plain

ARC098に参加しました。C問題を1回TLEしてD問題が解けず無事死亡しました。レートは1334→1298ということで、微減ですね。 D問題が解けなかったのは久しぶりなので練習不足を感じます。最近Kaggleが忙しくて過去問埋めもあまりできていません。

前回の記事

amalog.hateblo.jp

2018-05-21

AGC024に参加しました (445位)

競プロ

f:id:ejinote:20180521194539p:plain

AGC024に参加しました。A・B・Cを3完し、Dを途中まで解いて散りました。レートは1240→1334となりました。順調に水色を進んでいます。早く暖色になるぞという強い意志を持ってやっていきたいと思います。

と書いておいてウケるんですが、先週末土曜日にあったGCJ Round2はぶっちしてしまいました。飲み会に参加していて気づいたら0時だったのでもう無理でした。しまった。

前回のAtCoder

amalog.hateblo.jp

2018-05-07

ひとつの本屋で起きたこと。を読んで

日記

バズっていたこの記事を読んでいろいろ考えたのでメモがてら残しておく。

nyawaraban2014.amebaownd.com

これを読んでいる間は「なんだこの絵に描いたような無能な上司は」「たった一人のマネジメントでこんなぐちゃぐちゃになるんだなぁ」といった感想しか持たなかったが、数時間置いて読み返すと背筋が薄ら寒くなった。

これ。

繁忙期も終わっていよいよ棚の構成を考えなければならなくなっていた頃、私は『岩波文庫はなるべく少なくするように』と言われてイライラしていた。岩波書店の本は基本的に返品できない“買切”という制度。でも大学の書店では教授が大好きだし、授業でも使うし、他の出版社の文庫よりはるかに売れる。そりゃぁ選書が悪けりゃ在庫が増えるけど、2ヶ月ごとに100冊は注文しているけれど、ほとんど売り切れますよと言っても『もう注文はしないで在庫だけでまわして』と言われたのでカチンとキてその日のうちに100冊近く注文した。 (悪い店員だな、真似しないように！)

それもほとんど売り切れた。でもそういう店の特徴や実績は関係ないそうだ。

多くの店舗で岩波書店の本は（大学の書店ほど）売れていないのだろうし、買切制度も相まって在庫リスクも大きい。だから全体としては岩波文庫を縮小する方に向かったほうが「プラマイ合わせるとトータルでは」良いのかもしれない。でも、そうじゃないよね。各店舗もプラスにすべきだよね。

データ分析をしている人は常にこういうことが起きないか気を配るべきだと思う。油断しているとそれぞれの店で事情は違うのに「全体としての傾向としてはそうだよね」みたいな戦略を取りがちになる。

現場の感覚はきっと正しいことが多くて、一方でデータで見えてくるものもあって、どうバランスをとって両方を活かしていくか、ということが今後求められているマネジメント層やデータアナリストの在り方ではないだろうか。

ちなみに続編もだいぶ悲惨でした。

nyawaraban2014.amebaownd.com