やおよろず

ゆるふわな内容を書いても良い。と言うか何でも良い。そんな自由度の高いブログをめざします。

Educational Codeforces Roundをそんなにやっていけなかった話

この記事は カレーのち ぴょこりんクラスタ Advent Calendar 2018 - Adventar のために書いたものです。

本当は今日までにスマブラでVIP部屋に行きたかったんですが無理でした。精進します。

はじめに

ぴょこりんクラスタアドベントカレンダーってあるじゃないですか。
今もまさにそれ用の記事を書いているわけですけれども。
これまで自分は参加していなかったし、去年や一昨年は、25日分の記事を3人で埋めていたと言うから恐ろしいですよね。

自分は今年になってはじめての参戦となりますが、
一昨日の記事でも触れた夏の大合宿(仮)に参加したあたりで、アドベントカレンダーの記事を書くことが確定していました。

25日を4人で割ってもおよそ6日*1
そんなに沢山ネタを作るのは大変だなぁ、と思ってましたが、
「途中経過でもええんやで」という誰かしらのアドバイスを受けて思いついたのが続き物ネタ。
そのための布石として実行したのが、12/5に投稿した、Educational Codeforces Roundをやっていきたい話 - やおよろずでした。

本題

と言うわけで今回は、実際に12/5の記事を執筆して以降、 自分がどのくらいEducational Codeforces Roundをやっていけたかの話をしたいと思います。

成果

以下が成果となります。ご査収ください。

f:id:yaoshimax:20181222044132p:plain
10問解きました

12/5時点*2ではRound1 A,B*3 しか解いていませんでしたが、
その後にRound1のC、Round2のABCD、Round3のABCDEを解き、いい感じに階段状の図を作る事に成功しました*4
「なんだ10問か…」と思われるかもしれませんが、submission数で言えば29回。
ならせば1ヶ月毎日1submissionしたと言えるので、かなり頑張った方だと思います*5

以下では、Educational Codeforces Roundのいくつかの問題について、解説とか苦労話などを書いておきます。

8回誤答したRound 2 D「Area of Two Circles' Intersection」

問題ページはこちら

問題概要

2つの円があります。円の中心座標と半径はx_1, y_1, r_1 x_2, y_2, r_2として入力で与えられます。
この円の共有部分の面積を求めて出力してください。

解き方とか

数学ゲーですね。

  • 円が交わらないときは当然0
  • 片方の円が完全にもう片方を包含する時は、小さい円の面積
  • 上記以外の時、交点1つと中心座標(x1,y1), (x2,y2)をがなす角度  \theta_1, \theta_2 を用いて、 {r_1}^2 (\theta_1 - \sin \theta_1 \cos \theta_1) + {r_2}^2(\theta_2- \sin \theta_2 \cos \theta_2) が解

で求まります。 \theta_1 とかは余弦定理などを使えば計算できます*6

が、誤差が1e-6以内である必要があるため、適当な計算をして居ると誤差で不正解扱いになります。

f:id:yaoshimax:20181222051309p:plain
誤差と格闘している様子

  • 多倍長整数とか勝手にやってくれるしpythonの方が良いかな?と思ったが、pythonだと誤差が解決できなかった
    • 多分pythonのfloatが53bitなのが悪い*7。この問題、c++でlong doubleを使う必要があるらしい*8
  •  {r_1}^2 \theta_1  + {r_2}^2\theta_2 - {r_1}^2 \sin \theta_1 \cos \theta_1 - {r_2}^2 \sin \theta_2 \cos \theta_2と計算すると r_1, r_2の差が大きい時に誤差で解がずれる

あたりが特にはまりどころでした。
ネット上から他の方の解答を引っ張ってきて途中計算dumpしながらデバッグするくらいにはしんどかったです。

個人的に教育的っぽかったRound 3 D「Gadgets for dollars and pounds」

問題ページはこちら

問題概要(意訳)

 m個の商品がある。これらの価格はドルまたはポンドで与えられている。
あなたはs円までの予算で、m個のうちから k個の商品を購入したい。
ただし、あなたが所持できるのは日本円だけ。
商品購入時に、必要額のドル・ポンドを円と交換する必要がある(予め円をドルに替えて翌日以降持ち越し、とかは不可)。
ちなみにあなたは、ここから先、 i 日後には1ドル a_i円、1ポンド b_i円で変換できる事は知っている( 0 \le i \le n-1)。
最速で何日までに k個の商品を購入する事ができるのかを調べ、何日にどの商品を購入すべきかと合わせて出力せよ

解き方とか
動的計画法で頑張る方針(これだと解けない)

1日ずつ変換レートを見ながら商品の買う・買わないを判断しつつ、
 i 日目までに商品集合  M を買う値段の最小値を dp[  i ][  M ]円として保持する事を考えます
コードに起こそうとすると以下のような感じでしょうか。

for day in [0..n-1] do
  for all M, which is subset of [1, ..., m] do
    for all U, which is subset of M do
       cost = i日目に商品集合Uを買うコスト(円);
       dp[i][M] = min(dp[i][M], dp[i-1][M\U] + cost)
    end
    if Mのサイズがk以上でdp[i][M]がs円以下 do
       //i日目までに商品はk個以上買える。
       print Mの買い方
       return
    end
  end 
end 

この場合、 m個の商品のうちどれを買ったか・買わないかの情報(商品集合  M )を保持しなければなりません。 この状態数は 2mとなりますが、 m は最大で105なので、そんな情報持てません。

ちゃんとした解き方

