1
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?

0.はじめに

 先週はがくんとおちたので挽回しないとなと思う今日この頃
 A、Bは普通に解けましたが、Cが異様にむずかしい・・・。(既視感)
 なんとか行けそうなところまで持っていきましたが
 結局TLEが解消できずに時間切れ。
 解説は見ずに時短の工夫を施してなんとか
 ACとなったのは11分後でした・・・。
 
 レートは-39の728とちょっと前の水準にもどりました。

1. A - Unsupported Type

 言語によって難易度が変わりそうな問題。
 pythonなので、それぞれ値を読んだ後、
 XがリストA内にあるかをinで判定し
 結果を出力して終了。 

 https://atcoder.jp/contests/abc415/submissions/67707743

2.B - Pick Two

 回答の出力方法等若干癖があった問題。
 #が偶数個あることが定義されているので
 素直にループを回しながら先頭からSを見ていき
  #だったら出力用項目に保持し
  カウンターを1アップし
  Sの#を.に置き換え
  カウンターが1だったら”,”を出力用項目に追加
  カウンターが2だったら出力
 上記ループをSに#がなくなるまで繰り返しました。

 https://atcoder.jp/contests/abc415/submissions/67719034

3.C - Mixture

 まず問題の読解に時間がかかり
 その後思い描いた実装がうまくコーディングできずWAを連発し
 実装できたと思ったらTLEを解消できず時間切れになりました。

 【考え方】(以下ケースごとの処理)
  1.なってはいけない状態を辞書Dに登録(効率を考え後にSETに変更)
  2.N個の0を持つリストを用意しデキューqに追加
  3.以下キューが無くなるまで繰り返し
   -1.キューからリストXを取り出す
   -2.リストXを先頭から見ていき、0の時、1に変更して
     連結し、2進数と見た場合の値(状態)を求め
     Dになければ、その状態のリストをキューに追加
   -3.3-2.で作成したリスト内に0が無い時Yesを出力し
     ループ終了
  
  上記考え方で最初失敗しつつ、TLE7個まで持っていけました。

  その後高速化の工夫として以下を実施しました。
   1)辞書Dをセットに変更
   2)セットrを用意し、以前キューに追加したことがあったかを保持し
    ある場合はキューに追加しないようにする

 2)が功を奏しTLEが解消しました。

 高速化の工夫を最初の実装段階から意識に入れて行っていればなと悔やまれました。

 https://atcoder.jp/contests/abc415/submissions/67760979

以上

1
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
1
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?