00:03
AtCoder Beginner Contest 082
A問題。
Round up the mean
問題文。
2つの生成数A、Bが与えられます。
A、Bの平均値をXとします。
Xの小数点以下を切り上げて得られる整数を出力してください。
切り上げか。
切り上げってどうやるんでしたっけ。
Python、切り上げ。
小数点以下を切り上げ。
Math.floor
あ、違う。切り捨てだ。
小数点以下を切り上げ。
Math.Ceil
Import Math
とりあえず、入力例1、3は2。
1と3の平均値は2.0であり、小数点以下を切り上げて得られる整数は2です。
入力例2、74。
出力例は6。
7と4の平均値は5.5であり、小数点以下を切り上げて得られる整数は6です。
なので、とりあえずコードテストを。
A、Bイコールマップ
イントインプット
ドットスプリット
プリント
Math.Ceilは?
はいはいはい。
なので
Math.Ceil
かっこ
さらにかっこAプラスB
割る2かな?
6
入力例3、5と5で5が出たらOK。
多分大丈夫そうですね。
提出してみましょう。
A問題でインポートさせることないと思うんだけどな。
もうちょっと他にやり方あったかもしれないですがACしたので
とりあえずB問題いきます。
B問題
2オー
ん?
アナグラムズ
問題文
A小文字のみからなる文字列S、Tが与えられます。
あなたはSの文字を好きな順に並び替え文字列S'を作ります。
またTの文字を好きな順に並び替え文字列T'を作ります。
03:01
この時辞書順でS'小なりT'となるようにできるか判定してください。
例えばXY小なりXYAであり
アットコーダー小なりアトラスである。
はい。
まあこれは
相として小なりかどうかっていうのが確かPythonだと判定できたので
それを書くだけかな。
Aイコール
相としちゃおうか。
インプット
ドット相と
Bイコール
インプ
ソーテッドにしたほうがいいのかなこれ。
ソーテッド
インプット
でBも同じ。
プリント
一応AとBをそれぞれ
実行して確認しましょうか。
XYAXYで
プリント
イエス
何の時にイエス
IF
A小なり
B
ELSE
NO
逆か。
あ、そうか。
Sは
小順
で
Tの方は
後順ですね。
ソーテッド
インプットの
リバース
リバースドかリバースかどっちだこれ。
リバースド is an invalid keyword argument for sort
リバースならどうですか。
はい、出ましたね。
これだね。
では
イエスですね。
入力例3はNO。
06:01
はい。
大丈夫そうなので提出していきます。
ここからですね。
はい。C問題。
グッドシークエンス
問題文。
長さNの整数の列Aが与えられます。
あなたの目標はAのうちいくつかの要素を取り除き
Aを良い数列にすることです。
ここで数列Bが良い整列であるとは
次の条件が成り立つことです。
Bの各要素Xについて
Bに値XはちょうどX個含まれる。
例えば3334241424からの数列は良い数列です。
一方333324142は良い数列ではありません。
Aを良い数列にするために取り除くべき要素の個数の最小値を求めてください。
Nは10の5乗以下。
それぞれの数字は10の9乗以下。
はい。
辞書かな?
だからそれぞれの数字分
要素がないと良い数列とは言えないということですね。
なのでそのリストの中に
その数字以上
例えば3が4個入ってたら3を1個消さないといけない
というので1削除したらいいですよ
というのが答えになるんですが
少なかった場合だよね
少なかった場合は全部をカウントして消さないといけないので
DICディクショナリーを作りましょうか。
Aイコール
リストの
マップの
インと
インプットドとスプリット
4Aイン
大文字Aで
IF
DICショナリーの中に
A
NOT IN
DICショナリーの場合
DICショナリー
09:00
小文字A
は1
エルス
DICショナリー
小文字A
プラスイコール1
確認プリントA
違うプリントDICショナリーですね。
3が4個あるので
この4文の後に
アンサーイコール0にして
4
KEYと
ITEMS
4IN
DICDOT
ITEMS
これで
どっちも出るんじゃないか
KEYと
ITEM
なので
ここで
数字と数字の出現回数が求められたので
IF KEYが
アイテムより大きかったら
どうしようかな
アイテム個数が
個数がKEYより大きかったら
アンサープラスイコール
アイテムマイナスKEY
じゃなかった場合
IF
LIFにするか
LIF
逆パターンですね
KEYが
アイテム個数より多かった場合
つまり個数が足りなかった場合は
アンスプラスイコール
そのまま個数
もう丸ごと
その数字をなかったことにすればいい
プリント
アンス
いかがでしょうか
入力例1は
1が出たらOK
入力例2は
2が出たらOK
ちょっと大きい
標準入力例が欲しいですね
12:00
3つ目は0
4つ目は1
大きい例が欲しいな
5つ目は5が出たらOK
はい
入力例は全部クリアしたので提出してみましょう
辞書を使っての回答だったら
割と解けるようになってきた気がしますな
いけそうですね
はい、エンシーしました
D問題見てみましょうか
D問題
FTロボット
問題文
2次元平面の原点にロボットが置かれています
00ってことかな
最初、ロボットはX軸の正の向きを向いています
このロボットに命令列Sが与えられます
Sは次の2次、2文字のみから成り
先頭から末尾まで順に実行されます
F、今向いている向きに長さ1だけ移動する
T、時計回りまたは半時計回りの好きな方向に90度だけ向きを変える
ロボットの目標は命令列を全て実行し終わった後に
目標XYにいることです
この目標が達成可能か判定してください
はい
命令の数は8000以下ですね
目標が達成可能ならばYesを出力
達成不可能ならNoを出力
命令が与えられてゴール42ですね
入力1だと
だから00スタートで考えてって感じ
出力例1の解説を見ようかな
1番目の解説というか
出力例1の
こういう風に解くんだよってやつ
1番目のTで半時計回りに90度だけ向きを変え
2番目のTで時計回りに90度だけ向きを変えればいいです
せーの向きに向いてるからF
半時計回り
上に行く
12
右に行く123
そうですねはいはいはい
これはどうしたらいいんだ
Sイコールインプットでとりあえず入れといて
ゴール地点はXYで与えられる
大文字X大文字Yイコールマップ
15:03
イントインプット
ドットスプリット
ゴールから向かっていって
00に戻れるかどうか
っていうのが判定できたらいいですけどね
それでいってみるか1回
Sイコール
ソーテッドリストのインプット
のリバース
あ違うソートしちゃダメだ
リストのインプットを
カッコダブルクロンダブルクロンマイナス1ですね
そのまま反対にする
でXYがゴール
フォーアイインレンジ
いやどうしよう
まあいいかフォー小文字Sイン
Sで
いやこれ
そうかこれちょっと分かんなくなってきたな
今向いている向きに長さ1だけ移動する
そうか
まずFの数が
合計値と
同値以上かどうかで判定できそうですね
なので
FイコールS
ドット
カウント
ダブルクローテーションF
IF
いや
プリント
IF分で括るか
IFの数が
そもそも大文字Xプラス大文字Yより下だったら
18:02
もうそもそも行くことができないので
エグジット
プリント
ノー
ですね
で問題は
Fの数が
ちゃんと全部あったらどうするのっていう話なんですが
あいや
制約に書いてるな
Sの文字列は
X
Y
あでもXY以上ってだけだから
XたすY以上じゃないといけないから
これは書いといていいか
んー
ちょっと思いつかんなこっからが
Tの数をどう見るかっていう感じなんでしょうが
極端にFが多い場合
多分っていうのがちょっと考えつかないんですよね現状
解説見るか
D問題D問題
Sの長さをNとし目標の座標をXTYTとします
まず思いつく解法はDP
はーDP
このDPの乗体数はオーダーNの3乗で
繊維はオーダー1なので
全体の時間計算量はTLEするサイズになっちゃうと
ロボットの動き方をよく観察することで
DPの乗体数を減らしましょう
命令列をTを区切り文字として分割したとき
I番目の区間に含まれるFの個数をDIとします
この時ロボットの動き方は
右に距離D1だけ動く
上下隙の向きに距離D2
左右隙の向きに距離D3
上下隙の向きにD4
左右隙の方向にD5
以下同様となっています
よってX軸方向の移動とY軸方向の移動を
独立に考えることができます
あーなるほど
例えばX軸方向の移動については
右に距離D1だけ動く
左右にD3
左右にD5
一個飛ばしで考えることができるということですね
Tで区切った場合
という移動を終えた後
X座標がXTになっているようにできるか判定すればよいです
これは次のようなDPで計算できます
まあDPやってるって感じですね
この場合オーダーN事情
21:01
繊維はオーダー1なので十分に高速です
DPねー
ユーザー解説もあるので
それ見て今日は終わりにしようと思います
縦と動き
縦の動きと横の動きは独立にできる
Tで囲まれたFの個数を抜き出す
すると奇数番目にある数は横の動き
偶数番目は縦の動きに使える
Fの個数を抜き出したら奇数番目、偶数番目に分ける
横の動きの一番目は特別X軸の正の方向でしか動けない
それ以外はどんな方向でも動ける
左右上下どっちかですね
上か下か右か左か
座標0からスタートして左右どちらかに配列Vの数分だけ移動していって
座標Xまで移動できるか
もう少し言い換えると配列Vの数のセーフを入れ替えて
相和をXにできるか
これをチェックするにはDPをすればいい
DPねー
なかなか
DPとか
幅優先探索長さ優先探索とか
あとユニオンファインドとか
あの辺のアルゴリズムが
なんか身につかないんですよね
かけって話なんですが
とりあえずは他の方の回答を
見ておこうと思います
ではまた次回お疲れ様です