FORCIA Summer Internship 2018 参加記

フォルシア株式会社インターンに参加しました。記憶があまりないので想像で補って書きます。言えないこともあるのでさらに曖昧な文章になります。まずいと指摘された場所はどんどん消えていくので今が1番情報量が多いです。文章力もないのでNoiminさんのブログ(http://noimin.hatenablog.com/entry/2018/09/18/233705)をパクることにしました。会社名にはリンクを飛ばすといいということを学びました(賢い)。彼女のほうが僕より1週間後のタームのはずなんですけどね。時系列壊れる。

 

-40日

 今は数学科の院生をやってるんですけど、修士を出たら就職しようと思っているので流石に何もしないのもなぁと思っていたらAtCoderJobsに面白そうなインターンを見つけたので投げました。Jobsに求人を出してくださるとターゲットが明確に自分に向いてる感じがあって超応募しやすいんですよね。AtCoderさんありがとうございます(このブログでは多方面に媚を売っていこうと思います)。

 有給なのも大きくて、これは給料がいただけるからというよりは、お金出してまでインターン生を募るならがっつりと経験を積ませていただけるんじゃないかっていう。

 

-35〜-20日

 応募したはいいんですけど、書類選考ってだいたい研究内容とか実績とか書かないといけないわけで、ここで詰みました。なんちゃって数学科なので大した研究をまだ開始できていないうえに書いたところでインターンの内容とかすりもしないし、プログラミングを始めたのも今年に入ってからなのでろくな実績があるはずもなく。ほげもちと相談した結果「黄色なんで地頭は悪くないと思います」をそれっぽい感じの文章にして出しました。これで通ったら面白いなって言ってたら通りました。面白かったです。Rust検索エンジン開発コースに決まりました。

 

0日目

 前泊しました。前泊の宿泊料は負担しないよって言ってくださったんですが給料いただける時点でプラスじゃんという雑勘定をしました。場所は安心お宿新橋汐留

https://www.anshin-oyado.jp/shiodome/にしたんですがすごくオススメです。大浴場が24時間使えるだけで優勝なんですがホテルにあって欲しいものは大きなベッドを除いて全部あります。あと晩ごはんはてんぷらを食べました。もぐもぐ。前日だしRustでセグ木くらい書いてから寝ようと思ったら寝れなくなりました。なんとセグ木を空で書けなかった。

そろそろちゃんとしたインターンのブログに切り替えます。

 

1日目

 朝適当に来た電車に乗ったら逆向きでした。あとはいい1日だったと思います。お昼ご飯はカルビを食べました。この日は与えられた課題(あとで詳しく書きます)のコードを読んで、コードを読めば誰でも書けるようなものを書いたりしてたら終わりました。

 

2日目

 僕の課題は雑にいうと作りかけのアプリに新しい検索クエリを実装することでした。と言ってもすでに社員さんが書いていたアルゴをいい感じに組み込めばよかったんですが、1から書こうとして破滅をしたりしていました。この日のお昼ご飯はケバブでした。

3日目

 今回扱うデータベースに対してはいい感じに動くものが実装できたので、他のアプリでも使えるように汎用化した作りにしようとしました。汎用化しようと思うといろんなケースが想定されたり、今回実装したクエリが他のクエリとかなり異なっていたりで考えなきゃいけないことが多くて、開発してる感がありました。slackのステータスをてんぷらにしていたらてんぷら屋さんに連れて行っていただくことになって、自ら志願して共喰いをするサイコパスになってしまいました。

4日目

 昨日からの作業が昼頃に一応片付いたのでアルゴリズム早くならんかなぁみたいなことを考え始めました。とはいえ最終発表まで全然時間がなかったのですぐに改善しそうな定数倍だけいじることにしてガチャガチャやってました。僕は基本的に2/3から3/4くらいにして満足してたんですがなんか次のタームの人が爆速にしたらしくてすごい。この日のお昼ご飯は海鮮丼でした。いいものの食べ過ぎで胃が東京に染まりそうだったので晩ごはんでは博多ラーメンににんにくを多めに入れて中和しました。

5日目

 お昼ご飯は社内の競プロerさんたちとピザを食べました。競プロerさんとのお食事ということで当然アイドルトークで盛り上がりました。最終発表があったのですが僕以外の3人はアレクサで面白そうなアプリを提案していたり特徴語を抜き出してデータ分析していたりですごくて圧倒されました。しょうがないのでインターン参加者唯一の関西人らしく適当にボケをはさんでごまかしました。それなりにウケてよかったです。懇親会ではメンターさんとナブラ演算子ゲームをしました。あれはたぶんシラフでやるゲームではないんですが酔っててもできないのでどういう時にやるのが適切なのか謎です。

何も考えていなかったら宿を取っていなかったので安心お宿に電話してみたら余裕でした。神か。

6日目

 東京住みの友達とダラダラしてから大阪に帰ってABCに出たら社員さんのAtCoderアカウントが特定できました。

 

8日目

 人事の方からマイナンバーカードを忘れて帰ってるよと連絡がありました。ごめんなさい。

 

16日目

 無事受け取りました。

 

まとめ

 分からないことだらけで反省すべきところも多々ありますが、その中で(今後ちゃんと勉強することを仮定すれば)社会に出てもなんとかやっていけそうな自信も得られたので良かったと思います。あと社内の雰囲気がすごく肌に合っていたので勤めたい企業像も具体的になりました。

 あととにかく競技プログラミング(とバイト先の塾のVBA)でしかプログラミングをしたことがないという状態から脱出できてよかったです。結局アルゴリズムまで踏み込みきれなくて実装中心になってしまいましたが、むしろ僕にはちょうどいい課題だったように思います。社員さんからも直接ポテンシャル採用だと言われましたが、ほんとによく採ってくださったと思います。選んでくださった社員さんや、迷惑をかけ続けたメンターさんには(申し訳なさと)感謝しかありません。

 後悔としては(Noiminさんと丸かぶりするけど)メンターさんたちにもっと厚かましく色々聞きにいけばよかったというのと、他のインターン生徒との交流ですね。たぶんアレクサの人は僕と交わした口数よりアレクサに話しかけた回数のほうが多いと思う(それはそう)。

 なんか最後に感動的な文章を書きたかったんですが不可能なので終わります。あとフォルシアさんの魅力も全然書けてない気がするのでインターンがこれからの人たちはぜひ実際に参加して直接みてもらったほうがいいんじゃないかなぁと思います。その際はてんぷらが行けって言ってたって言ってください。たぶんてんぷら屋さんに連れて行ってもらえると思います。

f:id:tempura0224:20180919025717j:plain


PCK2017 予選11 ネットワークの課金システム

自分のブログの存在を完全に忘れていた(おいおい)。問題を解きました。

Charging System for Network | Aizu Online Judge

 

問題概要

頂点数Nの木(各辺s-t はコストc[s,t]を持つ)と整数Kが与えられる。以下のクエリをQ回処理する。

  • send : 2頂点u-v間のパスのコストの総和を答える。ただしコストがKの倍数である辺は0として計算する。
  • add : 頂点uから伸びているすべての辺のコストをd増やす。

制約は 1<=N,K,Q<=10^5

解法

明らかに「Kの倍数は0とする」の部分が厄介です。

addクエリは頂点に足された値を記録しておけば(これをa[u]などと書きます)辺u-vのコストは c[u,v]+a[u]+a[v] と計算できるが、sendクエリで普通に辺を1つずつ見ていくとO(N)かかってしまってダメ。

「Kの倍数は0とする」の操作をaddに押し付けることができればsendはオイラーツアーなりなんなりで高速に答えられるようになるけど、今度はaddで頂点の周りの辺をすべて見ないといけないのでO(N)かかってしまう。

 

八方塞がりに思えるのですが、ここでHL分解の以下の性質を思い出します。

(HL分解そのものについては書かないです、ごめんなさい(僕はこの方の記事で勉強しましたHeavy-Light Decomposition - beet's soil))

  • 各頂点についてそこから出るHeavy edgeは高々2本 
  • 各パスについて、通るLight EdgeはO(logN)本

 

するとこのような折衷案が思いつきます。

  • addクエリでは、頂点に足された値を記録した後、Heavy Edgeの値を更新する。
  • sendクエリでは、Heavy Edge は更新されているのでそのまま利用して、Light edge については1つずつ計算する。

 

上記の性質により、addクエリでは2箇所、sendクエリではO(logN)箇所しか計算をしないので高速に行うことができます。求めたいものは区間和なのでセグメントツリーを用いることで、addクエリをO(logN)、sendクエリをO((logN)^2)で処理でき、全体計算量は最初の入力等も含めてO(NlogN+Q(logN)^2)となり無事解くことができました。

 

実装↓ (雑然としているのでアです)

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3100945

 

 

 

ICPC2018 国内予選 参加記

ICPCお疲れ様でした。先に結果だけ書いちゃうとABCDの4完で30位でしたが学内順位の問題でアジアには行けませんでした。

以下軽い振り返りです。

メンバー

  • tempura0224 ぼく。ABとDorEを担当する予定だった。
  • zunda1st BCあたり担当。
  • chocorusk EorD,特に数学担当。

全員数学科で競技プログラミング経験は3人合わせて15ヶ月。

コンテスト

とりあえず予定通りぼくがAを開いて解く。

流石にすぐにできてBを見たらできそうだったからそのままやる。適当にやりすぎて1WA(悲しい)。

Cの進捗をzundaに聞くと微妙っぽかったので一緒に考えるとなんか解ける。適当に実装したら今度はちゃんと通る。

chocoruskがDは全探索でいけるというので全探索を書く。ぼく中心で実装したけどミスりまくって横から指摘されまくる。これ最初からぼくが実装しないほうがよかったのでは。いざ書き上がると一発で通る。

chocoruskたちにEを任せてFGを考える。これが完全に判断ミス(幾何も構文解析もろくにできないのになんで行ってしまったのか)。

トイレに行ったり教室内を走り回ったりしてるとEの解法が生えたので書いてみる。サンプルが全然合わなくて泣く。場合分けと評価の順番をミスりまくっていると教えてもらったので直す。サンプルが最後以外通って「浮動小数点例外」って怒られる。ナニコレ。何が違うのかわからないままコンテスト終了。

 

反省と感想

これの読者は大体わかると思うんですけど浮動小数点例外は0除算でした。エラーコード136とか言ってくれたらわかったのにっていうのは流石に言い訳でこれに気付けないのは本当にひどい。

弊大学は無駄にハイレベルで5完高速じゃないとダメだったらしいので完敗。

とはいえBのWAがなくてDの実装をchocoruskに任せてその間にEを詰めるとかしてれば無理じゃなかったような気もするので悔しい。まぁ0除算に気付けなかったので完全に論外なんですが。

 

ぼくは早生まれな関係で来年も出場資格があるらしいので実装力(とタイピング)を鍛えて来年こそはアジア行きたいですね。組んでくれる人見つかるといいな。

ARC094 F Normalization

 はい。ARC094のF問題(F - Normalization)の解法です。解説(aを0、bを1、cを2だと思うと和のmod3が保たれるとかいうやつ)がド天才だったのですが、もう少し思いつけるかもしれない解法でACしたので投稿します。

 といっても結局mod3を見ることにはなってしまうのでそこに至るまでのステップも書いていこうかと思います。

解法

 まず、操作後の文字列はどこかに同じ文字が連続する部分があるということはすぐに分かるのですが、それだけでは条件が足りなさそうです。また、操作の順番によってできる文字列が変わる(というか操作の順番を変えるとそもそも操作ができなくなることもある)ので左から順番に操作するorしないでDPといったことも出来なさそうです。ということで別の方向で考えてみましょう。

 数列や文字列に対して何らかの操作を施すタイプの問題では、

操作の前後で変化しないものに着目する
という方法が有効なことがあります。また、今回のように操作が3種類ある場合すべての操作に対して共通してなりたつものを見つけるとよいです。具体的に今回の問題の操作での個数の変化を見てみましょう。
  1. ab→cc   a:-1、b:-1、c:+2
  2. bc→aa   a:+2、b:-1、c:-1
  3. ca→bb   a:-1、b:+2、c:-1

「2増える」「1減る」という操作を同一視したいなぁという気持ちになりますね(なって。)。この時点でmod3に気づく人もいるかもしれませんが、さらにこれもよくある手法として、「個数の差(和)はわりといい性質を持ちがち」というのがあります。ということで各操作でのaの個数とb,cの個数の差の変化を見てみましょう。

  1. ab→cc   a:-1、b:-1、c:+2  b-a:±0、c-a:+3
  2. bc→aa   a:+2、b:-1、c:-1  b-a:-3、c-a:-3
  3. ca→bb   a:-1、b:+2、c:-1  b-a:+3、c-a:±0

 「aとbの差」「aとcの差」は操作の前後で「3増える」「変わらない」「3減る」のいずれかです。もうわかりますね。操作の前後で「aとbの差」「aとcの差」を3で割った余りは変化しないということです。なるほどここで3で割った余りがでてくるのか、という感じですね。3で割った余りがカギになることに気が付いてさらに考察を進めると解説の方針になるのかなぁ。

 とはいえこれで操作後の文字列に対する重要な性質がわかりました。

  1. どこかに 連続している部分がある

  2. 「aとbの差」「aとcの差」を3でわった余りは最初の文字列と同じ。

この性質をみたす文字列は本当に全部つくれるのかという問題はあるのですが、実は|S|≠3のときはできるらしいです。(証明は帰納法でできるらしい。解説に書いてた。)ということで|S|=3のときだけ全探索することにして、他は上の条件をみたすようなものを数えるためのDPをします。

 具体的には、dp[文字数][最後の文字][(b-a)を3で割った余り][(c-a)を3で割った余り] のようなdpテーブルを2つもって、1つで「2の条件をみたすもの全部」、1つで「2の条件を満たすが連続する箇所は1つも持たないもの」を計算して差をとるのが楽な気がします。

 ということでこれでこの問題をO(27*|S|)くらいで解くことができました。最初の文字列が連続箇所を持たない場合は答えに1足すのも忘れずに。一応自分のACコードのリンクを貼っておきます。

Submission #2374335 - AtCoder Regular Contest 094

 

※追記

 少し考察すると「aとbの差」のmod3が保たれるなら「aとcの差」のmod3も自動的に保たれることがわかるため、dpテーブルは、dp[文字数][最後の文字][(b-a)を3で割った余り]と1つ項を減らして計算しても大丈夫なようです。(Submission #2374698 - AtCoder Regular Contest 094)

感想

 本番中にこの性質に気づけていながら手計算の実験部分を間違えていて解けなかったのはちょっと悔しい。|S|=3の場合だけ無理というのも罠でした。短すぎる文字列なら例外がおこりうることには思い至るべきだったなぁ。700点はさすがに嘘な気がするけどとても面白い問題だと思います。

AGC022 E Median Replace

 AGCお疲れ様でした。EのMedian Replace(E: Median Replace - AtCoder Grand Contest 022 | AtCoder)の解法です。公式の解説が天才すぎたのですけど別の方法で解けたので書きます。

 場合の数をいきなり考えるのは難しいのでとりあえず判定問題を考えます。

 まずいろいろと実験してみると最初の2文字が11だとそれ以降の並びによらず美しい文字列なことがわかります。また、左から順番に見ていったときに、1はなるべく最後まで残すべき(111→1とか110→1とかの操作は極力しない)なことや、0が2つ以上連続していたらそこはさっさと潰して0が1つだけの状態にしてしまったほうがいいということが(直感的にですが)わかります。

 以上をまとめると文字列abcde...が与えられたときにとるべき戦略は

  1. 01cde...のとき:前の01は残しておいたほうがいいのでcde…以下で1をつくれる、つまりcde...が美しい文字列ならよいです。
  2. 00cde...のとき:前の00cは潰して0にするしかないので、0de...が美しい文字列ならよいです。
  3. 11cde...のとき:cde...以下によらず美しい文字列です。
  4. 101de...のとき:前の10は残しておいたほうがいいので、1de...以下が美しい文字列ならよいです。
  5. 100de...のとき:00dの部分を潰して0にしてしまうのが最適で、残る10e...が美しい文字列ならよいです。

 これで、与えられた文字列に対して1回の操作ごとに最低でも長さが2縮まるDPを書けてO(N)で判定することができます。

 数え上げも本質的には同じで、dp[n][a][b]で「n文字の文字列でabで始まるもののうち美しい文字列の個数」とすれば上記と同じ遷移が書けます。?がでてきたときは1と見たときと0と見たときの場合の数を足せばよいです。

 2と5のパターンはそれぞれc、dが?のときは2倍しなきゃいけないみたいな罠があったりするのですがこれでO(N)で解くことができました。

 https://beta.atcoder.jp/contests/agc022/submissions/2289522

 一応コードも貼っておきましたが可読性が死んでます。

 

 ところでこれを通せたのがコンテスト終わってから15分後くらいっていう、、、。

 コンテスト中に通せなかったのは一か所1にしなきゃいけないところが?も許容しちゃってたからなんですけどコンテスト中は気づけないもんですね。Atcoder苦手すぎてつらい。

 しばらくAGCも多いのでどこかで結果が出せたらいいなぁと思います。では。