0.はじめに
ABCの参加履歴とその時の所感を個人的にまとめたメモです。
1.A問題
4つの数字をmapで受け取って計算しながらアウトプット。
文字列は、問題文からコピペすると後ろに半角スペースがつくからそこは注意。
https://atcoder.jp/contests/abc269/submissions/34921671
2.B問題
なかなかてこずった問題。
条件から高々100マスの走査×２なので、時短の工夫は排除
縦横方向それぞれのチェックで、”＃”が初めに出てくるアドレスと
”＃”が初めに出てきた後”.”が初めに出てくるアドレス-１で
abcdを求める。
縦横がごっちゃになってしまい、求める順番がcd→abとなってしまった。
テストの結果、上記方法だと10マス目が＃だった場合に判定できないことが
分かり、10マス目が"＃"だった場合の判断も追加して合格
https://atcoder.jp/contests/abc269/submissions/34937220
3.C問題
最初見たときは難解で、D問題移行に逃げようと思ったが
そっちも難しかったのであきらめて取り掛かる。
例題等を見ているうちに以下の流れで行けそうとつかむ。
(1)Nを2進数の文字列Sに変換
例）11→1011
(2)２の”S内の下から桁数乗”の数列をLSを作成
例）1011→(1,2,8)
(3)LS内の数字の全組み合わせ+0のリストansを作成
例）(1,2,8)→（0,1,2,3,8,9,11）
(4)ansを小さい順に1行毎出力。
実装時メモ
(1)Nを2進数の文字列Sに変換
2バイト変換は”bin”を使う、頭に”0b”がつくから文字列にした後排除
S=str(bin(N))[2:]
(2)２の”S内の下から桁数乗”の数列Lを作成
下から何桁の求め方がスマートに行かなった・・・。
j=len(S)-i-1
(3)L内の数字の全組み合わせ+0のリストansを作成
itertoolsを使用
import itertools
略）
ans=[0]
for n in range(1,len(L)+1):
for conb in itertools.combinations(L, n):
ans.append(sum(conb)) #タプルをリスト型に変換
問題の読解力と、やればできるの精神が大事だと思いました。
https://atcoder.jp/contests/abc269/submissions/34946002
4.D問題
プログラミングの勉強で今一しっくりこなかった
再帰関数を使うんだろうなーと思いつつも
残り30分だったのでテスト日はあきらめました。
後日挑戦したら、意外と30分で行けたかもと思えました。
以下の方法での実装を検討
(1)考察１
1)X,Y,グループ(初期値-１)のリストを作る
2)上からリストを読み、読み込んだペアに該当する
ペアがあるかを判別
3)最後にグループ数カウント
ペア数が1000とはいえ、TLEくさいな・・・と判断
(2)考察２
1)2000×2000の枠を作成
2)X,Yそれぞれで枠を埋めていく
3)隣り合った組がどれくらい合うかをカウント
2000*2000を端から見ていくのが非効率的過ぎると判断
(3)考察３
1)2000×2000の枠を初期値0で作成
2)X,Yのアドレスに該当する枠のマスを-1で埋めていく
3)枠とは別にX,Y,グループのリストを作成
4)リストを上から見ていき、該当ペアの枠内
X,Yのマスが-１かをチェック、-1だったら
グループ番号を振り(1から始めグループごとに
カウントアップ)
隣り合った黒マスがあるかを再帰チェック
隣り合っていれば、振られたグループ番号で
枠内のマスを埋める
-1でなかったら、グループが設定されていると判断
5）振ったグループ番号最大値＝グループ数となるため表示
なんとなく、無駄な手順が挟まっている気もするが実装。
実装のポイント
1)2000×2000の枠を初期値0で作成
→枠の範囲の端っこだったら・・・とかの判定を最初入れていたが
めんどいので2100×2100とした。
2)X,Yのアドレスに該当する枠のマスを-1で埋めていく
→X,Yにマイナスがありえたので、すべて1050を足して
正の整数とした。
4)再帰関数
→以下のように関数だけ書くと、うまく動かなかったので
強引に戻り値を設定した。
競プロでしかPython使ってない経験の浅さを露呈
G_chk(XX,YY,now_G,H)
Q=G_chk(XX,YY,now_G,H) #Qはこの後何にも使わない・・・
LTEになったら打つ手なしだな・・と思ったが
すんなり通ってよかったです。
https://atcoder.jp/contests/abc269/submissions/35025956
5.E問題
なんとなく行けそうだったので挑戦
インタラクティブ問題好きだけど、テストしにくいのが難。
考察
最大1000マスで、1マスだけ埋まっていないマスを探す
ということで、2分探索すればいいんだろうなとあたりをつけるが
正直2分探索をコード化するといつも失敗するのでこわごわ取り掛かる。
問題自体は、駒が置かれていない行と駒が置かれてない列を
それぞれ求めるだけ。
行を求める時は、列は１～Ｎ指定、列を求める時は行を１～Ｎ指定とし
走査範囲列と、コンピュータの回答が同じか、ー１かで
走査範囲内に、空きがあるかないかを判断できた。
理屈は簡単だが、2分探索ロジックがうまく書けずてこずりつつ
特にこれといった山場もなく合格。
https://atcoder.jp/contests/abc269/submissions/35044570
Ｆ以降は、できるようになったらやってみようかと思います。