Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@marche(古川 隼)

競プロ備忘録#1　ABC197

Last updated at Posted at 2021-03-31

趣味で競プロ始めたので、後でざっと見直すための自分用のメモ書きとして。
問題の解説ではなく、こんなこと考えればよかったなとか、これ知っとけばよかったなとかを書いていきます。
#AtCoder Beginner Contest 197

  • 初めてのコンテスト。とりあえず紙一枚用意。半分しか解かなかったので表面だけで済んだ。毎回2枚用意しておけば十分な気がする
  • 言語はpython3でやったけど、次回からはpypyを使うようにする。python3は実行速度が遅すぎる。書き方自体は変わらないはず
  • ゆくゆくはC++もちゃんと勉強したほうがいいかも？
  • ABCは毎週土曜にあるということで大丈夫ですかね→全然そんなことないわ、ABC以外のコンテストにも積極的に参加しないと経験積めなそう
  • ARCは毎週日曜にある？今度問題見てみて、参加する意味ありそうだったら参加してみる。→全然そんなことない
  • 過去問はいつでも解けそうなので、基本的には過去問といてメモ書いてって感じで勉強していく
  • とりあえずABCは余裕で全問解けるように。言うて全くわからんってやつはなかったので一ヶ月以内には時間内にできるように頑張る！

#A.Rotate

長さ3の文字列Sが与えられて、最後の文字を一番初めに持ってきた文字列S'を返す問題。

入力
S

出力
答えを出力

  • とりあえず入力は
input()

で、呼び出すたびに一行ずつ文字列で入ってくる。

  • 文字列はリストみたいにインデックスでi文字目の文字を呼び出せる。全部str型なので普通に足し算して終わり。
解答
S=input()
print(S[1]+S[2]+S[0])

#B.Visibility

障害物の有無が.,#で表されたH✖️Wのマス目で、マス(X,Y)から見えるマス目を数える問題。見えるとはそのますから上下左右に#がぶつかるまである.の数。自分自身も数える。(#に囲まれてる個数じゃなくてよかった。)

入力
$ H\quad W\quad X\quad Y\ $
$ S_1\ $
$ S_2\ $
$ S_3\ $
$ \vdots\ $
$ S_N $

出力
答えを出力

  • 空白で区切られた数字のinput()の扱いに注意。map()の返り値はlistではなくmap object(一種のイテレーター)なので扱いに注意。いつかいろいろ検証。
H=map(int,input().split())[0]
W=map(int,input().split())[1] 
#上と下でinput()の中身が違うのでおかしくなる。そもそもmap objectの中身をインデックスで呼び出せるかどうかは調べる必要あり。

l1=list(map(int, input().split()))
#これでやれば確実。知ったの後になってなのでこの問題ではやってないけど
  • X,Yの座標が普段使ってるのと逆なので注意。
  • 基本的にはX,Yから上下左右に進んでいって、.だったら+1して次のマスへ、#だったら終了を繰り返す。
  • for文の範囲がごっちゃになるので、例題の図を書いて具体的な数字でやるとミス減らせる。ゆくゆくは反射的にわかるように。
  • 自分自身も含むのでans=1で初期化
  • reversed(range(x))で逆から読み込み。range(0,x,-1)でもいけるはずだけどなんかうまくいかなかったので今度調べる。
  • a,b,c,d=~で初期化するやつ便利そうなので今度調べる。
解答
l1=input().split()
H=int(l1[0])
W=int(l1[1])
X=int(l1[2])
Y=int(l1[3])
ans=1
S=[]
for i in range(H):
  S.append(input())

for i in reversed(range(0,X-1)):
  if S[i][Y-1]==".":
    ans+=1
  else:
    break

for i in range(X,H):
  if S[i][Y-1]==".":
    ans+=1
  else:
    break

for i in reversed(range(0,Y-1)):
  if S[X-1][i]==".":
    ans+=1
  else:
    break

for i in range(Y,W):
  if S[X-1][i]==".":
    ans+=1
  else:
    break

print(ans)

#C.ORXOR

数字のリストを何個かに区切って、各リストでOR演算した後にそれで得られたビットをXOR演算する。このとき得られるXOR演算の最小値を求める問題。

入力
N
$A_1\quad A_2\quad A_3\quad \cdots\quad A_N $

