APIO2018-practice

APIO 2018, Practice roundをやりました.
全巻下のデ乗せときます.
問題PDF確保してるのでそのうちペタるかも.

A. A + B

概要 : 二つの小数を足す.
解法 : やる.
コード:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  double a, b; cin >> a >> b;
  cout << fixed << setprecision(5) << a + b << endl;
}

B. Zero-complexity Transposition

概要 : 配列をreverseする.
解法 : 配列をreverseする.
コード:

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n; cin >> n;
  vector<ll> v(n); for(auto &e : v) cin >> e;
  reverse(begin(v), end(v));
  for(auto &e : v) cout << e << " ";
  cout << endl;
}

C. Wedding cake

概要

n個の有限小数
小数第aia_i桁まである.最後は0でない.
合計が1.

解法

max⁡(ai)\max(a_i)さんが1つしかなければNO.
あとは下のほうの位から見ていって,
非ゼロにしなきゃのとこを1にして,
繰り上がりと合わせて10の倍数になるように,
まずは非ゼロにしなきゃでそろえたりして,
足りなければmax⁡(ai)\max(a_i)さんのところにつっこむ.
小数第一位の繰り上がりが1であればYES. 2以上はNO.

コード

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
 
const int N = 1e5 + 10;
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> d[N];
  int m = 0;
  vector<string> ans;
  for(int i = 0; i < n; i++) {
    cin >> a[i];
    d[a[i]].emplace_back(i);
    m = max(m, a[i]);
    ans.emplace_back(string(a[i], '0'));
  }
  if(d[m].size() == 1) return (cout << "NO" << endl, 0);
  int up = 0;
  for(int i = m; i >= 1; i--) {
    int sz = d[i].size();
    sz += up;
    int p = (10 - sz % 10) % 10;
    sz += p;
    up = sz / 10;
    for(int j : d[i]) {
      int u = min(p, 8);
      ans[j].back() = '1' + u;
      p -= u;
    }
    if(p) ans[d[m].back()][i - 1] = '0' + p;
  }
  if(up >= 2) return (cout << "NO" << endl, 0);
  cout << "YES" << endl;
  for(int i = 0; i < n; i++) {
    cout << "0." << ans[i] << endl;
  }
}

D. Parquet Re-laying

概要

1x2のタイルが敷き詰められているので目的の形を回転だけで達成してください.
手順も教えてね.

解法

左上からそろえていきます.
なにに変化させたいかによってどこを変えればいいかは決まるので,
あとはDFSします.
デバッグすごくつらかったです.

コード

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int h, w;
string s[2][50];

vector<pair<int, int>> v;
void rot(int y, int x) {
  v.emplace_back(y, x);
  assert(v.size() <= 1000000);
  if(s[0][y][x] == 'L') {
    s[0][y][x] = s[0][y][x + 1] = 'U';
    s[0][y + 1][x] = s[0][y + 1][x + 1] = 'D';
  } else {
    s[0][y][x] = s[0][y + 1][x] = 'L';
    s[0][y][x + 1] = s[0][y + 1][x + 1] = 'R';
  }
}

void out() {
  cout << v.size() << endl;
  for(auto p : v) {
    cout << p.first + 1 << " " << p.second + 1 << endl;
  }
}

void dfs(int y, int x, char t) {
  if(s[0][y][x] == t) return;
  char c = s[0][y][x];
  int nx, ny;
  int tx, ty;
  char nt;
  if(c == 'R') {
    ny = y + 1, nx = x - 1;
    ty = y, tx = x - 1;
    nt = 'L';
  } else if(c == 'D') {
    ny = y - 1, nx = x + 1;
    ty = y - 1, tx = x;
    nt = 'U';
  } else {
    ny = y + (t == 'U');
    nx = x + (t == 'L');
    ty = y; tx = x;
    nt = s[0][y][x];
  }
  dfs(ny, nx, nt);
  dfs(ny, nx, nt);
  rot(ty, tx);
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> h >> w;
  v.reserve(1000000);
  for(int k = 0; k < 2; k++)
    for(int i = 0; i < h; i++) {
      cin >> s[k][i];
    }
  for(int i = 0; i < h - 1; i++) {
    for(int j = 0; j < w - 1; j++) {
      dfs(i, j, s[1][i][j]);
    }
  }
  out();
}

