0.はじめに
ARCは難しいなと思いながら取り組んだら、意外とABでACをもらえて
びっくりしました。
ARC160も参加してたのですが記事を書けるまでの感触すらなく
Qiita投稿もスルーしました・・・。
C問題以降は、歯が立つ感じがしなかったので1時間ですっきり終わりました。
コンテスト後レートが更新され、+34で過去最高の713を頂きました。
1.A - Make M
解き方をいろいろ考えたのですが、最終的に以下の考え方で進めました。
考え方
1.リストAを読み込み、大きい順に並べる。
2.大きい方からyc(=(N-1)//2)個を山候補として変数yamaに格納。
(A[yc]以降は谷候補となり、理論上リスト先頭から埋めていき
山候補を最後まで超えなければYesだめならNoとなる)
3.以下変数iを0からyc-1まで繰り返し
3-1.yama[i]>A[yc+i] and yama[i]>A[yc+i+1]の時次のiへ
3-2.3-1を満たさない時は、山を形成できないので”No”を出力して終了
4.3で終了しなければ”Yes”を出力して終了
点数的に考えてもビギナーのC問題と考えればまぁ納得の難易度でした。
https://atcoder.jp/contests/arc161/submissions/41804987
2.B - Exactly Three Bits
あまりBまで解けたことないのでちらっと見たら、意外と簡単そうだったので
取り組んだら、すんなり解けました。
考え方
1.Nを2進数にした時の1の数をカウントする関数
bit_countを準備
以下T回繰り返し
2.Nを入力
3-1.Nが7より下の時、条件を満たせないので-1を出力
3-2.Nが7以上の時
3-2-1.bit_count(N)=3の時、Nを出力して次の繰り返し
3-2-2.bit_count(N)>3の時
3-2-2-1.Nを2進数に変換したのち、文字列として先頭から読んでいく
3-2-2-1-1.先頭から3つ目までの1を活かしそれ以外は0とした2進数
文字列ansを作成
3-2-2-1-2.文字列ansを10進数で出力して次の繰り返し
3-2-3.bit_count(N)<3の時
(最初は文字列操作で答えを求めようとしましたが、1の数が
2以下になる数は稀であるので以下の方法に)
3-2-3-1.Nから1をマイナスし
3-1.~3-2-2-1-2.と同様の処理を行う。
Nから1マイナスした数も、bit_count(N)<3の時は
さらに1マイナスを繰り返す
https://atcoder.jp/contests/arc161/submissions/41809308
以上