00:03
AtCoder Beginner Contest 107、A問題、トレイン。問題文、N両編成の列車があります。この列車の前からI両目は後ろから何両目でしょうか。
入力例は4と2、出力例は3。4両編成の列車において、前から2両目の車両は後ろから3両目です。
なので、Nにプラス1してIを引いたらいいですね。
NとIをマップ、インとインプット、ドットスプリント。
で、プリント、Nプラス、Nマイナス1、プラス1かな。
Nマイナス、Iプラス1だ。
はい、提出。
はい、閉鎖しました。B問題いきます。
B問題、グリッドコンプレッション。
問題文、縦H行、横W列のマス目があります。上からI行目、左からJ列目のマスをIJと表します。
各マスは白または黒です。マス目の配色はH行W列の行列、AIJによって与えられます。
AIJがドットならばマスIJは白であり、AIJがシャープならばマスIJは黒です。
すぬけくんはこのマス目を圧縮しようとしています。
そのために、白いマスのみからなる行または列が存在する間、次の操作を繰り返し行います。
操作、白いマスのみからなる列または行を1つ任意に選び、その行または列を取り除いて空白を詰める。
各操作でどの行または列を選ぶかによらず、最終的なマス目は1位に定まることが示せます。
最終的なマス目を求めてください。
なんて言うんだっけこれ、行列圧縮?そのまま、なんかそういうアレがあったはずですが。
えー、だからドットだけの行を消すのは簡単なんですが、ドットだけの列っていうのが、
制約が100以下だから、20ループでもやっちゃってもいいかもですね。
どうしようかな。とりあえず、HとWを受け取ります。
大文字HWイコールマップイントインプットドットスプリット。
で、A、大文字Aにリストの中にリストが入る。インプット、
03:09
Yインレンジ、H回、一応確認プリントA。
で、テストコードを入れておくと。実行。
はい、あー。 行の中のシャープとかドットとかが
一個になっちゃうんだな。じゃあリストインプットですね。 これでばらけるはず。
はい、ばらけましたので、どうしようかな。 横でまずやっていって、
というか、フォーアインレンジHのリストインプットの中で、 これ、中でいけんかな。
ちょっとわかんないからいいや。 だから、大文字A、小文字Aを新しい空のリストにして、
フォーアインレンジH、if 大文字Aのi番目にドットカウントシャープが0だった場合、
というか、0だったというか、1以上だったらにしようか。 0だったらスルーっていうのはわざわざ書かなくてもめんどくさいので。
1以上だった場合、 つまりシャープがある、黒マスがある状態なので、小文字Aリストにドットアペンドのi番目。
そしたら一旦縦、横一列がなくなります。 次だ。縦ってどうやんのこれ。
フォーアインレンジレンA、で、フォーJインレンジレンAの0。
うん、合ってるね。 逆かこれ。
06:03
ギャウント、縦、i、j。 どっちがどっちだこれ。
yか、yを先にやらないといけないから。 なので、1個目の方分でCNTカウント変数を0で定義しておいて、
if小文字Aのj番目、小文字Aのji番目、 イコールイコールドットだったらCNTプラスイコール1。
で、絶対こんなことしなくてもいいんだよな。 回転行列使いたいな。どうやるんだろうな。まあいいや。
フォーアインレンジレンAの0。 フォーアインレンジレンAの0。
フォーアインレンジレンAの0。 フォーアインレンジレンAの0。
そうですね。それで点が。 それから辞書を使って
ドットの位置のインデックス数を記録しておいて、 最終的にその
ドットの位置があるインデックス数にプラスされた数字が Aの縦列、行列分の
数字と同じだったら そこをスライスでカットするっていう手もある。それにしようかな。それの方が
気持ち楽そう。dicイコールからの辞書。
フォーアインレンジレンA。
フォーアインレンジだからレンAか。 フォーアインレンジレンAの0番目。
09:11
IF AのIJ番目?
JI番目?どっち? IJ番目だね。
IJ番目イコールイコールドットだった場合
これは 列
横の数字だけを 記録したらいいから
Jだね。 IF dicJ
イコールイコール0だったら あー違うわ。IF dicJ
ノット。わかんなくなっちゃった。
とりあえずdicJプラスイコール1があって dicJがなかった場合ってどうするんだっけ
定義すればいいんだっけ。 IF dicJが
0より 1以上あったら
dicJプラスイコール1 else dicJイコール1
ん?あってる?プリントdic。 迷走している気がする。
はい、エラーが出ましたので
dictationじゃないな。いつも間違えるなこれ。 Python
辞書の作り方
初期化とかかな。 Python辞書初期化。初期化をした後は
12:10
ノットかなぁやっぱり。ノットで1回書いてみようかな。 それがもうダメだったら1回方文で全部の
index 0で定義してっていうのを やっていこうと思います。
IF日本語になっちゃった。
else
IF dictationに
J not dictation なら
dictation Jイコール0
else dictation Jプラス
dictation Jプラスイコール1
あー、シンタックスになるな。 じゃあ方文でも作ります。
inRange
連 a の
0番目で
iイコール0で初期化しておいて これでどうだ。
はい、出ましたね。 index 0は1、index 1は0、index 2は3、index 3は0ということで
こっち先にやったほうが良かったかな。まあいいか。 で
最終的な答え、アンサー2からのリストを入れて
for
v for i in range v どうしようかな。
idか。i in range a の0番目連 a 0
これも変数作ったほうが多分いいと思うんですけどね。 いちいち書いてるから。
15:04
で
で、これ1個ずつ1個ずつ入れていくかも。 めんどくさいや。
for i in range 連 a
for j in range
連 a の a 番目
a の0でいいや。 で、1個目の方文の間に
tmp、テンポラリーのリストを作っておいて
if dic j
not equal 連、違うわ。
連 a じゃなければ
tmp に .append a の
ij 番目。で、方文が終わったら
ans.append tmp でプリントアンスしたら
多分答えが出てくるはず。圧縮した後の。 はい、出ているっぽいねこれは。ok っぽいですね。
絶対こんなに書くやつじゃないんだよなぁ。 ハンパックしたらどうなる?これアスタリスクアンスにしたら
リストが3つになるのか。
まあいっか。普通に方文また書いて for i in range
range じゃなくて ans でプリント
ハンパック asterisk i で 出るはず。
アスタリスクにしたからあれか、スペース空いちゃって。 asterisk i .join
で括弧、スペース。 list object has not attribute join。あれ、ジョインできなかったっけこれ。
アスタリスクしちゃったから? アスタリスク消してもダメだね。
18:00
どうしたらいいのこれ。 for i in range。
リストオブジェクトはずあんアトリビュート ジョイン、Python
リスト
空白なし。 エンド
出力するだけならプリントにリストを渡す際にアスタリスクをつけてアンパック。
そうね。 エンドイコール何もなし。
アスタリスク i , エンドイコール
ダブルクォーテーション。 これでどうだ。
横一列につながっちゃったな。 アスタリスクを消してもダメだね。
エンドにしちゃうと開業がなくなっちゃうのか。 ジョイン関数ってどうなってたっけ。
Python ジョイン使い方。 そうか、文字列か。
使い方が違ったね。 先に
アスタリスクじゃないダブルクォーテーション. ジョインで
i を括弧の中に入れるんだ。 あ、やっとできた。
めっちゃ時間がかかったな。 で、入力例2は
斜めにシャープが入っている。 変更なしですね。
入力例3は
1個だけシャープがある。 シャープ1個を出す。
入力例4は なんかちょっと複雑な感じになっているがどうだ。
大丈夫そうですね。提出していきます。 24行
書いてる。 提出。
AC。あー良かった。ちょっとこれ後で答え見よう。 他の人の。
21:00
B問題のPython。この人ACしてるな。 あ、でも長いなこの人も。
はい、じゃあちょっとC問題。 時間が結構使ってますが、せっかくなのでやってみます。
C問題。キャンドル図。 問題文。数直線上にN本のロウソクが置かれています。
左からI番目のロウソクは座標XIに置かれています。 ただしX1小なりX2…小なりXNが成り立ちます。
最初のどのロウソクにも火がついていません。 すぬけくんはN本のうちK本のロウソクに火をつけることにしました。
今すぬけくんは座標0にいます。 すぬけくんは数直線を左右に速度1で移動することができます。
また自分と同じ座標のロウソクに火をつけることができます。 このとき火をつけるのにかかる時間は無視できます。
K本のロウソクに火をつけるのに最小な、必要な最小時間を求めてください。 N本のロウソクのうちK本のロウソクに。
それぞれのロウソクは座標XIに置かれている。 K本のロウソクに火をつけるのに最小の時間。
だから一番範囲を区切って指定して、一番差が狭いロウソクを考えればいいということですね。
入力例1はNが5、5本のロウソクがあってK3本ロウソクをつければいい。 その中で最小時間を求めよう。
座標はマイナス30、マイナス10、10、20、50。 出力例は40。次のように移動しながらロウソクに火をつければ良いです。
座標0からマイナス10。左から2番目のロウソクマイナス10に火をつける。 座標マイナス10から10へ。
で座標10から20へ移動する。 これは
何?DPとかになるの? 時計なさそうだなぁ。
NとKをマップ。 イント、インプット、ロットスプリット。
で、キャンドルリストはX。
XめんどくさいのでAにしましょう。 Aイコールからのリスト。
ん?リストいらないのか。 あ、いるな。リスト、マップ、イント、インプット、ロットスプリット。
で標準入力に入力例を入れます。
暑いな。 ちょっと服脱ぎたいけど音が入っちゃうのでやめときます。
24:00
で、はじめ0なんですよね。スタート。
スタートイコール0。でファンスに時間を入れるようにしておいて
DPイコール0かける
Nプラス10乗とかにしとく? 10乗というかNプラス10をかける
ぐらいにしておいて
はい、インレンジ
N
の
どうしようかな。そっか0の位置がわかんないんだなこれだと。
いやーちょっとB問題で体力を無駄に使ってしまったので
これは解けなさそうだな。C問題ちょっと早々に諦めをいたします。
あ、B問題のPython3のコード例ある。 あ、でも長いな結構。ちょっと後で見とこう。
はい、ではC問題の解説を見ます。 C問題キャンドル図。連続するK本のロウソクに火をつけるのが最適です。
N本のうち連続するK本のロウソクを選ぶ方法はN-Kプラス1通りしかないので全探索することにします。
連続するK本のロウソクのうち最も左のものをLとし最も右のものをRとします。
LとRを訪れれば自然と残りのロウソクを訪れることになります。
よって座標0を出発し座標XLと座標XRを共に訪れるための最短時間が求めるべき値です。
これが次の2通りの値の最小値です。 LからRの順に訪れる場合XLの絶対値プラスXR-XLの絶対値。
RからLに訪れる場合はXRの絶対値プラスXR-XLの絶対値。
連続するK本のロウソクを選ぶ方法を全探索しこの値の最小値を求めればそれが答えです。
時間計算量はオーダーNです。
そういうこと?ちょっとわかったかも。
実装できそうであればやってみますか。
DPとかじゃないですね。この解説のやり方でやるなら。
27:01
だからリストAは絶対にKよりは大きい。K以上なので。
スタートは0でしょ。
RとALがある。
ARとALがあって。
ARはAのiプラスK番目。
ALはAのi番目。
で
そうか。暗数はでかい方がいいのか。
10の10乗。暗数イコールMIN暗数AR-AL。
だからABSのARプラスABSの、さっき書いてあったことをやるだけなんですが。
AR-ABAL。
で、これのALスタート番も書いて、フリント暗数かな。
リストインデックスアウトオブレンジ。K-1かな。iプラスK-1かな多分。
0インデックスなんで。
ん?リストインデックスアウトオブレンジ。なんでなんで。
Kでしょ。
あ、そうか。
レンジNがN-Kか。
70。
いやいやいや。40って書いてるよ。
iプラスKがNをオーバーしたらブレイクするようにしたらいいのかな。
30:22
リストインデックスアウトオブレンジ。
いや、わかんないや。
他の方の提出例見ておきます。
ではまた次回お疲れ様でした。