途中のDFSは二回は, これをすることで必ず回転できることがわかります.

E. Lock Puzzle

概要

文字列sをtに変えて下さい.
操作はs=αβを任意に設定して,
s:=β^Rαに変えることです.
ただしβ^Rはβを反転させたものです.
文字数 <= 2000
操作上限 = 5100

解法

Subtask7がちょうどページの境目で見えておらず,
89点解法を書いてしまった.
それを少し改良したら, 満点になった.
アイディアは適当な一文字から初めて,
右,左に交互につなげていく.
一文字増やすのに2回,
微調整をして4000ちょいで達成可能.
あとはコード見て.

コード

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
string s, t;

vector<int> ops;
void op(int i) {
  if(i == 0) return;
  ops.emplace_back(i);
  string p;
  p = s.substr(n - i, i);
  reverse(begin(p), end(p));
  p += s.substr(0, n - i);
  s = p;
}

int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  cin >> n >> m;
  cin >> s >> t;
  string ts = s, tt = t;
  sort(begin(ts), end(ts));
  sort(begin(tt), end(tt));
  if(ts != tt) return (cout << -1 << endl, 0);
  for(int i = 0; i < n - 1; i++) {
    if(s[i] == t[n - 1]) { op(n - 1 - i); break; }
  }
  int k = 1;
  int rev = 0, tra = 1;
  int l = -1, r = 1;
  int right = 1;
  for(int i = n - 2; i >= 0; i--) {
    int st;
    if(right) {
      st = 0;
    } else {
      st = k;
    }
    for(int j = st; j < n; j++) {
      if(rev) {
        if(s[j] == t[(n - 1 + r) % n]) {
          if(right) {
            op(n - 1 - j);
            op(1);
            tra ^= 1;
          } else {
            op(n - j);
            op(n - (n - j + k));
            rev ^= 1;
          }
          right ^= 1;
          r++;
          break;
        }
      } else {
        if(s[j] == t[n - 1 + l]) {
          if(right) {
            op(n - 1 - j);
            op(1);
            tra ^= 1;
          } else {
            op(n - j);
            op(n - (n - j + k));
            rev ^= 1;
          }
          right ^= 1;
          l--;
          break;
        }
      }
    }
    k++;
  }
  if(!tra) {
    op(n);
  }
  op(n - (r - 1));
  op(r - 1);
  cout << ops.size() << endl;
  for(int el : ops) cout << el << " ";
}

感想

Practiceなのに難しいなあ心配だなあ.
CDE構築って構築大好きか？
DP無いのが不思議なくらいです(Cは桁DPか？)
Presentationは緩いみたいですね, trailing spaceや改行無しが許されるみたい.
Dが一番難しいというか, 苦手なタイプでした.
構築は最適性を求めているかどうか判断しなければいけない場合とか怖そうですけど,
十分な解をまず考えて, それでだいたい見つかるものが多いと思います.
ABCEは楽しかった.

難易度推定
A:100 B:100 C:400 D:600 E:500

snapshots

1

2

このブログの人気の投稿

YouTube Iridiumの紹介