出力
答えを出力

  • OR演算=|
  • AND演算=&
  • XOR演算=^
  • NOT演算=~
  • 演算子の意味はググって
  • OR演算、XOR演算とは?ってなったけど、解説があったから助かった。
  • bitを扱うのは初めてだったけど、いろいろなところで使うので慣れておこう。
  • 自分でいろいろ実装しなくてもpythonの関数とかでいろいろ機能あるので今度ざっと見ておく。
  • 要するに数字の間に仕切りを入れるか入れないかを全通りやるだけって、いう思考の指針は立ったけど、コードにどうやってすんの？ってなって飛ばした。
  • bit全探索なるものがある。
>>>bin(i) #iの二進数表示の頭に0bつけたものを表示
"0b1001" #的な感じ
>>>1001 & 1 #論理積。どっちも1なら1(=Ture),それ以外は0(=False)を返す。1の位が1かどうか判別できる
1
>>>1001>>2 #1001を2桁右にシフト、空いたとこには0を入れる。左も同様
0010
>>>(1001>>2)&1 #これらを組み合わせたi桁目が1か0か判別
0
>>>for i in range(2**(N-1))
...  for j in range(N-1)
...    if((i>>j)&1):
...      ~
#こんな感じで全探索する
  • 2**(N-1)を(N-1)**2に間違えて1敗
  • TLEでありえん敗退
  • python3は遅すぎ、pypyの方が10倍ぐらい早かったので今後はpypyを使う
  • 最初はOR演算全部計算して、最後にXOR演算計算してたけどデータの無駄遣い。順次ORとXORを計算していけばリスト作らなくでもいける。
  • ans=0になった時点でbreakする人もいた
解答
N=int(input())
A=list(map(int,input().split()))
ans=2**30

for i in range(2**(N-1)):
  cor=A[0]
  cxor=0
  for j in range(1,N):
    if (i>>j-1)&1:
      cxor^=cor
      cor=A[j]
    else:
      cor|=A[j]
  cxor^=cor
  ans=min(cxor,ans)
print(ans)

#D.Opposite

正2n角形の頂点Pが反時計回りに並んでいて、p_0,p_nの座標が与えられているので、p_1の座標を求める問題。

入力
N
$x_0\quad y_0$
$x_{N/2}\quad y_{N/2}$

出力
$x_1\quad y_1$

  • こんな問題も出るんだってなった。普通に数学として解いた。
  • 行列とか複素平面とか使いこなせないので地道に解いたけど、ゆくゆくはそのへんも
  • math万能。詳しくは公式リファレンス参照

  • acos(),asin()の範囲に注意。$\theta$の場合わけがめんどかった。
  • math.atan2()を使えば場合わけしなくても正しい角度が出てくる。次回からはこっち使う。
  • 場合分けとかで頭こんがらがって変数名とかも変になってる。図は大きくシンプルに書きましょう。
解答
import math

N=int(input())
l1=input().split()
l2=input().split()
n=N/2
x0=float(l1[0])
y0=float(l1[1])
xn=float(l2[0])
yn=float(l2[1])
Ox=(x0+xn)/2
Oy=(y0+yn)/2
r=math.sqrt((x0-xn)**2+(y0-yn)**2)/2.0

radx=(x0-Ox)/r
rady=(y0-Oy)/r

if radx>=0 and rady>=0:
  rad=math.asin((y0-Oy)/r)
elif radx>=0 and rady<=0:
  rad=math.asin((y0-Oy)/r)
elif radx<=0 and rady>=0:
  rad=math.acos((x0-Ox)/r)
else:
  rad=-math.acos((x0-Ox)/r)

rad+=math.pi/n

x1=Ox+r*math.cos(rad)
y1=Oy+r*math.sin(rad)

print(x1,y1)

#E.Traveler

数直線上にN個のボールがある。それぞれに座標X_iと色C_iが決まっていて、色の大きさが広義単調増加になるように全てのボールを回収する。座標0から出発して秒速一で動くときの最小値を求める問題。

入力
N
$X_1\quad C_1$
$X_2\quad C_2$
$X_3\quad C_3$
$\vdots$
$X_N\quad C_N$

