ABC218参加記
abc218にバーチャル参加しました。
A問題
(問題URL) :
ポイント
- 文字列のi番目を取り出す
この問題は、まず、天気予報が文字列で入力されます。C++では、<string>内のstring型が有用です。
文字列:sのi番目を取り出すには、添え字演算子:[]を使って、s[i]とできます。ただし、添え字は0から始まっていることに注意です。(そのため、1日目ならば、s[0],2日目ならばs[1]とする)
あとは、その文字が'o'かどうかを調べて、条件分岐すればOKです。
(提出URL) : https://atcoder.jp/contests/abc218/submissions/25845806
B問題
(問題URL) :
ポイント
この問題では、数字をアルファベットに変換する必要があります。そのような問題で大切なのが、アルファベットなどの文字とアスキー文字コードの連続性です。
プログラム上では、数字、アルファベット、日本語*1などのすべての文字が、文字コードとして、変換されていますが、その中でも、0~9,A~Z,a~zは、いずれもこの順番で連続になっています。そのため、'a'から3つ後の文字列は、'a'+3 (='d')などのように表すことができます。
参考: https://e-words.jp/p/r-ascii.html
これを踏まえると、辞書順で小さい方から $P_i$ 番目の英小文字というのは、辞書順で最も小さい英小文字である'a'から、$P_i -1$足した文字になります。
(提出URL) : https://atcoder.jp/contests/abc218/submissions/25845874
C問題
(問題URL) : atcoder.jp
(実装が面倒くさそうだったので飛ばしました...)
D問題
(問題URL) :
ポイント
- 定義を言い換えてみる
まず、選んだ4つの頂点が全ての辺が x 軸または y 軸に平行であるような長方形である条件を言い換えて、次のようにしましょう。
a,b,c,d という整数が存在し、(a != b , c != d)選んだ４つの頂点の座標が(a,c),(a,d),(b,c),(b,d)である
そうすると、対角線上に2つの頂点を選べば、あとは、条件を満たす2つの頂点があるかを調べれば良いです。
このような探索には、setのfindメソッドを使うことで、setに入っている要素数をNとして、O(log N)で使えます。
計算量はO(N2 log N)≒4 \times 107なので、十分に間にあります。
(提出URL) : https://atcoder.jp/contests/abc218/submissions/25846168
E問題
(問題URL) :
ポイント
- 問題を言い換える
この問題は、辺を連結になるように取り除き、その時に報酬を得るようになっています。しかし、辺を削除するという操作は一般的にやりにくいため、辺を追加しても、同じように言い換えてみます。
まず、高橋君はsum(C_i)を得ている。 ここから、グラフが連結になるように、辺:iを加える。その時、高橋君は-C_iを得る。
そのようにすると、最小全域木の問題になるため、クラシカル法などを使って解くことができます。
しかし、厄介なのは、元のCの値がマイナスの場合ですが、これらの辺は、取り除くと報酬が減ってしまうため、初めに連結・非連結に関わらす、グラフに追加します。(特に、有効辺でやっているときは要注意)
(提出URL) : https://atcoder.jp/contests/abc218/submissions/25847172
(このコード、辺がすべて多重辺+コストも同じの場合に弱いような気がするが...)
コンテストを通して
(コンテスト中の提出):
最終的に、A+B+D+Eの1200点の57:10+1WAで実際のコンテスト相当で1764位のperf1210でした...
グリッド上の探索が解ければ、レートが下がるところだったようなので精進します...
また、はてなブログでのatcoder解説では、文字制限もなく、マークダウン記法などもあって、自由に書ける一方、その分、時間がかかる(1時間程度経っている)ので、時間があるときにやっていきたいと重います。
