Python奮闘記

主にPythonのことを書くつもりだったけど、プログラミング周り全般の備忘録ということにした。大体競プロ。

ARC067-F Yakiniku Restaurants

競プロ

問題

F - Yakiniku Restaurants

N軒の店があり、それぞれ番号 1\cdots Mの肉があり、美味しさ Bが決まっている。 また、隣あう店を移動することができ、そのコスト Aが決まっている。 訪れ方と肉の選び方を工夫することで、番号 1\cdots Mの肉を集めたときの(美味しさ合計-コスト)の最大値を求める。

気持ち

区間 [l,r)の店を訪れるとするとコストが決まるので考えやすい。 区間を固定すると、各肉で独立に考えることができ、 それぞれ区間 [l,r) 内で一番美味しい肉をとってくれば良い。 ただこれだと計算量が O(N^2 M)となって間に合わない。

どうにか状態をまとめられないか考えてみる。 当たり前なのだが、肉番号 jを固定したとき、区間ごとに選ばれる肉は最大でも N種類しかない。 なので、各肉 i=1\cdots Nに対して「どの区間なら一番美味しいものとして選ばれるか」を考えると良さそう。

これはすなわち、「区間の他の要素が B[ i ] [ j ] より小さい」ということになる。もう少し区間 [l,r)として要求される特徴を整理すると、

  • L_iを B[i][j] > B[L_i][j]を満たす最小のindとしてとる。
  • R_iを B[i][j] > B[R_i-1][j]を満たす最大のindとしてとる。
  • 各 l=L_i .. iと各 r=i+1 ..R_i の組み合わせ [l,r)が肉 iを選ぶ区間になる。

となる。つまり各 iに対して L_i,R_iの情報さえあれば事足りる。これらはスタックを使って左右から走査することにより、全ての i=1\cdots Nに対して O(N)で求めることができる。

で、残る問題は各 iの情報をどうやって消すかということになる。 iの情報が残っていると、後で区間を固定した時に結局計算量が増えてしまうためである。 iの情報を消したものとして、それっぽい以下を考える。

dp [ L ] [ R ] = 区間 [L, R) の部分区間、すなわち L\le l かつ r\le Rなる区間 [l, r) 全てに対して足す美味しさ

これに情報を貯めていければ、最後に区間固定して計算する際に区間を縮めながらやっていけばなんとかなりそうである。

ただ、 dp[L_i ] [ R_i ] に B[ i ] [ j ] をそのまま足すのはまずい。区間 [L_i, R_i) の部分区間には iが含まれないものもあるからである。具体的には r\le iまたは i\lt lであるような [l,r)である(図を描いた方がわかりやすそうだが、めんどい)。 そのような「余計に足されてしまう区間」は dp[L_i ] [i ] と dp[i+1 ] [ R_i ] に集約される。なのでこいつらに - B [ i ] [ j ] を足しておけば後で差し引き0になる。

以上で解けた。計算量は O(N^2 + NM)である。計算量は増えるが、 L_i,R_iを求めるところはBIT使うのが自然かもしれない。

ACコード

上とはDPの定義が違って、dp[長さ][左端]にしている。そっちのが累積しやすそうだったからだが、あまり手間は変わらなさそう。

Submission #20276546 - AtCoder Regular Contest 067

def solve(N, M, A, B):
    INF = 10**18
    # dp[length][left]
    dp = [[0]*(N+1-i) for i in range(N+1)]

    for m in range(M):
        # find segment
        Left = [-1]*N
        Right = [-1]*N
        stack = [(INF, 0)]
        for i in range(N):
            b = B[i][m]
            while stack[-1][0] < b:
                stack.pop()
            Left[i] = stack[-1][1]
            stack.append((b, i+1))
        stack = [(INF, N)]
        for i in reversed(range(N)):
            b = B[i][m]
            while stack[-1][0] < b:
                stack.pop()
            Right[i] = stack[-1][1]
            stack.append((b, i))
        
        for i, (l, r) in enumerate(zip(Left, Right)):
            b = B[i][m]
            dp[r-l][l] += b
            dp[i-l][l] -= b
            dp[r-i-1][i+1] -= b
    
    SA = [0]
    for a in A:
        SA.append(SA[-1]+a)
    
    ans = -INF
    for length in reversed(range(1, N+1)):
        for l in range(N+1-length):
            d = dp[length][l]
            ans = max(ans, d - (SA[l+length-1]-SA[l]))
            dp[length-1][l] += d
            dp[length-1][l+1] += d
            if length >= 2:
                dp[length-2][l+1] -= d

    return ans

感想

解説と似てたけどちょっと違ったので書いた。いもす法と言われてみるとそうなのかな。

ABC129F Takahashi's Basics in Education and Learning

競プロ

問題

F - Takahashi's Basics in Education and Learning

等差数列 s_nがある。これを文字通りに左から連結した数字の mod M はいくつになるか。

気持ち

そのままだと扱いにくい。「連結」の操作は桁数さえ決まっていればなんとかなる。例えば桁数 cの数字 aを連結するなら、連結する前の答え Aに対し、

\displaystyle A\times 10^{c} + a

が答えになる。

こんな感じで考えると、数列を桁数ごとに分けて考えるのは自然である。 桁数を固定するとグッと解きやすくなる。実際桁を cに固定したのち、オフセットを後でかけるとして、 r=10^{c} 、初項 a_0 、項 n とすると、

\displaystyle A_n = a_0 \times r^{n-1} + (a_0+B) \times r^{n-2} + \cdots + (a_0 + (n-1)B) \times r^0

を計算すれば良いことがわかる。これは例えば a_0と Bに項を分けると等比数列の性質を利用すればいい高校数学問題に帰着する。よし、解けた！

...と思うのだが、実はこれだとWAをいただいてしまう。この考えだと詰めが甘い。等比数列の公式はご存知の通り(?)

\displaystyle 1 + r + \cdots r^{n-1} = \frac{1-r^{n}}{1-r}

となるので、 1-rで割る操作が必要になるのである。ところが今は法である Mが素数とは限らないため、逆元が存在しないかもしれない。この問題の邪悪ポイントである。

