AtCoder Beginner Contest 343に参加しました。
結果
A,B,C,Dの４問正解でした。
E問題が訳わからなすぎたのでF問題を解こうとしてみた。
多分セグメント木を使って解く問題なんだろうなと思ったけど、セグメント木のソースを用意していないし、
アルゴリズムもよくわかっていないのでぶっつけ本番で実装するのは無理だった。
1時間くらいは時間があったからセグメント木のアルゴリズムとか説明しているサイトを見ながら実装しようとはしたんだけど…
A - Wrong Answer
問題文の通り処理する問題。
0~9のうちA+Bと等しくないものを１つ出力すればよいので、 A+Bが0かどうか確認して、0じゃないなら0を0なら1を出力するくらいの実装でACできる。
B - Adjacency Matrix
接続行列が与えられるので、各頂点に接続している頂点を昇順に出力する問題。
頂点1から順番に処理しつつ、
頂点1から順番に今処理している頂点に接続しているかどうかを確認して、接続していればその頂点番号を出力していけば良い。
ループ処理をうまく使えば2重ループで簡単に処理できる。
C - 343
N以下の整数のうち立方数かつ回文となっている整数の最大値を出力する問題。
Nは以下の正整数なので線形探索するには流石に無理がある。
N以下の立方数だけを対象に回文かどうかを判断して条件にあう数を探すことにした。
こんな具合にforでループさせるとN以下の立方数（i＊i＊i）だけを対象に探索ができる。
for(long long i=1;i*i*i<=N;i++)
ある数が回文になっているかどうかは1桁ずつ分解して先頭からi番目と後ろからi番目が同じ数字になっているかどうかで確認した。
D - Diversity of Scores
コンテスト中、誰がどのタイミングで何点取るかがわかるので、毎秒選手たちの得点は何種類の値があるかを答える問題。
どうやって値を管理しようか悩んだけど愚直に解くことにした。 選手の得点を管理する変数と、連想配列で何点の選手が何人いるか管理する配列、今得点には何種類の値があるかを管理する値の3つを組み合わせて答えた。
ある時点で選手が得点すると、もともと何点で得点後は何点かをもとに、何点の選手が何人いるかの変数をメンテして、 その結果ある点数の人数が0になったりある点数の人数が0人から1人になったりをもとに、今得点には何種類の値があるのかの変数をメンテしていった。
F - Second Largest Query
数列が与えられるので指定した要素の値を更新したり、指定された区間で2番目に大きい数は何個あるかを答えたりする問題。
配列の一部の要素を更新しつつ、指定区間で条件を満たすものを答える系の問題なのでセグメント木を使って解く問題だと思った。
セグメント木はアルゴリズムを理解して自分用にコードを作ろうと思いつつ後回しにしていたので細かいアルゴリズムはわからず解くのは諦め気味だった。
セグメント木のアルゴリズムとかを説明しているサイトを見つつ即席で実装を始めてみたけどちょっと間に合わなかった。
考えた解き方としては2つセグメント木を用意して、一方では指定された区間の1番大きい数、2番目に大きい数のペアを管理して、もう一方の木で指定区間で2番目に大きい数を数えていけば答えられると思った。
最近セグメント木を使う問題の頻度が高い気がするから早めにソースを用意しておきたい…