と言うわけでどうするかと言うと、注目すべき性質としては以下があります。

  • ドル額で  d 円のとある商品を  x 日目までに買おうとするなら、最適な購入費用は  d \times \min_{i\le x} a_i である。
    • 要するに、  x 日目までの一番ドルが安い日に買っておけば良い
  • ポンド額で  p 円のとある商品を  x 日目までに買おうとするなら、最適な購入費用は  p \times \min_{i\le x} b_i である。
  •  x 日目までに  s 円の予算で商品が  k 個以上買える」が真ならば、任意の  x 以上整数 yにおいて「 y までに  s 円の予算で商品が  k 個以上買える」 も真

以上の条件が成り立つ事により、以下のような二分探索ができます。

left = -1
right = n
while(left+1 < n) do
 mid = (left+right)/2
 price = []
 for all 商品 do
  price.append(商品を mid日目までに購入するとした場合の最安値)
 end
 sort(price)
 sum = 0  // mid日目までにk個の商品を買うとしたら最安値でいくらになるか
 for i in [0,...k-1] do
   sum += price[i]
 end
 if( sum <=  s ) do
  right = mid
 else
  left = mid
 end
end

// right日が答えなので、その日迄に買うk個の商品の購入の仕方を出力する

この手によって、計算量を  O (m* \log(m) \log (n)) におとす事ができるので、  m の最大値が 105とかでも許されます。

実装がダルかった、Round 3 E「Minimum spanning tree for each edge」

問題ページはこちら

問題概要

 n 頂点  m 枝の重み付き無向グラフが与えられます。
このグラフは連結であること、多重辺やセルフループがないことは保証されています。
 e_0, e_1, ... , e_{m-1} それぞれについて、 c_i = \min (e_i を含むグラフの全域木のコスト) を求めてください。

解き方
基本方針

最小全域木を計算する代表的なアルゴリズムに、プリムのアルゴリズムがあります*9プリム法 - Wikipedia

平たく言ってしまえば、重みの軽い枝は、ループを作らない限り、片っ端から最小全域木を構成するものと考えて良い。
ってアルゴリズムです。

f:id:yaoshimax:20181222130705p:plain
プリムのアルゴリズムを説明しようとした雑な図

今回は「ある枝  e をつかった全域木の最小コスト」を枝ごとに求めなければなりませんが、
そう言う全域木は、
 e の端点を  u,v とすると「グラフの最小全域木上で  u から vまでのパスを考えたときに、一番コストの高い枝を、枝  eと置き換える」
事によって作る事ができます。

f:id:yaoshimax:20181222135138p:plain
雑に説明を試みる図

全域木上の2頂点間のパス中の最大辺を求める方法

というわけで、最小全域上の2頂点間のパスの最大辺を求める必要が出るんですが。
頂点数が最大で 2* 105 なので、毎回愚直に深さ優先探索とかして求めようとすると時間がかかるし、
全頂点対間のデータをテーブルに保持するのは頂点対が2 * 1010くらいあるので無理です。

これは、木と2頂点  u, v が与えられた時に、一番近しい共通親(Lowest common ancestor)を求めるアルゴリズムを応用することで効率よく計算できます。

まずLowest common ancestorを効率良く計算するにはどうするかと言うと、 前処理で各頂点 n について1番目の親、2番目の親、4番目の親、…2k番目の親をparents[n][k]に保持しておいて*10、 以下のような擬似コードにより、不必要な所をすっ飛ばしながら親を見つける、というものです。

function LCA(int u, int v){
  if(depth[v] < depth[u]) swap(u,v);
  // ここでdepth[v]がdepth[u]に等しくなるまでvの親をたどる(省略)

  while(u!=v && parents[u][0]!=parents[v][0]){
    // 親が一致しないギリギリである2^k番目の祖先までu,vを更新する
    int k =-1;
    while(parents[u][k+1]!=parents[u][k+1]) k++;
    u = parents[u][k];
    v = parents[v][k];
  }
  if(u!=v) return parents[u][0];
  else return u;
}

これがどうして全域木上の2頂点パス中の最大辺を求める事に繋がるか?というと、 各頂点 nについて、1番目の親、2番目の親、…2k番目の親をたどる迄の最大辺をmaxEdge[n][k]と保存しておけば 以下のような擬似コードが使えるのです。

function maxEdgeBetween(int u, int v){
  if(depth[v] < depth[u]) swap(u,v);
  ans = -1;
  // ここでdepth[v]がdepth[u]に等しくなるまでvの親をたどる(省略)

  while(u!=v && parents[u][0]!=parents[v][0]){
    // 親が一致しないギリギリである2^k番目の祖先までu,vを更新する
    int k =-1;
    while(parents[u][k+1]!=parents[u][k+1]) k++;
    // 更新する際に最大辺を更新する
    ans = max(ans, maxEdge[u][k]);
    ans = max(ans, maxEdge[v][k]);
    u = parents[u][k];
    v = parents[v][k];
  }
  if(u!=v){
    ans = max(ans, maxEdge[u][0]);
    ans = max(ans, maxEdge[v][0]);
  }
  return ans
}
解き方まとめ

と言うわけでこの問題については、

  • グラフの最小全域木とそのコスト S 求める
  • 最小全域木をたどりながらparentsとmaxEdgeを作る
  • 各枝  e = (u,v)について、S+weight(e) + maxEdgeBetween(u,v)を出力する

みたいな事をすれば、  O(m \log(n)) の計算量で解く事ができます。

プリムのアルゴリズムの実装に加えてLowest common ancestorを解く実装もする必要があるので糞だるかったです。

EF解けなかったけどGが解けた。Round 55 G「Petya and Graph」

問題ページはこちら

