読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

ABC006を解いてみた

ABC 競技プログラミング

abc006.contest.atcoder.jp

A問題

 一桁なので3のつく数は3のみで、3は3の倍数です。なので、3の倍数かどうかを確かめるだけで判定可能です。あとは出力するだけです。特につまづくことなく成功でした。

B問題

 再帰を使った処理だと遅すぎるだろうなーと想像がついたのでforループでトリボナッチ数列を求める処理を実装しました。それだけの処理で提出したところTLEで失敗…加算であればmodを使っても計算が成り立つことを思い出し前3つの和の10007の剰余を計算していく方法で実装しました。
 あとはn=1, 2, 3のときに出力する数字を別に処理して出力します。

C問題

 大人、老人、赤ちゃんの数の組み合わせのについて全探索するのではどう考えても実行時間に余裕がなさそうです… 昔算数でやった鶴亀算を思い出してその要領で求めました。まず全員大人だと仮定して、足りない数の分赤ちゃんや老人に置き換えていきます。int((m-n*2)/2)分大人から赤ちゃんに置き換えます。そして、(m-n*2)が奇数であれば一人分大人から老人に置き換えます。これだけで提出したところ例外処理が足りていなかったため残念ながらWAでした。
 全員赤ちゃんとしても数が足りないパターンと全員大人としても数が多すぎるパターンのときに-1 -1 -1を出力するように書き換えて提出して、成功!

D問題

 部分点10点の方法しか思い浮かびませんでした… その数字が最後になるときの最長の数列の長さを記憶することによる動的計画法の実装、さらに最長のの数列の長さで一番小さい数字を覚えていく方法(最長増加部分列)といった方法など発想できるようにがんばっていきたいです。

 Python3の標準入出力にはひとまず慣れてきて何も見ずにかけるようになってきました。あとmodの中での加算や乗算が成立することから変数のメモリを節約する方法だったりも思い浮かぶようになってきました。アルゴリズムの発想やコードの実装など頑張っていきたいです。