イメージ
YouTubeであれがしたい ブロックをしたり, コメントを非表示にしたり. そんなあなたに, Iridiumをおすすめしたい. まえおき というか蛇足だ. 足を頭に書くってのは愚策だろうけどね, 他愛もない話をね. 前までは動画投稿をしていたんだけどね, 今は大学まで一旦休むことにしているんだ. ちょっと前までは “忙しくて” なんて言ってたけど, それは毛頭おかしな話だったんだ. 僕が動画を投稿していた頃は忙しい中, 合間を縫ってやっていたことだ. だいたい動画投稿している人間なんて忙しい人だらけだろう. だから僕は, 忙しいなんて嘯くのはやめたんだ. でも忙しくするのは大事なことだと思う. 本題 僕もコメントを隠すuserscriptを書こうとしたことがあるんだけど, 現在のYouTubeはSPAだからいかんせん作りにくい. どうやって更新を検知したらいいかもわからないし… それで他のスクリプトから学ぼうと思ったら, いたれりつくせりのuserscriptを発見した. まーそれはYouTube++てやつなんだけどそれの後継がIridium. スクショがこんな感じ. わーすごい! 神か? 神なのか??? さきにDLリンクを紹介. https://github.com/ParticleCore/Iridium/wiki/Download 自分の環境にあったものを選べばok. 機能の紹介 いろいろあるよ. コメントをデフォルトで隠すようにする ブロックして表示しないようにする 動画を別ページに移動しても表示し続ける（スマホアプリ版みたいな機能） 動画ページでスクロールしても動画を表示し続ける 他にもたくさんあるし, 細かい挙動を設定で変えられる. 広告は消されるが, 設定で登録しているひとだけ許可, などができる. わーすごい! ブロックはすこし使い方にくせがあるが, 動画のサムネイル時点でホバーをして左上に出てくるBlockを押せばいい. 動画を表示し続ける機能なんかは公式が対応すればいいのにとおもうほど… なんのためのSPAやねん. とりあえずブロック機能がほしかったから, 使いまくっている. 結局コイツがYouTubeの更新をどうやって検知してるかわからずじまいだけど… 設定...
つづきをよむ！

うくこん

大悪魔様の誕生日です. https://beta.atcoder.jp/contests/ukuku09 lumasdqina で luma + ecasdqinaででました A 見てない＞＜ エカスドが通した B なんか自明な貪欲があるのでそれと同値のものを数えるといい. C ダイクストラだなって思ったのでダイクストラしたらTLEして無限に申し訳なくなって, よく考えたら01BFSどころか1BFSだったのでそうしたら通った. D Manacherして色々考えてダメそうって思ったけど, 二分探索がきれいにハマった. E 考察してもうだめだと思うなどした. 楽しかった. 5位だったのでとてもうれしいね.
つづきをよむ！

TDPC - T フィボナッチ

まだ解いてなくて自分で解きたかったりしませんか大丈夫ですか救ってもらってもいいですか解法書きますよ大丈夫ですかではいきます 【追記】上の文字がおかしく見えるひとは違う世界に住んでいます h1を文字大きくするためだけに使うのはやめようねSEOが死にますよ TDPC - T フィボナッチ 覗いたらやってみたくなったのでやってみたら一苦労。 きたまさ法 というのを使います。蟻本作者由来のアルゴリズムらしいですね。 蟻本の最後の「こんなアルゴリズムもあるよ」にも乗っているらしいですね。らしい、というのは椅子から動きたくないからです。 意味不明な記事がおおかった 僕の頭が足りないのでしょうが、「あーここの記事の通り式変形してこれをfとおけば自明で、典型なので〜」みたいな記事で、（いやほかのTDPCの問題の記事は良かったんですが、） そんなんいいから、いい記事置いときます m項間漸化式の高速なアルゴリズム バタ子(btk)という方の記事です ここ見ながらノート作れば完璧です。 完璧ですが、最後の x_u = Σ(i=1, m) s_i × x_i x_v = Σ(i=1, m) t_j × x_j ならば x_(u+v) = Σ(i=1, m) Σ(i=1, m) s_i × t_j × x_(i + j) になる というのが少し苦しみました あと、この TDPC-Tは上記記事(すなわちきたまさ法で解ける問題)の特殊ケース であるということを念頭においてください。このことは僕のコードにも詳しくコメントを入れました。 しかし上記の式はとても重要で、 x_uとx_vが求まればx_(u+v)がO(m^2)で求まることを意味しています 記事の後ろに解説書くので同じくハマった人がいたら助けになればなと。(MathJaxとか知らない！) Typical DP Contest : T - フィボナッチ kmjpという方の記事 以下引用 yukicoderをちゃんとやっていれば余裕。 まとめには yukicoderをやっていたら、TDPCの最終問題があっさり解けるようになっていた。 と。 yukicoderにきたまさ法を使える問題があるようです。 No.214 素数サイ...
つづきをよむ！