問題概要

 n 頂点  m 枝の無向グラフが与えられます。
各枝には w_i、各頂点には  a_iの重みが与えられています。

頂点の部分集合Uにより定義できる誘導部分グラフについて、
得点を「Uに含まれる枝の重みの総和ーUに含まれる頂点の重みの総和」で定義します。
この最大値を求めてください。

解き方

何となく燃やす埋める問題っぽさがあるなぁと思いながら考えてたらグラフの最小カットに帰着できました。

始点 s,終点 t、 元のグラフの枝 e_1,e_2,e_3... に対応する頂点集合 W
元のグラフの頂点 v_1,v_2,v_3... に対応する頂点集合 V
を持つようなグラフを考えて枝を以下のように張ります。

  •  e_i の端点 u,vから枝に対して、重み無限大の辺
  • 始点 sから各頂点に対して、 a_iの重みの辺
  • 各枝から終点 tに対して、 w_iの重みの辺

f:id:yaoshimax:20181222144946p:plain
雑な説明(作成都合で始点sが右側なのは許して)

こうすると求める値は、このグラフの最小カットCを用いて、  \sum w_i - C と表せます。

なんで?を雰囲気で説明すると、
始点~頂点の位置で辺をカットした頂点の集合を  V_1、辺をカットしなかった頂点の集合を  V_2とすると、
枝~終点の位置では、 V_2に属する点を端点に持つ全ての枝~終点の経路をカットしなければいけないですよね。
これは、 V_1= Uとみなした際に、

  • 前者のカットによる値が、「Uに含まれる頂点の重みの総和が得点から減点される分」
  • 後者のカットによる値が、「Uに含まれない頂点を端点にもつ枝は、そもそもの得点を得られない分」

にそれぞれ対応していると捉える事ができます。
よって、この減点分を最小にするのが得点を最大にする事と等価といえるのです。

ここまで考察できてしまえば、このグラフの最小カットは sから tまでの最大フローに等しい*11 ので、
後は最大フローのライブラリで殴るだけですね。

終わりに

競プロ勢じゃない方にこの記事ってどのくらい伝わるんですかね…分かりづらかったらすみません(ぷよぷよぶり2回目)
ともあれ、それなりに歯ごたえのある問題も解けたし、
このあたりをサクサク解けるようなライブラリ化したいなーと言うモチベにもなったので、個人的には良い機会でした。
これからも競プロやっていきます*12

*1:合宿当時まだ他の方の参戦は決まって居なかったので、4人で計算してます

*2:当時の記事のdemo画面などでご確認ください

*3:本質でないので脚注に書きますが、Round55のABCDGも解いてあります

*4:別に階段が好きな訳ではないです

*5:詭弁です。本当はもっと頑張りたかったと思っています

*6:実際は咄嗟に余弦定理を思い出すことができず、数式ごにょごにょして余弦定理求めるところから始めた

*7:テキトーに調べて53bitってなんで?と思いながらこう書きましたが、倍精度の仮数部が52bitなので妥当な値な気がしてきた

*8:pythonでもnumpy使えばlong doubleできそうですが競プロで使えるか分からないので未確認

*9:あとクラスカルもありますが。今回は使いません

