AOJ実はこれやったのが期末考査直前だったので、かなり適当に解いてます。秤につけた重りの重さと位置情報が与えられるので(0が支点)、秤を釣り合わせる為に重りを追加してください。重りを沢山つけてもいいですが、適当な重さの重りを-1か1の位置につければ釣り合います。入力で(位置)×(重さ)の情報を加算していき、その結果が正なら-1、負なら1の位置に結果の絶対値の重さの重りをつければ終了。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に変えます。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なはず。Scanner問題概要3台のスキャナーでN枚の紙を読み込む。i枚目の紙はT[i]秒かかるらしい。紙の順番を自由に変えた時、N枚の紙を読み終わるまで最短何秒かかるか。始めは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以降はテストが終わり次第進めたいと思います。日)ネットの海に生息するらしいバーチャルグソクムシ。競プロとCTFをメインに、たまにEsolangを混ぜます。(7)月別アーカイブリンクGitHubはてなブログをはじめよう!Hyogaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。