そーすにっき

なんかいろいろのせておくばしょ

あけましておめでとうございます(遅)

あけましておめでとうございます(6日遅れ)

1月7日だけどあけましておめでとうございます

今年の目標を暢気に載せておきます

  • ちゃんと大学を卒業する(卒研が心配でたまらない人)
  • Atcoder青になる(出来ればICPCの前に!)
  • ICPCつくば予選50位以内を目指す(要はDをACしたい)
  • DDCC、CODE (THANKS) FESTIVALに出る(優遇年次を外れたので難易度UP)
  • RubyPythonをちゃんと読み書きできる人間になる(特にPython

後は記事にならないネタとして

  • 独検4級以上を取得する(一度ドイツにビールではなくワインを飲みに行きたい)
  • C++refを全部読む(予約語全部覚えて使える程度にはなりたい)

なんてのも一応

CODE THANKS FESTIVAL

略してCTF(違)

結果:96th/99

AC:A,B,D

これはひどいという有様

A:一発目からCEをかます
原因:10分前あたりからのんびり打ってた上側のテンプレのstruct edge{...};のセミコロンが落ちてた
C/C++初心者かよぉ…とだいぶひどいため息をつく

B:なんか色々考えたけど最初に思いついたのは単にひっくり返してくっつければよいではないかと
ここでテンプレにstring.hが入っていないことに気づきAのCEも合わせて余計に焦る

C:最悪だった
冒頭でpriority_queueで行けるのでは?(これが正解)
が、priority_queueの更新コストをO(size)と勘違いする痛恨のアホをかましあろうことか選択肢から消してしまう
結果WAを叩きまくり、AC出来ず

D:5WA叩きながらもAC
すぐに互いに素な整数の余算の値の周期性からGCDと思いついたがそこからミスが多かった

E以降は読んでも全然ちんぷんかんぷんだったのでア

#include <vector>
#include <deque>
#include <iostream>
#include <cstdio>
#include <set>
#include <map>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <limits>
#include <random>
#include <string>

using namespace std;
using i64 = long long int;
using ui64 = unsigned long long int;
using f64 = double;
using f80 = long double;
using EDGES = vector<int>;
using GRAPH = vector<EDGES>;
 
struct edge{
    int f,t,c;
    bool operator<(const edge &e){
        return c < e.c;
    }
};
 
 
/////////////////////////////////
//a
int main(){
    int res = 0;
    int a;
    for(int i=0;i<8;i++){
        cin >> a;
        res = max(res,a);
    }
    cout << res << endl;
    return 0;
}

//b
bool is_ok(string s){
    for(int i=0,j=s.length()-1;i<j;i++,j--){
        if(s[i]!=s[j])return false;
    }return true;
}
 
int main(){
    string s;
    cin >> s;
    string t = s;
    reverse(t.begin(),t.end());
    int res = t.size()-1;
    for(int i=0;i<=t.size();i++){
        if(is_ok(s+t.substr(i,t.size()-i)))
        res = min((int)t.length()-i,res);
    }
    cout << res << endl;
    return 0;
}

//d
i64 f(i64 n,i64 k){
    i64 t;
    while(k){
        t = k;
        k = n%k;
        n = t;
    }
    return n;
}
 
int main(){
    i64 n,k;
    cin >> n >> k;
    // cout << f(n,k) << endl;
    if(n%k)cout << k-f(n,k) << endl;
    else cout << 0 << endl;
    return 0;
}

CODE FESTIVAL 2017 qual C

CODE FESTIVAL 2017 qual C - CODE FESTIVAL 2017 qual C | AtCoder

306位 国内107位 3完

qual Cしか出られなかった

A:文字列(5文字以下)が"AC"を含むか

lengthをlentghと誤タイプしCE

B:整数列の各項を±1するかそのままにすることで得られる数列の集合のうち全項の積が偶数になるものはいくつか

偶数と奇数を分けながらやるだけだと思いつくと早かった

C:英小字列に任意個の'x'を挿入し回文にできるか判定して、出来れば最小個数を出力

O(length)があるとすぐに気づいた

前と後ろから見る線形時間解法は自分の得意分野(Deque大好きなのもその辺が理由)なので早解きに成功

コードも短く済んだのでうれしい限り

反省:

BitDPが遠い…競技時間中1回もBitDPにたどり着けなかったので精進不足

#include <iostream>
#include <cstdio>
#include <utility>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <queue>
#include <random>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
using namespace std;
 
////////////////////////
 
//a
int main(){
  string s;
  cin >> s;
  for(int i=0;i<s.length()-1;i++){
    if(s[i]=='A'&&s[i+1]=='C'){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}
 
//b
int main(){
  int n;
  cin >> n;
  int t;
  i64 o=1,e=1;
  i64 r=1;
  for(int i=0;i<n;i++){
    cin >> t;
    if(t%2);
    else e*=2;
    r*=3;
  }
  cout << r-e << endl;
}
 
//c
int main(){
  string s;
  cin >> s;
  int r=0;
  for(int i=0,j=s.length()-1;i<j;){
    if(s[i]==s[j]){i++;j--;}
    else if(s[i]!='x'&&s[j]!='x'){
      cout << -1 << endl;
      return 0;
    }else{
      if(s[i]=='x'){i++;r++;}
      else{j--;r++;}
    }
  }
  cout << r << endl;
}

DDCC 2017 予選

結果:176位 3完

Dが解けなかったけど枠の都合予選通過しそう

A:2文字目と3文字目は違う必要があることを見落とし1WA

B:数字がオーバーフローし1WA

C:Dequeのおかげで5分でAC

D:解法できていたのに実装ミスから虚無

コードがうまく乗らないので準備でき次第載せます

#include <bits/stdc++.h>
 
#define i64 long long
#define ui64 unsigned long long
#define REP(i,n) for(int (i)=0;(i)<(n);i++)
#define REP2(i,k,n) for(int (i)=(k);(i)<(n);i++)
#define MDIST(a,b) abs(a-b)
#define DIST(a,b) sqrt((a)*(a)+(b)*(b))
#define ATCODER 1000000007
#define C " "
using namespace std;
 
////////////////////////
 
/* a */
int main(){
  string c;
  cin >> c;
  if(c[0]==c[1] && c[2]==c[3] && c[1]!=c[2])cout << "Yes" << endl;
  else cout << "No" << endl;
}
 
/* b */
int main(){
  i64 a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << 1728*a+144*b+12*c+d << endl;
}
/* c */
 
int main(){
  deque<i64> l;
  int n,c;
  cin >> n >> c;
  i64 tmp;
  for(int i=0;i<n;i++){
    cin >> tmp;
    l.push_back(tmp);
  }
  sort(l.begin(),l.end());
  int res = 0;
  while(!l.empty()){
    if(l.front()+l.back()+1<=c){
      if(!l.empty())l.pop_front();if(!l.empty())l.pop_back();res++;
    }else{
      if(!l.empty())l.pop_back();res++;
    }
  }
  cout << res << endl;
}

/* d */

Tenka1 Programmer Contest

http://tenka1-2017.contest.atcoder.jp/

結果:Cのみ300点

D500点が遠すぎたてかむずすぎた

C:二重ループを回すだけで解けるのを制約見逃しからかなり難しく考えてしまったので早解きに失敗

Cももう少し早く解けたしDのBit周りの精進がひどく足りない気がするので精進しなおします

でもまずはUbuntuの壊れた環境の再整備から…

#include <bits/stdc++.h>
 
#define i64 long long int
#define SPACE " "
using namespace std;
 
int main(){
  i64 N;
  cin >> N;
  i64 h=0,n,w,tmp;
  for(w=1;w<=3500;w++){
    for(n=1;n<=3500;n++){
      if(4*w*n-N*n-N*w<=0)continue;
      tmp = (N*w*n) % (4*w*n-N*n-N*w);
      if(!tmp){
        h=(N*w*n) / (4*w*n-N*n-N*w);
        break;
      }
    }
    if(h)break;
  }
  cout << h << SPACE << n << SPACE << w << endl;
}

おひさしぶり

更新が止まっているのは実家に帰っていたせいということにしておきたいんです

(全然問題解けてない)

そしてその間にAtcoderでは水色になりました

今日は競技プログラミングとは全然関係ない話にしようかと

じゃあ何かというとwindows10の0xc0000034エラーについての話

Windows Boot Managerの中身がぶっ壊れたというエラーの模様

無償アップグレード組で突然ハマるようで、ストレージの状態も悪くないのに再起動後突然ブートファイルが壊れてるとかどうなってるんだこのOSは

友人が突然これに引っ掛かり、自分もそのうちやらかしそうなのでとりあえず書いておきます

ブート

MediaCreationTool.exeをWindowsのサイトからDLして適当な外付けの何かに焼く

起動時F12を押してブートメディア選択して終わり(できないものもある)

修復

一番簡単な解決(出来ればベター)

>bootrec /fixmbr
>bootrec /fixboot
>bootrec /rebuildbcd

でもこれが通らない場合も少なくない模様

bcdbootをいじる

>diskpart
DISKPART> list disk
DISKPART> select disk 0
DISKPART> list volume
DISKPART> select volume 3
DISKPART> assign letter=S:
DISKPART> exit
>cd /d S:\EFI\Microsoft\Boot\
>ren BCD BCD.bak
>bootrec /fixboot
>bcdboot c:\Windows /l ja-JP /s S: /f ALL
>bootrec /rebuildbcd

これでエラーがなければ簡単だけども、どうやらBCD自体壊れてることがあるらしい
その時はBCDの作り直しから始まるとか

bcdeditで色々やる(あまり詳しくないので省略)

>cd S:\EFI\Microsoft\Boot
>bcdedit /createstore BCD
>bcdedit /store BCD /create {bootmgr} /d “Windows Boot Manager”
>bcdedit /store BCD /create /d “Windows 10” /application osloader

※エントリ {xxxx} は正常に作成されました と出るはず

>bcdedit /store BCD /set {bootmgr} default {xxxx}

中括弧を忘れるとエラー(1敗)

>bcdedit /store BCD /set {bootmgr} path \EFI\Microsoft\Boot\bootmgfw.efi
>bcdedit /store BCD /set {bootmgr} locale ja-jp
>bcdedit /store BCD /set {bootmgr} displayorder {default}
>bcdedit /store BCD /set {bootmgr} timeout 10
>bcdedit /store BCD /set {default} device partition=c:
>bcdedit /store BCD /set {default} osdevice partition=c:
>bcdedit /store BCD /set {default} path \windows\system32\winload.efi
>bcdedit /store BCD /set {default} systemroot \windows
>exit

後は起動出来れば勝ちなんだとか

出典

http://tooljp.com/Windows10/doc/system-recovery/trouble-shooting/0xc0000034/0xc0000034-Windows-not-start.html
https://panyaa.herokuapp.com/blog/54
http://qiita.com/Tats_U_/items/2639fab7cda852ad5143

AGC019

AtCoder Grand Contest 019 - AtCoder Grand Contest 019 | AtCoder

AGCはレート爆上げの機会になりやすくて嬉しいとか

結果:A,B2完

感想:Bの実装量をとても少なくできたので個人的には満足

A:

DPっぽく見えたけどそんなことはない

大容量ほど容量単価が安くないとそれを選択する意味がないので、それに当てはまらないサイズはカットして、上から順にとっていけばよし

0.25とか考えたくなかったので全部4倍して整数で解決(intOFに気づかず1WA)

B:

直感が輝き8分で終了

左からk文字に対しての並び替えを考えると左からk-1文字の並べ替え+αとなることが分かる

さらにαは左からk-1文字のうち左からk文字目と異なる文字の数と分かる(この辺は入力例1から試してみた)

上から1文字ずつバケットに読み込みながら異なる文字の数だけ足していけば解決

#include <bits/stdc++.h>
 
#define i64 long long
#define ui64 unsigned long long
#define ATCODER 1000000007
using namespace std;
 
////////////////////////

/* a */ 
int main(){
  #define INF -1
  i64 q,h,s,d,n;
  cin >> q >> h >> s >> d;
  if(q*2<h) {
    h=INF;
    // cout << 1 << endl;
  }
  if(q*4<s){ s=INF;}
  if(q*8<d){ d=INF;}
  if(h!=INF&&h*2<s){ s=INF;}
  if(h!=INF&&h*4<d){ d=INF;}
  if(s!=INF&&s*2<d){ d=INF;}
  cin >> n;
  n*=4;
  i64 res=0;
  if(d!=INF){
    res+=(i64)n/8*d;
    n%=8;
  }
  if(s!=INF){
    res+=(i64)n/4*s;
    n%=4;
  }
  if(h!=INF){
    res+=(i64)n/2*h;
    n%=2;
  }
  res+=(i64)n*q;
  // cout << q << " " << h << " " << s << " " << d << endl;
  cout << res << endl;
}

/* b */

char s[200005];
 
int main(){
  cin >> s;
  int alpha[26] = {0,};
  int t;
  i64 res = 1;
  for(int i=0;s[i]!='\0';i++){
    t = (int)s[i]-'a';
    alpha[t]+=1;
    res+=i-alpha[t]+1;
  }
  cout << res << endl;
}