AtCoder Regular Contest 049
WAするんじゃないかとヒヤヒヤしながらの提出だった…3完。18位と史上初の20位以内に入り込めました。
続きを読むAtCoder Beginner Contest 034
全完だけど、時間かけすぎた…特にC問題。
続きを読むyukicoder yukicoder no.349/350/351/352
3問目が分からなかった。つらい。最近競プロ出来てないからな…
続きを読むRUPC2016 Day1 A~D問題
実はこれやったのが期末考査直前だったので、かなり適当に解いてます。
A: 秤 / Steelyard
問題概要
秤につけた重りの重さと位置情報が与えられるので(0が支点)、秤を釣り合わせる為に重りを追加してください。
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=A
解説
重りを沢山つけてもいいですが、適当な重さの重りを-1か1の位置につければ釣り合います。
入力で(位置)×(重さ)の情報を加算していき、その結果が正なら-1、負なら1の位置に結果の絶対値の重さの重りをつければ終了。
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=1693093&cid=RitsCamp16Day1
B: ハミング距離 / Hamming Distance
問題概要
0と1からなる文字列が与えられます。リーディング0を許して2進数読みをしたとき、入力と違う桁数がDで、最も大きな2進数を出力してください。
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=B
解説
まず、左にあれば左にあるほどその桁が1であれば嬉しいです。逆に、右側の数字は正直どうでもいい。
ということで、まずは0だったものは左から順に変えられるだけ1にしてしまいましょう。
その後、Dが余るのであれば右から元々1だったものを0に変えます。
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=1693103&cid=RitsCamp16Day1
C: 足し算掛け算 / AddMul
問題概要
a〜zのアルファベットと+からなる数式があります。0〜9の数字と()、*を使うことで、数式の文字数を最小にした時の文字数を求めてください。
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=C
解説
まず、a〜zはそれぞれ9個以下らしいので、アルファベットごとにまとめます。
ここで、a*2+b*2と(a+b)*2は7文字で同じですが、a*2+b*2+c*2と(a+b+c)*2は()を用いたほうが得です。
また、(a+b+b)*2とa*2+b*4は()を用いないほうがいいです。
これらを用いると、「アルファベットの係数が同じなら()でくくる」という結論が出ます。
計算としては、各係数に何種類のアルファベットが該当するかを算出して、
- 該当アルファベットが1種類:+3文字(係数が1なら-2字)
- 該当アルファベットが2種以上:2*(アルファベット数)+3(係数が1なら-4)
という感じでやればOKなはず。(上の奴は項間の+は考慮してないので後で足してください)
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=1693158&cid=RitsCamp16Day1
この問題って、姉さん6番目の計算出来ないと解けないですよね…
D: スキャナー / Scanner
問題概要
3台のスキャナーでN枚の紙を読み込む。i枚目の紙はT[i]秒かかるらしい。
紙の順番を自由に変えた時、N枚の紙を読み終わるまで最短何秒かかるか。
http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=D
解説
始めは2分探索だと思い、1台ずつmed秒以内に読めるだけ紙を読んでリストから消し、ということをやって3台で全部消費できるか、という方針でしたが、サンプルに落とされました。(その時のコードが120行台…)
ということで、再帰を使って見ると、普通にメモ再帰で必要な配列は50*2500*2500*2500のbool型。これだと絶対に間に合いません。
ここで、bool型が無駄なので、
dp[i][j][k]:i枚目をどのスキャナーに読ませるか悩んでいるとき、1台目はj秒、2台目はk秒を消費している時の3台目が消費している最小のもの
とすると、DPが使えます。(個人的には物凄く無駄な感じがしますが、これで時間内に収まりそうです)
あとは、dp[N][j][k]、j、kの中での最大値を、j、kを変えながらこれらの最小値を求めれば答えが求まります。
MLEするので、配列はiを使い回してください。
http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=1694382&cid=RitsCamp16Day1
感想
D問題やられた…
E以降はテストが終わり次第進めたいと思います。(ただし、そろそろ3DCGもやらなくてはならないので忙しい…)
SRM683 Round1 Div.2
無事に全完。
続きを読むAOJ0012: A Point in a Triangle
もう1つやっていたので。
問題概要
3点a,b,cからなる三角形の中に点pが入っているか(線上は入っていない扱い)を求めよ。
A Point in a Triangle | Aizu Online Judge
続きを読むAOJ0010:Circumscribed Circle of a Triangle
暫く競プロが疎遠になっていますが、ちょっと幾何の基礎を。
問題概要
xy平面上の3点の座標が与えられるので、3点を頂点とする三角系の外接円の中心と半径を求めよ。
Circumscribed Circle of a Triangle | Aizu Online Judge
続きを読む