00:03
HHKB プログラミングコンテスト 2020
A問題の解説
A問題、キーボード。問題文、YかNのいずれかである文字Sと、AかBかCのいずれかである文字Tが与えられます。
SがYならば、Tの文字を大文字にしたものを出力してください。 SがNならば、Tの文字をそのまま出力してください。
SとTが与えられます。 Sイコールインプット。
Tイコールインプット。確か、アッパー関数ですね。 なので、プリント
T.アッパー
かっこかな。
Sイコールイコール 大文字のYだったら
エルス、そうでなければそのままTをプリント。一回これでちょっと何も見ずに出してみましょう。
アッパーローはACですね。だったはずですね。はい。ではB問題。布団。
問題文、縦H行横W列からなるマス目があり、それぞれのマスは散らかっているか散らかっていないかのどちらかです。
今からあなたはこのマス目に一つ布団を敷きます。縦または横に隣接するマス目の内部の2マスであって、
いずれのマスも散らかっていない場所に布団を敷くことができます。 整数H、WとHコの長さWの文字列Sが与えられます。
SIのJ文字目がドットの時、上からI行目、左からJ列目のマスは散らかっていません。
SIのJ文字目がシャープの時、上からI行目、左からJ列目のマスは散らかっています。
布団を敷く場所の選び方は全部で何通りあるか求めてください。 ドットが2個並んでいるところがあればそこを判定してくださいですね。
制約が100までなので、 全部試せばいけるかなって感じですかね。
HとWでSがHコ与えられます。
HWイコールマップイントインプットドットスプリットでLイコール
からのリストの中にリスト インプット
をなんちゃらインレンジ H
で確認でプリントL 入ってますね。20リストで
入ってますので 20ループでやっていきます。CNTイコール0
4Yイン レンジ
H で 4Xインレンジ
W
IFY
プラス2
ん?2?0スタートの時プラス1か。 FYプラス1が
H以下だったら&
Xプラス1が W以下だったら&
Y や
そうか上は考えなくていいから、上と左は考えなくていいですね。 右と下だけで判定していけるので
じゃあこれでいいや。 まず
このIF文の前にIF Lの
YXがイコールイコールシャープだったらスキップですね。コンティニュー。 でそうでなければ FYプラス1がH以下
Xプラス1がW未満 H未満 W未満の時に
どうしようかな。IF LのY
プラス1X イコールイコール
ドットだったらCNTプラスイコール1で
どうしようかな。縦だから関係ないなこれ。
WのパターンとHのパターンで分けましょうか。 IF Yプラス1がH未満だったら
で、かつですね&
LのYプラス1XがドットだったらCNTプラスイコール1。 で同じ要領でこれが縦の判定なので横の判定もします。
IF Xプラス1がW未満で LのYXプラス1
がドットだったらCNTプラスイコール1。 プリント法文全部終わったらプリントCNTで
出るはず。 入力例1は3
が出ました。入力例2がゼロ。 他の入力例がないのがちょっと心もとないですが
どうしようかな。 まあいいか。1回出してみます。
これもしダメだったらちょっと他の入力例をこっちで考えて 手打ちで試してみましょう。
C問題の解説
ACしたのでそのままいきます。 C問題 NEQ NEC
問題文。長さNの数列Pが与えられます。 各i 1からNについて0以上の整数でP1…
Piのいずれとも等しくない値のうち最小値を求めてください。 NとPは20万以下。
合計N行出力せよ。 いずれとも等しくない値のうち最小値。
入力例1はNが4でPの行列が1、1、0、2。 出力例は0、0、2、3。
0以上の整数でPイコール1と等しくない最小値はゼロです。 0以上の整数でPイコール1、P2イコール1のいずれとも等しくない最小値はゼロです。
0以上の整数で…ああはいはいはい。 どんどん追加されていくんだ。
この与えられた行数分 カウントしていって
現状ある中で一番少ない数字を 出してねってことですね。
ということなので
えっと… でも20万でしょ?
20万を20万回… 10の
10乗ギリギリアウト?
1回ちょっとシンプルな方文で試してみましょうか。
nイコールインとインプット。 これはあんまり関係ないと思いますが。
で、lイコールリストの
マップのインとインプットドットスプリット。
ほう。
テクショナリー作るか。dicイコール トゲトゲカッコ
フォアイン
l。if dicI… 違う。
if I in
dic。 もし中にあった場合…
いや違うなぁ。
0から20万なのでもこれをディクショナリーで作っておきましょう。
フォアインレンジ 0スタートの20万
2、0、1、2、3。で、20万1。
で、dicIイコール0。
if I… 違う。if
dicIが
ノットイコール0だったら入っちゃってるので
入っちゃってるので
for jイン
レンジ iプラ1から
20万1までを判定して
違う。ファイル文にした方がいい。while dicIが
0じゃないなら永遠に続けます。 iプラスイコール1。
で、dicIが
0だった場合止まるので print
Iですね。 で、if dicIが0だった場合
else printIで
dicIにプラスイコール1。 これでどうだ。
入力例1は0、0、2、3。 1、2、0、2。なんで?
ダブリだとそうなっちゃうのね。
ダブってる分にはいいんだ。ダブってる分にはいいので
dicI… そうか、初手が1だから1より低い可能性もあるんだなぁ
どうしようかな。0から20万までのリストを作る…リストというか
ディクショナリを作りました。 もし1スタートだった場合
いや20ループかなぁ 4i in l
4i in l 4j in レンジ
iプラス1…いや、えっと
0から20万1。
で、if dictionary jが
not equal… いや、equal equal 0だったら
print j
で、break…そうね。 だから1個目の一重ループ4i in lの時に
もうdictionary i
プラスイコール1しといてですね。
で、0からカウントしていって最初の使用していないものがあればそれをプリントする
で、いいはず。 0、0、2、3
入力例2は、0、0、0、0、0、0、6、6、6、8、8
0、0、0、0、0、0、6、6、6、8、8、OK
あ、よいしょ
あぶねー消しちゃった。 なんとかCtrl Zで音なきを言いました。
提出していきます。 大きい声出ちゃった。すいません。
7、10、あーちょっと大きいのは詰まってるなぁ
TLE 下。 これPyPyで提出したら何か変わる?
変わらなさそうですね。いまいちPyPyの使いどころがよくわかってないんですが
あ、同じところでやっぱり詰まってますね。 ディクショナリーにしたところまではいいんだろうけど、4分20万1をループさせているのが
ダメなんでしょうね。 なので
なのでと言っても どうしようかなぁといったとこですね。
今の値を記録しておく。 ディクショナリー4分
20万。 n が20万。
0以上の整数。 n にしておきますか。一応。
フレンジ n プラス 1に。 まあ変わんないと思うけど
どっちにしろ n が20万だった場合の処理が修正できてないので
あんまり意味はないと思いますが 一応試してみます。
ちょっと使い分けがあんまり思いつかないので 解説を見ていきましょうか。7番目で止まりますね。8問目でTLEしてます。
だから8問目が多分マックスの数字なんでしょうね。 TLE が3つ、LE 実行時エラーが1つ。
実行時エラーは何だ? 解説を見ていきましょう。C問題。
それぞれの出力をするために最初の i 項をセットや配列などで管理し、0から順にこれらの項に登場するか確認する方法では、少なくともオーダー n 二乗以上かかるケースが存在し、これでは間に合いません。
しかし i が大きくなるにつれ追加された整数の種類数が徐々に増えていくことを考えると、i が大きくなるにつれ答えも増加すること、減少しないことが考えられます。
よって、ある i に対する答えを求めたいときは、i マイナス 1 について求めた答え以上の値で、今まで追加した整数の中に登場しない最小の値を求めれば良いです。
これは値を小さい順に1つずつ試していき、見つけたところでループを抜けるという実装でも、合計でオーダー n 回ですみます。
配列でこれを実装すればオーダー n、セットでこれを実装すればオーダー n ログ n でこの問題全体が解けます。
これ2万、20万、スキャン、アット、法文、法文1個ですね。
あ、でも法文の中にホワイルド文を入れてますね。 ユーザー解説もあるので見てみましょう。
nc プラプラだなぁ、パイソン後で見てみます。 こういったクエリ問題では、1クエリだけの場合ではどのように答えるかを考える。
i イコール n の場合は、いずれとも等しくない値で、かつ最小値を求める一番愚直な方法として、0 から数列に含まれるかをチェック、最初に含まれない数を答えるという方針がある。
これが私がやったやつですね。この場合は数列に含まれるかを高速に判定するため、セットを使用することができる。
数列に含まれる数字をすべてセットに追加し、0 から順にセットに含まれているかを判定して、含まれていない数を答えるようにする。
これで計算量は p の最大値 log n となる。 セットだったらいけたのかなぁ。
ちょっとセットでやり直してみますか。 なんかセットだったらいけたっぽいような
ことを言ってますね。
大文字 s イコールセット フォアインレンジ
l フォーアインエル
if
いやでもわかんないな。ちょっとわかんないな。 じゃあ他の方の python コードを見て
考えておきます。
解けんな。 ではまた次回お疲れ様です。