#2 競技プログラミング日記
この記事について
この記事は自分が解くことができた問題の解説と躓いた問題でどこで躓いたのか初心者視点から解説していく記事です😃
今回のコンテストの反省
今回のコンテストではA,B問題は速攻で解くことができたがC問題でTLE連発で躓いてしまった(>_<)原因としてはpython のindex関数の計算が多いことが原因で言語仕様を知ることの大切を再認識することができました。
A問題
A問題解説
今回の問題でめんどくさい点はABC 001~ABC349までの文字列と比較しなくてはならずこれをどうやって早く入力するのか?という点だと思います。僕は今回はpython を用いているので以下のように
ABC001〜349を入力しました!
contests = []
for i in range(1, 350):
if i != 316:
contests.append(f"ABC{i:03}")
そのあとは、以下のようにif文を用いてこの配列の中に含まれるのかどうか
判定しています!
s = input()
contests = []
for i in range(1, 350):
if i != 316:
contests.append(f"ABC{i:03}")
if s not in contests:
print("No")
else:
print("Yes")
B問題
B問題解説
この問題は制約条件から十分に計算数が少ないので全探索で回答できると考えられます!
さらに問題文、穴Tに歯が生えていたら抜く、そうでない場合生やすより
反転すれば良いのかな?ということがわかると思います。
反転をするという事は,True,Falseのような真偽値で表した方が扱いやすいという事がわかると思います。なので問題文より全ての歯に歯が生えていると仮定できるので以下のようなコードで表す事ができます!
#標準入力を受けとる
n, q = map(int, input().split())
t = list(map(int, input().split()))
# 初期状態では全ての穴に歯が生えている
teeth = [True] * n
not を用いて真偽値を反転させる事できるのでこの処理をTで指定された
位置のみこのnotの処理を適用する事を行います。そのあとTrue==1であるので最後に処理後の配列をsumで合計値を求めこの値を出力することで
正解✅になります!
n, q = map(int, input().split())
t = list(map(int, input().split()))
# 初期状態では全ての穴に歯が生えている
teeth = [True] * n
for hole in t:
# 穴の番号は1から始まるので、1を引いてインデックスに変換
hole_index = hole - 1
# 穴に歯が生えていれば抜く、生えていなければ生やす
teeth[hole_index] = not teeth[hole_index]
# 最後に残っている歯の本数を数える
remaining_teeth = sum(teeth)
print(remaining_teeth)
C問題
C問題反省(T . T)
数学の整数問題のようにとりあえず上記画像のように実験してみるとすぐに
1から順に下の画像のように住所録を作成しその配列の要素数の値でなかったら住所録にかかれている場所の値と入れ替えていく事で回答できると考える事ができます。
この回答の方針はOKですが一つ落とし穴があり住所録のかわりに,python の
指定した値の配列中の位置がわかるindex 関数を用いて回答するとindex関数の計算数がo(n)なのでn回実行するfor文中にあるとo(n^2)となってしまいTLEしてしまいます( i _ i )僕はこれにハマり今回のコンテストはA,B問題までしか回答できませんでした〜
コンテスト結果
ganesya0112さんのAtCoder Beginner Contest 350
(Promotion of AtCoderJobs)での成績:6697位
パフォーマンス:482相当
レーティング:53→87 (+34) :)
Highestを更新しました!
#AtCoder #ABC350(PromotionofAtCoderJobs)
今回のコンテスト結果は以上の通りでした!
これからも茶色目指して頑張りたいです(^。^)
この記事が気に入ったらサポートをしてみませんか?