tsutaj https://blog.hatena.ne.jp/tsutaj/ hogecoder https://tsutaj.hatenablog.com/ PAST AtCoder 問題概要 原文はこちら atcoder.jp 長さ の数列 があり、 ははじめ昇順にソートされている。この数列に対して以下で説明される操作を合計 回行った後、最終的にできた数列を出力せよ。 整数 が与えられるので、 と を交換する。 整数 が与えられるので、 を昇順にソートする。 制約 解説 愚直にやると間に合いそうにないので、何か発想の転換が必要です。まずはどうやったら時間内に処理できそうかを考えてみましょう。 1 番目のクエリは隣り合っている要素を swap するだけなので簡単に で実現可能です。以降、2 番目のクエリをどうするかを考えます。まず、準備のため 転倒数 という概念を次のように… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftsutaj.hatenablog.com%2Fentry%2F2020%2F06%2F06%2F180119" title="第三回アルゴリズム実技検定 N 問題: 入れ替えと並び替え - hogecoder" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20N Hatena Blog https://hatena.blog 2020-06-06 18:01:19 rich https://tsutaj.hatenablog.com/entry/2020/06/06/180119 1.0 100%