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もやらなくてはならないので忙しい…)

AOJ0010:Circumscribed Circle of a Triangle

暫く競プロが疎遠になっていますが、ちょっと幾何の基礎を。

問題概要

xy平面上の3点の座標が与えられるので、3点を頂点とする三角系の外接円の中心と半径を求めよ。

Circumscribed Circle of a Triangle | Aizu Online Judge

続きを読む