D - Preparing Boxes (opens new window)

概要

• $N$個の箱にボールを$1$個入れるか否かを選べる
• 以下を良いボールの入れ方とする
  • $1$以上$N$以下の任意の整数$i$の倍数が書かれた箱の個数の和を2で割った余りが$a_i$
• 良い入れ方を1つ求めよ
  • 存在しない場合は-1を出力せよ

思考

• 大きい方から入れていき, 入れた時にその公約数の箱に値を伝播させれば良さそう
• 実装がうまくいかない

ここで30分終了

• 実装して提出
• RE?
• wandboxで試す
• メモリの二重解放を示唆される
• 配列外参照でした

ここで10時間くらい別のことをする

• 改めてコードを見ていると, 1-indexedで書けば良いのでは?と思う
• 書く
• 通る

気づいたこと

• 配列の中身が計算結果になるような時は1-indexにすると良い
  • 部分的に1-indexedにするのではなく, 全てを0/1-indexedで統一すると良い
• マクロを使っているとコードが見にくく(醜く)なるので普通ので書いても良いかもしれない
  • マクロは問題が解けるようになった次の段階?

提出

• 提出 #7376990 (opens new window)