「転職しました」

あるいは、@muo_jpの頭の中。

技術の話だと思った?残念、さやかちゃんでした!
本エントリは「Android Advent Calendar 2011」への参加エントリです。12/22担当の@muo_jpと申します(ぺこり

「転職しました」というのは、ひょっとすると今年一番多く見たblog記事タイトルですね。転職アドベントカレンダーとか裏の裏の裏の裏の裏ぐらいまで開催出来るんじゃないかという勢いです。

イントロ

AndroidやiOSはエコシステム(生態系)を構成する要素です。OS本体だけで完結するものではなく、それを載せる端末、そして上位で動作するアプリケーション、その他サーバサイドなど数多の要素が複雑に絡み合ったものです。今回は、Androidエコシステムの中でも実際にアプリやハードウェア、サービスを開発している技術者にフォーカスした話を書いてみます。つまり、技術者の転職という話です。OSバージョンアップの話もADKの話も全部すっ飛ばして、転職の話です。
とにかく今年はAndroid界隈を中心に、自身の周囲で転職する人が多い年でした。そんな年の終わりに、技術者の転職というものと、これからの技術者における個人と会社のありかたみたいなのを考えてみた次第です。書いてるのは至って普通なことで、新しいとしたらAndroid好きなエンジニア(私)がAndroid方面の人々の転職を一年間眺めてきた結果を書いてるというあたりでしょうか。
技術者としての人生の考え方、転職の考え方などについて最近だと転職エージェント系の視点で書かれたのは多いけど、エンジニア視点ってのはあんまりないかなと思い、これは今年のうちにAndroidな話のひとつとして書いておいたほうがいいと信じ技術ネタをぶん投げて書くことにしました。
用意していたエントリを当日になってごっそりキャンセルしてこの記事書き始めましたさーせん。そして、内輪向けの書き方にならないよう注意を払ったつもりですが、通りすがりに読んでイミフ、という感じだったら私の力不足です。先に謝っておきます。

注意書き

• 技術者転職how-toでも、技術者採用how-toでもないのでご了承ください
• ごめんね、AndroidエントリなんだけどAndroid技術エントリじゃなくてごめんね

2011年、ソーシャル、スマートフォン転職の一年間

明らかに、転職の年だったという話。年の後半、秋口あたりから転職者がかなり多かった。最近だと@tomo_watanabeさんとか@adamrockerさんとか@zaki50さんとか。
少し引いて考えてみると、ソーシャル系とスマートフォン系、共に人の動きが激しい一年だった。
ソーシャル系は昨年の頭あたりからずっと。ソーシャル系では、サービス開発志向の人が多くSAPへ、より大規模なデータやインフラ/ミドルウェアへの興味が強い人が大手プラットフォームへ集中という構図。

スマートフォン系(iOS/Android)は今年に入ってから激しくなった。とはいえ、まだマネタイズが難しい。iTunes Store / Android Marketで展開するアプリにおいて、課金での売上を読むのは依然として難しい状況。スマートフォンの中でもB2Cでお金になっているのはソーシャル(特にゲーム)が多いという状況。

このへんは一定は産業化されてるという話を少々。ある程度新規参入しやすい領域というよりは産業化/大規模化が進行している。つまり規模の経済が成り立つようになりつつある。ゲーム系だと従来の大手コンソール向けゲームベンダーが強くなってる。

B2B(2C)の観点だと、ユーザのスマートフォン移行が急激に進行しているために従来提供してきたサービスをスマートフォンへ「対応させざるを得ない」状況が生じたことでの仕事が多いように見える。端末の販売に直結するAndroid本体周辺のプリインアプリケーションなども一定ボリューム投資されている状況ではあるが、支配的な発注額は占めていない(はず)。となると新規投資フェイズの会社へ行くか、ソーシャル系で筋の良さそうな会社へ行くか、B2B(2C)の発注者または受注者側へ行くか、はたまた全く別の軸を選ぶか、という流れ。

なんで転職の舞台がスマートフォン(特にAndroid)って話。単純に考えると、そのエリアに強い人の転職市場における市場価値上昇という話。これはAndroid端末の種類・出荷台数を見れば明らか。 だけどそれって本当にお金になってるの?って話は先程書いたとおり。ただ、アプリ/サービス開発需要が高まった結果、技術者の転職しやすい状況にはなった。

では、人の流動性って上がったのかな?というのは当然気になる疑問だけど、調べてない。同じく人材市場として観た際の流動性についても、上昇したのか否かという数字を持っていないので確実なことは言えない。

ここで成長してる市場における人材の流動性が高まるというのは、平均勤続年数が低下しつつ、平均給与が比較的変動しないないしは上昇する状況と考えられる。少なくとも自身の周囲では起きているように思うけれど、サンプルが少なすぎるのでなんとも言えない。

転職者の簡単なプロファイル的なもの。直感的にはこんな感じ、というのをまずぶん投げておく。

エンジニアに限って(というのが、他の方面の人をあんまり知らないから)言えばわりと独身者が多い。年齢的に20代半ばから30代前半辺りの人が多い。ちょうど企業の中での自身の成長というのを強く意識する頃かなという感じ。

リスクに対する許容度を考えてみる。リスクの許容度は、当然結婚や子供によって左右される。リスクを取ってでも新たな行動を取ろうとするモチベーションについて考える際に参考にしたいのはマズローの欲求階層仮説。彼は人の欲求を以下の5段階に分け、このより高いレベルに向かって希求するものだとした。

1. 生理的欲求 / 生命維持のための食欲・性欲・睡眠欲等の本能的・根源的な欲求
2. 安全の欲求 / 衣類・住居など、安定・安全な状態を得ようとする欲求
3. 所属と愛の欲求 / 集団に属したい、誰かに愛されたいといった欲求
4. 承認の欲求 / 自分が集団から価値ある存在と認められ、尊敬されることを求める欲求
5. 自己実現の欲求 / 自分の能力・可能性を発揮し、創作的活動や自己の成長を図りたいと思う欲求

5段階の中でフェイズの壁を感じた時に、自身の状況を強く考えるんじゃなかろうかというのが、直感的なところ。けどそれだけだとなんだかうそくさいので、いろんな人のケースを考えつつもう少し検討してみる。

転職していったひとびと

私の周りには、前向きな転職をしてる人が多い。いやまあ、後ろ向きな理由を好んで話すようなもんじゃないだろうからそう見えてるだけかもしれんけど。

これには時期的な事情が多分にあると考えられる(このへんは2節目で書いた)。もちろんクリエイターに認められない部分はあるけど、Androidは常用端末として一定以上の地位を占めるようになってるのは事実。

前向きな転職する人が多い一方で「Androidなんていう、まだ誰も知らないけどきっとこの先大きなうねりを生みそうな技術に賭けるために完全に畑違いだけど行くぜ」って感じのは、もうないんだろうな。ちょっと寂しい。まあいいや。

それはさておき。

エンジニアな人(特に、Android界隈に居る人々)の頭の構造ってどういう感じだろうと考える。

実際にどんな転職した人が居るっけ。1年前ぐらいから転職してる人多い。具体名を挙げるのは控えたい。数例を挙げるとこのような感じ。

• メーカー勤務でわりと好き勝手にやれて給料も良かったけれどスタートアップへ転職した人
• メーカー勤務で技術的な挑戦エリアの狭さを感じ、またその組織を変えていくことが非常に困難だと感じてスタートアップへ転職した人
• メーカーの研究所勤務で、実際に新しい技術を使った開発を行いたくてスタートアップへ転職した人
• 新卒からSIer勤務で自身の技術的な興味範囲と周囲のギャップに悩みスタートアップへ転職した人

かくいう私も転職組でね。あんまり長々と自分語りをしたいわけではないのでサラッと書いておくと私のバックグラウンドは経営学、生き方は主にテンションベース。身の回りに凄い人が多くて、そういう人と話すと、めっちゃテンション上がりながらめっちゃ憂鬱感じるという驚異の重ね合わせ状態を体感出来て楽しい、という感じ。

さて、そう言うほどAndroid方面の方々の転職話をしっかりと知っているわけでもないので、以下の分析では他に私が話を聞く機会があった方の中でマインド近そう、と感じた人の分も含めてみる。

皆がどういうポイントを重視して転職していったのかという話

• 十分なお金を稼ぐことが出来るか
  そして、それが本源的に持つ金銭的価値と比較して適切と考えられるか(バブルならバブルで、期間の読みは妥当か)
• 人間関係
  自分の求める距離感とマッチしているか(ある意味、会社の空気)
• 会社から受けるストレス
• マネージャとの関係
  エンジニアはエンジニア出身のマネージャなど、技術面で何かしらの尊敬を出来たりする人の言うことしか聞かない(ってことが多い)ので、マネージャが技術に対して一定以上の認識を持っているかどうか
• 新しいことが出来る環境か
  AndroidやiOSなどに特化したスタートアップへ転職した人にはここが大きい感
• 自身の人生の中でのステップ
  技術に深く関わり、自ら実装するフェイズからマネジメントフェイズへの移行なども
• 会社の未来
  時代の変化にあわせて仕事の中身を変えていくことが出来るか
• 自身でどこまでをコントロールすることが出来るか
  まずいところがあったとしても、自分の力で変えていくことが出来るか
  これをコントロールしたい度が強いほど、初期スタートアップへ行ってる感
• 自身が会社のメインストリームに居らるかどうか
  メインストリームに居るべきと考えられるのか(むしろ新規投資系の事業に居たほうがいい場合もある。このへんは会社のスタイルによる)
• 尊敬できる人が居るか

逆に、このへんの全てではないけれど一定の領域で満足を得られている人は転職していないし、当分転職しなさそうな人も多い。

転職していったAndroiderってこんな人かなー

• 会社以外の人と触れる機会が多い人
• 社外の勉強会や定例会での発表を行なう人
• 積極的に情報を取り込み、自分の中で処理して発信する人
• 飲み会好きな人
• なんか新しいことやってみるのが好きな人
• ヘンな人
• 尖った分野を持ってる人
• いくつかの分野を合わせてヘンなことを出来る人
• 技術に対して取り組む姿勢(ここはあんまり一致する像が浮かばない。むしろいろいろ)
• 技術がとことん好きな人も居る
• 技術を使ってなにかを作ることが好きな人も居る
• 人を巻き込んでサービスを作るのが好きな人も居る
• Android好き?
• 必ずしもAndroid大好きじゃない人も

これからのAndroid界隈の転職の形

業界全体としてマネタイズ策がもっとうまく出来て行かないと、早晩限界が来そう。当然単価は下がるしオフショア化もある程度は出来るようになっていくから(特に、新しいことをやるよりも既存の仕組みをルーチン回して新サービス/アプリ化する仕事から順次)。
大手志向って出てくるの?これ、微妙なところ。
個人(フリーランス)でやるか、会社でやるか。個人のほうが自由を確保出来るか?という話。会社で一定安定した収益基盤を保持しているほうが、積極的な投資を行える場合もある(これは会社の文化にもよる)。
個人対会社という構図。
技術者を集める構造とか分かる?技術者にとって、よりよい会社のありかたってどんなものだろう。技術者が会社に対して持つ要望(先ほど挙げたのが一例)を、全てではないにしても可能な範囲で満たすこと。難しい?難しいですたぶん。けど、他の会社が技術者に対する魅力を一定以上訴求するようになれば、ここを頑張らなきゃどうしようもなくなるので、この先はもう少し頑張る会社が増えると読んでる。

どういう会社に転職するとこの先幸せになれるんだろう。人によって全然違う。しかし、やっぱ凄い人が居るところに人は集まる。会社は自社の魅力をこれまでよりももっとオープンにすれば、割と伝わりやすい時代にはなってる。

会社と個人がうまく付き合っていくには

個人対会社というのは敵対関係じゃないし、片側が搾取する関係でもないべき。どっちかというと補完的なもの。会社だと厄介だけど個人だとやりやすいってエリアは、ここ数年かなり増えてる。例えばOSSの利用ひとつとっても、会社でGPL'edなソフトウェアのソースを利用して何かを作ってリリースというのは、現実問題結構大変。個人なら、当然自分自身の判断でなんとかなる。稟議の行列がしんどいと思うものはどんどん個人化してしまうのが良いはず。

その結果「会社で出来ないから個人でやる」というものがどんどん増え、開発者の会社に対するコミット度合いがどんどん低下するようなら会社のあり方を考えないとまずい。この意味でも「時間を100%コミットして、仕事終わったらヘロヘロになって自分の時間で何も出来ないような状態が恒常的である会社」などでは、その業務自体から得られる成長や満足が一定以上なければ人の流出は止まらない。
どういう形であれば個人の成長と会社でのアウトプットを両立出来るんだろう。ここには割と考えられることがあって

この1年間とか3年間とかを振り返って自分は成長することが出来た?出来たならそれは会社のおかげ?自分のおかげ?出来なかったならそれは会社のせい?自分のせい?それって多分一歩引いて考えると自分のせいなんだけど会社を変えることで改善しそう?

という問いを自分に対して投げかけてみて、会社での成長(または金銭面を含めた満足)と個人での成長(または金銭面を含めた満足)がバランスしているかを見ると、そこそこ分かる気がする。それと、関連してこれからの技術者像ってのを考えてみる。

• 社内・社外及び社内+社外でのコラボを多めに
  自身の視点を広げ、現時点で自身の持つ価値を比較的正確に把握するため
• 技術だけでない、せめてもう一つの視点を持つべき
  経営視点?サービス視点?デザイン視点?自身が既に持っているバックグラウンドなどをほどよく活かしつつ、従来とは異なるエリアへ取り組むことで継続的な成長を習慣付けることが出来そう

こういう感じだと、会社と個人というのをうまくバランスさせて成長していくことが出来そうな感じ(自分の周囲とか見ていて感じるものなのであんまり客観性無いけど)。
一方、会社としては、人を囲い込むのが良いかというとそんなことはない。人間関係でも会社対個人でも、ヘタな囲い込みをするほど相手をなめちゃいけない。例えば、人材流出を防止する目的で勉強会参加禁止措置を取るなどすると、どんどん人は辞めていく(出来る人からやめていく)。

この1年半のうちに転職した人間として

作りたいと思った瞬間がアプリ/サービスの作りどき、端末は買いたいと思った時が買いどき、転職しようと思った瞬間が転職どき。

となると、自分がどういう状況になったら転職したいと思うのか、ということを想像しておくと兆候を掴んだ時に動きやすくなる。自分の場合は、だいぶ前にITをやるということだけ決めて仕事を始めたので、前職がITやめると決まった瞬間に転職活動始めた。確か、電話で話し終わった瞬間にDoDA開いてた。
twitterや各種Android関連の集まりで会える人って、面白いバックグラウンド持ってる方が多い。なんせ、Android界隈って起源が全然違うめっちゃ多様な人々が集まってる。そしてエンジニアがいかに大切な存在かということを分かってる人がいっぱいいる。だからこそたまに異様に心強いんじゃないかなー。生き方とかも参考になる。
つい先日も「これからの年収の話をしよう」という話があったりと、先輩に学ぶことも多いしね。割と損得抜きに思いをぶつけられる相手が多いような気がする。もやもやしたら(問題無い範囲で)ぶつけてみたらいいんじゃないかな!

人生は考えたほうが断然楽しい!

ということで

私、中澤 慧は12/31付でKLab株式会社を退職しません。

私、来年はたぶんPS Vitaで遊びます。SDK欲しいです。

実は、@vvakameに「みゅおの頭の中みてみたい」と言われたので書いてみたというのも少しあります。小ネタの仕込みから、アニメネタへ偏ってるかが分かると思います(攻殻/まどマギ/ピンドラ)。

あ、そうそう。最近読んだ中では「先延ばし屋の予定帳」が秀逸でした。締め切りすぎないとパフォーマンスが上がらん的な話。締め切りを2倍過ぎてから作業を始めると、どんなに悪くても締め切りを4倍遅れることはないという素晴らしい理論です(白目)。

ではではこんなところで。長文お付き合いありがとうございました。来年も楽しい一年になりますように、そして(省略されました…続きを読むにはご自身で書いて下さい)

TopCoder SRM練習 - SRM 525 DIV 2 Easy/Medium

次回のSRMで復帰予定なのでそろそろ感覚取り戻していくべく練習。
以前とは違ってSRM同様75分の中で解くのを重視。

今回やったのはSRM 525 Div 2

まずはEasy問題。

(0, 0) - (N-1, 1) の 2 x N な通路中を(0, 0)からスタートして(N-1, 0)まで到達出来るかどうかを判定して返せ

という問題。で、条件としては「1点以上を共有しているマスには移動できる」の中で制約に「Wとマークされているマスは水浸しで通れない」ってのがある。
少し図に書いて考えてみると
□□
□□
ok
□■
■□
ok
■□
□■
ok
□■
□■
ng
■□
■□
ng
ということで、縦にFが2つ並んでいるものを除けば良いということになる。で、これはうっかり忘れてたのだけれどゴール地点がW(水浸し)ならそもそも到達不可能として弾かなきゃいけない。後から問題の制約条件読むと「道の最初と最後は水浸しじゃない」と明記されてたので救われた形。

public class RainyRoad {
 public String isReachable(String[] road) {
  int width = road[0].length();
  for (int i = 0; i < (width - 1); i++) {
   if (
     (road[0].charAt(i) == 'W' && road[1].charAt(i) == 'W') ||
     (road[0].charAt(i + 1) == 'W' && road[1].charAt(i + 1) == 'W')
     ) {
    return "NO";
   }
  }
  return "YES";
 }
}

コードはこのとおり。無駄に2列ずつやってるのは、最初のうち問題を読み間違って「上下左右にしか動けない」と勘違いしてた状態で書いたコードの残骸(非効率だけど間違いではない)が含まれるから。システムテスト通ってスコアは212.31 / 250。

続いてMedium問題。
読んだ瞬間には「うわ、GDD DevQuiz系?」と探索アルゴリズムに弱いのを思い出したけど、まずはしばしごにょごにょ考えた。
問題をざっくり訳すと

指定サイズ(1辺は1-30マス)の盤面のいくつかのマスにコインが置かれてる。このとき、コイン群を盤面全体に対して上下左右いずれかに動かし、盤面の端から適当な数のコインを落として指定された(K枚)のコインのみを盤面に残すための最短手数を返せ

というもの。
単純に考えると1回のオペレーションで4通り、探索すると最大30x2=60手なので2^120ぐらい読む必要がある。これは2秒の制限中では明らかに無理。
ということでしばらく図を眺めてごにょごにょと考え「移動順はともかく、元盤面の中でサブの盤面を定義してその中にK枚のコインが残るようなケースのうち最も手数の少ないものを探しだす」んだと思いついた(ちょい遅かった)。
こうすると始点と終点の選び方で30^4、選んだエリアの中に含まれるコインの枚数を数えるのに最大30^2(実際はサブセットに限定される分、もうちょい小さい)の計30^6、ループは7億回ちょいとなって2秒制限の中ではやばい感じがするけどひとまず実装してみた。
ちなみに実装中に考えていたループ回数の低減策は「指定エリアに含まれるコイン枚数を辞書として持つ」で、計算量的には30^4+30^2と相当効くはず30^4+30^4となって半分程度に出来る(辞書の辿り方によってはむしろ悪化する)。ただ、その分81万要素を保持する必要が出てくるので変なパックするとメモリ足りなくなる(64MBしか使えないらしい)。まあこのあたりは一旦HashMapあたりで作って不足するならcharの配列あたりに落としていけばいいかなと。
で、そんなことをほんのり考えつつひとまず書いたナイーブな実装がこれ。

public class DropCoins {
 public int getMinimum(String[] board, int K) {
  int min = 9999;
  int width = board[0].length();
  int height = board.length;
  for (int i = 0; i < width; i++) {
   for (int j = 0; j < height; j++) {
    for (int k = i; k < width; k++) {
     for (int l = j; l < height; l++) {
      // (i, j) -> (k, l)
      int tmpCnt = 0;
      for (int m = j; m <= l; m++) {
       for (int n = i; n <= k; n++) {
        if (board[m].charAt(n) == 'o') {
         tmpCnt++;
        }
       }
      }
      if (tmpCnt == K) {
       int left = i;
       int top = j;
       int right = width - k - 1;
       int bottom = height - l - 1;
       int steps = 0;
       if (left < right) {
        steps += left * 2 + right;
       }
       else {
        steps += left + right * 2;
       }
       if (top < bottom) {
        steps += top * 2 + bottom;
       }
       else {
        steps += top + bottom * 2;
       }
       if (steps < min) {
        min = steps;
       }
      }
     }
    }
   }
  }
  return (min == 9999 ? -1 : min);
 }
}

時間切れになるかなーと思いつつシステムテスト(この適当さがあんまり良くないんだけど)走らせたところ、最も時間のかかるケースで411msかかりつつも時間内に処理出来てパス。スコアは265.44 / 600。
例によって道筋が立ってからはほとんど一本道でいけたけど危なくてしょうがない。
tmpCntのカウント中にカウントがKを超えた場合には途中で諦めるというのも手なんだけど、そのぶん分岐が増えるわけで微妙。

Hard問題は開いてないし当分開かないでいいと思う。

アーロンチェア買ったら家に入らなかった

前からずーっと欲しかったアーロンチェアをついに買ったわけです。
14万円弱するにはするんですが、軽く12年保証がついてるので年数で割るとMacよりも格段に安いなと思い。。
ちなみに日曜注文し火曜の午前中に到着という素晴らしい対応(どのお店とは書きませんが)。

で、朝に「大きめの荷物届いてますがご在宅ですか?」という電話連絡が来て「YES!YES!YES!YES!」と歓喜。そして数分後

( ﾟдﾟ)ﾎﾟｶｰﾝ
噂には聞いていたけど予想以上に箱がデカく、配達に来てくれたクロネコなお兄さんも「いやー、そのまま入れるの無理だと思うんで表でバラしてください」とのブン投げっぷり。ナイス。

で、到着嬉しいので身体にフィットするよう諸々調整。そして座ってみた感覚はさすがだなぁ、という感じ。前傾チルトモード多用しそう。

残念ながら、我が家にはワーキングデスクが無い(コタツになるちゃぶ台しか無い)ので、しばらくの間はチェア単体+膝の上にPCで運用しようと考えてた。

けれど仕事から帰ってきてふと目の前を見るとやたら背が高く頑丈な段ボール箱がある。

「これ切って丁度いい高さに調整して、それに似た机買えばいいじゃん」

ということでまずハサミ使ってちょうどいい高さに詰めた。

次に足を格納して作業スペースとするべくゴリゴリとハサミで段ボールを切り、

なんか机っぽくなった。チェアを収めてみると

という感じ。これは満足度高い。しかも、梱包でビクともしてなかった段ボールなので

これ案外このまま使えるんじゃね?
と欲が湧いてくる。天板頑丈だし好き勝手に汚せるしと失うものは特になさげだったので

普通に実戦投入しました。天板がヘタるまでは使うつもり(ちなみに天板までの高さは62cmが狙った高さみたい)。 blog更新再開のための肩ならし的に、またしてもものを買った系の記事書いてみました。次からは方向結構変わります。

MacBook Air 13" Mid 2011 開封の儀

MacBook Air 13インチ、Core i5 1.7GHz、4GB MEM、256GB SSDなモデルを買ったので開封の儀など。

といっても写真をひたすら貼っていくだけ。

午前10時、50人ほどに膨らんでいたアップルストア銀座の行列に告げられたのは「本日、MacBook Airの入荷はありません」という残念すぎる言葉。ダメもとで近くの有楽町ビックカメラへ行ってみると、平然と展示しているし在庫もあるということだった。

ただ店員さんからの注意点が2つ

「Officeはまだ対応してないようです」

「不具合かどうか確認出来てない状況ですが、電源延長用ケーブルの先端が通常の二又+アース線ではなく三又のものになっています。仕様なのか誤混入なのか不明な状況ですが…」

まあいいや、っと購入。

ん?2.95kg?

なんかシールの貼り方的に、梱包完了は7/9だった模様。

外箱あけると子箱が中に

取り出す

わくわく

なんか注意書きなどされているけどあまり気にしない。

箱あけたところ。こう見るとやっぱり2010年秋モデルとさほど変わらない。

注意書きが書かれた紙で本体保護シートが封されてる形

やぶりかけ

本体開いたとこ

液晶保護用のシートを外した

電源投入!テンション上がる背景

言語選択

地域選択

キーボード選択

入力方法選択

Wi-Fi設定

他Macからの情報インポート。今回はスルー

アカウントピクチャ設定。当然ジンジャーブレッドマン

パスワード入れてアカウント作成

ユーザ登録。けっこうしっかり入力させられる

使用許諾契約

ジェスチャーの練習的なもの

ついにログイン画面

多少さわってみたところ

触ってみた感想ですが、CPUが強化された分のサクサク感、前に使っていたMBAと比べて2倍のメインメモリを積んでいる安心感、同4倍容量のSSDによる「容量気にせずAndroidのソースでもなんでも来い」感が素晴らしいです。Lionも1日使えばだいたい慣れるし、買ってよかったと思ったのでした。

TopCoder SRM練習 - SRM 511 DIV2 Easy

今日もちょいちょいと。
GameOfLifeDivTwo

・ライフゲームの変形版
・ドットが円形に並んでる
・状態Tでの各ポイントの生存状態は、その前(T-1)で自身プラスマイナス1つの計3つのうち2つ以上が生存していた(=>true)か否か(=>false)で決まる

ということで愚直に端っこをループさせてこういうふうに解いた。計算量的には、-1にあたる場所とNにあたる場所をもうちょい特殊に扱って毎回境界外をつなぐ処理を行わないようにすれば減らせそう。まあ、Top Submission見てもこんな感じ。途中喋りながらやってたというのはあるけど、さらっと書いてから配列のコピーで微妙にハマりprintfデバッグ繰り返した結果159.31。うーん、イマイチ。正答率91%、平均点183。

public class GameOfLifeDivTwo {

 public String theSimulation(String init, int T) {
  int setLen = init.length();
  boolean stateList[] = new boolean[setLen];
  boolean stateTmpList[] = new boolean[setLen];
  for (int i = 0; i < setLen; i++) {
   stateList[i] = init.charAt(i) == '1';
  }
  for (int i = 0; i < T; i++) {
   for (int j = 0; j < setLen; j++) {
    int liveCnt = 0;
    int nextIdx = j + 1;
    if (nextIdx == setLen) {
     nextIdx = 0;
    }
    if (stateList[nextIdx] == true) {
     liveCnt++;
    }
    int prevIdx = j - 1;
    if (prevIdx == -1) {
     prevIdx = setLen - 1;
    }
    if (stateList[prevIdx] == true) {
     liveCnt++;
    }
    if (stateList[j] == true) {
     liveCnt++;
    }
    stateTmpList[j] = 2 <= liveCnt;
   }
   for (int k = 0; k < setLen; k++) {
    stateList[k] = stateTmpList[k];
   }
  }
  String retStr = "";
  for (int i = 0; i < setLen; i++) {
   retStr = retStr.concat(stateList[i] == true ? "1" : "0");
  }
  return retStr;
 }

}

TopCoder SRM練習 - SRM 450 DIV1 Easy

昨日に続いて、少しずつやる。
今日やったのはOrdered Nim。

・AliceとBobの2人がゲームをしてる
・複数のヒープ(インデックスが振られている)のうち1つから、1つ以上の石を交互に取り出す
・あるヒープから石を取り出せる条件は、そいつよりインデックスの小さなヒープが全て空の場合だけ
・最初に取り出すのはAlice
・各ヒープに入ってる石の数は10億個以下
・お互いが最も効率的にゲームをプレイする場合、勝つのはAliceかBobか返せ

先日落としたトラウマ化しつつある問題と少々似てるところがある。いくつかケースを紙に書いてみて
・Aliceが必ず勝てる場合以外は、Bobが必ず勝てる(直感的にこうだけど未証明)
・n-1番目へたどり着いたら全部取って勝てるので、n-2(境界注意)までが勝負
・"Aliceが勝つかどうか"をn-2番目のヒープから逆順でたどって検証していけばよさげ
・あるヒープに石が最初から1個しかなければ、勝者判定をひっくり返す
・あるヒープに石が最初2個以上あれば、その次(ループ上はひとつ前)のヒープにある石が1個であれば勝者判定をひっくり返し、2個以上であればAliceの勝ち判定とする(総取りか1つ残すかのどちらかで、Bobに不利条件を押し付けられるから)
とたどり着いた。

テストケースを自前で増やしてやばそうなパターンを拾えるようにしたけれど、それでも抜けがあって一度failed system test。その後訂正し再提出して75.0pt(実際だったら0pt)。なかなか凹みますな。avg=205 / 正答率74%。この回なら文句なしに落ちてる。

public class OrderedNim {

 public String winner(int[] layout) {
  String ALICE = "Alice";
  String BOB = "Bob";
  if (layout.length == 1) {
   return ALICE;
  }

  boolean aliceWins = true;
  boolean oneStoneFollows = false;
  for (int i = layout.length - 2; 0 <= i; i--) {
   if (oneStoneFollows == true) {
    if (layout[i] == 1) {
     aliceWins = !aliceWins;
    }
    else {
     aliceWins = true;
     oneStoneFollows = false;
    }
   }
   else {
    if (layout[i] == 1) {
     aliceWins = !aliceWins;
     oneStoneFollows = true;
    }
   }
  }
  return aliceWins ? ALICE : BOB;
 }

}

"both players play optimally"な問題はまあまあ苦手だなぁ。

TopCoder SRM練習 - SRM 450 DIV2 Easy

簡単な問題でもいいので、出来るだけ毎日解くキャンペーン中。
今回やったのはStrangeComputer

・指定位置のメモリを書き換えると、そこから右(概念的に)が全て指定した値でフィルされてしまう、変なコンピュータが与えられてる
・入力(文字列)で指定されたメモリ状態にするための最短手数を返せ
・なお、初期状態は0埋めされてる

public class StrangeComputer {

 public int setMemory(String mem) {
  char prevChar = '0';
  int opCnt = 0;
  for (int i = 0; i < mem.length(); i++) {
   if (mem.charAt(i) != prevChar) {
    opCnt++;
    prevChar = mem.charAt(i);
   }
  }
  return opCnt;
 }

}

こんだけ。同じ値が連続すれば、その分は前オペレーションで指定済みとなるので手数増やさずに設定したことに出来る。230.98、passed system test。平均スコアが213.15で正答率93%なのでこんなもん。