*10:2011-12-05 - (iwi) { 反省します - TopCoder部 の Doublingの図とか見るとわかりやすいかも?

*11:最大フロー最小カット定理 - Wikipedia

*12:でもそろそろ競プロ以外の趣味コーディングもしたいんですよね。UnityかReactあたり使うヤツももうちょっとやりたい

合宿でUnityを触ったきりだった話

この記事は カレーのち ぴょこりんクラスタ Advent Calendar 2018 - Adventar のために書いたものです。

スマブラのアドベンチャーをクリアして全キャラ解禁しました。
VIP部屋は遠いです。やっていきます。

はじめに

脱出ゲームってあるじゃないですか。
フラッシュゲームが元ネタだと思いますが、ここ数年はリアル脱出ゲームという形でもかなり広まってきた感がありますね。
自分は何度かリアル脱出ゲームのお誘いを受けて遊ぶ機会がまた増えてきたのですが、
謎を解きつつアイテムを集めて少しずつゴールに近づいていく感覚はやはり面白いものです。

本題

既にある合宿参加者の記録 - お菓子食べる部などでも言及されている合宿のころから、
自分はUnityを使って脱出ゲームっぽい者をが作れないか?と思っていました。

結果としては、全然作りきれませんでした

途中経過の内容が以下になります。 https://yaoshimax.github.io/MagicRoomEscape/

やれること

  • 十字キーで移動
  • マウスカーソルで丸い水晶とか紙の目元かランタンとかクリックできる
  • ランタンを取るとItemの所に炎マークがつく
  • ランタンを取った状態で暖炉をチェックすると暖炉に火がつく

今回は、合宿前後で自分が行った事について書いていこうと思います。

合宿前:事前準備

Unityのチュートリアルは玉転がし・シューティング・2Dローグライクあたりまで一度やったことがあったのですが、
完全忘却済みだったので、玉転がしのチュートリアルを再び復習しました。
【Unity 入門】【チュートリアル】玉転がしゲームを作る - コガネブログ

後は、とりあえず部屋を作った上で、
プレイヤーが十字キーで移動ながら、プレイヤー視点でカメラが移動していくような状態を作ろうとリハーサル。

しかし、実はこの時点でいきなり暗礁に乗り上げていました。

はじめはプレイヤーとしてただの円筒形オブジェクトを用意し、オブジェクトにカメラをくっつけ、
その円筒形オブジェクトを操作するscriptを書いて…という実装をしていたのですが、
部屋の隅っこに行った際にうまく止まってくれない現象に長らく悩まされていました。

悪戦苦闘の末、CharacterControllerをつかってプレーヤーを動かす - Taka8’s blogにあるような、
こういうときに使うのにうってつけのControllerがあることに気づき、ようやくスタートラインに立てた気分になります。

ぶっちゃけ、これだけで結構な日数を使ったし、これだけで合宿の準備は終了です。 ただ、これすら調べてない状態で合宿に入っていたら、きっと悲惨なことになっていたでしょうね。

合宿当日

室内のレイアウト周りの調整

ひとまずはリハーサルの成果により、部屋の中を人(with カメラ)が動き回る状態を作り、 その後はアセットストアと戯れながら適当に家具を設置するなどしました。

Unityはアセットを使えばそれなりの見栄えのものができるので、ついつい作業できた気になりますよね。

ただ一方で、イメージに100%合致するアセットはなかなか存在しないのが悩みどころです。

例えば自分の場合「なんか、占い師が使いそうな、丸い水晶みたいなヤツ」が欲しいなぁと思ったところ、 アセットストアでよさげな者を見つけることが意外と難しいものでした*1

仕方がないので、水晶はsphereオブジェクトによさげなテクスチャを張り付けて自動生成。
水晶を乗っけるクッション?みたいな者は、座布団のフリーアセットを流用する、などの運用でカバー案を考えながらレイアウトをしていきました。

あと、暖炉のアセットを壁に埋め込ませようとしたら、継ぎ目の部分がどうしても浮いてしまう、と言う問題にもぶち当たっていたのですが、
これは解決方法が分からなくて諦め。こういうのって皆さんどうしてるんだろう。詳しい人教えてください。

アイテムを見つけて、クリックしたらメッセージが表示される仕組みを作る

ここからはひたすらググりながら実装しています。

  • アイテムにオンマウスで色がハイライトされる
  • クリックすると、別途用意されたレイヤーにテキストオブジェクトが表示される

的な実装です。こう言うと簡単そうですが、 実際にはテキストオブジェクト表示中にさらにプレイヤーが動けちゃったりとか、さらにクリックできちゃったりする現象が発生するので、地味に手間取りました。

クリックでアイテムを取得する仕組みを作る

ググりながら色々と考えつつ実装していきます。

基本的には、先述の「クリックしたらメッセージがでる」仕組みの派生で、 常に描画されてるエリアをつくり、そこに特定条件したでオブジェクト表示をするようにしました。

本当は複数アイテムの取得などの対応も考えたかったのですが、合宿中だったし、シンプルに。 地味に取得したアイテムを非表示にするなどに手間取ったりもしました。

オブジェクト表示についても、本当はアイテムの3Dオブジェクトその者を小さく乗せたかったのですが、 これが結構大変で挫折。

アイテム取得時に特定箇所をクリックするとイベントが発生する仕組みを作る

ランプを持った状態で暖炉をクリックすると暖炉が光る(ランプを投げ込むイメージ)
と言う仕組みを作りました。
このあたりまでくると既存の知識の組み合わせではあったので、割と終了間際にざくざく書いた気がします。
大分実装がごちゃごちゃである自覚は、ある。

おおよそ、合宿中に行えた実装範囲はこのくらいだったかとおもいます。

合宿後にやったこと

合宿メンバーは特に分かると思うんですが、正直あまり進展はないです。

というのも、暗証番号入れたら箱の鍵が開く仕組みを作りたかったんですが、
よさげなアセットがない&自力でやるのが難しくてまごついてます。脱出ゲームとしては個人的に必要不可欠だとおもうんですけどね。。。

というわけで、やったこととしては、

  • 細かなバグ修正(暖炉の火をつけた後にまた暖炉が選択できて、『暖炉の火が消えそうだ』とか言われていた
  • 光源の設置と明るさの調整(合宿時は暖炉の火が小さすぎて全然見えなかった)
  • 棚の扉がクリックで開くようにする
    • 実は直前までこれバグってると思ってて非公開にするつもりだったが、WebGLビルドしてみたら動いていた…
  • WebGLでのコンパイルと公開

あたりです。

終わりに

Unityはアセットの組み合わせで簡単に色々作れると言われますが、
実際は組み合わせ方なり、何もないばあいに自分で作る所なり、結構な地力が必要だなぁと思います。
ただ、プログラマたるもの(?)、ゲームを作るのはやっぱり一度はやってみたいところですし、
今後も引き続き開発できると良いなぁ…と思います。

*1:現時点ではまだ有料アセットを使ってません

ぷよぷよe-sportsセルフ反省会

この記事は カレーのち ぴょこりんクラスタ Advent Calendar 2018 - Adventar のために書いたものです。

今日はスマブラを我慢しました。やっていきます。

はじめに

ぷよぷよってあるじゃ無いですか。
自分は幼少期に初代ぷよぷよ*1 をはじめに触り、
しばしブランクがあったものの、15th Anniversaryで復活し、ぷよぷよフィーバー(クラシック)、20th Anniversaryと遊び続け、
ぷよぷよクロニクル・ぷよぷよテトリスあたりで一端離れ… と、 浮き沈みの激しい遊び方をしていました。

ぷよぷよテトリスあたりで熱が冷めていたのが正直な所だったのですが、
今年になってぷよぷよ日本eスポーツ連合のプロライセンス認定タイトルとなり、
ぷよぷよe-sportsという新しいソフトが発売され…と、
個人的に再びぷよぷよが熱いシーズンを迎えつつあります。

とは言っても、ガチ勢といえる程の実力者では無いため、オンライン対戦ではかなり苦戦を強いられているのですが。

プレイ時間としてはかなりの時間を費やしてきた自負はある*2のですが、
やれどもやれども、なかなか勝てない。漫然とやるだけでは駄目なのだなぁ、と痛感します。

何事も上達するには、過去の失敗を見返して反省し、成長しようと努力しないといけませんね。

と言うわけで今回は、いくつかピックアップしてきた自分のぷよぷよのプレイングのセルフ反省会を行いたいと思います。

ケース1:粘れなかったぷよぷよ

youtu.be 左側が僕です。

行動の説明と振り返り

時間は動画上の時間で表記し、画面右下の時間はつかいません。

  • 0:09:相手の盤面を見て、赤発火の三連鎖(ただし赤が1個)の状態なので紫二色で三連鎖速攻を仕掛ける

ただし、相手のネクス*3・ネクネク*4にそれぞれ赤が1個ずつ含まれていたので、
この判断はあまり正しくありません。実際に今回は、0:13ごろに相手が赤を3つ用意して3連鎖を打たれてしまいました。
たまたま4連鎖・5連鎖では無かったので生きながらえましたが、危なかったですね。

…正直、相手のネクスト・ネクネクまで見るのは滅茶苦茶難しいんですが。修行が必要なところです。

  • 0:14~0:28: 連鎖が作れずモタついたら、追撃連鎖がきたので、とりあえず高く積んどいた

すでに大分雲行きがあやしいですね。0:14時点で赤緑を置きミスしていて、しばらくは以降連鎖の形の再構築に苦戦してました。
0:17時点の赤紫は右から2番目の列に赤を下に縦て置いた方がやりやすかったかも知れません。
少なくとも、 紫青紫青と縦に並んでいる一番右の列は滅茶苦茶使いづらいです。

  • 0:28~0:30:お邪魔画布ったら突然見えてきた紫→緑の連鎖。そして痛恨の段差計算ミス

緑紫が連続している事とお邪魔が降った後の形をみて紫→緑の2連鎖を作ろうと考えました。
しかし、その後においた0:30の赤青の置き方が最悪で、ここで青赤逆に置けば紫→緑→赤→青の4連鎖まで可能だったはずです。
もともとその4連鎖は狙っていたのですが、左から3列目の緑の下のお邪魔ぷよが消えるのを考慮漏れしていました。

  • 0:32~0:37:紫がくることを祈っていたら緑青→緑赤→赤赤→赤青→赤青というツモがきて泣く泣く赤と青を1回ずつ消す

正直これはどうやって組めば良いのかわからなかった。今でも分からない。
とりあえず元の位置に赤を再セットできたので、僕の脳内では紫→緑→赤の3連鎖でした。

  • 0:38~0:42:相手の連鎖に反応して紫を消す。3連鎖のつもりだったが2連鎖になる。

0:28~0:30に起こしていた勘違いがここに来て発覚したわけです。
0:38の赤青で赤を左から3列目において置けば紫→緑赤の同時消し2連鎖になってまだ良かったはずですが
僕の脳内では3連鎖だったため、必死に左から4列目に退避させています。切ない。
退避させるにしたって、3列目に青、4列目に赤としておいた方がまだ良かった気がします。
(そうすると連鎖後に青がしたの方にある青とくっつくので)

  • 0:44~1:15:必死に堪えるターン

0:50で残り4スペースしかないのにツモ3つで紫4つをかろうじてつなげられたのがまず第一に神ツモでした。
その後0:54で相手が落としたお邪魔ぷよが左から3列目に降っていたらそれもまた詰んでいましたが、
別の列(見えない所)に降ったためかろうじてまだ緑が消せて生きて行けそうなきになります*5
後は2連鎖でスペースを確保しながらチマチマとやっていました。
相手の残りぷよ数が少なくて、相手の連鎖数が4連鎖以上になら無かったのにも助けられています。

  • 1:15:本当は3連鎖にできた2連鎖

1:14時点でぷよが1列降る事が分かって居たので紫青を2列目に置きつつ紫→青or緑でなんとか、と思って居る所。
咄嗟に1:15時点の赤ゾロをテキトーに左に置きつつ次の緑青で緑をおいて紫赤で紫を消していますが、
1:15時点の赤ゾロを右に置けばこれは3連鎖にできました。

必死すぎて緑青紫しか注目してなかったんですよね。

  • 1:28 :絶望の置きミス

いい感じに相手の攻撃を牽制していたらそれなりにスペースができてきたので、
紫緑を右から3列目に置いて紫→緑→赤とかの3連鎖を構築予定でしたが、紫緑がなぜか右から2列目に置かれてしまい絶望。
相手から連鎖も飛んできたので、 再び高く構えつつ、紫と緑のどっちか消せばいい気持ちになりながら堪えてます。

  • 1:42~:相手のぷよが殆ど無くなったが、こちらも連鎖が思い浮かばず。暫くして青緑紫赤の4連鎖を考えるも間に合わず

このあたりで大分緊張がきれた感じがありました。
とりあえず振り返っていて思ったのは、1:51の赤紫で謎に赤を消しつつ紫で緑に蓋をしたのが最高に悪い形で、
左から3列目に紫を下に置いとけば、その直後の緑紫を右から3列目に緑を下にして置けば緑→紫赤の同時消し2連鎖ができた。
これならその直後に赤→青の2連鎖も打てていただろうし、この2連鎖同時消しが作れなかったのは痛かった。

ケース2:ワンチャン掘れたはずのぷよぷよ

youtu.be 右側が僕です。短いです。

行動の説明と振り返り

-0:22 :相手から3連鎖飛んでくるが、連鎖を発火するための青が来ないので、黄色を高く詰んでおいた。

こういう攻撃を堪えるために一番右の列の黄色とか青とかが使えれば良いのですが。
今回のツモだと黄色ばっかりでどうしようもナサゲですね。
改めて見ると序盤からかなり空いては組みづらそうな形を組んでいましたし、こちらから速攻を仕掛けても良かった気がします。

-0:30:赤緑3連続の捌き方が思い浮かばず、お邪魔ぷよが3段降れば緑→黃→青→(ry)と連鎖できると信じて赤を消す

当然お邪魔ぷよは3段以上降るので負けます。これは甘えです。

と言うか、今回のツモで言えば、0:26で緑黄色が見えた時点で、以下のようにする事で無駄消しなく連鎖を繋ぐ事が可能でした。 ネクネクを見てから手を変える柔軟性が足りてないのかも知れないな、と言う気持ちになりました。

0:26時点1手目2手目3手目

ケース3:ギリギリ逆転できたぷよぷよ

youtu.be 左側が僕です

行動の説明と振り返り

  • 0:04~0:09:GTRの形を狙ったが思った以上に作りづらい形になってしまった

GTRと言うのはリンク先画像のような形で紫→赤→緑と連鎖をつなげる基本形です。
相手側は僕とは異なり緑→赤→紫のGTRを組んでいるので比較しやすいですが、
僕は最初から3番目におく赤緑を今の形においてしまった為、
紫青→赤赤→紫紫→赤赤というツモを0:09の形のように無理矢理おいてしまっています。
同じ時刻の対戦相手さんの盤面は僕のように赤2個が独立してるなども無く綺麗なのに対し、自分の盤面はかなり悪いですね。

基本的に、3番目のツモを見てから置き場所を相手さんのように組んでいくのが一番だと思います。

が、他に何か手は無いだろうか…と思って少し考えた方法としては、
1手目を今の形で2手目から置き方を変えられる場合は、こう おく手もあったかも。
新GTRみたいな形 が目指せれば一番ですが、
今回のツモだとこうなるみたいな形にするとかだろうか。
紫が分散してしまっているし、思ったほど 良い方法ではないかもしれないけれど、赤2個が離れてないだけましかも。

  • 0:10~ 0:14:連鎖の組み替えと空虚になる右半分

紫紫・青緑をみて連鎖のルートを一番左列の赤→紫→青(これからつなげる)→紫(これからつなげる)とする形に組み替え。 0:14時点で一番左列に青紫と置けば赤発火(緑→赤としても良い)できる下地が整い、直後の青緑で青だけ乗っけてます。
ただ、その代償として右側がすっからかんですね。
あまりでこぼこ憎まない方が大連鎖を組む上では良いとされている(気がする)ので、この形はあまり良くないです。
あと、左から二列目に青を乗っけた都合で緑赤緑赤みたいな奇怪な形ができているのもかなり使いづらかったです。

  • 0:22~0:24:連鎖の最後を緑→赤時得るように作ったけれど紫の置き場を失敗した件

これは置きミスだとリアルタイムでも気づいていませんでした。
0:24時点で連鎖の末尾は緑→赤紫同時消しで確定してしまってますね。
0:24付近の青と紫の位置を逆にするか、こうおいた方が連鎖としては繋がりそうでした。
(より一層でこぼこになるので実際そうした方が良いのかはわからないけど。。。

  • 0:26 :おじゃまぷよが降ってきたことでこの後どう組んだら良いかわからなくなる。

お邪魔は全ての計算を狂わせるんですよね。多分元々は右から3列目に青を置くつもりだった気がします。
が、そもそも青がそうそう来ないし、赤赤や緑緑のツモを処理する方法が分からず、結局適当においちゃってます。
後後の意味では英断だったのは、お邪魔が怖くなったのでこのタイミングで一番左上に紫をセットし、
本線を赤1個or緑3個で消せるようにしてたこと、くらいですかね。

  • 0:39 :相手の3連鎖に為す術が無い

赤1個or緑3個で本線が発火できるといったものの、周囲の色を巻き込まないためには結構都合の良い置き方が限られました。
そもそもその形が悪いと言う話はあるんですが、3連鎖をきても何をする事もできないし、
当時は右半分どうしたら連鎖繋がるか考えるのに必死だったので、雰囲気詰んで後は堪えてから考えることに。

  • 0:40: とりあえず紫を消したら意図せず3連鎖になり良い形になったし、相手は本線を発火していた

青が消えるのは正直予想してなかったです。が、どちらかと言えばもっと嬉しかった副作用があり
0:45時点で、発火させづらかった赤が青→赤と消せるルートが開拓されていました。

これがなかったら勝てなかったと思います。

  • 0:45~:気合いでその後連鎖をつなげて発火する

時間的にどのくらい迄かとかは相手の連鎖を見えてないので雰囲気で紫まで挟んでから発火。
結果的には最後の赤紫同時消しが功を奏して火力勝ち。

…と、まぁ、結果的には勝ちを収めていますが

(1) 相手のお邪魔が降らなかったら本線を発火させるのが大分辛い形になっていた
(2) そもそも右半分の形を綺麗に組めていなかった

と言うあたりは滅茶苦茶反省点だな、と思います。

おわりに

言葉でぷよの「こここうすればよかった」説明するの凄いムズいですね。伝わらなかったらすみません*6

ちなみにこの後、撮れ高を求めて遊び続けていたら階級も2段階落ちたしレートも100位下がりました。
復習するのもそうだし、ムキになっってやけくそ連鎖を打たないようなメンタル強化も必要そうですね。。。

*1:相殺なんて無かった。これはこれで意外と戦術があり面白いのでぷよm@sでググってください

*2:ぷよぷよサークルで百本先取とか何回かやってた時期もあります。5時間ぶっ通しでぷよぷよするの大分ハードでした

*3:次に引くぷよのことです

*4:次の次に引くぷよのことです

*5:こう言うの、潔く負けろと言われる人も多いのですが、個人的にはワンチャン拾える可能性があるなら拾うよう努力する派です

*6:ぴょこりんさんはぷよぷよができる人なので伝わっているはずです

減量に一応成功したが最近伸び悩んでいる話

この記事は カレーのち ぴょこりんクラスタ Advent Calendar 2018 - Adventar のために書いたものです。

スマブラしていたら体調を崩しました。やっていきます。

はじめに

体重ってあるじゃないですか。
自分は数年前くらいからじわじわと増加を感じていたのですけれど、
今年は流石にいい加減健康にならなくては、というケツイを胸に抱き、減量のため努力しました。

f:id:yaoshimax:20181211173648p:plain:h300
6~8月で78kgくらいから69kgくらいまでがっつり落ちた

6月の減少の仕方が凄いですよね。自分でもよく頑張ったなぁと思うと共に、
こんなに効果があるものか、と驚いた出来事でもありました。

で、なぜこんなに急激な減量に成功したかと言いますと。
間食や晩酌の数を減らしたと言うのももちろんあるのですが、とりわけ心の支えだったのが…

f:id:yaoshimax:20140310114828j:plain:w300
SUBWAY!!!!
はい、SUBWAYです。
昼食として野菜を上限*1にしたサンドイッチを食べ続けたのが、かなり効果的だったと思います。
トッピング・ドレッシングの変更などもできるので、はじめ数ヶ月は飽きること無くずっとSUBWAYに通い詰めていました。

…とは、言ったものの。そんな状態がずっと続くわけでもなく。

f:id:yaoshimax:20181211174704p:plain:h300
9月以降の中盤の伸びが怪しい
9月あたりからSUBWAYに行くことがなくなり始め、身体も徐々に緩んでくるようになりました。

SUBWAYの手前にコンビニがあるので、つい移動を面倒くさがってミックスサンド*2を買ってしまうようになり、 それが徐々にもの足らなくなり食べる量が増え…と、完全に堕落の一途をたどっている今日この頃です。

健康面などを考慮して、SUBWAYモチベをもう少し高めたい気になりました。

本題

と言うわけで、SUBWAYのメニューからカスタマイズしたい内容を選択したら
その結果のカロリーとお値段がわかるスマホアプリを作りました。

github.com

デモ

https://github.com/yaoshimax/SubwayCalorieCalculator/raw/movie/movie/demo.gif

以下は、作るまでの流れなどを軽く書いておきます。

下準備:カロリーの算出方法

調査

SUBWAYは結構丁寧にカロリー表示してくれています。
栄養情報PDF:https://www.subway.co.jp/menu/pdf/eiyo.pdf

このデータを見ると、

  • サンドイッチ全体(全部お勧め設定)のカロリー
  • パンのカロリー
  • ドレッシングのカロリー

がわかります。 全体のカロリー=パン+具+野菜+ドレッシングなので 野菜+具のカロリーは単純な引き算で計算できそうです。

…で、野菜って結局何カロリーあるんだ?と言う話なんですが。 結論から言うと、ここが良くわかりませんでした。

日本の栄養情報には野菜ごとのカロリーは記載されてないし、
一部メニューはトッピングとして具のカロリーが記載されているのでその値から野菜のカロリーを逆算する手も考えましたが、
いまいち帳尻の合う値になら無くて挫折(多分トッピングorメインで枚数なり分量なり違う)。

英語サイトでは、各メニュー↓のnutrition calculatorを見れば「VEGGIES」を選択できるのですが、
Menu - Black Forest Ham | SUBWAY.com - United States (English)
日本とは野菜の種類が異なり、にんじんの項目が存在しないし、
そもそも同じ名前のサンドイッチでもカロリーが異なる*3し、どのくらい真に受けて良いのかわかりません。

とりあえず参考情報として、英語サイト的には、レタスとトマトだけ10 kcalで他は0 kcalで計上されているようでした。

雑な仮定

結局は何が正しいのかは良くわからないので、

  • レタスとトマトは他の野菜より2倍程度カロリーが多い
  • レタス・トマト・にんじん・ピーマン・レッドオニオンを入れると15kcalくらいになる*4

という思い切った仮定をおいて、レタス・トマト=4kcal、にんじん・ピーマン・レッドオニオンを2kcalとして計算し、野菜以外の具のカロリーを算出することにしました。

f:id:yaoshimax:20181211181555p:plain:w500
雑な計算をするスプレッドシート

ちなみに、全体のカロリーは全てお勧めの設定で行われているので、
お勧めの組み合わせ=写真に掲示されている組み合わせと(これまた)仮定をおき、
使われているパンと野菜を目力で推定して入れています*5
ホワイトとウィートの違いとか全然わからないし、思った以上に人力で頑張る形になりかなり心が折れつつあったんですが、
雰囲気分かれば良いよねと割り切って実装をしていきます。

実装

カロリーの値を決める所まででかなり大変になりましたが、実装です。 react-nativeでガシガシ書きました。

パンと具材は1個しか選びようがないので、pickerを使い、
野菜・トッピング・ドレッシング*6などの複数選択させる方には、 react-native-label-selectを使っています。

実は、複数選択させる方はかなり鬼門でした。
はじめはreact-native-multiple-selectを使うつもりだったのですが、
どうあがいても自環境では文字が表示されなくて、label-selectに突貫工事で書き換えています。

しかも、react-native-label-selectの方もメンテがされて無くて、
issueで報告されているように、react v15.5以降では動きません。
結局、node_modules下のsrcファイルを修正PRと同じように書き換えて動作させています。

おわりに

まだまだ実用にはほど遠いですが、
せっかくだし一回くらいスマホアプリ作りたかった、という欲求を少しだけ満たせて楽しかったです。
以下のTODOを残してしまったのは心残りですが、気が向いたらやっていきたいと思います

  • サンドイッチを選んだときに野菜やパンを全部お勧めのものに上書きする機能
  • 具材の写真とか載せたい(でもPicker/label-selectの仕様的にむずそう)
  • 野菜全部、はオプションでワンクリックで設定させたい
  • 野菜の分量でちょこっとカロリー増減させたい(厳密計算難しい領域だし大して変わらない気がするので優先度下げちゃった)
  • リリースビルドしてスマホ単独で動作できるようにする
  • 季節限定メニューの内容を持ってこれるようにする(写真から目力で推定するところで詰むのでブレイクスルーが必要)

*1:『野菜上限で」でお店の人にも通じます。量には個人差があります

*2:カロリー的にSUBWAYと大差ないあたりを探すとこのあたりに行き着く

*3:例えば日本のターキーブレストレギュラーサイズは264kcalですが、英語サイトの方では280kcal

*4:海外で20kcalなら日本のはもう少し少ないだろう読み

*5:常に野菜全部入れてたからローストビーフにトマト入ってないのにこの段階で気づきました。当時一律計算させようとしてたから割と絶望

*6:ドレッシングもミックスできるので一応複数選択可能にしました

Educational Codeforces Roundをやっていきたい話

この記事は カレーのち ぴょこりんクラスタ Advent Calendar 2018 - Adventar のために書いたものです。

ぴょこりんクラスタ新人です。よろしくおねがいします。

はじめに

競技プログラミング(以降、競プロ)ってあるじゃないですか。
自分は競プロを細々と続けてるんですけど、

  • 学生当時最大手だったサイト TopCoder の衰退
  • 周囲レベルの高騰
  • 時間とれない

あたりの理由で、最近はあまり思ったように活動できてない自覚があります。

せっかくアドベントカレンダー書くんだし、12月を通して少し修行しようと思いまして。
知り合いのレッドコーダー*1にお勧めされた、Educational Codeforces Roundをやっていきたい気分になりました。

Educational Codeforces Roundというのは Dashboard - Educational Codeforces Round 1 - Codeforces などのことで、
教育的な問題の詰め合わせらしいです。
リンクはRound1ですが、現時点ではRound 55まで存在しています。

しかし、やっていきたい気持ちになったものの、
漫然とやるだけだと達成感が足りないので、やっていきを高める必要があります。

本題

Educational Codeforces Roundの解いたものがわかるような進捗可視化ツールを作りました。

github.com

デモ

起動が遅かったりマウス操作が雑で所定のオンマウスになった絵がとれてなかったりしますが。大体これで察して欲しい。 https://github.com/yaoshimax/progconviewer/raw/media/media/demo.gif

雑な説明

仕様
  • 何かstartしたらブラウザが開いて問題一覧が表示される
  • 解けたか解けてないか未着手かで色分けがされる(誤答投げまくった時用にaccept数/submit数も表示させといた)
  • 問題番号をクリックしたら所定の問題リンクへと飛ぶ

これだけ。

実装

codeforcesが各種情報取得APIを提供している*2ので、
それをnodejsでたたけるライブラリ*3をつかいます。

コンテスト情報からEducational Codeforces Roundsと言う名前のあるコンテストを取ってきておいて、
別途、問題情報と解答投稿情報から各問題が解けたか解けないかの情報を作っておいて、
後者を前者でフィルタしつつ、Reactでよしなに表示するだけです。

コンテストページを探すのは地味に面倒*4なので、 これだけでもあると便利だと思います。

こぼれ話

本当は点数順に並び替えもやりたかったけどEducational Roundの問題には点数が設定されてなかった為断念しました。
ReactはじめてなのでTutorial触りつつ雰囲気で書いたんですが、動くものができるのはやっぱり楽しいですね。
ちなみにReactにしたのは、自分がこれまでに触ったことのない&それなりに流行ってそうなもの、という理由。
今回使ってみた感想としては、Webページをパーツごとに定義しながら組み立てていく感じは割と好みかも知れない。

しかし、いざ表示させてみると明らかなんですが、
Educational Round、2018/12/05時点で、55コンテスト*大体6問以上なので、330問以上はあるんですよね。。

………

………………

………………………………

マルス理論
一日30問ずつ倒せばいけるか…?

どう見ても無理です*5。本当にありがとうございました。

そもそもペース配分を考えるなら Advent Calendar Contest 2018 - yukicoder にすべきなんですよね。

おわりに

競プロネタ、やろうと思うと無限にネタが提供できてしまい面白くないので、
12/22に結局Educational Roundどのくらい解いたの?の話をする以外、プロコンの話は封印します。

ネタはもちろんこれから作ります。やっていきます。

*1:競プロが強い人のことです。大体はヤバい

*2:https://codeforces.com/api/help

*3:https://www.npmjs.com/package/codeforces-api

*4:linkの番号とcontestの番号が一致しないので、ググって出す以外の良いリンクの探し方を僕は知らない

*5:スマブラ楽しみですね