CodeForces378_C (div.2)

久々にCodeForcesに参加しました。

C問題の問題文: http://codeforces.com/contest/733/problem/C


モンスターが食べる、食べられると、互いの体重を足した1つの値になり、順番は入れ替わることはないので

左端から体重(aで与えられる数列)を足していき、bで与えられる数列と一致するかを見ていきました。

この時に、各bの要素を構成するaの部分列が全て同じ値の場合は食べる、食べられることができないので、チェックする必要があります。


次に、モンスターが食べる、食べられる際にはどのモンスターがどちらのモンスター(左か右)を食べるかを列挙する必要があります。

この処理がだいぶ面倒なのですが、まず、aの部分列の中で1回食べた時に体重が1番重くなるモンスターを探します。

そのモンスターを起点に、最初に左を食べた時は左を食べ続けてから右を食べる、 最初に右を食べた時は右を食べ続けてから左を食べる操作を行います。

こうすると、一回食べた時のモンスターの位置のずれ方が、1つ小さくなる(左を食べる時)、またはそのままになる(右を食べる時)ので出力するときが楽になります。


最後に、bの各要素をaの部分列で生成するので、bの数列が出来た場合にもaの数列がまだ残っている場合があります。

この場合にも"NO"を出力する必要があるので、縮めていったaの数列とbの数列の長さが一致するかを見て、最後出力を行っています。(この処理を書いていなくて、一回test13で落ちました。)

第3回 mixi git challengeに参加してきました

git challengeとは


gitを使っていく上での問題(conflictの解決など)について、解決を試みるchallengeで、正誤判定にはCircleCIという継続的インテグレーションを行うツールを用いて判定を行っていました。
自分ではこういったツールを使ったことがなかったので、すごいな・・となっていました。
問題の難易度別に星の数が決まっており、解いた問題の星の数で順位が決定されます。
alpha.mixi.co.jp

参加したきっかけについて


自分のgit経験では、研究や趣味で書いているコードを個人的に管理するために使っているぐらいで、実際にconfilictの解決などといったことはあまりやったことがありませんでした。
実際の開発現場で起こったような問題を題材にして問題が作られているとのことだったので、そういった問題について取り組んでみたいと思い、応募しました。
交通費についても半額出していただけるので非常にありがたかったです。

参加してみて


午前中はキーノートで、Poiboyの開発ではどのようにgitを使っているかという話を聞きました。 午後からはgit challengeでした。最初の方の問題から躓いてしまったのですが、スタッフの方に助けてもらい、なんとか問題を解くことができました😢
星2の問題についても解くことができたので少しは力になれたかなと思いました。
結果については、ペアの方のおかげでなんと優勝することができました・・!

ランチ・懇親会についても、美味しくご飯を食べながら、スタッフの方や参加者の方とたくさん話をすることができたので良かったです。 f:id:accelation:20160822160054j:plain:w300 f:id:accelation:20160822160107j:plain:w300

最後に


今まで使ったことないようなgitの便利なサブコマンド(git show, git rev-listなど)について学ぶことができました。
また、gitの内部構造についても少し知ることができたのでよかったです。そしてこれからも精進していきたいと感じました。
最後になりますが、イベントを開催してくださった皆様に感謝の気持ちでいっぱいです。ありがとうございました!!
f:id:accelation:20160822182551j:plain:w300

SRM 695 div2 med

問題文:
https://community.topcoder.com/stat?c=problem_statement&pm=14366

まず、生成するパスワードを空文字列で初期化を行い、“constant strings”を長さの長い方(vectorの後ろ)から連結していきました。

”aaa”の後にまた”aaa”を連結してしまうと長さ6のconstant stringsが出来てしまうので、生成している文字列の1番最後を見て、aだった場合はb, bだった場合はaから始まるconstant stringsをくっつけるようにしました。

constant stringsを連結する際に、”aaaa”の場合は、
“aaa”x2, “aa”x3, “a”x4
のconstant stringsを含むので、与えられた引数のvectorからそれぞれの数を引くようにしました。
途中で負の値が出てしまった場合には生成することができないので、空文字列を返します。

最後に、x = {1, 0}といった場合にパスワードの長さが足りないので
文字列を返すときに与えられたvectorと生成したパスワードの長さが一致するかを見ています。

ABC025: C - 双子と○×ゲーム

問題文
C: 双子と○×ゲーム - AtCoder Beginner Contest 025 | AtCoder

ゲーム木の探索で、まだゲーム木の探索を書いたことがなかったので
解説スライドを見ながら、実装を行いました。

score = 直大さんの点数 - 直子さんの点数

とすることで、2つの点数を同時に扱うことができて、
直大さんのターンではscoreを最大化、直子さんのターンではscoreを最小化
になるように探索を行いました。

Planetary Exploration

0560: Planetary Exploration
Planetary Exploration | Aizu Online Judge

まずm*nのJ, O, Iのいずれかの文字の入った長方形領域の情報が与えられ、左上が(a, b)・右下が(c, d)となるような長方形領域の中にあるJ, O, Iの数をそれぞれ出力するような問題でした。
今回は3次元配列を用意して、J, O, Iについてそれぞれの累積和を計算しました。

もし女子大生プログラマに『アルゴリズム』を図解で教えるとしたら - paiza開発日誌
2次元の累積和の計算については、この記事がすごくわかりやすく書いてあったので参考になりました。

Dangerous Bridge

0231: Dangerous Bridge
Dangerous Bridge | Aizu Online Judge
体重mの通行人が橋を時刻aに渡りはじめ、時刻bに渡り終わるという情報がn個与えられ、その情報から通行人の体重の総和が150を超えるかどうかを判定する問題でした。
0 <= a, b < 2^31(=2147483648)となっている一方、nは(1 <= n <= 100)で100個しか情報がなかったので
bridgeをmapとして、bridge[渡り始める時間] = 体重
として累積和を計算しました。
また、渡り終わる時間は逆に体重を引けば同様に計算できます。

A Traveler

0549: A Traveler
A Traveler | Aizu Online Judge

累積和を使う問題(使わなくても通りましたが・・)でした。
distancesをi番目の町までの距離とすると、たとえば1~3番目までの距離はdistances[3] - distances[1]で素早く求めることができます。