京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)に参加しました。
結果
A,B問題の2問正解でした。
なかなかに酷い結果だった。C問題でハマり、D問題を先に解こうとしたけどTLEなり、 改善案がぱっとは思いつかなかったのでC問題に戻ったけど最終的にC問題も解けず…
A - 484558
入力された数値を16進数に変換するだけの問題。 A問題にしてはちょっとめんどくさい気がする。
16で割った余りを求めて、16で割ってを繰り返して16進数変換後の各桁の値を求めつつ、 各桁の値を文字列に変換していった。 C++なら文字列の0～9は'0'に0~9を足せば用意できるし、A~Fは'A'に０～５を足せば用意できる。 なので各桁の値が9以下ならそれを'0'に足して10以上なら10を引いたものを'A'に足す。
あとは変換後の文字列が1桁なら先頭に0を足して出力すれば良い。
B - Maintain Multiple Sequences
多次元配列の指定された要素を出力する問題。 多次元配列の扱い方を知っているかどうかの問題だと思う。
特に詳しく考える必要もなく、入力を配列に入れてその後指定されるQ個の要素を順番に出力する。 ちょっと気をつけるとすると配列は0始まりに対して、要素の指定は1始まりなので1つずらしてあげるくらいかなあ。
こっちがA問題でも良い気がする。
C - Manga
微妙にハマってACできなかった…
基本的にシミュレートで答えを求めようとしたけどうまくシミュレートできなかった。
考察としては
- 最初N冊しか持っていないので答えとしてありえる最大値はNになる。
（N冊本を持っていて1巻ずつ順番に読むのでN+1巻以降は絶対に読めない。） - 同じ巻は2冊以上いらない。
- 2冊売って1冊買うので操作を繰り返すほど手元の冊数は減っていく。
なので最初に売って問題ない本が何冊あるのかを数えて何冊買えるのかを計算する。 あとは1巻から順番に揃っているかどうかを確認していった。足りない巻数がある場合は買える冊数を1消費して買ったことにして次を見ていった。
あとはWAになる度にどんなパターンだとだめか考えて修正してを繰り返していったけど、完全に直しきることはできなかった。
D - Flip and Adjust
サクッと実装してみたけどTLEになったし修正方法もすぐには思いつかなかった…
はじめはDPで解こうとして、DP[i番目のカード][表・裏]=和 として解こうとしたけど最終的にN枚のカードの表裏の情報も必要になるので違うかなと思って別の解き方を考えることにした。
次に思いついたのが幅優先探索で全通り試してみる方法。
とは言えNの最大値が100なので計算回数が最大ででざっくり計算すると
なので十中八九TLEしそう。
サクッと実装して提出してみたけど案の定TLEした。この方針だと特に計算量の改善方法が思いつかなかった。
解説を読むとDPで解くのが想定解だったっぽい。
