もう落ちないように気をつけます.
1990台からABCで橙パフォを取って上げるのなんか卑怯っぽい
うん.
Re:Re:AtCoderで青色になるまでにやった事とかをまとめる
やったこと
水色パフォを取りました
AtCoderで黄色になるまでにやった事とかをまとめる
6/1に開催されたM-SOLUTIONS プロコンオープンで黄色になりました！やったー！
自分語り
塚本(@shibh308)です。今年のJOIでは平均以下の点数で本選落ちでした。これを書いている時点でのレートは2006で、今までのレート推移はこんな感じ(下画像参照)です。
成績について
下に青になって以降のパフォーマンス遷移(AtCoder Performancesを使用させて頂きました)を貼っておきます。
今年に入ってからのratedコンテストだと、500までが全部解けて600と700が半分程度、800と900が2割程度の正答率になっていました。(それ以上の配点の問題は解けていません)
今までに解いた問題について
AtCoderの公式コンテスト(ratedもしくはunrated企業コンテスト)の500点問題までを埋めて、600〜800をある程度と1000までをほんの少し解きました。
AtCoder Scores とAtCoder Problemsの画像だとこんな感じです。
あとはAOJ/AtCoder-JOIの画像のようにJOIの難易度6-9をある程度解いていますが、私はJOI勢ではないのでこれ以上埋まる事はないと思います。
Codeforcesやyukicoder、CS Academyなども合わせると、解いた問題の合計がだいたい1400問ぐらいらしいです。
やったこと
AtCoderのコンテストに出ました。
まだレートが実力に追いついていない(と信じている)ので、ratedのコンテストに出ると平均してレートが上がります。 逆にコンテストに出なかったり、参加したコンテストがunratedになるとレートが上がりません。
おわりに
JOI2018/2019 春季トレーニング合宿 参加できませんでした記
はじめに
JOI本選で178点、Bランクだった。春合宿には落ちてしまった。
オープンコンテストがあるのでネタバレを見ずにそれを解いて、気分だけでも春合宿参加者に負けないようにしていく。できれば点数で春合宿erに勝っていきたい。
オープンコンテスト
1日目
試験(Examination)
を満たす
の個数を各クエリ毎に
を変えながら数え上げる問題。
問題文を読んで、まずは小課題1を解く。これはで二重ループを回すだけで解ける。2点。 高速化をすればこれで100点を取れてしまうらしい(後で試してみたら2.5msで通すことができた)けど、流石に本番にそれをやる余裕はなかった。
小課題2はが必ず0になる。成績とクエリを数学の点数の順に昇順ソートすると1つ目の式が消える。2つ目の式は座標圧縮+BITでよくあるやつをすれば解ける。ここまでで40分
満点解法ではその上で3つ目の式に対応できるようにどうにかしなければいけない。しかしこれは割と簡単で、BITの上に個数を載せていたのをやめて、代わりにBITの各要素をsetにしてを追加、取得クエリではsetの要素内で
以上のものの個数を数え上げればよい。setでは最後の部分ができないので平衡二分探索木を使うなりさらに座圧+BITをするなり、をすれば解ける。ここまでで1時間。
かなり上手く考察が進んだと思っていたのだが、春合宿会場ではこの問題の満点解法を13人が通していたらしい。恐ろしい。 自分が解けていること、正答者数が多い事から難易度11はなさそうで、BITの上にさらに何かを載せるという部分が難しいので難易度9でもなさそうだと感じた。
ナン(Naan)
有理数の上でケーキ分割問題を解くもの、らしい。本番ではケーキ分割問題の存在自体を知らなかった。
とりあえず小課題1を解く。の場合、右から1人目、2人目の順番に取るか、2人目、1人目の順番に取るしかないので、両方のケースを調べる。
各人物毎に公平な分配だと感じる最大の幸福度が決まっていて、それより大きな幸福度が与えられるような大きさのナンを貰っても意味がない事に気づくと、切られたナンを取る人の順番を決めた時の最適な切り方と公平な分配が可能かどうかがわかる。これを実装して5点。
これが分かると小課題2も階乗でのパターン全列挙で解ける事がわかり、やると合計29点が貰える。bitDPをすればもう少し人数が多くても対応できそうな気がするが、残念ながらそのような制約を持つ小課題はなかった。
少し休憩を挟んでいた事もあるが、これだけで実装に2時間以上を費やしてしまった。とても悲しい。 本番で100点を取れた人はいなかったようなので、どうやらこの問題の配点は29点らしい事が分かった。
難易度12だと思うのだけれど、典型といえば典型のようなので難しい。難易度12のマージテク問題が今となっては(難易度12の中では)かなり楽な方に分類されるように、15年後のJOI勢はこのような問題も典型問題として簡単に解けるようになっているのかもしれない。
ビーバーの会合(Meetings)
3点を指定するとその3点からの移動距離が最小になるような頂点の番号が返ってくるため、クエリ回数を一定以下に抑えながら木の構造を復元する問題。
この時点で残り時間が30分を切っている。何もわからないため、とりあえず小課題1だけを解く事にする。
頂点数が極端に少ないため、回クエリを実行して頂点番号を保存、ありえる木を全列挙して、それぞれシミュレーションする事にする。
流石に個程度の辺それぞれに対して張るか張らないかを決めたらTLEを起こしてしまうため、木である事を使っていい感じにすると間に合う。実装は間に合わなかった。
0点だった。もし時間が十分に残っていたとしてもほんの少しの部分点しか取れなかったと思う。反省。
春合宿参加者の中でも0点の人は1人しかいなかったらしい。大失敗をしてしまった。何も分からなかったので難易度12だと思う。
まとめ
100+29+0=129点。1問目が解けたため良い点数にはなったと思うのだが、上手くやればあと数点は稼げたのではないかという気分になってしまう。
もし春合宿に参加していればおそらく得点で8位〜12位辺りに位置していると思うのだが、残念ながら春合宿には参加できていない。
2日目
ふたつのアンテナ(Two Antennas)
もう片方との距離が一定以上かつ一定以下なら通信できるアンテナが一定間隔に並んでいて、区間クエリが与えられるので区間内の双方向に通信できるアンテナの中で高さの差が最大なものを答える問題。
小課題1を見る。で解いてもいい事がわかり、これは前計算を何もしなくてもクエリ毎にその区間内のアンテナの組を全探索すればよい事がわかり、解ける。
小課題2を見る。全てのアンテナの組に対して、その2つが双方向に通信できるかどうか、通信できるならその高さの差(ここではスコアと呼ぶ事にする)をあらかじめメモする事ができる事がわかる。
求めたい物は にあるアンテナの組の持つスコアの最大値 なので、よくある区間DPをする事でこれを解く事ができる。
小課題3を見る。クエリが1つで、区間が全範囲を指している。
地点を左から順番に見ていく事を考える。ある地点が(片方向に)通信する事ができる区間のは右と左に2つあるが、右側のものだけを考える事にする。
そうするとSegtreeの区間取得クエリが丁度適用できるようになる。絶対値の最大値を計算するので難しいように見えるが、区間minを持つSegtreeと区間maxを持つSegtreeを両方用意してしまえばよい。
このままでは右側片方向の通信にしか適用できないが、地点の区間になるので、Segtreeに対して
の取得が始まる前タイミングで要素追加、
の取得が終わった後のタイミングで要素削除をするようにすれば双方向に通信する事ができ、これで解ける。
初日の1問目と似た雰囲気を感じる、よい問題だった気がする。取れる部分点は全て取って、満点解法を諦めて他の問題に移るタイミングも適切でよかったと思う。春合宿の会場で同じ得点を取った参加者がかなり多かったはずで、おそらく難易度は12な気がする。
ふたつの料理(Two Dishes)
問題概要の説明をする必要がわからなくなってきたので、読んで。
小課題1はボーナスの値が正である事が保証されていて、ボーナスを得る事ができる境界の時間が全て一定になっている。
まずはかかる時間と得ることができる得点を累積和で保存しておく。
Naanの小課題1と同じように、カレーを先に作るか丼を先に作るかを決めたり、決め打ちをしながら累積和と二分探索を組み合わせたりする事で解ける。適当だが、これで5点を取る事ができた。
小課題3を考える。でDPをするような見た目をしていて、また、達成したカレーの工程の個数と達成した丼の工程の個数からかかる時間がすぐに求まる事を考えると、累積和と組み合わせてよくあるDPをする事で解く事ができる。小課題2もこれが解ければ自動的に通るため、追加で10点。
実装を手早く済ませた上で自明な部分点を取る事ができたのはかなりよい動きだったと思う。満点が出ておらず、この問題もすぐ諦める事ができたのはかなり良かった。難易度はほぼ間違いなく12。
ふたつの交通機関(Two Transportations)
グラフが2つ与えられるので、2つを合体させたグラフの都市間の最短距離を求めよ。
独立なソースファイルを2つ用意し、その2つ間のやりとりはbool、なおかつやりとりの回数を一定回数以内に抑えなければいけない、間違ってもAtCoderには出せないとても面白い形式の問題。
小課題1を考える。これは与えられるグラフが1つなので、ダイクストラをするだけで解ける。答えの出力をできる関数がA側、グラフが与えられるのがB側なため、求めた最短距離を2進数に変換して送る必要がある。最悪ケースで距離を30bit管理すると落ちるので注意する。6点。
小課題2を考える。B側にある全ての辺の情報をA側に送信すればよいので、それをする。B側の辺の数が、辺の情報は頂点
つとコストがあるが、頂点情報には
bit、コストには
bit、合計すると
で、クエリ制限は
回なので、これで8点を取る事ができる。
小課題3を考える。合体させたグラフが連結である事が保証されているので、これは木になる。
B側の辺のみを考えるとこれは自明に森になるので、あらかじめDFSをしておいてのようにすれば、A側に伝える時に必要な頂点情報の数は
個に抑える事ができ、小課題3が解けた。
小課題4以降を考える。まず、辺情報そのものを送るのではなくAとBのそれぞれでダイクストラをして、その結果をマージする事を考える。
そのままダイクストラをすると当然正しい結果が得られないので、「まだ確定していない頂点の中で、都市0との距離が距離が最も短い頂点」を考える。AとBからこの情報を取得し、そのうちの短い方を取り出す操作を回繰り返す事で、通常のダイクストラと同様に解く事ができる。
回の操作1回につき、距離情報に
bit、頂点番号情報に
bit、それをABそれぞれに対して行うので合計で
回のクエリが必要となる。
ならこれで解く事ができ、ここまでで38点を得られた。
ダイクストラの最短距離の更新に着目すると、前回の更新地点と今回の更新地点の距離の差はたかだか500以下になる事がわかる。そのため、その分の値を減らすことでbitかかっていたものを
bitに減らす事ができ、小課題6までを解く事ができる(本来
bitでよい部分を
bit取ると小課題6が通らなくなってしまうため、注意する)
ここまでをコンテスト中に考察して84点を得る事ができた。満点解法では、距離情報を送信した後に距離を比較し、距離が長い方からは頂点番号を送信しないという方法を取る。距離が短い頂点の情報だけ更新してしまえば、確定しなかった方の頂点の情報は更新をしなくていいというのが理由になる。
これをする事で、各クエリ毎にbit減らす事ができ、満点を得る事ができる。
あまり得意なタイプの問題ではない印象だったが、無事84点を取る事ができてよかった。残りの16点についても本当にもう少しという所だったので、このような所を詰める事ができたらよいと思った。
難易度はだいたい10ぐらいだと思っているのだけれど、正答者数がかなり少ない気がする。
まとめ
35 + 15 + 84 = 134点。かなりの成功だったと思う。コンテスト終了直後は成功したのか失敗したのか分からない程度の印象だったが、他の参加者の点数分布を見た限りだと、どの問題も通すべき課題は全て通し、問題3については100点こそ得られなかったものの、なかなかの高得点を得る事ができたと感じた。
春合宿参加者全体の順位で見ても、これだけ取れていれば1桁順位はほぼ確実なのではないかと思った。今後もこのようなパフォーマンスを取っていきたい。
3日目
指定都市(Designated Cities)
問題概要は省略。
小課題1について考える。これは頂点の部分集合全てに対してその集合内の頂点全てを特別都市に指定した場合の答えを保存し、popcount毎に分類しておく事で解く事ができる。ほぼ自明枠。
小課題2について考える。まず与えられた木を適当な頂点を根とした根付き木とする。根の頂点のみを指定した場合、根から子の方に向かう辺のコストの総和が答えになる。
根の頂点以外を指定した場合について、選んだ頂点と根を結ぶパス上の頂点について、コストの値が根を選んだ場合と逆になる。そのため、根から選んだ頂点とのパスに含まれるコストの値を使って適当に計算して、木DPをすると解ける。
小課題3について考える。小課題2の時と同様に木DPをして片方の頂点を選び、もう片方の頂点とのパスに含まれる重みの総和の分だけさらにコストを減らす事ができ、それを実装すると点数が貰えるような気がしたが実装をする事ができなかった。
小課題4以降は全く分からなかった。小課題3すら実装できずに13点のみで、かなり酷い結果になってしまった。
ランプ(Lamps)
区間を選んで0に変更、1に変更、区間flipの3種類の操作をして、文字列AをBと一致させるための最小操作回数を求める問題。
小課題1について考える。全てのbitを0にするか1にするかをそれぞれ決めても状態数が十分少なく済むため、頂点でBFSをすると解ける。6点。
小課題2以降が全く分からなかった。ある程度の人数がこの問題を解いていて、6点しか取ることができなかったのはかなり悲しい。
時をかけるビ太郎(Bitaro, who Leaps through Time)
問題設定が面白かった。
小課題1について考える。これはで愚直にやってよいので、解く。制約がかなり大きいのでこれを高速化しても満点は取れそうになかった。残念。
区間取得、区間変更クエリが与えられる問題なため、Segtreeに載せる事を考える。の時点で関数と対応する区間の始点に突入した場合の、区間の終点に出てくる時の最小スコアと時間の組 のような関数を考えると、Segtreeにはこの関数を載せて、関数同士のマージ動作を実装すればいい事がわかる。
想定解はこれで合っていたようだが、ここからの実装で大きな失敗をしてしまった。Segtreeに載せる要素が6つ(始点の最小時刻、始点の最大時刻、終点の最小時刻、終点の最大時刻、区間の長さ、区間のスコア)で、それらのマージ動作で6つの場合分けを実装しなければいけない事になり、他の問題が解けずに集中力が切れていた事もあり、実装ができずに破滅してしまった。
とても難しかった。厳しい。
まとめ
13 + 6 + 4 = 23点。本当に悲しい。通すべきだった部分点すら通せない、実装ができない、集中力が途中で切れてしまう、様々な所で失敗してしまった。
現時点で合計286点、初日と2日目のペースが続いていれば4日で500点を目指せたのに、大失敗をしてしまった。参加者全体の中ではおそらく15〜18位ぐらいだと思う。
4日目
24 + 0 + 6 = 30 かなしい
まとめ
4日合わせて129 + 134 + 23 + 30で316点だった。3日目と4日目が酷すぎる。残念ながら今年の進級はほぼ確定しているため来年のJOIには参加できない可能性が高いが、もし留年する事になったら来年の春合宿を目指して頑張りたい。
ABC121に参加したよ
はじめに
10:50で全完、ペナなしで12位だったよ
成功したのでコンテスト中の流れや考察についておはなしするよ
コンテスト中の流れ
コンテストが始まって、最初にDをみたよ 問題文が読めるまで7秒ぐらいかかった気がする(回線さん…)
D問題
問題文が分かりやすくていいね 区間[A,B]の値を全てxorした値を求めよって問題だよ
まずは制約を読むと普通にやると通らなさそうな事がわかって、こういうのは各bit毎に決めていく(ここ典型ポイント)といいんじゃないかな？みたいに思ったよ
でも各bit毎に決める時の判定がむずかしそう＞＜(5秒ぐらい考えても分からなかったので、他の解法を考える事にしたよ)
問題文をもう一回読んで考えると、[A,B]の値は[0,A)と[0,B]の値のxorを取ればいい事がわかるよ(ABC007-D 禁止された数字 とか、桁DPでよくある考え方だと思う)
[0,B]は[0,A) xor [A,B]だから、こうすると[0,A)の部分が2回xorされて打ち消し合って、結果的に[A,B]だけ残るよ
で、ここまで考えるとf(x)=[0,x]の全てのxor を速く求められれば解ける事がわかるので、それをしたい でもわからないので実験をするよ(多分この辺で1分半ぐらい？)
愚直に600ぐらいまで全探索をして、"x: (ここに[0,x]の累積xorが入る)"みたいなのを600行出力したよ そうすると、明らかに4で余りを取った周期で何かが起きている事がわかるよ
具体的には、余りが0ならそのままxを返す、余りが1なら1を返す、余りが2ならx + 1を返す、余りが3なら0を返す をすればいい事がわかるよ なので実装をして、サンプルが会ったので投げると通った(ここまで5:41)
ちなみにこういうのは特に証明しないで投げてるよ 手元の実験で合っててサンプルが合ってれば通るみたいな気分だよ
提出した直後に順位表をチラ見すると400がまだ(ジャッジ待ちの僕を除いて)2人にしか解かれていない事が分かって、とても気分がよかった
C問題
問題文を読んで、適当に入力受け取り部分を書いたよ
値段が少ない順に買っていけばよいのはわかるんだけど、個数に制限がある → 値段と個数でpairを作ってそれを配列に入れて、それをソートして前から持っていけばよい みたいになったよ
Aiの制約がキツいので64bit整数を使う(intだとオーバーフローする)事に気をつけて実装、C++でpairの入ったvectorに要素を新しく挿入する時はemplace_backを使うとmake_pairとか書く必要がなくて便利だよ(setやqueueなど、他のデータ構造にもemplaceという関数があるよ)
これで通して終わり Dを提出してから2分20秒、考察+実装にかかったのがちょうど2分ぐらいだよ
B問題
問題文を読んで入力読み込みを書くことにするんだけど、すごい面倒な感じになってるよ
問題文はサラーっと読み流しつつ入力を読む、こういうのは最悪問題文を全部ちゃんと読まなくてもなんとなく書けばいいと思う…
「N個のソースコードのうち…個数を求めてください。」ってあるからN回ループを回して全探索をすればいい事がわかるよ(どうせABCのB問題なので、制約を読まなくても全探索でよさそうな事がわかる…)
あとはそのすぐ上の行にある式をそのまま実装、サンプルを合わせると通った Cを提出してから1:51秒 B問題にしては相当たいへんだと思う
A問題
とりあえず読むとよくあるやつな事がわかって、こういうのは答えもよくあるやつなので総和から引いて引いて重なった部分を足し直す(包除げんりみたいなかんじ？)といいと思うのでサンプルをを投げると合って、通ったよ これ普通に(H-h)*(W-w)で解けた事にコンテスト終わってから気がついたよ
おわり
ひさしぶりに成功して楽しかった。D問題で実験に走った割には速く解けて3位だったのは良かったんだけど、速い人は本当に速いんだなぁとおもった。
Dはf(b)-f(a-1)みたいに事に気づいて、あとは累積xorさえかければ実験ができて、この実験さえできれば天才じゃなくてもわかるので、実験しような！！！！
〜完〜
典型なのか典型じゃないのかよくわからないテクニックっぽいやつをまとめようとした
はじめに
ちょっとTLで話題になったので書きました。
半分自分用のメモみたいな感じで、緑〜青の人が知っていそうな/知っていると役に立ちそうなテクニックみたいなものを列挙していきました。
僕自身赤色つよつよコーダーな訳ではないので、言ってる事にいろいろガバがあったり、文字を打つのが苦手なので日本語が怪しかったりする所があります。(ごめんなさい…)
まだ怒られなさそうなやつ
解を決め打った時に判定できるなら二分探索！
最小となる...を求めよ、みたいな問題で解を決め打った時に達成できるかの判定が簡単な場合とか
D - Widespread
D - 壊れた電車
ゲーム系とかは逆操作を考える！
状態を上書きする系の問題は逆順に見ると1度決めた所が上書きされなくなって楽らしい
終端状態から遡るのはゲーム系の典型でもある
B - Contiguous Repainting
C - Knot Puzzle
絶対値最大化は+-を決め打ち！
正方向に最大化するパターンと負方向に最大化するパターンを決め打って両方のパターンを調べるといい場合がある
D - Patisserie ABC
二次元グリッド左下移動数え上げでHWが1000以下とかはどうせDP！
どうせこれで解けるので
F - 通学経路
E - 通勤経路
F - お土産購入計画 (Gifts)
F - 屋台 (Food stalls)
最適なケースが定数個に収まるなら全部やる！
条件を満たすパターンを考えると数パターン程度に収まる事があって、そういう場合はそれを全部試すといい
D - Lazy Faith
C - Chocolate Bar
ビット演算による最大化は上位から貪欲！
例えばK個選んでand演算した結果を最大化、みたいな問題は上位bitから貪欲にやればいい
B - Sum AND Subarrays
階乗の約数はそれぞれの数ごとに素因数分解！
すごい典型
C - Factors of Factorial
D - 756
括弧列は"("で+1して")"で-1した累積和！
部分列が括弧列になっているかの判定はa[l]とa[r]が一致しているか、[l,r]のminがa[l]より小さくなっていないかでできる
C - 部分文字列と括弧
和が0の区間や和が倍数の区間の個数は累積和+map！
累積和を取って、mapに個数を保持してからN*(N-1)/2をすると解ける
D - Candy Distribution
A - Zero-Sum Ranges
木とグリッドグラフは二部グラフ！
性質として覚えておくと解ける事がある問題がある
C - 広告
E - 木と整数 / Integers on a Tree
制約に40とか30とかあったら多分半分全列挙！20とかは多分bitDP！16とかなら多分3NのbitDP！
制約から決め打つのも戦術なのでやってみると便利
D - 徒競走
C - 部門分け
D - ナップサック問題
辞書順最小は前から貪欲！
すごい典型 辞書順最小と書いてあったら基本的に先頭の文字から決めていけばいい
C - 次のアルファベット / Next Letter
x軸とy軸を独立に考える！
独立に考えられる時はそれをするといい
D - FT Robot
E - CARtesian Coodinate
A - Affiches
ゲーム系はとりあえず小さなケースで実験！
詰まったら実験、というよりも考察の第一段階ですぐ実験するぐらいでいい気がする 特に変数の少ないYes/No問題で全探索が有効
D - ABS
D - Alice&Brown
H - 8^kゲーム
E - Tozan and Gezan
式で表せる場合はとりあえずそれを書いて式変形！
ぼくはこれを使って問題を解けた事がないですが…
D - 井井井 / ###
最小全域木はクラスカル法の気持ちになる！
辺の数を減らしたくなる場合など、クラスカル法について考えると確実に使われない辺がある事がわかる場合がある
C - Gr-idian MST
円環は長さを2倍にするとバグりにくい！
いちいちmod Nをするよりこうやって計算する方がいい
D - Static Sushi
倍数の場合だけ判定する場合などは調和級数を考える！
for(int i = 1; i < N; ++i)for(int j = 0; j < N; j += i)がO(NlogN)になるので、通らないと思ったものが実は通る場合がある
E - Grouping
F - チーム分け
G - Chicks and Cages
ゲーム系は相手の行動の逆操作が最適な場合を考える！
相手の動きをそのまま返して膠着状態にする、みたいな手が有効な場合も多い
A - Taro vs. Jiro
N<=40ぐらいで片側半分を決めた時にもう片側がすぐ決まるなら半分全列挙！
片側の集合を決め打って考えた時に、もう片側の最適な選び方や条件を満たすパターン数がO(1)とかO(N)程度で求まる 場合に半分全列挙がすごい有効
G - Mixture Drug
構築はとりあえず2ベキか市松模様かヘビっぽい形を考える！
構築が出た時にとりあえずこの辺は試しておくとよさそう
D - All Your Paths are Different Lengths
D - Grid Coloring
差の絶対値の総和の最小化は中央値！
中央値は気をつけないとバグりやすいので注意する
E - CARtesian Coodinate
C - Linear Approximation
中央値は二分探索！
そのまま適用できる事は少ないけど、中央値に関する問題を言い換えたりする事ができて便利な事がある
D - Median of Medians
最大値の最小化は二分探索！
最大値を決め打った時の判定が楽な事が多いので、最大値の最小化が出た瞬間に二分探索を疑った方がよさそう
B - チーム決め
平均が一定になる組み合わせは先に全要素からそれを引いておく！
これをすると選んだ個数について考えなくてよくなる
E - Meaningful Mean
C - 高橋君とカード / Tak and Cards
英小文字は26字しかないからbit全列挙ができる！
時々使う気がする
D - Yet Another Palindrome Partitioning
数列の区間に関するクエリはセグ木か平方分割を試す！
これすごい怒られそうなんですけど、とりあえずこの2つを使ってできるかどうか考えるのは有効だと思う
C - 倍数クエリ
D - Dangerous Hopscotch
E - Hash Swapping
マンハッタン距離は45度回転をすると軸を分離できて便利！
x'=x+y,y'=x-yとして、マンハッタン距離はmax(abs(x'1-x'2), abs(y'1-y'2))になる
E - Equilateral
D - 博覧会
並び替えて回文にできる場合は各文字毎の出現数のうちの奇数の数が1つ以内！
使いどころが微妙だけど使えると楽しい
D - Yet Another Palindrome Partitioning
Yes/Noの構築は自明なNo以外全部できると仮定して解く！
N<=100とかならフローを使う！
これたぷ〜(ありがとうございます:man-bowing:)1. YesかNoを出力させる構築問題は、自明にNoの場合以外は常にできるとして解く(特に低難易度)
— ミドリムシ+ (@Euglenese) May 20, 2019
2. N≦100とかならフローを疑う
怒られそうなやつ
最悪テクです
Yes/No判定や場合分け問題はassertとかabortつけて投げる！
「Yes/Noで答えて、Yesなら構築せよ」みたいな問題はYesの時だけREを吐かせて、提出時にWAが出なかったら少なくともNo判定をしたものは正しい事が分かる
部分点狙いなら関係ないケースは強制終了する！
これは最悪テクではないですが、これをするとTLE連発をしないのでジャッジへの罪悪感が減ります
証明のない貪欲とか一見嘘解法に見えるやつもとりあえず投げる！
WAを吐いたら嘘、全ケースACだったなら(たとえ実は嘘でも)得点が貰えるので勝ち
同じぐらいのレートの人や得意分野が似ている人の順位や各問題の提出状況を見る！
配点に対して明らかにAC者数が多い問題はやる価値あり。自分の方が順位が高いといい気分になれる
二分探索や三分探索の時はちょっとだけ多めに値を取って試す！
特に三分探索はバグらせやすいので、こういう事をすると役に立つ場合がある
なぜかWAを吐いた場合はintを全部long longに変えて提出する！
一般に広く普及している最悪テクで、これをすると通る事が割とあって精神によい
制約が小さいなら埋め込み！
最悪をすると通る場合がある
D - うほょじご
なんとなく単調性が見えたら二分探索！なんとなく凸に見えたら三分探索！
なんとなくそう見えたらとりあえず書いて投げるとよくて、特にABCだと実は嘘だったとしても割と通る
D - Various Sushi
番兵はたくさん置く！要素数はたくさん余計に持つ！にぶたんの初期値の幅は大きく取る！
定数倍がほんの少し悪くなるとしても誤差の範囲内なので、こういう事をしてしょうもないWAを減らす
bitsetを使って定数倍高速化をすればオーダーがヤバくても通る場合がある！
bitsetとかmap→unordered_mapとかGCC→Clangとかにぶたん→しゃくとり(オーダーレベルの高速化)、数ケースだけTLEする場合は定数倍を頑張って落とすとよい 時々これが想定解になる事がある
D - No Need
C - Median Sum
JOI2018/2019 春季トレーニング合宿 参加記
参加できません。
