整数列Aの操作
AtCoder Beginner Contest 294、A問題、フィルター、問題文、長さNの整数列Aが与えられます。
Aから偶数だけすべて取り出し、元の順番を保って出力してください。
やるだけですね。
nイコールイントのインプット、
aイコールリストのi%2イコールイコール0、
リストのi%2イコールイコール0、
4iインレンジ、
リストマップイントインプットかな?
マップのイントインプットスプリット、本当に?
ちょっとコードテストしてみましょうか。
入力を入れます。
elseもいるんだこれ。
じゃあ普通に取りますか。
aイコールリストのマップのイントインプットスプリット、
ansイコールからのリストを小文字A、
if小文字A%2イコールイコール0だったら、
偶数だけを出すんでしたっけ?
偶数を取り出した列を、そうですね。
%2イコールイコール0だったら、
ans.append小文字A、
最後に4文が終わったらプリント、
アスタリスクansでOK。
提出しましょうか。
一応入力例2と3もやっておきましょうか。
入力例2はOK。
入力例3は大丈夫そうですね。
では提出していきます。
ASCIIアートの問題
ACしたのでB問題いきます。
ASCIIアート。
ASCIIアートか。
問題文。
0以上26以下の整数からなるH行W列の行列Aが与えられます。
Aの上からI行目、左からJ列目の要素はaijです。
H個の長さWの文字列Sを次の条件を満たすように定めます。
SIのJ文字目はaijが0ならばperiod、
そうでなければaij番目の大文字アルファベットである。
Sを順に出力してください。
数字の1だったらA、数字の2だったらBです。
行列が与えられて0だったらドット、
それ以外だったら最大26なのでアルファベット。
ラージAからラージZまでを出力してくださいということですね。
すごい最後、ASCIIアートで猫が書かれてますね。
アルファベットを出力するのに
いいコードがあったんですよね、覚えてないけど。
とりあえず入力をとります。
HWイコールマップのイントインプットドットスプリット。
H行W列Lイコールリストのインプット、
なんちゃらインレンジHかな。
AをプリントLして入力例1をこれで入力ができているかどうかの確認を012003。
良さそうですね。
二重行列になってないな。
リストの中にリストインプットを押しましょうか。
小文字になっちゃうな。難しいですね。
マップイントインプットスプリットを入れたらいける?
いけましたね。
二重ループで一個ずつ見ていきましょうか。
4YインレンジH
4XインレンジW
4YインレンジW
4YインレンジW
パイソンアルファベット数字
ORDとCHRがあるんですね。
チャーとかだったっけな。
数字からアルファベットなどに変換するのはチャーを用います。
先ほど表示されたように65は大文字のAなので
CHR65プラス
4YインレンジH、4XインレンジWの後にTMPして
LYXを変数に入れておきましょうか。
ごちゃつきそうな気がするんで。
TMPが0だったらLのYXはドット。
それ以外だったらLのYXは
CHR65プラスTMPの%26
これでいけない?いけそうな気がするけどどうでしょうか。
一旦プリントLしておきます。
全然違うのが出てきた。なんで?
CHR数字からアルファベットに変換するのはCHRを使います。
65は大文字のAですよ。
%26が邪魔だった?
%26がなければそのままBCDが出てますね。
でも出したいのは
ABCなので
マイナス1か。65プラスTMPマイナス1か。
ABCが出ました。
あとは4、small l, in, large l
プリント、アスタリスク、small l
空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空
空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空白空
シークエンスかマージシークエンスシーズ
問題文長さ n の競技単調増加率 a と長さ m の競技単調増加率 b が与えられます
競技単調増加率の操作
ここですべての i j 1 以上 n 以下 j は 1 以上 m 以下について ai not equal b j が成り立っています
長さ n プラス m の競技単調増加率 c を次の操作を行った結果得られる列として定めます
c を a と b を連結した列とする厳密には i イコール 1 から n について ci イコール ai とし
i イコール n プラス 1 n プラス 2 n プラス m について ci イコール b i マイナス n とする
a のリストの後ろにそのまま b を足すのが c ってことですね で c を小順に相当する
a と b がそれぞれ c では何番目にあるか求めてくださいより厳密にはまず i イコール 12 n について ck イコール ai を満たす計を順に求めた後 j イコール
1 から m について ck イコール bj を満たす計を順に求めてください
1行目には a がそれぞれ c では何番目にあるかを空白区切りで出力 2行目には b がそれぞれ c では何行目何番目にあるかを空白区切りで出力
はいはいはいはい それぞれの
列を 何番目にあるかそれぞれの列を足して
小順に相当して その後もう1回それぞれの元の数列を
照らし合わせて a
数列 a の1番目の数字は
2つを合わせて相当した数列 c の何番目に当たるかっていうのを出力しろうですね で
それぞれの数字が まず nm が1以上10の5畳以下
で a と b のそれぞれの要素が10の9畳以下 法文したら
いっぱいいっぱいになる毎回インデックスとかで調べると多分 tle になる やつですねこれはなので
そうだな まあ1回
その tle する方でやってみましょうかそれしか 今のところ思いつきがないので
そこから派生できる考え方もあるかもしれない nm イコールマップのインとインプットドットスプリット で
入力例を先に入れておいて a と b が与えられる a イコール
リスト マップとインプットドットスプリット
で上に同じで b で c イコール
ソーテッド a プラス b 一応プリント c
して確認しておきましょうか a と b が与えられてプラスして
まとまった小順のリストができましたね
こう 小文字 c インラージシー
で 小文字 a のリストと小文字 b のリストを用意しておこうかな
イフ 小文字 c インラージ a の場合
a ドットアペンド
ラージ a ドットインデックス小文字 c プラス1
で エルスつまり b の方にある場合は小文字 b ドットアペンド
ラージ b ドットインデックス
小文字 c プラス1で
プリント a と
プリント b 1 2 3 4 1 2 3
あれなんで 1 3 4 7 2 5 6
あそうか大文字 a と a ドットアペンド 大文字 c のインデックス c か
1 3 4 7 2 5 6
で多分このやり方で入力例はクリアできるんですよね 1 2 3 4 5 6 7 8
ok 入力例 3 1 2 5 9 11 12 15 20
入力例はクリアできるんですよ で多分このインデックス関数っていうのが毎回
何リストの中を全部洗ってる はずなので
ってなると 10の何畳階っていうのは結構
厳しいんじゃないみたいな話だと思うんですよね c 問題って大体 そういう
操作時間がエラーになっちゃうから 4分のループとかじゃ解けないよみたいなのが多いんで一応提出してみますが
入力例はクリアしたのでね あーもう一発目からちょっと重いですね実行時間1
27分の1でジャッジ中 tle 実行時間制限長か なのでここからは関数を使わないアルゴリズムか何かで記録していかないといけない
っていうのが趣旨になってくるんですよね で私はまだその辺が
落とし込めてないというか 全然身についていないのでだいたい c 問題でケツマズくと
いうことです 辞書にしたらいいのかなぁ
辞書ってでも出現理屈を出すだけだから いや待てよんと
辞書ありだなぁ とフロム
いやいや デフォルトディクト使おうと思ったけど
あんまりやり方わかんないからいいや
dic イコール トゲかっこ
ディクショナリーを作っておきます
ディクショナリーと呼ばれる
どうしようかな 4小文字 a in ラージ a
if ディクショナリー
いや違うな レンか 4i in レンジ
len c
ってやらなくても n プラス m でいいか まあいいや
c の文字列数分長さ分 4分をしますで何をするかというと
dic の i 番目
if i not in
dic だったら
まずは dic の イフも何もないなこれ足さなくていいや
dic の i イコール i プラス1
違うかえーっと なんか違う気がしてきたな
0番目 1番目
単調増加 abc ci だな
ディクショナリーに ci c の i 番目の数字を入れて
その数字にそのキーに対応するバリューが i プラス1
だから c の0番目 1番先頭に与えられるのは1
が与えられますというふうに処理していきます
で 4 小文字 a in ラージ a
プリント
どう これ何なんだっけ定出の形は空白区切り
空白区切りで出力せよ 空白区切りの出す方わかんねー
4 e プリント dic の
小文字 a で
エンドイコール空白とかにしたら
ダメ これで
b も同じく 4 b 小文字 b in ラージ b でディクショナリー小文字 b
をプリント なるほどここでプリント小文字
何もなしを出したら開業される 開業はされる
されるが一番後ろが 空白出てるんですけどこれ大丈夫かな
出してみますか これで wa になったら後ろの小文字空白をどうにかしよう
っていうのを考えないといけないですね 入ってるね入ってるねー
16 19 22
25 o ac スター嬉しい いいですねー
ということで辞書を使えばなんとかなるよって話ですねこれ遠藤で空白区切り で出すの
後ろ空白ついても大丈夫なんだな はいじゃあちょっとおそらく解けないでしょうか d 問題
受付に行くアルゴリズム
やってみましょうか d 問題バンク問題文銀行に人人人
1人人 n が並んでいます 9アルファベットの9ですね9個のイベントが発生しますイベントは次の3種類
のいずれかです 数字の1受付に呼ばれていない人のうち最も小さい番号の人が受付に
呼ばれるに x 人 x が初めて受付に行くここで人 x は既に1回以上受付に呼ばれている
さんすでに受付に呼ばれているが受付に行っていない人のうち最も小さい番号の 人が再度呼ばれる
3種目目の3種類目のイベントで受付に呼ばれる人の番号を呼ばれた順に出力して ください
3種類目のイベントで受付に呼ばれる人の番号を呼ばれた順に出力してください すべての人が1回以上を呼ばれている時に一瞬1種類目のイベントが発生することはない
2種類目のイベントについて人 x は既に1回以上受付に呼ばれている 2種類目のイベントについて人 x が2回以上受付に行くことはない
呼ばれている人が全員既に受付に行っている時に3種類目のイベントが発生することはない 3種類目のイベントは少なくとも1回発生する
n は1以上5かける10の5乗 9クエリーは2以上を5かける10の5乗
以下ですね うーん
11321 えっとどうなってんの
最も小さい番号の人が呼ばれる人 x が初めて受付に行く 呼ばれる呼ばれる
呼ばれる呼ばれる3回目すでに受付に呼ばれているが受付に行っていない人のうち最も 小さい番号
9かなぁ
人 x は初めて受付に行く 呼ばれる付けに行く
x は1回以上受付に呼ばれああ9だと2番目のクエリーがちょっと 処理できなさそうですねこれ
うーん 11212223そうだね後ろの
後ろの要素も使われている場合があるので クエリー
2番目が
解説を見ましょうか d 問題 2つの解法を紹介します解法1 std コロンコロンセットを使う解法
何これ c プラプラーのやつですね 順序付き集合型を利用する方法です
具体的には次の手順で受付に呼ばれたがまだ受付に行っていない人の集合を管理し ながらイベントを処理していきます
コールド変数を受付に呼ばれたがまだ受付に行っていない人の集合とする 初めコールドは空である
またラスト変数を最後に呼ばれた人の番号とする 便宜上始めラストはゼロとするその後イベントを順に処理する
イベントの種類に応じ次の処理を行う 一つ目のイベントの場合呼ばれるですね次に呼ばれるのはラストプラス1である
やってラストに1を足した後コールドにラストを追加 2種類目のイベントの場合特定の呼ばれた人誰かが行くですね
x をコールドから削除する 3種類目のイベント2回以上呼ばれた人が行くですね
3種類目のイベントの場合コールドの最小の要素が答えである これを出力する
はいこれはC++なんでちょっと 2つ目の解法もC++でございますね
一応解法の文章だけ読みますね 解法2 線形時間で解く方法より計算量の良い方法として解法として時間計算量が
オーダー n プラス q である解法も紹介します 問題の制約から問題の制約から3種類目のイベントで呼ばれる番号は
工技単調増加するという性質を持ちます 速い人順数字が小さい人順ってことですね
証明入り方で考えます3種類目のイベントで人 y が呼ばれてその後人 x x 省なり y が呼ばれたとします
呼ばれた人の数字よりもっと若い数字の人がその後呼ばれたとします すると y が呼ばれた時点で人 x はすでに1回以上受付に呼ばれていて
1回目の呼び出しは番号順であるためかつまだ受付に行っていないため矛盾が発生しますと よって次のような手順で線形時間で解くアルゴリズムを構成できます
まず最後に3種類目のイベントで読んだ人の変数番号を変数 ans アンスで常に保存しておきます
そして3種類目のイベントが来るたびにアンスの示す人が受付に行っていない人になる までアンスの値をインクリメントして得られるアンスの値を出力します
この操作によってアンスのインクリメントされる回数は min n 級階で抑えられるので計算量はオーダー n
プラス9になります なるほど
わかんないので 他の方の提出だったり youtube の方で
そう youtube の方でね結構今日プロ実況とかゆっくりで解説実況されている方とかもいらっしゃ るんでその辺もちょっとちらほら見ながら
勉強中ですということで今回はここまで ちょっと新問題
まともに考えて初めて解けたような 気がするので
今までは結構やっつけでやってたんでね 嬉しい気持ちですではまた次回お疲れ様です