00:04
AtCoder Beginner Contest 296回目。A問題、オルタネイトリー。問題文、N人が一列に並んでいます。
列の状態は、長さNの文字列Sで与えられ、前からi番目の人はSのi文字目がMの時男性、Fの時女性です。
男女が交互に並んでいるかどうか判定してください。男性同士が隣り合う箇所も、女性同士が隣り合う箇所も存在しない時、かつその時に限り、男女が交互に並んでいると言います。
問題文、オルタネイトリーは、オルタネイト交互にの英語ですね。確かね。
入力はNSが与えられます。 だからMFMFMFあるいはFMFMFMってなってたら
1文字目が大文字のESですね。 なので
Nイコールインと、インプット
Sイコールインプット、で、for i in range n
どうしようかな。if 文字は
1文字から始まるのか。if n i イコールイコール
m だったら n-1にしとくか。
range n-1にして、if n i イコールイコール m
i 番目がm だったら、で、and ですね。and
n i プラス1個目、この次も
m だったら、よいしょ。
exit print
の、elif n の i 番目が
f で、and
いや、ここにorを入れたらいいか。if n の i 番目が m かつ n の i プラス1番目が m
だった場合を括弧で括って、ここは
03:04
よいしょ。 n の i 番目が f かつ n プラス1番目の
文字が f だった場合、どっちかですね。
この場合、print no で、ループが全部終わって大丈夫だったら print yes
で、どうでしょうか。提出。コードテストをしていないが、あ、re が出た。
ので、しっかりコードテストをするべきですね、やっぱり。
えっと、入力例、入力例。
入力例1、ロックの mfmfmf で、yes。
あ、もう初っ端のアウトだな。int object、あ、int object だった。n じゃなくて s ですね。
そらでもわけだ。if 分の n を全部 s にして、
一回再提出してみようかな。提出。
はい、ac しました。ので、b 問題いきます。
b 問題。チェスボード。問題文。チェス版のどこにコマが置かれているか答えてください。
縦8マス、横8マスのグリッドがあります。グリッドの各マスには次のルールで定められる長さ2の文字列の名前がついています。
左から1列目にあるマスの名前の一文字目は a である。
同時に左から2、3…8列目にあるマスの名前の一文字目は b,c,d,e,f,g,h である。
下から1行目にあるマスの名前の2文字目は1である。
同様に下から2,3…8行目にあるマスの名前の2文字目は2,3,4,5,6,7,8 である。
例えばグリッドの左下のマスの名前は a,1。右下のマスの名前は h,1。
右上のマスの名前は h,8 です。
グリッドの状態を表す長さ8の8つの文字列 s1からs8が与えられます。
s i の j 文字目はグリッドの上から i 文字目。i…
s i の j 文字目はグリッドの上から i 行目。左から j 列目のマスにコマが置かれているとき、アスタリスク。
06:01
置かれていないときドットであり、s1からs8の中に文字、アスタリスクはちょうど1つ存在します。
コマが置かれているマスの名前を決め…求めてください。はい?あ、はいはいはい。
入力でそのドットとアスタリスクの文字列が与えられるので、アスタリスクの場所を教えてくださいか。
なるほどね。うん。8×8がもう決まっているのであれば、もう普通に方文でいけそうな気はしますけどね。
for in range 8で、
a イコール インプット イフ アスタリスク
in a…いや、どうしようかな。
まぁいっか。 if アスタリスク in a だった場合、
まず一番最初にans で空の文字列を作っておいて、ans
プラス…
インデックス求めるのどうやるんだっけ? a ドット インデックス アスタリスクかな?
で、ちょっと面倒ですがアルファベットのリストも作っておきましょう。
abcdef というのを文字列にして、リスト…
ん? abcdefgh か。 h まで書いて、リストに1文字ずつ。これもなんかやり方あったんですよね。
忘れちゃったけど後で調べよう。efgh まで作って、
09:04
ans プラスイコール アルファベットのリストの
何番目ですかっていうのが a ドット インデックス アスタリスク番目。で、ans プラスイコール
str の i プラス1番目。
で、
print ans の
exit でいいんじゃない?
コードテストしないでガチャを提出。 あー、和が出たねー。
やっぱりコードテストって大事なんですね。 入力例を見てみましょうか。
入力例は a1…あ、そうだ、逆だった。 下からだなぁ。下からってことは…
下からってことは… 012345678 って出るから
わる…8? str i プラス1
パーセント8かな。 ちょっとコードテストこれで出してみましょうか。
入力例1は a1が出たらオッケー。 a0 なので
i プラス1を消すのか? 違うね。
i プラス1パーセント8プラス1か。ややこしいな。
a1 入力例2は b3…
b7。およ。
んーと、 どうしようかなぁ。めんどくさいなぁ。
普通にもう 大文字の l のリストを作って
l に a を入れる。 l イコールインプット
12:11
フォアインレンジ 8 で a イコール
l の i 番目にしとけば
あ、違うわ。 l イコール
l の
コロンコロンマイナス1で逆順にできたはずなので そのまま str i プラス1で
いけるんちゃうの? b 3
b 3ね。出力例1は a 1
a 1ね。オッケー。 提出していきます。ちょっと喉がイガラっぽい。
はい、エーシーしました。長かったな。では新問題。 新問題。ギャップエグジス…イグジスタンス
問題文。長さ n の数列 a が与えられます。 1小なりイコール i j 小なりイコール n である組
i j であって ai マイナス aj イコール x となるものが存在するかどうか判定してください。
制約がマイナス10の9乗から10の9乗まであるので 4文じゃちょっと難しいかもしれないですね。
与えられる a の数列の組み合わせ2つで
x という数字が与えられるのでそれが作れるかどうかの判定をお願いします。 そこに関するインデックス数は出さなくていいので
yes no だけなので コードテストに一旦入力例1を
入力例1は n が6 x が5 でリスト a が3 1 4 1 5 9
出力は yes 9-4 で5ができますと
うーん ちょっと思いつかないなぁ
15:01
n x イコールマップ
イントインプット ドットスプリット
で a イコールリストの 上の行をコピペ
マップのイントのインプットスプリット で
そうとしちゃってもいい気がするんだけどなぁそうと関係あるかなぁ
まあ1回普通に4分で組んでみますか 4
はいインレンジ
n マイナス1
4 j レンジ
1から n まで
いや i i プラス1から n まで
if ai
- ag
エコールイコール x は
a
と a j マイナス ai でもいいんだね別に
a j マイナス ai
これこれくじっと
プリント イエス
そうでなければプリント
の入力例1はイエス出力で入力例にはの
の入力レースさんはイエス あれの
あー h マイナス h っていうのもできるんだじゃあ
間の i から n までだな
18:01
1回出してみましょうか多分 tle だか何だかになると思いますが ちょっとこれ解放が思いつかないので
解説を見て 今日を終えようと思いますもう1個目の時点で
あー tle ですね実行時間超過 解説 c 問題
j を固定したとき ai マイナス aj イコール x となるための ai の値は1位に定まります このため a の中にそのような値が存在するかどうかを判定できれば
よいです 愚直に配列を操作すると最悪の場合1回あたり初めて見るのこれ
オーム オメガ
n 時間かかり全体でオメガ n 事情時間となるため実行時間制限に間に合いません オメガであっているこれ
オーム オームオメガーですね
数学用語でどういう意味なんだろう c プラプラのベクターに対するファインド
python のリストに対する in java のリストに対するコンテインズなどを用いた場合も同様です 実行時間に間に合いませんですね
標準ライブラリの計算量にも注意しましょう リスト a をセットで保持するなどすれば1回あたりオーダーログ n
全体でオーダー n ログ n となり実行時間制限に間に合わせることができます この問題は尺取り法により相当相当プラス線形時間で解くこともできます
a を並び替えても答えは変わらないので a を小順に相当します j を固定して i を探す際 j が小さい順に並べると対応する
i も単長増加となることから線形時間ですべての j について調べることができます やっぱ相当しても良かったんだなちょっと
c++しか 回答例がないので他のユーザーの方の
python 回答を見ておこうと思います ではまた次回お疲れ様です