出力
答えを出力

  • 問題読んでちょっとして時間切れ。
  • 最初数直線が1~Nしかないと誤解。数線分ではないです。
  • 小さい色から回収していけばいいが、同じ色がある場合の回収方法が問題。
  • 同じ色の最短の回収方法は、まず現在地から近い方の端っこのボールに向かって、その後もう一方の端っこのボールに向かえば良い。つまり現在地→右端→左端の順番か、現在地→左端→右端の順番かの2通り。
  • 回収し終わったらどちらかの端にいる。
  • これらを利用して色i-1を回収し終わって座標xにいる状態から色iを回収して座標x'にいる状態までの時間を2通り分求めて、小さい方を記録していく。
  • 動的計画法(ある状態からある状態への変移に注目する方法?)はよく使いそうなのでたくさん問題といて慣れておく
  • 1≦C_i≦NなのでN個の空リストを持ったリストを作ってそこに書くボールを格納して行けば変に並べ替えたりしなくて済む。
  • a,b=map()はちゃんと動くっぽい
  • 最初は0から始まるのでedge[0]=(0,0)
  • edgeは色がないところは無視して作る方がシンプル。色の大きさの順番にしか意味はないので
  • インデックス関係ごっちゃになるのでちゃんとサンプルで確認する。特にout of indexには注意する。
  • デバッグ用のprint()系はちゃんと消してから提出すること(1敗)
解答
N=int(input())
color=[[] for i in range(N+1)]
for i in range(N):
  x,c=map(int,input().split())
  color[c].append(x)

edge=[(0,0)]
for i in range(1,N+1):
  if color[i]==[]:
    continue
  edge.append((min(color[i]),max(color[i])))

dp=[[0]*2 for i in range(len(edge))]
for i in range(len(edge)-1):
  l,r=edge[i]
  nl,nr=edge[i+1]
  length=nr-nl
  dp[i+1][0]=min(dp[i][0]+abs(l-nr),dp[i][1]+abs(r-nr))+length
  dp[i+1][1]=min(dp[i][0]+abs(l-nl),dp[i][1]+abs(r-nl))+length

ans=min(dp[-1][0]+abs(nl),dp[-1][1]+abs(nr))
print(ans)

#F.Construct a Palindrome

N頂点M辺の単純とは限らない連結な無向グラフがある。
辺iには文字$C_i$が書かれている。頂点1から頂点Nにいくまでに通った道の文字を順につなげて文字列を作るとき、回文になるならばその際の文字列の最小の長さを求めよ。同じ辺は何回通っても良い。

入力
N　M
$A_1\quad B_1\quad C_1$
$A_2\quad B_2\quad C_2$
$A_3\quad B_3\quad C_3$
$\vdots$
$A_N\quad B_N\quad C_N$

出力
答えがあれば答えを、なければ-1を出力

  • むずかすぃ
  • グラフは慣れるまでは難しそうだし、慣れるまで時間かかりそう。なるべくたくさん実装して慣れよう！
  • と思ったけど、一つ一つの考え方は簡単そう。いつか別記事でまとめる。

###取り急ぎのグラフについて

  1. 単純グラフ→始点と終点が同じ辺(ループ)が無いかつ、始点と終点の組み合わせが同じ辺(多重辺)が複数個ない
  2. 連結→全頂点が地続きであるということ
  3. 無向グラフ→一方通行でないということ
  • 回文である→偶数長と奇数長で分けて考える。
  • 偶数長なら1→xとN→xが同じようなxがある。
  • 奇数長なら1→xとN→yが同じようなx,yがあり、x,yが隣接している。
  • 解説見てもよくわからん→完全に理解した
  • 文字列を両端から辿っていくと必ず等しくなるはずなので、それが可能な頂点の組み合わせだけでグラフを作る。
  • 具体的には(1,1)から(N,N)までの$N^2$の頂点を用意する。各頂点はxとx’、yとy'の間に辺があり、かつ辺の文字が同じ場合に辺を張る。
  • こうしてできた新しいグラフで考えれば良い。
  • 文字で書くとややこしいので、入力例2を参考に図で考える
    figure_1.jpg
  • 後はコードにするだけだけど頭こんがらがったので簡単なやつでグラフの練習してからにしまーす。
  • リストの内包表記に注意
list=[[[]]*N] #これだと全て同じオブジェクトになる?つまりもう一度初期化しないと同期したまま？
list=[[]for i in range(N)] #これなら違うオブジェクトで二次元リスト作れる
  • 文字列をUnicode値にするにはord()その逆はchr()
  • from collections import duqueで普通にdequeが使えるらしい
  • 何回通ってもいい系は総当たりの新しいグラフ作るのがセオリーだったりする？

#結果
スクリーンショット 2021-03-31 17.35.22.png

相場がわかんないけど、思ってたより上の方だった。3問しか解けてないのに…。毎回こんな書いてたら書く方ばっかに時間が取られるので、当たり前を増やしてもっとメモ書き程度にできるようにする。次回はもっと頑張る！

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?