AtCoder Heuristic Contest 025参加記
AtCoder Heuristic Contest 025
AtCoder Heuristic Contest 025に参加しました。 問題文はこちら↓ atcoder.jp
今回でヒューリスティックのレートが青色になりました！
問題文概略
- N個のアイテムをD個の袋に、重さができるだけ均等になるように分ける。
- アイテムの重さを直接知ることはできず、天秤を使って判断する。
- 天秤の左右の皿にアイテムを好きなだけのせると、{左に傾く, 右に傾く, 釣り合う} のいずれかの結果が得られる。
- このクエリをQ回行うことができる。
得点は、袋の重さの分散が小さいほど良い。
制約
- 30≤N≤100
- 2≤D≤N/4
- 2N≤Q≤32N
問題文を読んで思ったこと
- 最初に連想したのは、天秤を2回使って8枚のコインから軽い偽物を見つけ出す問題です。しかし今回の問題にはあまり関係なさそうです。
- 比較ができるということは、比較ソートができそうです。
- 暫定的な解を作ったとして、それの良さを判定するのが難しそう。
- 解の評価にもクエリ回数を消費してしまうので、焼きなまし法は向いてなさそう？
正の得点を得る
まずは正の得点を得られるコードを書きます。 なかなか解法が思い浮かびませんでしたが、人間がやるならどうするかを想像して、以下のように作りました。
- アイテムを各袋にできるだけ同じ数ずつ入れる。
- 以下をクエリ回数の限界まで繰り返す。
- 袋の重さを比較して、最も重いものと最も軽いものを探す。（クエリ D-1回)
- 重い袋からランダムにアイテムを一つ取り出し、軽い袋に入れる。
テスタの製作
クエリに応答したり、スコアを計算するためのテスタプログラムを製作します。 公式からも配布されていますが、多数のテストケースを試したり、結果を集計したりしたいので、自作しました。
製作したテスタで前項のコードを100ケース試してみると、平均スコア（低いほど良い）は6,413,402 (6.41M)となりました。 ここから改善していきます。
アイテム重量をざっくり推定する
袋に振り分けた後、重い袋から軽い袋へ移動するアイテムは、軽いものにしたいです。 そこで、初めにアイテムの重量を推定することにしました。
すべてのアイテムを重量順でソートするために必要な比較の回数はNlogN回くらいで、本問題の制約ではケースによってはクエリ回数が足りなくなります。
そこで、勝ち残り式トーナメントのように、アイテムを比較して重いほうを脱落させ、軽いほうを次のステージへ進出させます。何回戦まで勝ち進んだかを基準に、重量を推定します。1回の比較ごとに1つのアイテムが脱落するので、"優勝"を決めるまでに必要な比較回数はN-1回です。
平均スコアは5.67Mとなりました。
100回のテストのうち、最もスコアが悪かったケースのスコアとシード値を出力するようにしました。 最悪ケースの結果をビジュアライザで確認して、改良していきます。
重量を均等に割り当て
せっかく重量を推定しているので、初めに袋に入れるアイテムを選ぶときにも、推定重量を考慮して均等になるように配るようにしました。
平均スコアは5.62M、ほんの少し改善しました。
重いほうもトーナメントをする
これまでのトーナメント方式だと、半数のアイテムが1回戦敗退で、同じ重さとして推定されてしまいます。 そこで、軽いアイテムが勝ち残るトーナメントで1回戦敗退になったアイテムで、逆に重いほうが勝ち残るトーナメントを行って重量推定をするようにしました。
平均スコアは4.55Mでした。
良い解が得られた時点で終了する
ビジュアライザで観察していると、途中で良い解になったにもかかわらず、その後悪化するということがありました。
非常に軽いアイテムを最も重い袋から最も軽い袋に移動したときに袋の重さの最大最小が入れ替わった場合、アイテムの振り分けがかなり均等にできていると言えそうです。
一定以下の重さのアイテムを移動したことで袋の最大最小が入れ替わったら、その時点の振り分けの状態を回答とすることにしました。
平均スコアは3.98Mでした。順調に下がっているようです。
袋の重量順を保持しておく
これまでは、重量最大最小の袋を探すために全探索していましたが、これではクエリ数の無駄使いなので、袋を重量順に並べておき、アイテムの移動によって重量が変化したときには二分探索で挿入することで、袋のソート状態を維持するようにしました。
平均スコアは3.14Mでした。
トーナメント方式の"シード"の問題
100ケースのうち、スコアが最悪だったものを見てみると、非常に重いアイテムを非常に軽く推定していて、それを動かしたことでスコアが大きく悪化していました。
トーナメント方式なので、たまたまより重い相手とばかり当たっていると、重いアイテムが上位に勝ち進んでしまうことはあり得ます。しかし、それにしても異常な推定値でした。
当該ケースはアイテム数が65で、問題のアイテムは最後のNo.65でした。65は、2 ^ 6 + 1です。それを踏まえてコードを見ていると、重大な問題に気付きました。
トーナメント方式で次のステージに勝ち残るアイテムを決めるとき、残っているアイテム数が奇数の時は、最後のアイテムをトーナメントでいう"シード"のように、無条件で次のステージに進ませていました。
65個のアイテムでトーナメントを行うと、アイテム数は65 -> 33 -> 17 -> 9 -> 5 -> 3 -> 2 -> 1 となります。決勝戦以外ずっとアイテム数が奇数であり、最後のアイテムは不戦勝を続けることになってしまいます。
シードに選ばれるアイテムを、ステージごとに右端、左端交互になるようにしました。
（今振り返ると、ランダムにしてしまったほうがよかったと思います。両端は2回に1回シードになってしまうので。）
平均スコアは2.52Mでした。
Nに対してQが十分大きい時にはきちんとソートする
ケースのQがNlogNよりも大きければ、トーナメント方式ではなく、確実なソートができます。ソートした後にもクエリを残しておく必要があるので、余裕をもってQがNの10倍以上ある場合にはアイテムのソートを行うことにしました。
ソートアルゴリズムは実装が簡単そうなクイックソートにしました。
平均スコアは2.45Mでした。このあたりからテストケースを1000個試すようにしました。
行き詰まる
その後細かい改良を行い、平均スコアが1.64Mまで下がりましたが、そこで行き詰まってしまいました。最悪ケースを観察し、思いついたことを試してみても、何をやってもスコアが悪化してしまいます。
Q/Nが小さい時の重量推定方法として、アイテムをいくつか纏めて束にして、その束をソートするという方法を考えました。これを実装するにはコードの大幅な変更が必要なので、思い切って全面的に書き直しました。しかし、スコアはむしろ悪化してしまいました。
最後の3日間ほどは、取り組んでいたにもかかわらずスコアはよくなりませんでした。
結果
最終結果は265位、パフォーマンス1595でした。
AHC019以来青パフォとれていないので、取りたかったです。
感想と反省
- 前半は、100ケース試す⇒最悪ケースを観察する⇒改善する⇒効果確認 というサイクルを回してスコアを改善していけたのが良かった。
- 後半はスコアが伸び悩んだ。
- 最悪ケースにばかり注目したのが良くなかったかもしれない。
- 最悪ケースは不運が重なった極端に悪いケースなので、これに対応しようとして全体的に悪化してしまったのかもしれない。
- 平均スコアを指標にしたのが良くなかったかもしれない。
- 最悪ケースにばかり注目したのが良くなかったかもしれない。
THIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017）参加記
THIRD プログラミングコンテスト 2022 （AtCoder Heuristic Contest 017
今回意識したいこと
- 記録をとる
- どう考えたか、どう改善したか、その結果どうなったかなどを記録するようにする。
- ちゃんと記録を取っていた回（AHC014）はわりと成績が良かった。
- 参加記を書く時にも役立つ
- よく観察する
- 高度な知識がなくても、よくデータを観察すれば有用な気づきを得られることもあるはず。
- そのために、いろいろな情報を出力するようにする。
- 自作ビジュアライザが理想だけれど、難しいので、テキストファイルに出力したり、それを表計算ソフトで処理したりしてみる。
ルールの確認
まずはルールを見ながら思ったことをメモしていきます。
- 平面無向グラフで表現される道路網の工事計画を立てる。
- 工事で道路が使用できなくなることによる不満度を抑えることを目指す。
- 500 <= N <= 1000 であるので、ワーシャルフロイド法によって全点対最短路を求めることができない。
- 1回もできないので、工事前の全点対最短距離を求めることさえできない。
- ダイクストラ法なら1回くらいならできそう？
- ABCでよく見るグラフと違い、頂点に座標が存在する（平面グラフと言うらしい）。
- 得点は、すべての組み合わせの2点の、工事による最短距離の増加量によって算出される。
- 到達できない場合は10^9として扱われる。
- 頂点が半径500の円内に収まっていて、辺の重みが頂点間のユークリッド距離×1000であることを考えると、10^9というのは相当大きい。
- 可能な限り、グラフが非連結になることは避けたほうがよさそう。
- 到達できない場合は10^9として扱われる。
- すべての道路を一度ずつ工事しなければいけないので、「どの道路とどの道路を同時に工事するとよくないか」を考える問題と言える？
正の得点を得る
改善の目安にするために、まずはランダムに工事を行うコードを提出します。
一日ごとの工事数が均等になるようにして、あとはランダムに工事する日を割り振りました。
不満度（低いほど良い）は37,538,194,005（≒37.5G）でした。
得点計算関数を作る
入出力を与えると、得点（不満度）を返す関数を作ります。 ワーシャルフロイド法だと、seed=0 (N=791, M=2277) で35秒かかりました。 ダイクストラ法で書き直すと、3.5秒になりました。 公式ビジュアライザと比較して、正しく不満度を計算できていることを確認しました。
改善はじめ
さあ、ここからが本番です。 改善方針として真っ先に思い浮かんだのが、グラフを連結にする、というものです。
本当に連結にすることが重要かどうか確認するために実験をしてみました。
ランダムに工事計画を立てた時の、各日ごとの連結成分の個数と不満度を計算し、集計しました(seed=0-99)。
やはり、連結成分が複数になると不満度が桁違いに上昇しています（縦軸は対数目盛）。 工事全体の不満度は各日の不満度の平均から計算されるので、1日でも非連結になる日があると、そのテストケースの点数は非常に低くなるでしょう。
連結になるか、時間が足りなくなるまで、工事計画をランダムにシャッフルし続けるプログラムを作成しました。
結果は、不満度7.72Gと、かなり良くなりました。 連結状態に注目するのは良さそうです。
連結させる
非連結になったグラフを見てみると、一つの頂点に接続している辺すべてが工事中になることで、非連結になってしまっているようです。
頂点を共有する辺を同日に工事する計画になっていたら、別の日に割り当てるようにしました。
結構ばらけているように見えます。しかしこれでも、テストケース100個中7個で非連結になってしまいました。 頂点数３～５個程度の連結成分ができてしまうことがあるみたいです。
提出してみると、不満度は6.43Gで若干よくなりました。
確実に連結させる
辺を一つずつ見ていき、その辺の工事日に辺の両端が別の連結成分に属している場合、工事を別の日に割り当てることで連結させていきます。この処理によって新たに非連結になる日ができる可能性があるので、時間いっぱい処理を繰り返します。
100テストケースすべてで連結にすることができました。 提出すると、不満度は1.01G、かなり減っています！
しかし順位はあまり変わっていない気がします。 相対スコアは、テストケースごとに独立して不満度に反比例するので、極端に悪いケース（非連結だったケース）が並まで改善されても、あまり相対スコアに影響しないのかもしれません。
工事による他の辺への影響を調べる
一つの辺を工事中にしたときに、最短経路がどのように変化するか調べてみます。 すべての頂点対の最短経路を調べ、工事前と工事中の最短経路として使われる回数の変化を調べます。
ビジュアライザを自作して、結果を表示してみました。
- 緑：工事する辺
- 赤：工事中に最短経路として使われることが増える辺
- 青：工事中に最短経路として使われることが減る辺
緑の辺を工事するときには、赤い辺が代わりに最短経路として使われることになるので、同時に工事しないほうが良いといえそうです。
青い辺は、緑の辺からあまり角度を変化させずに伸ばしていった辺、
赤い辺は、青い辺と平行に並んだ辺、
という感じでしょうか。
平行な辺は「バイパス」として機能するので、直感とも一致します。
バイパスを確保する
ある辺について、その辺との角度の差が小さく、ユークリッド距離が小さく、延長線上にないものを、バイパス辺とします。
まずランダムに工事日を割り当て、そのあと辺を一つずつ見ていき、バイパス辺を同じ日に工事することになっていたら別の日に変更する、という処理を繰り返します。 最後にグラフ全体が連結になるように工事日を変更します。
提出結果は、不満度977Mでした。手間がかかった割にあまり変わりませんでした……。
1つの面の周りで同時に工事しない
辺によって分割された領域を「面」というそうです。 面を挟んだ反対側に移動したいとき、面の外周に沿って回り込む経路が最短経路になりやすそうです。また、右回りが最短経路なら、左回りが二番目に短い経路ということもよくあると思います。 そこで、1つの面を囲む辺を同じ日に複数工事しないようにします。面を囲む辺の数が工事日数Ｄより大きいときには、できるだけ分散させるようにします。
テストケース100個で実験してみたところ、 (辺の数M / 頂点の数N) が小さいときには、バイパスを確保するアルゴリズムよりもいい成績が出やすくなりました。
M/Nが2以下のときにはこのアルゴリズム、そうでないときにはバイパス保護を採用するようにしました。
提出結果は905Mでした。そろそろ時間なのでこれを最終提出とします。
感想と反省
- 連結することが超重要（というより大前提？）だということに気づけた。
- 実験して確かめられたのがよかった。
- ちょっとしたビジュアライザを作れた。
- 静的な画像を出力するだけなら結構簡単だった。
- アルゴリズムをちゃんと実装できているかどうか確認するのに役立った。
- 面を列挙するアルゴリズムの実装が難しかった。
- 山登り法ができなかった。
- ごく少数の頂点を選んで評価したら、真の評価値とはかけ離れたものになると思い込んでしまった。
- 試してみればよかった。
- ごく少数の頂点を選んで評価したら、真の評価値とはかけ離れたものになると思い込んでしまった。
- 公式ビジュアライザの使い方をよく読むべきだった！！
結果
暫定262位です。難しかった～。
estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）参加しました
はじめに
estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）に参加しました。
個人的な体験談で、解説にはなっていません。
ルールの確認
まずはルールをざっくり見ていきます。
- 長方形を作れるような位置に印をつけていく。
- 長方形を作るときに、外周上に4頂点以外の印があってはならない。
- すでにある辺上に印をつけることはできる。
- 複数の長方形で辺を共有できない。
- 交差はできる。
得点
- 交差はできる。
- それぞれの印ごとに、位置によって決まる点数を得られる。
- 「中心からのユークリッド距離の2乗+1」がその位置の点数になる。
- 印は多いほど良い。中心から離れているほど良い。
ビジュアライザ
ビジュアライザのマニュアルモードで遊んでみました。
- ルールがわかった。
- むやみに大きな長方形を作ると、後々長方形を作りづらくなる。
- 中心から離れた点に印をつけるのは、（人力では）かなり難しそう。
- できるだけ密集して印をつけていくのがよさそう？
得点計算関数
どこから手を付けたらよいかわかりませんが、とりあえず、必ず必要になるであろう得点計算関数を作ることにしました。 得点計算をするには、各格子点に印がついているかどうかという情報が必要です。
以下の状態を持つ型を定義して盤面の状態とし、それを引数として得点を返す関数を作りました。
- N
- M
- 各格子点の印の状態
ビジュアライザで表示される得点と比較して、ちゃんと計算できていることを確認。
盤面の状態を表現する
得点計算のためには印の有無さえ分かればよいですが、長方形を作っていくことを考えると、当然、長方形の外周となる「線」の情報も保持する必要があります。 線の情報の持ち方としては、以下の2つを思いつきました。
- 線が引かれうる場所を最小単位（隣り合う格子点の間）に区切って、各区間に線が引かれているか/いないかで表す。
- ２つの頂点のペアで表す
新たに線を引くときの処理は(2)のほうが実装が簡単そうですが、ある場所に線を引けるかどうかの判定のために、すでに引かれている線の情報を取り出すときには、(1)のほうが都合がよさそうです。とりあえず、(1)を採用することにします。
状態を正しく持てているか確認するために、標準出力で表示できるようにしました。
斜めがあるので結構難しかったです。ここまでで、すでにやり切った感。。
でもまだ何も提出していないので０点です。
正の点数を取る
順位表を見てみると、正の点数を取った人のうちの最低点が14,048,321で、同点のひとがたくさんいます。おそらくこれが、印を一つも追加しないときの得点だと思います。まずは、この14,048,321を超えることを目標にします。
なんとなく、小さい長方形を敷き詰めたほうが良い気がするので、辺の長さが１の正方形を描けるだけ描いていく、というアルゴリズムにします。 盤面全体を端から順にみていき、正方形を描けるなら描く、という処理を時間いっぱい繰り返します。
しょぼい！
得点は15,176,634 (15.1M)でした。正の点数が取れたのでよしとします。 以降点数はM(100万)単位で表記します。(0.1M未満切り捨て)
ところで、seed=0のときは初期状態が「estie社のロゴ」という特殊なパターンなので、seed=1以降の結果を見て考察したほうが良いのかな、と思いました。
seed=1だとこんな感じ。これ以降seed=1の画像を貼っていきます。
つづいて、45度傾いた最小の正方形も描けるだけ描くようにしてみました。
急に増えた！
でもまだまだ。
点数は19.7Mでした。
大きい長方形も描く＆高速化
大きい長方形も描いていきたいのですが、現状のアルゴリズムのままだと計算量が膨大になりそうです。 現状は、
- 結ぶと長方形になるような格子点4つを決める。
- 4つのうちちょうど3つに印がついていることを確かめる。
- 長方形の外周上に他の印や線がないことを確かめる。 という手順を踏んでいます。
盤面の端のほうの、まっさらなあたりでもこんなことをやっているので、かなり無駄です。 そこで、すでにある印を頂点として含む長方形を探す方法に変更します。 印を順番に見ていき、その印を利用して作れる長方形のうち、最も小さいものを作る、というアルゴリズムを実装しました。
だいぶそれらしくなったんじゃないでしょうか。
点数は30.0Mでした。
小さい順に描く
大きい長方形を不用意に描くと、あとから長方形を描き足しにくくなりそうです。 描いてよい長方形の大きさの閾値を決めておき、すべての印を調べても長方形を書き足せなくなったら、閾値を引き上げていきます。
32.0M。ちょっと上がった。
そろそろ、楽に実装できる改善点がおもいつかなくなってきました。
時間は足りてる？
今のプログラムは4.8秒で処理を打ち切って出力しています。試しに処理時間を変えて実行してみます。時間を長くするとスコアが伸びるようであれば、高速化でスコアが伸びる余地がある、ということになります。また、時間を短くしてもスコアが変化しないようであれば、時間が余っていて、遠慮なく処理を増やしてよいということです。
結果は……
| 実行時間[秒] | seed=1のスコア |
|---|---|
| 0.01 | 432543 |
| 0.05 | 604477 |
| 0.1 | 604477 |
| 1.0 | 604477 |
| 3.0 | 604477 |
| 4.8 | 604477 |
| 10.0 | 604477 |
全然余ってた！
敷き詰める
上図のように、印と縦横の線が隙間なく描かれている状態を考えると、四角形は辺を共有できないという制約上、下図のような四角形の組み合わせでできているはずです。
つまり、最小の正方形が市松模様状に並んでいるパターンです。これを実現するために、チェス盤でいう同色のマスにのみ、最小の正方形を描いてよい、という制約を設けました。
斜めの最小の正方形を描く場合においては、上図の緑の線と紫の線は互いに影響しません。
それぞれのレイヤごとに、正方形が市松模様に並ぶように、正方形を描く場所を制限します。
各レイヤで敷き詰め方が2パターンあるので、2x2x2の8パターン試して最良のものを採用。
結果はこちら。
かなり敷き詰まってる！！ 提出結果は35.8M点！
焼鈍
そろそろ焼きなましをしたいです。（なおコンテスト中は以下の方法を山登り法だと思っていました。）
一部の印を消して、長方形を描き直していきたいのですが、印を消した時には、その印を利用して描いた印も消さなければ、不正な出力になってしまいます。
それぞれの印に、その印を描いた時に作られた長方形の情報を持たせます。長方形の残りの３頂点が、依存先の印になります。逆方向にもたどれるようにしておきます。
ランダムに印を一つ選び（初期状態からあるものは除く）、削除します。その印に依存するすべての印を再帰的に探索し、すべて削除します。その状態から長方形をかけるだけ描き、元の状態と点数を比較し、良くなっていたら更新します。
得点は跳ね上がり、46.8M点！ 暫定順位80位になりました。
まさかこんな順位に来れるとは思っていませんでした。でも、強い人たちがラストスパートをかけてきそうなので、あまり浮かれるとがっかりするかも。
その後、消す印の数に上限を設けたり、なるべく外側に印をつけるようにしたりして少し改善し、暫定48.5M点、82位となりました。
最終結果
システムテストの結果が出たら書きます。
感想
苦しくも楽しかった！ ビジュアライザでいい感じの絵が出たときはとても興奮します。
単純なルールでありながら、人によって考察がいろいろあり、それでいてアルゴ的な最適解が出るわけでもないのが面白いです。問題作る人すごすぎ。
方法を思いつくことと、それを実装することの間には大きな隔たりがあるということを改めて実感しました。
今後の課題
もっと多くのテストケースを試したほうがよさそう。
いろいろな定数を直感で決めてしまったけれど、ちゃんとデータを見て調整するべきだった。そのためにも、いろいろなデータを見える化すべき。焼きなましが回った回数や改善度合いとか、テストケースの種類（印の密度など）による得点の傾向とか。
おまけ 用意した主な関数一覧
- 指定した座標から指定した座標を見た方向（0~7）を返す
- 指定した座標が盤面内にあるか返す
- 指定した座標に印があるか返す
- 2つの座標を結ぶ線上に印があるか返す
- 指定した座標に印をつける/消す（依存関係も修正する）
- 指定した座標から指定した方向に線が引かれているか返す
- ２つの座標を結ぶ線上に線が引かれている箇所があるか返す
- ２つの座標の間に線を引く/消す
- 指定した座標から指定方向に向かって最も近い印を返す
- 指定した長方形を描けるか確かめる
- 指定した印を頂点とする、作れる長方形のリストを返す
- 指定した長方形を描く/消す
- 指定した印と、それに依存する全ての印と長方形を消す
- 回答用文字列を生成する
- 指定した座標の重みを返す
- 盤面の印の重みの総和を返す
- 盤面の得点を返す
- 盤面の状態を出力する
ARC140 A-Right String
問題概要
文字列Tの先頭の文字を末尾に移動することを繰り返して作れる文字列の種類をf(T)とする。
文字列SのK文字以下の文字を変更した後のf(S)としてあり得る最小値を求める。
1 <= N <= 2000
0 <= K <= N
考察
先頭の文字を削除して末尾に追加することをシフトすると呼ぶことにします。
長さNの完全にデタラメな文字列Tをシフトしていくと、シフトするたびに新しい文字列となり、N回シフトすると一周してもとの文字列に戻ります。よってf(T) = Nです。
f(T)を小さくするには、一周する前に元の文字列になればよいことになります。
例えば、T = "ABCABCABCABC" のとき、3回シフトすると元の文字列と同じになり、それ以降は今までに現れた文字列にしかならないので、f(T) = 3です。
この問題は、↓ができれば解けることになります。
文字列SをK文字まで置き換えて、できるだけ短い文字列を繰り返した文字列にする。
繰り返し単位となる文字列の長さは、Nの約数である必要があるので、Nの約数を小さい順に見ていき、その長さの文字列の繰り返しを作ることができるかどうか調べていきます。
例として、次のようなSを長さ2の文字列の繰り返しにするには、何文字置き換えればよいか考えます。
S = "ABAACC"
見やすいように2文字ごとに改行します。
AB
AA
CC
ここで、各列について、その列を構成する文字がすべて同じになればよいです。
左から1番目の列は[A, A, C]なので、CをAに変えれば全てAになります(操作1回)。
左から2番目の列は[B, A, C]なので、いずれか1文字に他の2文字を合わせればよいです（操作2回）。
一般には、行数 - 列内で最も多く現れる文字の個数 でその列に必要な操作回数がわかります。
この例では合計3回の操作が必要になります。
必要な操作回数がK以下であれば、その繰り返し文字列を作ることができ、繰り返し単位の長さが回答になります。
モノグサプログラミングコンテスト2022（AtCoder Beginner Contest 249）振り返り
Monoxer Programming Contest 2022（AtCoder Beginner Contest 249） - AtCoderに参加しました。
ABC3完でした。D問題は解法は分かったもののバグ取りができずに時間切れとなりました。コンテスト終了後に、オーバーフローする可能性があることに気づき、Intをlongに変更したら通りました。悔しい。
制約が2*10^5だったので十分余裕があると思って早々にオーバーフローのことが頭から抜けてしまいました。掛け合わせたら4*10^10で32bitに収まらないというのに……。
AtCoder 入緑しました！
AtCoder Beginner Contest 247にて、緑色になりました。
色変というからには、成長を振りかえりたいところなのですが……
↑残念ながら、初回からパフォーマンスは800~1000程度であまり変化していません。参加回数が少ないうちはレーティングが実力よりも低くなるそうなので、その補正が外れることでレーティングが上がってきたわけですね。
つまりここからは本当に実力が上がらないとレートが上がらないことになります。
それはともかく、緑になれたことはうれしい！
今までやったこと
コンテストにはできるだけ毎回出て、それ以外の日は主に過去問をやっていました。それから、典型90問の★2と★3を9割ほど解いています。
AtCoder以外のサイトでは、Codewars を利用していました。Codewarsの特徴として、解答の「ベストプラクティス」が見られるという点があります。
8kyu~7kyuの簡単な問題を解くだけでも、解答後に便利な書き方を知れて楽しいです。新しい言語を学び始めるときに、かなり良いんじゃないでしょうか。
今後の目標
緑の次は水色……はちょっと高すぎるので、レーティング1000を目標にします。
E869120さんが書かれた下記の記事を参考に学んでいこうと思います。
AtCoder Regular Contest 138 振り返り
AtCoder Regular Contest 138に参加しました。
結果
B問題のみAC。緑まであと少し！
B - 01 Generation
問題概要
空の数列xに対して以下の操作を任意の順番で行い、指定された数列を作れるか？
- 操作A：xの要素すべてをflip(1なら0、0なら1に）した後、先頭に0をつける
- 操作B：xの末尾に0をつける
作れるかどうかをYes/Noで回答する。
考察
空の数列に対してA/Bどちらの操作を行っても[0]になるので、[0]から始めると考えます。
操作Aのみ行った場合、数列は次のように変化していきます。
0 → 01 → 010 → 0101 → 01010 → 010101
次に操作A/B両方行った場合を考えます。
操作Bは最初の0よりも右側にしか影響しないので、最初の0より左側は、操作Aのみ行った場合と同様、先頭が0で、以降1/0が交互に並びます。
具体例として数列 0100110 で考えていきます。
前述のとおり、左端から0/1が交互に並んでいる部分は操作Aで作ることができます。
この例では、左から3個、010の部分が操作Aで作れます。数列[0]から始めると考えると、2回の操作Aで010を作れます。操作Aが3回以上行われた場合は010...がより長く続くはずなので、操作Aは2回までしか行われていません。
次に、残りの0110の部分を操作A/Bで作れるかどうか考えます。
- 各数字は、その位置に0が追加されて以降にflipされた回数（=操作Aの回数）の偶奇を意味しています。
- 数字は左から右に向かって追加されていくので、各数字のflip回数は右隣の数字のflip回数より多いか同じになります。
以上の条件を満たすように各数字のflip回数を決定し、最低限必要なflip回数が操作Aの回数（2回）以下であれば、数列0100110を作ることができます。
右端の数字は、数字が0ならflip回数0、1なら1です。
右端から左へ辿っていくと、数字(0/1)が変化する部分でflip回数が1増えることになります。
この例では、0110の部分を作るのに最低限2回のflip(操作A)が必要ということがわかります。
010の部分は2回のA操作で作れるので、0100110は操作A/Bで作ることができます。
