AtCoder Grand Contest 014 D - Black and White Tree
N頂点からなる木について、交互に白黒白と色を塗っていくゲームをする。最後に1回だけ、黒が隣接している白の点を一斉に黒にする。この時白が残っていれば白の勝ちである。最適に行動したときにどちらが勝つか求めよ。
木の葉が2個以上ある節が存在すれば勝ち確定である(※)。そうでない時は、頂点が2n個の直線状に並んでいるところについて、葉の一歩手前に白を置くと、黒は葉に置かないと「-○-○」(右端が葉)のような形を作られて白が勝ち確定であるので、葉に置くという行動が最適解になる。「-○-●」よってこのような形になったあと、この部分は無視してよく、結果として2n個の直線状に並んでいるところはどんどん頂点を削除していこう。そういう操作を続けていった結果、(※)の状態が現れた、もしくは1点のみになった時点で白の勝ち、それ以外は黒の勝ちである。
実装としてはdfsで直線上のところは頂点の偶奇をつけておき、そうでないところは子が奇数の点をカウントし、2個以上あったら白の勝ち確定、それ以外は奇数の数を親ノードに返す、みたいなことをする。O(N)。
Codeforces 411 Div.1C Ice cream coloring
ツリーTが与えられて、Tの各頂点v[i]にアイスクリームの集合s[i]が与えられる。同一のアイスが含まれる頂点だけからなる部分グラフは連結である。この時、新しいアイスの集合を頂点とするグラフGを、Tのある頂点v[i]があって、アイスaとアイスbがs[i]に含まれるならば、aとbの間に無向エッジを貼る。この時、Gの最小Coloringを構成せよ。
Gにおいて、Tの各頂点に対応するs[i]に含まれる元ついてはクリークとなる。さらに、部分グラフが連結であるという条件から、二つのクリーク同士を接続する頂点集合もクリークとなる(つまり二つの独立したクリークで接続されていることはない)。なのでクリークごとに貪欲に色を決めていけば良い。
つまり、dfsで各クリークを見ていったとして、その時点で着色可能であった色が、別の頂点の探索中で棄却されることはない。
そのためTのある頂点からdfsする。今見ている頂点がGのクリークに対応する。Colorを数字で表した時、既に着色済みの頂点を除いて小さい方から貪欲に色をつけていく。O(V)。
AtCoder Regular Contest 073 E: Ball Coloring
(x[i], y[i]) (1≦i≦N) が与えられる。任意の点について、xとyを交換できるとき、これらの点をすべて含み、辺がx軸またはy軸に平行な長方形の面積の最小値を求めよ。
まずすべての点についてx[i]≦y[i]となるようにしておく。この時をminX, maxYとするとき、次の2パターンが存在する。
- max(y[i]) - min(x[i]) の長さの辺がある
- 角の座標が(min(x[i]), max(y[i]))となる
2の場合はもう一つの角の座標が(max(x[i]), min(y[i])) なので、これで面積が出る。
1の場合は残りの辺の最大の高さh=max(x[i])として、x[i]を小さい方から見ていき、h - x[i] をもう一方の辺の長さとして面積を計算する。hは今見ているx[i]に対応するy[i]とのmaxを取り更新、次の辺について調べる。x[i]がmin(y[i])を超えない範囲で調べた後、min(y[i])が角のy座標になるパターンも調べてそれぞれの最小値を求める。O(N)。
Google Code Jam 2017 Round 1-C A
Dashboard - Round 1C 2017 - Google Code Jam
円柱型のパンケーキをN枚の中からK枚選択して、大きい順に重ねたとき底面を除いた表面積を最大化せよという問題。
まず側面を除いた面積は最大の半径を持つパンケーキの上面の面積に等しい。なので、パンケーキを側面の面積順でソートすると、大きい順にからK-1枚は常に選ぶ必要がある。残りの自由度はパンケーキ1枚なので、総当りする。
最初に選んだパンケーキK-1枚の中の最大の半径を取得しておき、総当たりのパンケーキの半径とmaxをとるとそれが上面の円の半径。この半径と、今見ているパンケーキの側面積と、元々選んだK-1枚の側面の面積が今見ているセットの総表面積になる。O(N)。
RのProxy設定
RのProxy設定はぐぐると色々出ては来るのですが、それでもトラブルが多いのでメモ。
まず同じProxyでも以下のパターンが存在します。
- Proxyのホストとポートを指定し、Proxy自体に認証はなし
- Proxyのホストとポートを指定し、Proxy自体に認証がある
- pacスクリプトによるProxy設定で、Proxy自体に認証がある
(pacスクリプトで、かつ認証なしのパターンはあんまり聞いたことないです)
まずpacスクリプトによる設定の場合は、本来社内LANへの接続をProxy側で判断すべきところをクライアントのスクリプトに任せているだけというパターンが多いので、pacスクリプトの中身を見てやれば、CRANのインストール等は結局2に集約されるかと思います。
さて、Windows上のRのProxy設定ですが、確証はないものの以下の2個の設定のいずれかが有効になるようです。
R+RStudioで使っている限りでは2が優先的に認識されているような感じがします。
(が、ネット上の情報では1が書かれているパターンが多いです。)
さらに認証については http_proxy_user = ask と環境変数を設定することで、認証ダイアログが開く、みたいな記述があります。
(が、これもたまに有効にならなかったりします。)
また認証付きProxyの場合のめんどくさい要素として、認証パスワードの定期変更があるかと思います。そのため、RだけでなくGitやnpm, pipなどのProxy設定を毎回書き換える必要があり、かつ平文で記述されたパスワードが至る所に散乱しているので精神衛生上もよくありません。
そこでおすすめしたいのが、Fidderを使った認証付きパスワードの一元化です。
Fiddlerは下記のサイトで入手できるいわゆるローカルProxyです。
http://www.telerik.com/fiddler
これにFidder Scriptというのがありますので、このScriptのOnBeforeRequestのところでProxy-Authneticationヘッダーを付与してしまいましょう。
やり方としては以下のQiitaに書いてありますが、これは固定値埋め込みになっています。
Script自体はC#チックですので、環境変数にパスワードとIDを書いておくと、そこから読み込んでBASE64エンコーディングした値を入れてやる、という方法もあります。
Visual Studio Codeを認証付きProxy環境下で使う
— あやせひろみ (@hiromi_ayase) 2017年4月7日
1. Fiddlerをインストール
2. Scriptタブから画像のコードを書いてSave Script
3. 環境変数 http.proxyAuthorization に<ユーザ名>:<パスワード> を設定 pic.twitter.com/kqWpGK5Ifu
これで設定し、Fidderを起動するとhttp://localhost:8888 にローカルProxyができますので、これをシステムProxyと環境変数http_proxy等に設定してあげることでCRANへのアクセスもProxy環境下でも可能になります。
TopCoder Open Marathon Match Round1
グラフのノード及びエッジ、そのエッジの「長さ」が与えられる。このグラフのノードを700x700の整数座標に配置するときに、エッジの「長さ」になるべく近くなるような配置を求めよ。
私はエッジをバネと見立てた力学系のモデルを組んでみました。そして全体が安定したらスコアに影響する辺をランダムで移動させるというもの。スコア的には微妙で余り時間もとれませんでしたが楽しかったです。
一位の人の戦略は公開されていてとても参考になる感じ。
square869120Contest #4 C - Calendar 2
昔解いた問題の忘備録。
a[i]が与えられる。幅7マスでn行あるカレンダーについて、すべてのa[i]について、mで割った余りがa[i]であるようなマスを黒く塗る時の連結成分の個数を求める問題。
まず最初に7nがmの倍数であるようにa[i]を調整しよう。(a mod x を a mod yにするのはそれほど難しくない)。その状況で実際に実験してみる。すると連結成分の数がある種の1次関数になっていることがわかる。その為、切片と傾きを求めて終わり。
まず連結成分の数が1次関数になるということは感覚ではわかるが証明はぱっと思いつかない。でも競プロではある程度自明なことはそのまま信じよう。次に塗りつぶし系は実験が大事。こういう問題ではまずロジックを考えるのではなく愚直に実行して可視化してみるべき。