そうなると等比数列の公式は使うことができない。でも漸化式の決まった数列の要素を高速に求める手法を我々は知っている。そう、行列累乗である。 つまりさっきの A_nをうまいこと行列の形で書ければ...という気持ちになる。

ここまで行ければもう答えは出たようなものである。遷移はベクトル (A_n, a_n, 1)に対して考えれば良い。

ACコード

Submission #19568265 - AtCoder Beginner Contest 129

ちょっと汚いけど勘弁(ライブラリ省略)

import sys
input = sys.stdin.buffer.readline

def solve(L, A, B, mod):
    maxdig = len(str(A+B*(L-1)))
    alreadySelected = 1
    ans = 0
    for c in reversed(range(1, maxdig+1)):
        imax = min((10**c-A+B-1)//B-1, L-1)
        imin = max((10**(c-1)-A+B-1)//B, 0)

        a0 = A+B*imin
        d = B
        r = 10**c % mod
        n = imax - imin + 1
        if n <= 0: continue
        mat = [
            [r, 1, 0],
            [0, 1, d],
            [0, 0, 1]
        ]
        pmat = power_mat(mat, n, mod)
        score = a0 * pmat[0][1] + pmat[0][2]
        score = (score * alreadySelected) % mod
        ans = (ans + score) % mod
        alreadySelected = alreadySelected * pow(10, n*c, mod) % mod

    return ans

L, A, B, mod = map(int, input().rstrip().split())
print(solve(L, A, B, mod))

感想

modが素数じゃないの邪悪すぎる、と思ったがそれも含めてこの難易度なのかと思うと納得する。考察の段階でちゃんと細かいところまで詰めないといけない良い例。

ARC085-E MUL

競プロ

問題

E - MUL

数列\(A\)がある。ある\(i\)を選んで\(i\)の倍数のindexの要素を消し去る、という操作を繰り返せる。残った数列の合計値の最大を求める。

気持ち

操作全体は、要素をふたつ(選ばれるor選ばれない)に分けるものとみなせる。bit探索は思い浮かぶが、当然間に合わない。

ところで要素をふたつに分けるのはグラフにカットを入れる操作と見ることもできる。選ばれた側と選ばれなかった側に分けるという。 そうすると最小カット問題に帰着させる発想が生まれる。最小にしたいのは今は「損」な分であるから、辺の重みは基本「損する重み」を設定する。辺がカットの対象となった時(=辺の両端が違うグループに属するようにした場合)、相応の罰金を支払う、と捉えてもいい。

さらに具体化していくと、

  • S側は叩き割られたもの、T側は残されたもの
  • \(a>0\)のものは基本残したい。叩き割る際に罰金が発生するようにしたい。つまりS側に属するようになった時に罰金を背負わせたいので、Tとの間に辺を張る。
  • \(a\le0\)のものは基本叩きわりたい。上と逆の理由で、Sとの間に辺を張る。
  • 一番めんどそうな拘束条件。\(i, j\)(\(j\)は\(i\)の倍数)に対して、「\(i\)がS側に属する\(\Rightarrow\)\(j\)がS側に属する」と言い換えられる。これは破られて欲しくないという気持ちをこめて、\(i\)から\(j\)に罰金infの辺を張る。

とうまくはめられる。最小カット問題は最大流問題と等価なので、解ける。

ACコード

Submission #19252377 - AtCoder Regular Contest 085

(ライブラリは省略)

import sys
input = sys.stdin.buffer.readline
 
INF = 10**18
 
N = int(input())
A = list(map(int, input().rstrip().split()))
 
s = N
t = N+1
 
dinic = Dinic(N+2)
base = 0
for i, a in enumerate(A):
    if a > 0:
        base += a
        dinic.add_edge(i, t, a)
    else:
        dinic.add_edge(s, i, -a)
        for j in range(2*i+1, N, i+1):
            dinic.add_edge(i, j, INF)
 
c = dinic.flow(s, t)
print(base-c)

感想

制約からフローありえるかもとは思ったが、最大流についてばかり考えていて「流すのに自由度あって拘束条件反映できなくね？」となって方針を捨ててしまった。ふたつに割り振るのをカットとみなすのはなかなか面白い。今後役立つ知見かもしれないので記事にもしておいた。

フォルシアサマーインターン参加記

就活

フォルシア株式会社のサマーインターン(5日間)に参加してきました。 記録は残しておいた方がいいかな、ということでつらつら書きます。なんか長くなったので適宜読み飛ばしてください。

きっかけから参加まで

5月ごろからインターンは探していた。今年はコロナ情勢ということもあって、インターンできなかったら就活やばいんじゃねと軽くビビっていた。 でも夏は学会やら何やら忙しくて、数週間の開発！みたいなガッツリ系は結構厳し目な見込みだった。 やったことない言語で開発するのも、キャッチアップできなかったら怖いなあと思っていたので、ある程度自分のスキルセットに合致するというのも重視していた。

フォルシアのインターンはAtCoder Jobsで見つけた。コース概要を覗いてみると、何やら面白そうな感じ。5日間なら参加できそうだし。 主に開発系コースとデータサイエンス系のコースがあった。そういえばデータサイエンスとかってやったことないな。どんな感じなんだろ、と思ってとりあえず申し込みボタンをポチった。まあRustで開発できる自信がなかったというのもあるけど....

書類審査(プロフィールを見られたのかな？)後、面接があった。 面接した人が最終的にメンターさんなのだが、あまり面接という感じはしなくて、世間話をしてたら終わってしまった(え？)。 これは面接として機能しているんだろうかと疑問に思ったが、数週間後に合格の連絡がきた。

課題概要

簡単にいえば、(お客さんの)広告にかけるコストを最適化してくれ、ということだった。 広告にかけるコストを上げれば結果として売り上げは上がるが、売り上げが伸びたからといって広告に多額の費用を費やしていたら意味ないよね。 ということで、最適な広告コスト設定を考える、というのが課題だ。

広告はネット上のもので、現状のコスト、サイトへのクリック数、売り上げ、などなどのデータが与えられるのでそれらを眺めて色々考えてみてくださいね、という感じだった。手法はお任せしますということだった。

開催前にこの概要を聞いたときは結構楽観視していた。ただのパラメータ最適化問題に見える。影響を数式で表すことさえできれば、お得意の(？)探索を実装すればいいんじゃないか？という見込みだった。

〜業務編〜

まずは課題のこと中心でタラタラ書きます。適当に読み飛ばしてください。

初日

インターンは全日オフィスで行われた。 新宿というだけで結構ビビってしまうが、オフィスが駅の目の前にあってさらにたまげてしまった。 家の中の快適さに慣れてしまった半ニートには、少々刺激が強かったかもしれない。

集合時刻に集まった学生は自分を含めて3人だった。思ったより少ない。コースもうちょいあった気がしたが、別日程なのかな。 午前中は書類の手続きや自己紹介、注意事項の説明などの予定だった。 書類仕事の合間に、他のインターン生と少しずつ会話して仲を深めた。コースは別々だったので一緒に同じことをやるわけではないが、まあせっかくだし。なお全員東大生だった。やっぱ優秀な人が通ってくるということなのか、こええ...。

午前の最後にキックオフミーティングがあり、メンターさんやインターン運営チームの紹介があった。ここで「みなさんは○倍の倍率の選考をくぐり抜けてここにいるので、ぜひ頑張ってください！」といった趣旨のことを言われ、インターン生一同ビビる。 結構綿密にスケジュールが組まれており、ランチにどの社員さんが連れて行ってくれるかとかまで決まっていた。すげえ。 初日はメンター3人+インターン生3人でのお昼だった。「なんで申し込んだの」「普段何やってるの」とか色々話題になった。 なお昼食後、インターン生のうちの1人の正体に気づいてしまう。(長くなりそうなのであとで詳しく書く)

午後から作業に入る。 結果からいうと、初日はデータを眺めるので終わってしまった。 というのも、広告のコストと売り上げにはある程度相関があるものと思っていたが、実際に可視化してみるとどうもそうでもないっぽいことがわかったからである。 しかも想像していたのとは違って、単一の広告を運用するのではなく、運用するページが何個もあるような状態だった。 なのでパラメータが多数ある状態で、コストの割合を抑えつつ、全体としての売り上げを最大化しなくてはならなくなった。 相関があればなんらかの関数を設定してフィッティングし、その関数を元に解を探索すればいいんじゃないか、という自分の目論見は初日で崩れ去ることになった。

さらにいえば、データはエクセルファイルで渡されたのだが、これを使いこなすのもちょっと手間取った。pandasは触ったことはあったが、何も見ずにサラサラ書けるというわけではなかったので、時間がかかってしまった。この辺は開催前に確認しておいてもよかったな...。

あっという間に時間は過ぎ、初日の作業時間は終わった。あまり残業はして欲しくない主義だったようだ。作業は時間内で頑張って、時間になったらさっさと帰りましょうという感じだった。1日の終わりには夕会(その日やったことなどを軽く報告する会)があった。他のインターン生がやってることを知れたり、メンターさんからアドバイスをもらえたり、刺激になった。

初日は色々刺激が強かったのか本当に疲れてしまって、帰宅したらほぼすぐに寝てしまった。

2日目

眠かった。初日はノリでなんとかなった感あるが、先週まで10時起きだったのが8時起きになったので。でも二日目からは家からオフィスまでのルートが最適化された(電車の乗る位置とか)ので、予定より早く着くようになった。その分早く作業にとりかかれたのはよかった。 相変わらずデータを眺めていて、うんうん唸っていた。見かねたのか、メンターさんに「毎年そんなもんです」と励まされる。それでもうんうん唸っていると、前年のインターン生のとったアプローチとかを教えてくれた。前年の人もこんな感じで唸っていたが、最終的に得意の強化学習でなんとかしたらしい。そして、メンターさんから「もちろん最終ゴールは売り上げが最大化するような方法を考えることだけど、究極的には君が頭を使って考えることに意味があるんだ」という趣旨のことを言われる。

実際に運用する気持ちになってもう少し考えると、「現在うまくいってるものはコストをさらに費やし、うまくいってないものはコストを減らす」という当たり前の着想を得る。メンターさんも同じようなことを考えていたらしい。「ベイズ推定というのがキーワードですね」と言われてポカンとしてしまった。知らなかった。なのでこの日の残り時間はベイズ推定を勉強していた。

あんまりこれといった見通しも立たず、この日は割と落ち込んでいた。夕会で「まあそんなもんです」とまた励まされる。

3日目

3日目、寝て覚めたら謎の自信が湧いてきて、なんとでもなるという自信が出てきた。今後どう進めるかの流れを決めた。具体的には、

  1. コストから売り上げまでの影響を与える関数を決める
  2. 売り上げの変化をどのようにコスト設定にフィードバックするのか考える
  3. 決めたモデルに従って、実際のデータに対するコスト設定を見積もる
  4. 決めたコスト設定での運用をモデルに従ってシミュレーション

という風にすることにした。3,4はPythonで実装することにした。

ここまで決めると、ある程度見通しがたったためか安心感が生まれた。でも一方で残り3日でこんなにできるのか？という気持ちになった。

3日目はコスト設定見積もりのスクリプト実装までやった。ただ、 相変わらずpandasの扱いに慣れず、思ったより手間取った。クエリの取り方とか。これO(N2)になってね？とか気にし始めてごちゃごちゃやっていた。データ数は5000くらいだったのでO(N2)だと若干遅い。結局慣れてるPythonのdictに頼ってしまったが、本当はいいやり方あるんだろうな。。

データをデータフレームから一旦取り出すときは、クラスを使うようにした。実際これがあとでカラム追加したいときに役に立った。お、なんか開発人間っぽいぞ、と思う一方で、pandasに慣れていればいらない工夫なんだろうなあ、とも感じていた。

4日目

終わりが近い。かなり焦っていた。ちなみにここまでくると朝起きてからの行動も最適化されてきて、出社指定時刻の45分前には到着してしまっていた(は？)。

この日は残りの「シミュレータを組む」という作業をやることになった。 ただこれがまた大変な作業で、エクセルファイルに空欄があったりして例外処理めんどくせーと思ってるうちに4日目が終わろうとしていた。時間経つの早過ぎない？

一応この日のうちに一通り回せる程度まで完成はさせた。が、どうも挙動がおかしく、売り上げが元の60倍になるという結果が出てきた(は？)。 よく調べたらそもそも使うデータに欠陥があって、次の日にデータを変えようということになった。

夕会では他の人はかなり順調に作業を進めているということがわかり、自分の無力さをまざまざと感じてしまった。

最終日

最終日の夕方ごろから成果発表会があり、やったことを社員さんに発表する。その準備もあるため、実質的な作業はこの日の午前で終わりだった。

最終日ともなると出勤最適化もかなり洗練してきて、オフィスに集合の1時間前についてしまった。社員数人しかオフィスにいなかった。静かでちょっと心地よかった。

さて、昨日の不具合だが、データを変えてみたところ...それらしい結果は出てきた。が、「うまくいかないものを切る」の方が強く作用してしまったのか、売り上げは落ち込んでしまった。コストを上げたものに関しては売り上げは伸びて欲しかったのだが、どうも芳しくなかった。 モデルの関数を変えたりしてはみたが、あまり結果に影響はなかった。うんうん唸ってたら午前が終わってしまった。うーん、悔しい。

2時間クオリティでスライドを作ったのち、発表会で発表をした。結果は本当に微妙なものなので炎上したりしないか心配だったが、社員さんたちはすごく熱心に聞いてくださった。おかげで発表自体は滞りなく進めることができた。質問も別に責め立てるようなものでもなく、単純に興味があったからという感じだった。心の弱めな自分にはありがたかった。

発表会の後、懇親会を経て5日間のインターンは終了した。

〜イベント編〜

業務外であったこととかをつらつら書いていく。すごく手厚いおもてなしを受けていた。

こるとんさん

面白い方でした。

前提知識

  • 僕はこるとんさんと同じ学年(しかも確か理一時代は隣のクラス)で、競プロやる前から彼をTwitter上の有名人として知っていた(顔は知らない)

  • 競プロを始めてから彼が相当な実力者と知り、競プロ有名人の中では一番(密かに)応援している

  • 僕のアカウントは彼からフォロバされてない

正体判明まで

初日、出社すると同じくインターンに参加する学生(Aさん)がいたので話しかけた。彼がRust開発のコースと知った。

僕「Rustは結構普段からやられてるんですか？」

Aさん「いや、実はあまりやったことがなくて...」

ん？やったことないのに参加できるの？インターンって結構スキルマッチとか気にされるイメージだったけど、もしかしてこの人はとんでもなく優秀な人？

フォルシアといえば競プロ界隈では有名な方なので、もしかしたら競プロやってるかも？

僕「やっぱ競プロやってるんですか？」

Aさん「ええ、まあ...」

ん？なんか歯切れ悪いな...あんまり熱心にやってないか、隠したいかのどっちかなのかな。でもやってないならもう少し答えてくれそうだけど。実は競プロ強者？

もし有名人だとしたら誰だろう、と考えているとkort0nさんが思い浮かんだ。そういえば聞いた学部はkort0nさんと同じだし、同じ学年だし、最近Rust云々ってツイートしてたような...

ここまでで確信率40%。

初日の昼は、メンター3人+インターン生3人でランチした。このときに次のような会話がなされた。

メンターさん1「趣味はなんですか？」

僕「競技プログラミングをやってます」

メンターさん1「そうなのか、本当に競プロ人口増えてるね」

メンターさん2「Aさんなんかは、"高み"にいるよね」

Aさん「ええまあ...でも僕より強い人がこの会社にいることを知っているので」

また「ええまあ」かい。というかやっぱ"高み"にいる人なのか。「僕より強い人」というのはtempura_cppさんのことだろうけど、レートを知ってるメンターさんがわざわざ"高み"というからには、自分よりはレートが高い人間なんだろう。一応自分はレート黄色をアピールしてたので、てんぷらさんより低いとなるとAさんは橙相当なのか？ なんかどんどんkort0nさんに思えてくる...

ここまでで確信率80%。

昼食後、インターン生3人で休憩ルームにいく。どこかで「あなた、もしかして？」と言い出したかったが、その前にどこかから社員さんがAさんに親しげに話しかけてきた。

社員さん「よう」

Aさん「あ、お久しぶりです」

あれ？社内に知り合いいるんですか？もうこれは競プロの繋がりとしか思えなかった。DDCCとか聞こえたし、社員さんの方はてんぷらさんで確定。そして、てんぷらさんと親しげに話す、今までの情報に合致する人といえばもうこるとんさんしかいないだろ、と確信する。

僕「あの、正体分かっちゃったかもしれない」

こるとんさん「え！？」

ACだった。

メンターさん

自分の担当のメンターさんはなかなか個性的な方だった。というか色々と凄かった。 あんまり書くとアレなので詳細は省くが、「人生の成功者」感が凄すぎた。話も面白かった。

社員さんとランチ

これは一番すごいと思った。5日間のランチの予定が全てスケジュールされていた。近隣のお店に社員さんが連れて行ってくれて、昼食代は会社から出してくれた。 一緒にいく社員さんは毎回チェンジされ基本初対面だったが、すごく気を使ってくださり、楽しく食事できた。

話題としては、

  • メンターさんなど、社員の話
  • インターン課題の話(大体励ましてもらってた気が)
  • 大学の研究の話
  • 働き方の話
  • 会社の雰囲気の話

などなど、色々話した。楽しかった。

社長ランチ

3日目昼のスケジュールに「社長ランチ」が組み込まれていた。ベンチャーの社長と会うということで、まあ結構緊張していたが、出てきた焼肉弁当がめちゃ美味しかったので緊張は紛れた。 社長さんは実際に話してみると結構愉快な方だった。楽しくお話した。

前々から「質問を準備しておいた方がいいよ」と社員さんに言われていたが、業務に夢中で特に用意してなかった。 ちょっと余白ができたときに適当に「コロナ期間大変でしたか？」と聞くと色々答えてくれた。やっぱ利益を出す方向と社員を守る方向でバランスをとるのが大変だったみたい。まあ経営する側は大変なんでしょう。

食事会

3日目の夜にインターン生3人と社員さん2人で食事に行った。初日以来インターン同期とあまり話せていなかったので、いい機会をいただいた。

話題は否が応でもこるとんさんの話になる。この頃にはもう1人のインターン生(Bさん)も正体に気づいていたらしく、こるとんさんを「クソライターオブザイヤー様」と呼んでいた。

僕「Aさん(こるとんさん)のツイート拝見させてもらってますよ！二色下は...とか好きです笑」

こるとんさん「よく見てるなあ〜！笑」

社員さん「そのネタは何？笑」

こるとんさんがあれは誤解なんだというところまで説明すると、

Bさん「え！？あれってそういうことだったんですか？！」

どうやら誤解が解けたようだ。

その他にも大学の話とかメンターさんの話とか、結構いろんな話をした。この夜は楽しかった。業務の方の進捗が微妙だったなだけに余計に。 この夜に、こるとんさんにフォロバしてもらった。

バーチャルコンテスト

4日目の夜、バーチャルコンテストのお誘いを受けたので参加した。

いつものパソコンじゃないのでスニペットがなかったりデバッグ環境がなかったりしたのでガチで参加はできなさそうだったが、まあ楽しむつもりで。 4問で最後が青diffということで、時間内にはできるでしょ。

f:id:wattaihei1234:20200907204418p:plain

あれ？なんか勝ってしまった。どうやらこるとんさんは誤読してしまったらしい。二色下でも、勝てる！

発表会後

ちょっと自由時間があったので、インターン生3人で競プロの話をした。

僕「どうやったら強くなれますか？」

こるとんさん「問題を解きましょう」

はい.............

懇親会

最終日の夜、懇親会があった。もはや何を話していたとかはよく覚えていないが、インターンの振り返りとかをしていたのかな。 コロナ対策ということで、5人くらいのグループに分かれた。なのでここではあまりインターン同期と話せなかったけど、まあしょうがないか。 初めて話す社員さんもいたが、楽しくお話できた。

その他感想

  • 優秀な社員さんが多いせいか、ベンチャーなのにかなり落ち着いているな、という印象を受けた。この前にベンチャーのインターンに行っていたので余計にそう感じた。
  • とにかく段取りがしっかり組まれていた。ランチだけでなく、初日の行動や席配置まで非常に綿密に計画されたものだと思う。「仕事できる人」が企画した感じだった。運営チームさんありがとう。
  • 社員さんがみんな優しかった。とても居心地がよかった。
  • 実際に出社できてよかった。やっぱ会社の雰囲気とかは実際に働いている現場を見ないとなんともいえないし。こるとんさん含めいろんな人と話せたのが一番の収穫かもしれない。
  • 競プロはやはり１つの文化として定着しているようだった。バチャコン後に感想戦もやった。楽しかった。

とにかくすごいおもてなしを受けました。ありがとうございました。

からくり株式会社3daysインターン参加記

就活

インターンに参加したので記憶にあるうちにまとめておく。

背景ときっかけ

4月からアルバイトがリモートになってしまい、社員の人と話す機会が極端に減ってしまった。 不安症なので就活イベントにときどき参加して、自分の立ち位置を測っていた。 色々企業の人と話すと、自分はポテンシャルがあって即戦力レベルの実力も持ってるみたいに気持ち悪いくらい持ち上げられた。 その一方で、目指すものをもう少し定めた方がいいねとも言われることが多かった。 というのも自分はとにかく色々なものに手を出していて、これ作れるのかオモシレー、この言語身に付けてみたい、といった具合に特に明確な目的なくプログラミング学習してきた。ポートフォリオも一貫性がなく、何をしたいのかよくわからない人間に見えているのだと思う。 本心としては競プロが一番やりたいことなのだが、もちろん純粋な競プロが仕事になるはずがなく(ただのネトゲである)、競プロとは別に仕事としてやりたいことを見つける必要があると感じていた。

そういうわけで、夏季インターンでは自分の視野が広がることを期待していた。が、いざ申し込むとなるとESとか面接とか色々と面倒で(オイ)、結局申し込んだのは4つになった。そのうち1つは選考中に中止が決定、1つは断られ、残り2つは選考が通ったが1つは日程が合わなさそうなので断った。最初はインターン1つでもいいかと思っていたが、夏は長いのに1つだけはもったいないと少し欲が出てきた。

もう適当なものでもいいからなんかないかな、と思ってたらサポーターズから招待がきた。これがからくりインターンだった。どこだそこ、と思ったが3日間のハッカソン形式ということで気軽に参加できそうと思った。開催1週間前に招待するってなかなかやなと思ったが、とりあえず申し込んでみた。結果、参加することになってしまった。

本番まで

内容はSwift+XCodeでiOSアプリの開発をすることであった。自分はSwiftは１ヶ月くらいで簡単なアプリを作っただけで、てんでトーシロなのだが、開発内容的にはまあなんとかなりそうレベルであった。事前課題があり、本番までの数日間でデモアプリを一通り動かせるようになるレベルを要求された。サンプルが用意されていたので、基本はこれを参考にして進めた。XCodeをいじるのは久々だったのでかなりググりながら(StoryBoard周りは本当に忘れてしまう)だったが、基本を確認できたと思う。というかSwiftLintの(XCodeの方なのか？わからん)自動補完が優秀すぎて、コード書くのはほぼ何も考えなくてもできた。"やることで実力がつく"と謳われた任意課題もあったが、研究の方のタスクが重くなっていたので適当なところでやめてしまった。

本番

一日目

オフィスは浜松町にあった。この数日間はとても暑く、外に出るだけで地獄だった。 出社して自己紹介フェーズに入る。参加者は5人だった。無給なのにわざわざ地方からきた人もいて、結構驚いた。レベル感は様々で、Swift職人みたいな人もいればまだ初めて間もないという人もいた。 会社の説明や課題の説明、グループ分けが行われたのち、昼食を挟んで開発が始まった。 個人的にはここでもう少し事前課題のフィードバックが欲しいと思った。グループはGitHubの利用経験と事前課題の提出内容で2つに分けられた。自分は3人チームに振り分けられた。

自分以外の2人がGitHubほぼ初心者で、必然的に自分がコード管理リーダーみたいな立ち位置になってしまった。いや別に自分も全然詳しくないのだけれど、他の2人がbranchを切るって何？くらいの感じだったので。

まずチームで作るものの設計を相談した。サンプルを参考に好きな機能を付けてみて、という雑な振り方をされたので何をつけようか話し合った。といってもアプリの大枠はAPIを利用したもので、APIの制限上大した機能は付けられなさそうに思えた。あと三日間という短期間でできそうなことは思ったより少なそうであった。作るのものの優先順位をつける必要性を意識せざるをえなかった。また、3人で開発するに当たってどう役割分担するかも大事であった。経験やレベル感を考慮し、基本的には1画面ごとに1人が担当する形になった。

初日は役割分担までやって、GitHubの基本的な使い方を確認したところで時間になった。帰ったら少しは開発を進めようかと思ったが、色々な人と話して疲れたので寝てしまった。

二日目

二日目に入る。書き忘れていたが、開発には自前のパソコンを使うように言われていた。自分のMacBook Airは2014年モデルで、メモリ4GBのストレージ128GBと、もうひと昔前のスペックだったため、XCodeでのビルドとかめっちゃ時間がかかるのである。競プロにはPCスペックはほぼいらないためこれでもいいかwと思っていたが、この数日間の開発でとても気になるようになった。他の2人のMacBook Proが一瞬でビルドが終わる様子を見るととてもうらやましかった。この時点で自分のPCスペックがグループ内でネタとして？確立した。

三日間という短い時間で完成させるにはやはり作業効率を少しでもあげる必要がある。自分はときどき他の2人の様子をみて、なるべく疑問点や詰まったところをグループで共有するように促した。ここで感じたのが、なるべく相談の敷居を下げるようにした方が話題を発しやすいということである。1人で開発するのが長いと、どうしても人に質問するより前に自分で解決できないか考えたくなる。わかる。この姿勢自体は褒められるものであるが、期間が差し迫っている場合はなるべく早期の解決を求められるため、疑問点などはどんどんグループ内で共有すべきなのである。この心理的障壁を少しでも下げるために必要なのは人間関係的な問題が大きいと思い、コミュニケーションが苦手な自分だがなるべくチームメイトと話題を作って信頼関係を築くのに努めた。これも立派なリーダーの仕事になりうるな、と感じた。

メンバーの完成したコードをマージするのは自分の役割だった。ここで苦労したのが、XCodeの表示に使われるprojectファイルが、ファイルを追加するたびに書き換わってしまう点である。projectファイルの中身はたとえば

     082CF76924D5B245001F7680 /* Client */ = {
            isa = PBXGroup;
            children = (
                082CF76A24D5D526001F7680 /* APIClient.swift */,
                0841933824D950FF00BFCBD3 /* ErrorType.swift */,
                0841933624D9505800BFCBD3 /* Logger.swift */,
            );
            path = Client;
            sourceTree = "<group>";
        };

といったような感じで、正直人間が読むものに思えなかった。だがプロジェクトにファイルを追加すればコンフリクトが起こってしまい、しかもファイル内容をうまく定めなければXCodeにスクリプトなどが表示されなくなってしまう(何回か失敗してローカルプロジェクトを作り直した&作り直してもらうことになった)。プロジェクトファイルの内容は膨大で、マージにとても時間がかかった。後で社員さんに聞いたら「そこは慣れですね」と言われてしまった...

肝心のコードの方は、この人のこの実装ができないと進まない！といった状態になって思うように進まなかった。まあマージ作業で忙しかったのでどっちにしろ進まなかったと思うが。 この「〇〇ができないと▲▲ができない！」という状態になることは多く、たとえば画面間遷移をすり合わせるのは大変だった。結局遷移の関係ないところだけメンバーに実装してもらって、遷移に関しては自分が実装する形になった。終わった後で気づいたがこれはむしろ逆の方がよかった。先に画面遷移部を実装してしまい、画面の詳細を分担した方が効率よく作業できたと思う。反省。

二日目の終わりになってもメインの機能はまだ完成しておらず、さすがにヤバイと思った。家でもちょっと作業することにした。 全然関係ないが、ここで研究室の方から(タスクに関するきつめの内容の)メールがあり、帰った後かなりメンタル的に落ち込んでいた。この日は寝たのは3時半くらいだった。

最終日

最終日に簡単な発表とフィードバックがある。メインの機能は開発終了時間の1時間前くらいにようやく形になった。ここまでにさらに色々トラブルがあったのだが、ちょっと焦りすぎていてよく覚えていない。本当にこれ完成するのかと思っていたが、形になったときは結構安堵した。 残り1時間で細かいデザインなどを修正し、開発は終わった。ただ時間になっても修正案件は山のようにあり、発表までの空き時間(社員さんがコードを読んだりしてたと思うが、長かった)にも修正を続けた。最終日になるとメンバーもGit操作に慣れてきたようで、色々使いこなせるようになったようである。よかった。

その後自分らの作成品を簡単に発表し、社員さんから機能面/コード面の両方でフィードバックを受けた。自分らのチームへの指摘としては、

  • 時間がないときはライブラリに頼るというのも賢明な選択(ライブラリが使える状況にあるならなるべく使った方がいいというのはそうだろとも思ったが)。
  • 処理は関数/クラスにこまめに分ける。たとえばUIViewControllerにいくつも処理をベタ書きすると読み取りにくくなる。
  • チーム開発ではなるべく無駄な実装をしない。混乱の元になるのでコードは必要最低限に。
  • UIは使う人にわかりやすく。ボタンを押すだけの一ステップが心理的障壁になってしまう場合がある。

という感じだったろうか。まあどれも言われれば基本的なことなのだが、開発に夢中になってると疎かになりがちな点である。どうしても「動けばOK!」という気持ちになりがちだが、この辺に気を配りながら実装できるのがプロなんだろうなあ。 ちなみにもう片方のチームは自分らの機能に加えて色々やっていたようで、発表で完成度の差をまざまざと感じさせられた。まあ向こうはSwift職人がいたみたいだし、二日目の夜は2人とも帰ってから熱心に開発してたみたいだし(言い訳)。。

発表が終わって、懇親会が始まった。色々話をした。社員さんたちの仲は良く、働くのが心底楽しいという感じだった。新卒3年以内の人が多く、年齢層はかなり若めだった。フレッシュだなあという印象を受けた。 少し時間が経つと、なんと社長さんまでやってきた。ベンチャーを経営しているだけあって、身にまとうオーラが常人とは異なっていた。今回のインターンの開催経緯などを話してくれた。そして逆に、学生側に色々(「なんで申し込んだの？」とか)質問もしてきた。半分面接みたいだな、と苦笑いしながらも楽しくお話しできたと思う。

結構長いことお話をして、3daysインターンは終了した。

感想

企業の印象

社員さんは全体的に若く、「まだまだこれから」という雰囲気をビンビンに感じた。プライベートでの付き合いも多そうで、まるで大学のサークルみたいな雰囲気(想像)だった。ただ逆に、会社外の人との繋がりがあるようにはあまり感じなかった。良くも悪くも閉じている、という印象を受けた。人間関係でトラブルがあったりしたらつらくなりそう。

働き熱心なのは思った通りで、残業とかも苦なくやっているようである。それだけ楽しいということなのかもしれないが、体力のある若者が多いからというのも大きそうである。

チーム開発

バイトではプロダクトのほんの一部しか関われていないため、ここまで本格的にチーム開発をしたのは初めてだった。特にリーダー的な立場にいたので、気づくことは多かった。仕事の振り方や分担方法には結構悩んだ。めんどそうなところは自分がやってしまったが、本当はここもチームで知識を共有すべきだったのだと思う。かつてバイトで仕様書を読んで、処理内容どころか細かく変数名などまで定めてあったのを見たとき、「は？ここまで細かく決まってんならこれ書いた人が実装すれば良くない？？」と感じたことがあった。が、このように「全体に齟齬ないように仕様を定める」というのはプログラミングとはまた違った判断力が要求される、立派な仕事になりうることを理解した。そういう意味で視野を広げることはできたと思う。

あとはすでに書いたが、チーム内でのコミュニケーションをとるのも大事だと感じた。情報を共有しやすくするため、仲間との信頼関係をしっかり築くのも生産性を上げる上で重要な要素だと感じた。こういうのは経営者の仕事かと思っていたが、現場の雰囲気を作り出すのはやはり現場の人間なので、自分の世界に入りすぎないでいることが大事だ。ただテレワークになるとまた事情は変わってきそうな気もするが。。

技術的な話

うーん。実は今回あまりコードを書いていない気がする。でもXCodeが優秀なので、Swiftを書くこと自体にはあまり苦労しなかった気がする。Web系ほどゴリゴリに実装する能力が求められる感じではなかった。実力を伸ばすなら色々作って経験を積むしかないとも言われた。もう少し何かやろうかな。。

就活生と話してみて

向上心があるというか、キャリア意識が強い人が多いと感じた。普段いる研究室(そもそもあまり行ってないが)やTwitterでの競プロ界隈には、将来のことは二の次で今楽しいと思うことをやるという人が多い。自分もその考えに染まっていることをまざまざと感じさせられた。そういう意味ではかなり刺激になった。

全体として

いい経験になったと思う。

ARC074-E RGB Sequence

競プロ

問題

E - RGB Sequence

\(N\)要素の列があって、それぞれRGBで塗り分ける。 \(M\)個の束縛条件があって、各条件は区間中の色の種類数を指定する。

気持ち

O(N3) まで許す制約と、条件で束縛される数え上げという見た目から、DP臭がムンムンする。 では何を状態と見るかということが問題になる。

条件\(l,r,x\)を読んだときの判定はループが\( r \)に到達したときに考慮するのが良さそう。 3色しかないので、各色について1つずつ状態を持たせられそうである。 もっと言えば、各色について最後に使ったindexを状態として持っておけば、何色使ったかを判定することはできる。 この条件をちゃんと満たすものだけ遷移させるようにすればOK。

ACコード

Submission #15580318 - AtCoder Regular Contest 074

import sys
input = sys.stdin.readline

mod = 10**9+7

# (i, j, k+1)に置くのが、条件(l,x)に適しているか
def check(i, j, l, x):
    return (x == 3 and l <= i) or (x == 2 and i < l <= j) or (x == 1 and j < l)


N, M = map(int, input().split())
LRX = [list(map(int, input().split())) for _ in range(M)]

LX = [[] for _ in range(N+2)]
for l, r, x in LRX:
    LX[r].append((l, x))

dp = [[[0]*(j+1) for j in range(i+1)] for i in range(N+2)]
# dp[i][j][k] (k <= j <= i) 
# 三色それぞれ、最後に使ったindex(1-indexed)がi,j,k

dp[0][0][0] = 1

for i in range(N+1):
    for j in range(i, N+1):
        for k in range(j, N+1):
            
            # 一番前の色を置く
            ok = True
            for l, x in LX[k+1]:
                if not check(j, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][j] = (dp[k+1][k][j] + dp[k][j][i]) % mod
            
            # 最後
            ok = True
            for l, x in LX[k+1]:
                if not check(i, j, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][j][i] = (dp[k+1][j][i] + dp[k][j][i]) % mod
            
            # 二番目
            ok = True
            for l, x in LX[k+1]:
                if not check(i, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][i] = (dp[k+1][k][i] + dp[k][j][i]) % mod
        

ans = 0
for a in range(N+1):
    for b in range(a,N+1):
        ans = (ans + dp[N][b][a]) % mod

print(ans)

感想

DPではありそうとは思ったが、「最後に使ったind」を状態にするのは思いつかなかった。 そしてそれを理解した上でもバグらせまくるという、、

AtCoder黄色になりました

競プロ

5/3のABCで黄色になりました！

 

f:id:wattaihei1234:20200504105333p:plain

 

まだもうちょいかかるかな〜と思ってたのですが、サクサク上がってしまって自分でも驚いてます...

適当にやったこと、思ったことを書きます。適当です。

 

 

 

精進について

 

f:id:wattaihei1234:20200504111839p:plain

f:id:wattaihei1234:20200504111858p:plain

 

 水〜青初期までは青Difを毎日一問解くということをやっていました。青になってからはしばらくは黄Difでも同じことを続けていましたが、なんか気が抜けてしまって、うっかりしてたらStreakを切ってしまいました(は？)。

 Streakが切れてからはAtCoderはほとんど触ってないです。代わりに、Codeforcesのvirtual contestをほぼ1日1回のペースでやってます。これは結構効果的だったと思っています。バイトなどで疲れた日でも、とりあえず[Registration for virtual participation]のボタンを押して解き始めれば、(最初の方の問題は簡単なので)勝手に競プロモードになれます。

 2時間終わって解けなかったものは解説見てました。ちょっと抵抗あったんですが、まあCodeforcesだし。それに時間内に解けないということは本番のコンテスト中にも解けないでしょうから...大抵しょうもないミスであることが判明するんですが

 

 

 

アルゴリズムについて

 正直、青になってから新しく学んだアルゴリズムってほとんどないです。一応アリ本には一通り目を通しましたが、使ってない知識はたくさんあります。これはABCの理念(たぶん)が知識より思考力を重視してるからだと思います。ABCに出るだけなら、フローとか知らなくてもそんなに困らないし。ちなみに自分はセグ木すら書いたことないです...(BITでなんとかなった)

 持ってるライブラリだけ紹介しておきます。

  •  BIT ... ARCとかでは出番多かった印象。座標圧縮+BIT上二分探索でstd::setの代用みたいなものも用意してました。
  • セグ木 ... 一回TLEしてから触ってない
  • UnionFind ... はい
  • SparseTable ... Codeforcesやってたら欲しくなった。
  • 桁DP ... ソラで書くの厳しい
  • 最大二部マッチング ... 使ったことなし
  • 幾何 ... ABC-Fで幾何が流行ったときに作った
  • ダイクストラ ... よく使うので。たぶんソラで書けるけど一応。
  • LCA ... ずっとダブリングにしてたけど、最近EulerTour + SparseTable に切り替えました
  • エラトステネスの篩、素因数分解 ... はい
  • RollingHash ... 文字列問題ではときどき出番があった
  • Z-Algorithm ... 出たから作ったけど出番が。

 

うーん、こうしてみるとあんまり整備しきれてないですね。

 

 

 

黄色になれた要因

 上をみると限界精進してる訳でもないし知識がある訳でもないしなんだこいつって思いますよね。私もそう思います。

 じゃあ自分に何の強みがあるかと考えると、「苦手分野を減らした」って点が大きいかなと思います。レートが上がると天狗になりがちですが、たまたま自分の得意な分野だったとか、直近に類題を解いてたとかで上がっただけってことは十分あります。それで次に苦手分野が出て解けない...となってはもったいないです。出てきた問題に１つ１つ謙虚に向き合うのが良いです。

 あと青になってから意識し始めたこととして、「数式に落とす」ということがあります。頭が整理できないときこそなんとか数式に片付けられないかと考えるようになりました。数え上げとかは特にこれかなと思います。

 

 

 

Pythonで競プロをやることについて

 twitterで目にするプロフィールにPythonと書く人も増えてきて、もう一大勢力と言っていいくらいなのではないかと思います。

 C++と比較して実行速度が遅いという点からちょっと煙たがられることもあるようです。でもちゃんとメリットはあると思っていて、

  • コーディング量が少ない
  • long long とか気にしなくていい

など。言語アップデートも来たし、もはや「Pythonだから〜」とか言ってられないくらい強い言語になってるんじゃないかというのが個人的な感想です。

 そもそも実行速度が厳しくて解けない、というケースは(AtCoderでは)あんまり遭遇したことないです。AtCoder側もPythonを蔑ろにしないような努力をされてると感じますし、大抵は自分の思考が足りないかおかしな実装をしてるという場合がほとんどです。謙虚にいきましょう。

 

 

 

メンタル的な話

 当然なのですが、レートが上がれば嬉しいしレートが下がれば悲しいです。でもあまりレートにこだわりすぎるのはよくないな、と最近気付きました。実力がつけば自ずとレートは上がるのですから。「レートを上げる」というよりは、「自分の適性にレートを収束させる」くらいの気持ちでいようと心がけました。ここは強気なんかい

  この「自分の適性」を上に設定すると行動がちょっとずつ変わると思います。「自分は本来黄色だからこれくらいの問題は瞬殺できるはず」「難しそうだけど黄色の実力あるし解けるだろう」などと。一種の自己暗示みたいですね。。

 

 

 

 

 

達成した感想と今後について

 いやあ、嬉しいです。一年前HelloWorldしてたころを思うと、すごく登ってきたなーと感無量です。始めたときは水色は頑張ればなれそうで青はワンチャン？くらいに思っていて、黄色とか雲の上の存在でした。人間やればできるんだなあ。ABCも卒業したし、もうビギナー卒業と言ってもいいのでは？

 この上は橙ですか。でもratedの回数が激減するので、これまでの色変とは難易度が明確に違うと思っています。橙からは本当に天才しかなれない領域だなーというのが今の印象です。それにほぼABC速解きだけで手に入れたレートなので、ARC,AGCで戦える気がしない...

 今後競プロ以外にも力を入れていきたいので、競プロはまあコンテストには出るかーくらいの心持ちでいようと思います。(こう言っとかないと気付いたら競プロやってるしヤバイ)

 

 

 

 

以上です。