A問題：at-corderのレーティング判定
M-SOLUTIONS プロコンオープン 2020
A問題
Q in at-corder
問題文
M君は、at-corderに参加している選手の一人です。
彼の最高レーティングは、Xです。
at-corderでは、最高レーティングに応じて選手に9位が与えられます。
レーティング400以上、1999以下については、以下の通りです。
M君は、1級から8級まであります。
400以上、599以下が8、600以上、799以下が7、という風になっています。
M君は、何級を持っていますか?
これは、そのまま、コピペしたのを、if文にして、ぶっこむだけですかね。
Nイコール、intのインプットを、
あれ?
かっこいい。
かっこが出てこない。
あ、出てきた。
int、input、
で、そのままさっきのコピー、
ああ、するとバグるのか。
バグるというか、表示がおかしくなるので、
1個ずつ書きますか。
if、400以上、599以下。
400以上、Nが、
599、600にしとくか。
600より少なかったら、
アンサーが、イコール、0にしといて、
一番最後にまとめて、プリントアンサーにしよう。
400以上、600未満が、8。
600以上、800未満が、7。
アンスイコール、8。
if、lif、Nが、
700?800って言った?
800だね。
800未満だったら、アンサーは、7。
lif、Nが、1000かな、たぶん。
1000ですね。999以下。
1000以下が、アンサーは、6。
lif、1200未満かな、たぶん。
アンサーは、5。
lif、N。
1400未満、アンサーは、4。
繰り返しですね、もうこれは。
N、1600未満、アンサーは、
lif、1800未満、アンサーは、2。
400から1999まで与えられるから、
もうそっから先は考えないでいいね。
lif、
Nが、2000未満だったら、アンサーイコール、1。
うん、ちょっとコードテスト試すのめんどくさいんで、このまま出してみます。
はい、ACしたので、B問題に行きます。
B問題、マジック2、1は、問題文。
M君は、以下の3枚のカードを持っています。
整数Aが書かれた赤のカード。
整数Bが書かれた緑のカード。
整数Cが書かれた青のカード。
彼は、天才的な魔術師なので、以下の操作を軽快まで行うことができます。
3枚のうち、いずれか1枚のカードを選び、書かれた整数を2倍する。
操作を行った後、以下の条件が同時に満たされれば、魔術は成功です。
緑のカードに書かれている整数は、赤のカードに書かれている整数より真に大きい。
青のカードに書かれている整数は、緑のカードに書かれている整数より真に大きい。
魔術を成功させることができるかどうか、判定してください。
制約は7以下なので、
もうこれは思いつくことをバッとやれば解けそうですね。
A、B、Cを受け取ります。
マップのイント、インプット、ドットスプリット。
軽快操作できます。
イントのインプット。
入力例。
7・2・5で3回操作できます。
答えはイエス。
例えば、以下のように操作を行った場合、魔術を成功させることができます。
1回目、青のカードを選ぶ。
赤のカードには7、緑には2、青には10。
2回目、緑のカードを選ぶ。
赤には7、緑には4、青には10。
3回目、緑のカードを選ぶ。
赤には7、緑には8、青には10。
うーん。
緑のカードに書かれている整数は赤のカードに書かれている整数より真に大きい
だから
ホワイインレンジ警戒やって
警戒まで行うことができるだから
まあいいか
クリア条件は
緑が
赤緑青の順で小さければいいかな
青が緑よりでかい
緑が赤よりでかいなので
そうですね
if
a小なり
b小なり
cだったら
exit
print
yes
どうしようかな
まず
if
aが
bが
bより
小さかったら
でその中で
いや
ほんと
逆にするか
aが
bより大きかったら
bかけるイコール2
if
いや
違うな
lif
cが
bより小さかったら
だから
b大なり
cだったら
cかけるイコール2
でプリント
no
んーと
このprintyesのif文
一番最後にしときましょうか
for文の中の
で入力例1はyes
入力例2はno
お?
あ、noが出ました
んー
ちょっと
怪しいですが
出してみましょうか
一応
少々不安なところ
やっぱりわが出た
えーーーと
b問題
何個間違えてる?
5個間違えてる
ので
以下の3枚のカードを持っています
3枚のうち
いずれか1枚のカードを選び
書かれた整数を2倍する
操作を行った後
以下の条件が同時に満たされれば
魔術は成功です
えー
赤
aは何も
しなくていいんですね
だから
うんうんうんうんうん
入力例1は
どんな風になってますか?
いけてますね
これで良さそうなんだけどな
何がダメなんだろう
exit print yes
exit print no
んー
exit print yes noを
一番最後にしましょうか
exit print
多分そこ関係ないと思うけど
見栄え的に
exit print yes if a小なりb小なりc else no
exit print yes if a小なりb小なりc else no
警戒もしaがbより大きかったらbを2倍
もしbがcより大きかったらcを2倍
うーん
いやあってる気がするんですけどね
ダメ?
ちょっとこれ出してダメだったらねえ?
ダメだったら解説見ようかな?
ダメだと思うけど多分
法文の中をいじってないから
ダメですね
ちょっと解説見てみましょうか
b問題
えーと
この問題には大きく分けて
以下の2つの解法があります
前単作ベースの解法
貪欲法ベースの解法
前単作ベースの解法
以下のように操作に番号をつけることを考えます
前単作ベースの解法以下のように操作に番号をつけることを考えます
前単作ベースの解法以下のように操作に番号をつけることを考えます
操作1 赤を2倍 操作2 緑を2倍 操作3 青を2倍
そこで操作1をP 操作2をQ 操作3をR回行うとき以下の通りになります
赤のカードに最終的に書かれた整数はA×2のP乗
緑はB×2のQ乗 青はC×2のR乗
このようにカードに書かれた整数は各操作の回数PQRの値に依存します
つまりA×2のP乗 青なりB×2のQ乗 青なりC×2のR乗×PたすQたす
あ かけるじゃないね 制約ですねこれ
PたすQたすR 青なりイコールKを満たす皮膚整数PQRの組がある場合のみ
答えはイエスとなることがわかります
Kは7以下なので30ループを用いて全探索を行うと解くことができます
30ループ?
30ループ?
Aを2倍させる必要なくない?
整数A
緑のカードに書かれている整数は赤のカードに書かれている整数より真に大きい
B問題：カード操作と魔術の成功判定
青のカードに書かれている整数は緑のカードに書かれている整数より真に大きい
赤いじる必要なくない?
20ループでよくない?
一旦C++なので読むのは置いといて
貪欲法ベースの解法
どんな方法を使えば最短手数で魔術を成功できるか考えてみましょう
自明な考察として
あ これこれ
赤のカードには一切操作を行わないことが最適であることがわかります
なぜなら赤のカードに操作を行った場合
他のカードに対して操作すべき回数が増えるからです
同様に考えて
緑のカードに対して行う操作も
赤のカード 青なり 緑のカードとなるために
必要な最小回数で構いません
このようにその場その場で最善だと思われる手を選び
答えを得る方法を貪欲法と言います
以下C++での実装例です
うーん
あーなるほどね
法文じゃなくてファイル文にして
AがB以上の間カウントを1プラスしてBを2倍して
で もう一個ファイル文を使って
AがA以上である間カウントを1プラスしてCを2倍してっていうのをして
最終的にそのカウントににがけしたカウント数が
操作の回数K以下だったらイエス
じゃなかったらノーを出す
あーこれわかりやすいな
これでちょっと実装してみて今日終わりにしましょうか
えーっとCNT カウント変数0で
ファイル えーっと
A ダイナリーコールBで
Bの間
CNTプラスイコール1
よいしょCNTプラスイコール1
でBかけるイコール2
でもう一個ファイル文を使います
BダイナリーイコールCの間
CNTプラスイコール1でCかけるイコール2
でプリントイエス
IF
解答の実装と終了
CNTが
小なりイコールKだったら
そうじゃなかったらノーを出力
で
提出してみましょうか
なんで自分のあれが
あー通りましたねダメだったんだろう
ちょっと後で見直しておきます
ということで今日はここまでにしておきましょう
お疲れ様です