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;
}

2017-10-13

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 */

2017-10-01

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;
}

2017-09-15

おひさしぶり

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

（全然問題解けてない）

そしてその間に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

2017-08-27

AGC019

AtCoder Grand Contest 019 - AtCoder Grand Contest 019 | AtCoder

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

結果：A,B2完

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

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

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

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

直感が輝き8分で終了

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

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

上から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;
}

2017-08-21

ARC081

お盆前に帰省＋諸々で精進出来なかった結果がこれだよ！

結果：Cのみ

C:
入力：要素数N　値A_i(i[0,N))
出力：Aから相異なる4つを選んで最大の長方形の面積を出力
解法：
ソートして2つ等しい要素があれば大きい順にそれを選んでいく
3, 5，5，5, 7,...などの場合に5,5,5,5と選択しないように注意する

#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
using namespace std;
 
////////////////////////
 
int main(){
  vector<int> a;
  int n;
  cin >> n;
  a.resize(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  sort(a.begin(),a.end(),greater<int>());
  int m1,m2;
  m1 = m2 = -1;
  for(int i=0;i<n-1;i++){
    if(a[i]==a[i+1]){
      if(m1==-1){
        m1 = a[i];
        i++;
      }else{
        m2 = a[i];
        break;
      }
    }else continue;
  }
  if(m1>0&&m2>0)cout << (i64)m1*m2 << endl;
  else cout << 0 << endl;
}

Dを1時間かけて解けなかった（400点）
400点問題で詰まってしまうのは重症なので精進しなおします

2017-08-10

8000 - FizzBuzz

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=753&page=show_problem&problem=6022

海外の問題、解いてみたくなって、キャッチーなあの言葉に釣られて選択

結果：まんまFizzBuzzだった

えぇ…（困惑）

#include <bits/stdc++.h>

using namespace std;

int main(){
  int c;
  cin >> c;
  int x,y,n;
  while(c--){
    cin >> x >> y >> n;
    for(int i=1;i<=n;i++){
      if(!(i%x)&&!(i%y))cout << "FizzBuzz" << endl;
      else if(!(i%x))cout << "Fizz" << endl;
      else if(!(i%y))cout << "Buzz" << endl;
      else cout << i << endl;
    }
  }
}

そーすにっき

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

CODE FESTIVAL 2017 qual C